# 第三章 字串、向量和陣列 筆記

## 命名空間（namespace）的 using 宣告
- 使用某個命名空間（namespace）：例如 using std::cin 表示使用命名空間 std 中的名字 cin
- 標頭檔中不應該包含 using 宣告，因為這樣使用會導致使用該標頭檔的原始碼（source）也會使用到這個宣告而帶來風險

## 程式庫的 string 類別
- STL（Standard Template Library）的字串類別 string 表示長度可變動的字元序列
- 使用前必須要 #include \<string>，然後 using std::string;

### 定義並初始化 string

初始化（initialize）string 物件的方式：

| 方式 | 解釋 |
| -- | -- |
| string s1 | 預設初始化（default initialization），s1 是空字串 |
| string s2(s1) | s2 是 s1 的一個拷貝 |
| string s2 = s1 | 等同於 s2(s1)，s2 是 s1 的一個拷貝 |
| string s3("value") | s3 是那個字串字面值的一個拷貝，不包括 null 字元 |
| string s3 = "value" | 等同於 s3("value")，s3 是那個字串字面值的一個拷貝 |
| string s4(n, 'c') | 以字元 c 的 n 個拷貝初始化 s4|

- 拷貝初始化（copy initialization）：使用 = 將一個已有的物件拷貝到正在創建的物件
- 直接初始化（direct initialization）：透過括號對物件初始化

### 在 string 上進行的運算

string　運算：

| 操作 | 解釋 |
|-----|-----|
| os << s | 將 s 寫到輸出流 os 當中，回傳 os |
| is >> s | 從 is 讀取以空格分隔的字串到 s，回傳is |
| getline(is, s) | 從 is 讀取一行輸入到 s，回傳 is |
| s.empty() | 如果 s 是空的就回傳 true，否則回傳 false |
| s.size() | 回傳 s 中的字元數 |
| s[n] | 回傳 s 中位在位置 n 的 char 之參考，位置從 0 開始 |
| s1 + s2 | 回傳 s1 和 s2 串接（concatenation）所成的字串 |
| s1 = s2 | 以 s2 的一個拷貝取代 s1 中的字元 |
| s1 == s2 | 如果含有相同的字元，那字串 s1 和 s2 就相等 |
| s1 != s2 | 此外，相等性（equality）有區分大小寫 |
| <, <=, >, >= | 比較運算是區分大小寫的，並且使用字典順序（dictionary ordering） |

- string IO：
- 執行讀取運算 >>：忽略到開頭的空白（例如 spaces、newlines、tabs），然後讀取字元直到遇到下一個空白字元為止
- getline：讀取一整行，包括空白字元，直到換行符號 newline，且結尾不包含 newline
- s.size() 回傳的是 string::size_type 型別，這是一个無號（unsigned）型別的值，不要和 int 混用，事實上，大部分的程式庫型別，都定義有數個附帶型別，這些附帶型別能夠以獨立於機器的方式使用那些程式庫型別，而 size_type 就是其中的一種
- 兩字串 s1 + s2 相加時，要保證 + 號至少一側是 string 型別

string s1 = "hello" + "world" // 錯誤，因為 + 號兩側均為字串字面值，而非可進行 + 運算的 string 類別

- 字串字面值和 string 是截然不同的型別

### 處理一個 string 中的字元

- ctype.h vs. cctype：C++ 修改了 C 的標準庫，名稱為去掉 .h，前面加 c
如 C++ 版本為cctype，c 版本為ctype.h
- 盡量使用 C++ 版本的標頭檔，即 cctype、climits 等等

cctype 標頭檔中定義了一組標準函數：

| 函式 | 解釋 |
|-----|-----|
| isalnum(c) | 如果 c 是一個字母（letter）或數字（digit）就為 true |
| isalpha(c) | 如果 c 是一個字母就為 true |
| iscntrl(c) | 如果 c 是一個控制字元（control character）就為 true |
| isdigit(c) | 如果 c 是一個數字就為 true |
| isgraph(c) | 如果 c 不是一個空格（space）但是可列印的（printable）就為 true |
| islower(c) | 如果 c 是一個小寫字母（lowercase）就為 true |
| isprint(c) | 如果 c 是一個可列印字元（即一個空格或有可視表達形式的字元）就為 true |
| ispunct(c) | 如果 c 是一標點符號字元（punctuation character，即不是控制字元、數字、字母或可列印空白的字元）就為 ture |
| isspace(c) | 如果 c 是空白（whitespace，即一個 space、tab、vertical tab、return、newline 或 form feed）就為 true |
| isupper(c) | 如果 c 是一個大寫（uppercase）字母就為 true|
| isxdigit(c) | 如果 c 是一個十六進位數字（hexadecimal digit）就為 true |
| tolower(c) | 如果 c 是一個大寫字母，就回傳其小寫；否則原封不動地回傳 c |
| toupper(c) | 如果 c 是一個小寫字母，就回傳其大寫；否則原封不動地回傳 c |

- 使用範圍 for（range for）遍歷字串：for (auto c: str)，或者 for (auto &c: str) 使用參考直接改變字串中的字元（C++11）
- 使用下標運算子 []（subscript operator）取得字串中的字元的參考：[] 中需輸入輸入參數為 string::size_type 型別，即使使用 int 整數也會被自動轉型（type convertion）成該型別

## vector
- vector 是一個容器（container），也是一個類別模板（class template）
- #include \<vector> 然後使用 using std::vector;
- 容器（container）：裡面包含了其他物件
- 類別模板（class template）：本身並非函式或類別，但可以實體化（instantiation）出一個類別。vector 是一個類別模板，而 vector\<int> 則是一個類別
- 通過將類別放在類別模板名稱後面的尖括號中來指定生成何種類別，如 vector\<int> ivec;

### 定義並初始化 vector

初始化一個 vector 的方式：

| 方法 | 解釋 |
|-----|-----|
| vector\<T> v1 | 持有的物件之型別為 T 的 vector。預設初始化，v1是空的 |
| vector\<T> v2(v1) | v2 有 v1 中每個元素的拷貝 |
| vector\<T> v2 = v1 | 等同於 v2(v1)，v2 是 v1 中元素的一個拷貝 |
| vector\<T> v3(n, val) | v3 有值為 val 的 n 個元素|
| vector\<T> v4(n) | v4 有一個 value-initialized 物件的 n 個拷貝 |
| vector\<T> v5{a, b, c...} | v5 有跟初始器（initializer）同樣數目的元素；元素是由對應的初始器所初始化 |
| vector\<T> v5 = {a, b, c...} | 等同於 v5{a, b, c...} |

- 串列初始化（list initialize）：vector<string> v{"a", "an", "the"}; （C++11）

### 新增元素到一個 vector

- v.push_back(e) 在容器尾部增加一個元素 e
- 在一個範圍 for 述句之中必不能改變 vector 容器的大小，否則將造成未定義行為（undefined behavior）

### 其他的 vector 運算

vector 的運算：

| 操作 | 解釋 |
|-----|-----|
| v.emtpy() | 如果 v 是空的，就回傳 true；否則就回傳 false |
| v.size() | 回傳 v 中的元素數目|
| v.push_back(t) | 將帶有值 t 的一個元素加到 v 的尾端 |
| v[n] | 回傳 v 中處於位置 n 的元素的一個參考 |
| v1 = v2 | 以 v2 中的元素之拷貝取代 v1 中的元素 |
| v1 = {a,b,c...} | 以逗號分隔的串列中的元素之拷貝取代 v1 中的元素 |
| v1 == v2 | 如果它們有相同的元素數，而且 v1 中的每個元素都與 v2 中對應的元素相等，v1 與 v2 就相等 |
| v1 != v2 | 同上 |
| <,<=,>, >= | 有使用字典順序時的正常意義 |

- vector 物件（以及 string 物件）的下標運算子（subscript operator），只能擷取容器內已存在的元素，不能用於添加元素

## 迭代器簡介

- 所有的標準庫容器都可以使用迭代器（iterator）
- 類似於指標型別，迭代器也提供了對物件的間接存取（indirect access）

### 使用迭代器

迭代器的運算:

| 運算子 | 解釋 |
|-----|-----|
| *iter | 回傳迭代器 iter 所代表的元素的一個參考 |
| iter->mem | 解參考 iter 並從底層的元素擷取出名為 mem 的成員。等同於 (*iter).mem |
| ++iter | 遞增 iter 來參考容器中的下一個元素 |
| --iter | 遞減 iter 來參考容器中的前一個元素 |
| iter1 == iter2 | 比較兩個迭代器是否相等。如果代表相同的元素或兩者皆是同一個容器的 off-the-end 迭代器，那麼兩個迭代器就相等 |
| iter1 != iter2 | 同上，改為比較兩個迭代器是否不相等 |

- 迭代器的定義方式：vector\<int>::iterator iter
- 使用解參考運算子 *（dereference operator）來取得該迭代器所代表的元素
- auto b = v.begin(); 回傳指向容器 v 第一個元素的迭代器
- auto e = v.end(); 回傳指向最後一個元素的下一個元素的迭代器（one past the end），這個迭代器又稱作尾端後迭代器或 end 迭代器（off-the-end iterator），代表該容器尾端後（off the end）一個不存在的元素
- 因為 end 所回傳的迭代器（iterator）並不代表任何元素，它不能被遞增或解參考
- 如果容器為空，begin() 和 end() 回傳的是同一個迭代器，都是尾端後迭代器（the-end iterator）
- 養成使用迭代器和 != 的習慣（泛型程式設計的通用用法）
- 迭代器（iterator）：每種標準容器都有自己的迭代器。C++ 傾向於使用迭代器而不是下標運算子（subscript operator）遍歷元素
- const_iterator：只能讀取容器內的元素，但不能改變
- 箭頭運算子：解參考 + 成員存取，it->mem 等同於 (*it).mem

### 迭代器的算術運算

vector 和 string 迭代器支援的運算：

| 運算子 | 解釋 |
|-----|-----|
| iter + n | 將一個整數值 n 加到一個迭代器，會產出在該容器內推前了那麼多元素的一個迭代器。所產生的迭代器必須代表同一個容器中的元素，或超出其最後一個元素一個位置的位置（off-the-end） |
| iter - n | 同上，只是改為減去 |
| iter1 += n | 迭代器加法的複合指定，指定到 iter1 中的新值，是 iter1 的值加上 n 的結果 |
| iter1 -= n | 同上，只是改為減法的複合指定 |
| iter1 - iter2 | 將兩個迭代器相減會產出一個數字，將這個數字加到右手邊的迭代器會產出左手邊的迭代器。所產生的迭代器必須代表同一個容器中的元素，或超出其最後一個元素一個位置的位置（off-the-end） |
| >、>=、<、<= | 作用在迭代器上的關係運算子（relational Operators）。如果一個迭代器所指涉的元素在容器中出現的位置比另一個迭代器所指涉的元素所在之位置還要前面，我們就說前者小於後者。會產出一個 bool 表示大小關係是否正確 |

- difference_type：保證足夠大以儲存任何兩個迭代器之間的距離，可正可負

## 陣列（array）

- 相當於 vector 的低階版，長度固定

### 定義並初始化內建的陣列

- 初始化：char input_buffer[buffer_size];，長度必須是 constant expression，或者不寫，讓編譯器自己推斷
- 陣列不允許直接赋值给另一個陣列
- 某些編譯器會以編譯器擴充功能（compiler extension）的形式允許陣列的指定。避免使用非標準的功能通常會是個好主意。用到這種功能的程式，在不同的編譯器底下將可能無法運作

### 存取一個陣列的元素

- 陣列下標運算子須包含的型別：size_t
- 字元陣列的特殊性：结尾處有一個空字元（'\0'），如 char a[] = "hello";
- 用陣列初始化 vector：

int a[] = {1,2,3,4,5};
vector<int> vec(begin(a), end(a));

### 陣列和指標和指针

- 使用陣列時，編譯器一般會把它轉型成指標
- 指標存取陣列：在運算式（expression）中使用陣列名時，名字會自動轉換成指標指向陣列的第一個元素
- 相減兩個指標的結果會是一個名叫 ptrdiff_t 的程式庫型別，是一個有號的整數型別，定義在 cstddef 中

## C 風格的字元字串（C-style strings）

- 從 C 繼承來的字串
- 用空字元结束（null terminated）
- 對大多數應用來說，使用標準庫的 string 類別會比使用 C 風格的字串更安全、更高效率
- 存取 string 中的 C-style string ： const char *str = s.c_str();

C 標準庫的處理 string 的函式，定義在 \<cstring> 中：

| 函式 | 介绍 |
|-----|-----|
| strlen(p) | 回傳 p 的長度，空字元不計算在内 |
| strcmp(p1, p2) | 比較 p1 和 p2 的相等性。如果 p1 == p2，回傳 0；如果p1 > p2，回傳一个正值；如果 p1 < p2，回傳一個負值 |
| strcat(p1, p2) | 將 p2 附加到 p1 之後，回傳 p1 |
| strcpy(p1, p2) | 將 p2 拷貝到 p1，回傳 p1 |

盡量使用 vector 和迭代器，少使用陣列

## 多维陣列

- 多维陣列的初始化：int ia[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};

### 指向指標的指標

- 定義：int **ppi = &pi;（pi 是一個指標）
- 解參考：**ppi;

### 動態陣列

- 使用 new 和 delete 表達和 C 中 malloc 和 free 的功能，即在 heap 中分配儲存空間
- 定義：int *ptr = new int[10]; 10 可以被一個變數取代，不需要是 constant expression
- 釋放 heap 中的陣列：delete [] ptr; 注意不要忘記 []
### 型別別名簡化了對多維陣列的指標

型別別名（type alias）能讓我們更輕易閱讀、撰寫和理解對多維陣列的指標，舉例來說：

#include <iostream>

using std::cout;
using std::endl;

int main() {
  int ia[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};
  using int_array = int[4];
  typedef int int_array[4];
  for (int_array *p = ia; p != ia + 3; ++p) {
    for (int *q = *p; q != *p + 4; ++q) cout << *q << ' ';
    cout << endl;
  }
}

可定義 int_array 作為四個 int 陣列這個型別的名稱。我們使用這個型別名稱在內層的 for 迴圈中定義我們的迴圈控制變數