# 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(f)); // 長度為 5 的整數 array，內容為 {0, 0, 0, 0, 0}
int b[5];
memset(b, -1, sizeof(f)); // 長度為 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++`
Sign in with Wallet
Connect another wallet