# C++ 陣列 array 及 STL vector
> 作者:王一哲
> 日期:2023年8月6日
## 傳統的陣列 array
C++ 傳統的陣列 array,可以用來儲存多筆相同格式的資料,儲存這些資料的記憶體位址是連續的,所以讀取資料時,是依據陣列開頭的記憶體位址再加上索引值,索引值由 0 開始。以下是關於 array 的基礎知識。
<br />
### 産生 array
可以使用所有內建的資料格式,例如 int、float、char、string,也可以使用自訂的資料格式,但是一個 array 當中所有的資料只能是同一種格式。語法通常有以下3種
```cpp
資料格式 名稱[長度];
資料格式 名稱[長度] = {資料1, 資料2, 資料3, ...};
資料格式 名稱[長度] = {0};
```
1. 第一種:産生 array 時沒有指定資料內容,切記在讀取 array 前一定要填入資料,否則無法預測會讀到什麼數值。
2. 第二種:可以省略**長度**,編譯器會自動根據資料內容決定 array 的長度。
3. 第三種:産生指定長度、所有資料皆為 0 的 array。
```cpp=
int a[5]; // 長度為 5 的整數 array,沒有指定資料內容
int b[] = {0, 1, 2, 3, 4}; // 長度為 5 的整數 array,內容為 {0, 1, 2, 3, 4}
int c[5] = {0}; // 長度為 5 的整數 array,內容為 {0, 0, 0, 0, 0}
int d[5] = {1}; // 不好的寫法,長度為 5 的整數 array,內容為 {1, 0, 0, 0, 0}
int e[5] = {-1}; // 不好的寫法,長度為 5 的整數 array,內容為 {-1, 0, 0, 0, 0}
bool f[5] = {true}; // 不好的寫法,長度為 5 的整數 array,內容為 {1, 0, 0, 0, 0}
bool g[5] = {false};// 長度為 5 的整數 array,內容為 {0, 0, 0, 0, 0}
char alphabet[] = {'A', 'B', 'C', 'D', 'E'};// 長度為 5 的字元 array
string names[] = {"Albert", "Bob", "Conan", "David", "Ethan"};// 長度為 5 的字串 array
```
<br /><br />
### 搭配 memset 設定 array 內容
如果想要使用 memset,需要先引入函式庫 cstring,語法為
```cpp
memset(名稱, 0, sizeof(名稱)); // 將指定名稱的 array 資料全部設定為 0
memset(名稱, -1, sizeof(名稱)); // 將指定名稱的 array 資料全部設定為 -1
```
例如以下的程式碼
```cpp
int a[5];
memset(a, 0, sizeof(a)); // 長度為 5 的整數 array,內容為 {0, 0, 0, 0, 0}
int b[5];
memset(b, -1, sizeof(b)); // 長度為 5 的整數 array,內容為 {-1, -1, -1, -1, -1}
```
<br /><br />
### 取得 array 的長度
array 沒有回傳長度的功能,通常是用 array 使用的記憶體除以資料格式使用的記憶體,語法為
```cpp
sizeof(名稱)/sizeof(資料格式);
```
例如以下的程式碼
```cpp
int a[5];
int length = sizeof(a)/sizeof(int); // 回傳值為 5
```
<br /><br />
### 取得指定索引值的資料
語法有兩種
```cpp
名稱[索引值]; // 比較常用的語法
*名稱 + 索引值; // 用指標 * 取得 array 開頭的記憶體位址
```
例如以下的程式碼,輸出的值皆為 1。
```cpp
int a[] = {0, 1, 2, 3, 4};
cout << a[1] << "\n";
cout << *a + 1 << "\n";
```
<br /><br />
### 使用 for 迴圈填入資料
如果想要産生一個很長的 array,但是資料之間有規律性,通常會使用 for 迴圈填入資料,手動填入資料太麻煩了,例如以下的程式碼,産生的 array 內容為 {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}。
```cpp
int a[10];
for(int i=0; i<10; i++) a[i] = 2*i;
```
<br /><br />
### 使用 for 迴圈印出資料
如果想要印出 array 的資料,不能使用以下的語法,這樣只會印出 array 的記憶體位址。
```cpp
cout << 名稱 << endl;
```
通常會使用 for 迴圈配合索引值印出資料,例如以下的程式碼
```cpp
int a[] = {0, 1, 2, 3, 4};
int length = sizeof(a)/sizeof(int);
for(int i=0; i<length; i++) cout << a[i] << " \n"[i == length-1];
```
輸出為
```cpp
0 1 2 3 4
```
這裡使用了一個小技巧,最後面的 [i == length-1] 是指當方括號中的條件成立時印出換行符號 \n,如果條件不成立時印出空格。因為程式競賽或 APCS 經常會要求這樣輸出答案,用空格分隔資料,但是最後一筆資料直接換行、不加空格。
<br /><br />
### 二維 array
二維 array 很像把資料分布在 xy 平面上,每筆有兩個索引值,就像是 x、y 座標值。由於二維 array 看起來很像數學中的矩陣,通常會沿用矩陣的講法,將 {{0, 1, 2}, {3, 4, 5}} 這樣的二維 array 稱為 2 列 (row)、3 欄 (column)。産生二維 array 的語法為
```cpp
資料格式 名稱[列數][欄數];
資料格式 名稱[列數][欄數] = {{資料1, 資料2, 資料3, ...}, {資料4, 資料5, 資料6, ...}, ...};
```
如果産生二維 array 時有指定資料可以省略列數,編譯器會自動從指定資料判斷列數,但是欄數不能省略。例如以下的程式碼,a 的內容為 {{0, 1, 2}, {3, 4, 5}},b 的內容為 {{1, 2, 0}, {3, 4, 0}},因為 b 應該有 3 欄,沒有指定的資料自動補 0。
```cpp
int a[2][3] = {{0, 1, 2}, {3, 4, 5}};
int b[][3] = {{1, 2}, {3, 4}};
```
如果要印出二維 array 的內容,也是利用 for 迴圈
```cpp
int a[2][3] = {{0, 1, 2}, {3, 4, 5}};
for(int i=0; i<2; i++) {
for(int j=0; j<3; j++) {
cout << a[i][j] << " \n"[j == 2];
}
}
```
輸出為
```cpp
0 1 2
3 4 5
```
<br /><br />
## STL vector 函式庫
STL vector 與 array 不同,可以動態地改變容器長度,使用上比較方便。要先引入函式庫,函式庫的官方說明書在此 [cplusplus.com std::vector](https://cplusplus.com/reference/vector/vector/)。
```cpp
#include <vector>
```
<br />
### 建立 vector
vector 的資料可以是所有內建的資料格式,例如 int、float、char、string,也可以使用自訂的資料格式。語法為
```cpp=
// 産生空的 vector
vector<資料格式> 名稱;
// 産生填入相同資料的 vector,資料可省略,預設值為 0
vector<資料格式> 名稱 (資料數量, 資料);
// 由 vector2 複製資料,也可以改變記憶體位置只複製部分內容
vector<資料格式> 名稱 (vector2名稱.begin(), vector2名稱.end());
// 由 vector2 複製資料
vector<資料格式> 名稱 (vector2名稱);
// 由已定義的 array 複製資料
vector<資料格式> 名稱 (array名稱, array名稱 + array長度);
// 産生陣列並指定資料
vector<資料格式> 名稱 {用逗號分隔的資料};
vector<資料格式> 名稱 = {用逗號分隔的資料};
```
例如以下的程式碼
```cpp=
vector<int> v1; // v1 是空的
vector<int> v2 (5, 1); // v2 的內容為 {1, 1, 1, 1, 1}
vector<int> v3 (v2.begin(), v2.end()); // v3 的內容為 {1, 1, 1, 1, 1}
vector<int> v4 (v3); // v4 的內容為 {1, 1, 1, 1, 1}
int data[] = {0, 1, 2, 3, 4};
vector<int> v5 (data, data + sizeof(data)/sizeof(int)); // v5 的內容為 {0, 1, 2, 3, 4}
vector<int> v6 {0, 1, 2, 3, 4}; // v6 的內容為 {0, 1, 2, 3, 4}
vector<int> v7 = {0, 1, 2, 3, 4}; // q7 的內容為 {0, 1, 2, 3, 4}
```
<br />
### 迭代器 iterator
迭代器可以用來取得物件對應的記憶體位址,有以下幾種:
```cpp=
名稱.begin(); // 回傳起點位址
名稱.end(); // 回傳終點位址
名稱.rbegin(); // 回傳終點位址,由後向前向讀取資料
名稱.rend(); // 回傳起點位址,由後向前向讀取資料
名稱.cbegin(); // 回傳起點位址,回傳值為常數
名稱.cend(); // 回傳終點位址,回傳值為常數
名稱.crbegin();// 回傳終點位址,由後向前向讀取資料,回傳值為常數
名稱.crend(); // 回傳起點位址,由後向前向讀取資料,回傳值為常數
```
迭代器的變數名稱通常是 it,寫法有兩種,例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4};
vector<int>::iterator it = v.begin();
auto it = v.begin();
```
但是 vector\<int\>::iterator 只能用在 begin()、end(),還是用 auto 會比較方便。如果要印出陣列中所有的資料,可以配合迭代器處理,例如以下的程式碼
```cpp=
vector<int> v = {0, 1, 2, 3, 4};
for(auto it = v.begin(); it != v.end(); it++)
cout << *it << " \n"[it == v.end()-1]; // 印出的值為 0 1 2 3 4
for(auto it = v.rbegin(); it != v.rend(); it++)
cout << *it << " \n"[it == v.rend()-1]; // 印出的值為 4 3 2 1 0
for(auto it = v.cbegin(); it != v.cend(); it++)
cout << *it << " \n"[it == v.cend()-1]; // 印出的值為 0 1 2 3 4
for(auto it = v.crbegin(); it != v.crend(); it++)
cout << *it << " \n"[it == v.crend()-1]; // 印出的值為 4 3 2 1 0
```
<br />
### 填入資料
第一種語法為
```cpp
名稱.assign(長度, 資料);
```
例如以下的程式碼
```cpp
vector<int> v;
v.assign(5, 10); // v 的內容為 {10, 10, 10, 10, 10}
```
<br />
第二種語法是由另一個 vector 中指定的記憶體位址複製資料,不包含終點位址。
```cpp
名稱.assign(起點, 終點);
```
例如以下的程式碼
```cpp
vector<int> v1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v2;
v2.assign(v1.begin()+5, v1.end()); // v2 的內容為 {5, 6, 7, 8, 9, 10}
```
<br />
第三種語法是由另一個 array 中指定的記憶體位址複製資料,不包含終點位址。
```cpp
名稱.assign(array起點, array終點);
```
例如以下的程式碼
```cpp
int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v;
v.assign(data+5, data+10); // v 的內容為 {5, 6, 7, 8, 9}
```
<br />
### 從最後面填入資料
語法為
```cpp
名稱.push_back(資料);
```
例如以下的程式碼
```cpp
vector<int> v;
v.push_back(0); // v 的內容為 {0}
v.push_back(1); // v 的內容為 {0, 1}
v.push_back(2); // v 的內容為 {0, 1, 2}
```
<br />
另一個工具是 emplace_back,語法為
```cpp
名稱.emplace_back(資料);
```
看起來效果和 push_back 差不多,但是據說少了複製構造的步驟,所以效率更高。例如以下的程式碼
```cpp
vector<int> v;
v.emplace_back(0); // v 的內容為 {0}
v.emplace_back(1); // v 的內容為 {0, 1}
v.emplace_back(2); // v 的內容為 {0, 1, 2}
```
<br />
### 於指定的位置插入資料
語法為
```cpp
名稱.insert(記憶體位址, 資料);
```
要配合迭代器取得記憶體位址,例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4};
v.insert(v.begin(), -1); // 於最前面插入 -1,v 的內容變為 {-1, 0, 1, 2, 3, 4}
v.insert(v.end(), -2); // 於最後面插入 -2,v 的內容變為 {-1, 0, 1, 2, 3, 4, -2}
v.insert(v.begin()+2, -3); // 於開頭處向後 2 格插入 -3,v 的內容變為 {-1, 0, -3, 1, 2, 3, 4, -2}
v.insert(v.end()-2, -4); // 於結尾處向前 2 格插入 -4,v 的內容變為 {-1, 0, -3, 1, 2, 3, -4, 4, -2}
```
<br />
另一個工具是 emplace,語法為
```cpp
陣列名稱.emplace(記憶體位址, 資料);
```
看起來效果和 instert 差不多,但是據說少了複製構造的步驟,所以效率更高。例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4};
v.emplace(v.begin()+1, -1); // 於開頭處向後 1 格插入 -1,v 的內容變為 {0, -1, 1, 2, 3, 4}
```
<br />
### 刪除最後面的資料
語法為
```cpp
名稱.pop_back();
```
不需要任何參數,沒有回傳值。例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4, 5};
v.pop_back(); // 刪除開頭處的資料,v 的內容變為 {0, 1, 2, 3, 4}
```
如果陣列是空的,會回傳程式記憶體區段錯誤,例如以下的程式碼
```cpp
vector<int> v;
v.pop_back();
```
<br />
### 刪除指定範圍的資料
語法為
```cpp
名稱.erase(起點位址, 終點位址);
```
不包含終點位址。例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4, 5};
v.erase(v.begin()); // 刪除開頭處的資料,v 的內容變為 {1, 2, 3, 4, 5}
v.erase(v.begin(), v.begin()+2); // 刪除開頭處及下 1 格的資料,v 的內容變為 {3, 4, 5}
v.erase(v.begin(), v.end()); // 刪除所有資料
```
<br />
### 清除所有資料
語法為
```cpp
名稱.clear();
```
不需要加上任何參數,清空資料後陣列長度為 0。
<br />
### 交換兩個 vector 的資料
語法為
```cpp
名稱1.swap(名稱2);
```
<br />
### 取得最前面的資料
語法為
```cpp
名稱.front();
```
不需要任何參數。例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4, 5};
int a = v.front(); // a 的內容為 0
```
如果陣列是空的,會回傳 0,例如以下的程式碼
```cpp
vector<int> v;
int a = v.front(); // a 的內容為 0
```
<br />
### 取得最後面的資料
語法為
```cpp
陣列名稱.back();
```
不需要任何參數。例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4, 5};
int a = v.back(); // a 的內容為 5
```
如果陣列是空的,會回傳程式記憶體區段錯誤,例如以下的程式碼
```cpp
vector<int> v;
int a = v.back();
```
<br />
### 取得指定索引值的資料
語法有兩種,分別為
```cpp
名稱[索引值];
名稱.at(索引值);
```
兩者有點差異,例如以下的程式碼
```cpp
vector<int> v = {0, 1, 2, 3, 4, 5};
int a = v[1]; // a 的內容為 1
int b = v[10]; // 索引值超出範圍,回傳 0
int c = v.at(1); // c 的內容為 1
int d = v.at(10); // 索引值超出範圍,回傳錯誤訊息 std::out_of_range
```
<br />
### 取得長度
語法為
```cpp
名稱.size();
```
不需要任何參數,回傳值格式為 size_t,沒有正負號的整數。
<br />
### 回傳最大長度
語法為
```cpp
名稱.max_size();
```
不需要任何參數,回傳值格式為 size_t,沒有正負號的整數。在我使用的系統中回傳值為 2305843009213693951,為 $2^{61} - 1$。
<br />
### 調整長度
語法為
```cpp
名稱.resize(長度, 資料);
```
將陣列調整成指定長度,資料參數可省略,預設值為 0。例如以下的程式碼
```cpp
vector<int> v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
v.resize(5); // v 的內容變為 {0, 1, 2, 3, 4}
v.resize(10, -1); // v 的內容變為 {0, 1, 2, 3, 4, -1, -1, -1, -1, -1}
v.resize(15); // v 的內容變為 {0, 1, 2, 3, 4, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0}
```
<br />
### 調整使用的記憶體
語法為
```cpp
名稱.shrink_to_fit();
```
不需要任何參數,沒有回傳值。例如以下的程式碼
```cpp
vector<int> v (100); // v 的內容為 100 個 0
v.resize(10); // v 的內容變為 10 個 0
v.shrink_to_fit(); // 調整 v 使用的記憶體
```
<br />
### 回傳使用的記憶體大小
語法為
```cpp
名稱.capacity();
```
不需要任何參數,回傳值格式為 sizt_t。例如以下的程式碼
```cpp
vector<int> v;
for(int i=0; i<100; i++) v.push_back(i); // v 的內容為 {0, 1, ..., 99}
cout << v.capacity() << endl; // 使用記憶體 128
cout << v.size() << endl; // v 的長度為 100
```
<br />
### 檢查 vector 是否為空
語法為
```cpp
名稱.empty();
```
不需要任何參數,如果陣列為空回傳 1,如果有資料回傳 0。
<br />
### 二維 vector
二維 vector 很像把資料分布在 xy 平面上,每筆有兩個索引值,就像是 x、y 座標值。由於二維 vector 看起來很像數學中的矩陣,通常會沿用矩陣的講法,將 {{0, 1, 2}, {3, 4, 5}} 這樣的二維 vector 稱為 2 列 (row)、3 欄 (column)。産生二維 vector 的語法為
```cpp
vector<vector <資料格式>> 名稱;
vector<vector <資料格式>> 名稱 = {{資料1, 資料2, 資料3, ...}, {資料4, 資料5, 資料6, ...}, ...};
```
<br />
如果使用第一種語法,通常搭配 for 迴圈及 push_back 填入資料,例如以下的程式碼
```cpp
vector<vector <int>> v;
for(int i=0; i<2; i++) {
vector<int> tmp;
for(int j=0; j<3; j++) {
tmp.push_back(i*3 + j);
}
v.push_back(tmp);
}
```
v 的內容為
```cpp
{{0, 1, 2},
{3, 4, 5}}
```
<br />
如果使用第二種語法,可以將資料寫在同一行,也可以將不同列的資料寫在不同行讓欄位對齊,例如以下的程式碼
```cpp
vector<vector <int>> v = {{0, 1, 2},
{3, 4, 5}};
```
v 的內容為
```cpp
{{0, 1, 2},
{3, 4, 5}}
```
<br />
vector 與 array 不同之處,vector 並沒有要求每列的欄數相同,例如以下的程式碼
```cpp
vector<vector <int>> v2 = {{0},
{1, 2},
{3, 4, 5},
{6, 7, 8, 9}};
```
v2 的內容為
```cpp
{{0},
{1, 2},
{3, 4, 5},
{6, 7, 8, 9}}
```
<br />
如果要印出二維 vector 的內容,也是利用 for 迴圈搭配索引值或是迭代器,例如以下的程式碼
```cpp=
vector<vector <int>> v = {{0, 1, 2},
{3, 4, 5}};
// 搭配索引值
for(size_t i=0; i<v.size(); i++) {
for(size_t j=0; j<v[i].size(); j++) {
cout << v[i][j] << " \n"[j == v[i].size()-1];
}
}
// 搭配迭代器
for(auto it = v.begin(); it != v.end(); it++) {
for(auto it2 = (*it).begin(); it2 != (*it).end(); it2++) {
cout << *it2 << " \n"[it2 == (*it).end()-1];
}
}
// 搭配迭代器,但是每筆資料後面都有空格
for(auto row : v) {
for(auto c : row) {
cout << c << " ";
}
cout << "\n";
}
```
輸出為
```cpp
0 1 2
3 4 5
```
<br /><br />
## 結語
以上是我目前常用到的 array 及 vector 功能,如果之後有遇到其它需求會再補充內容。
<br />
## 參考資料
1. [cplusplus.com Arrays](https://cplusplus.com/doc/tutorial/arrays/)
2. [cplusplus.com std::vector](https://cplusplus.com/reference/vector/vector/)
---
###### tags:`C++`