C++ 陣列 array 及 STL vector

作者：王一哲
日期：2023年8月6日

傳統的陣列 array

C++ 傳統的陣列 array，可以用來儲存多筆相同格式的資料，儲存這些資料的記憶體位址是連續的，所以讀取資料時，是依據陣列開頭的記憶體位址再加上索引值，索引值由 0 開始。以下是關於 array 的基礎知識。

産生 array

可以使用所有內建的資料格式，例如 int、float、char、string，也可以使用自訂的資料格式，但是一個 array 當中所有的資料只能是同一種格式。語法通常有以下3種

資料格式 名稱[長度];
資料格式 名稱[長度] = {資料1, 資料2, 資料3, ...};
資料格式 名稱[長度] = {0};

1. 第一種：産生 array 時沒有指定資料內容，切記在讀取 array 前一定要填入資料，否則無法預測會讀到什麼數值。
2. 第二種：可以省略長度，編譯器會自動根據資料內容決定 array 的長度。
3. 第三種：産生指定長度、所有資料皆為 0 的 array。

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

搭配 memset 設定 array 內容

如果想要使用 memset，需要先引入函式庫 cstring，語法為

memset(名稱, 0, sizeof(名稱));  // 將指定名稱的 array 資料全部設定為 0
memset(名稱, -1, sizeof(名稱)); // 將指定名稱的 array 資料全部設定為 -1

例如以下的程式碼

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}

取得 array 的長度

array 沒有回傳長度的功能，通常是用 array 使用的記憶體除以資料格式使用的記憶體，語法為

sizeof(名稱)/sizeof(資料格式);

例如以下的程式碼

int a[5];
int length = sizeof(a)/sizeof(int);  // 回傳值為 5

取得指定索引值的資料

語法有兩種

名稱[索引值];   // 比較常用的語法
*名稱 + 索引值; // 用指標 * 取得 array 開頭的記憶體位址

例如以下的程式碼，輸出的值皆為 1。

int a[] = {0, 1, 2, 3, 4};
cout << a[1] << "\n";
cout << *a + 1 << "\n";

使用 for 迴圈填入資料

如果想要産生一個很長的 array，但是資料之間有規律性，通常會使用 for 迴圈填入資料，手動填入資料太麻煩了，例如以下的程式碼，産生的 array 內容為 {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}。

int a[10];
for(int i=0; i<10; i++) a[i] = 2*i;

使用 for 迴圈印出資料

如果想要印出 array 的資料，不能使用以下的語法，這樣只會印出 array 的記憶體位址。

cout << 名稱 << endl;

通常會使用 for 迴圈配合索引值印出資料，例如以下的程式碼

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];

輸出為

0 1 2 3 4

這裡使用了一個小技巧，最後面的 [i == length-1] 是指當方括號中的條件成立時印出換行符號 \n，如果條件不成立時印出空格。因為程式競賽或 APCS 經常會要求這樣輸出答案，用空格分隔資料，但是最後一筆資料直接換行、不加空格。

二維 array

二維 array 很像把資料分布在 xy 平面上，每筆有兩個索引值，就像是 x、y 座標值。由於二維 array 看起來很像數學中的矩陣，通常會沿用矩陣的講法，將 {{0, 1, 2}, {3, 4, 5}} 這樣的二維 array 稱為 2 列 (row)、3 欄 (column)。産生二維 array 的語法為

資料格式 名稱[列數][欄數];
資料格式 名稱[列數][欄數] = {{資料1, 資料2, 資料3, ...}, {資料4, 資料5, 資料6, ...}, ...};

如果産生二維 array 時有指定資料可以省略列數，編譯器會自動從指定資料判斷列數，但是欄數不能省略。例如以下的程式碼，a 的內容為 {{0, 1, 2}, {3, 4, 5}}，b 的內容為 {{1, 2, 0}, {3, 4, 0}}，因為 b 應該有 3 欄，沒有指定的資料自動補 0。

int a[2][3] = {{0, 1, 2}, {3, 4, 5}};
int b[][3] = {{1, 2}, {3, 4}};

如果要印出二維 array 的內容，也是利用 for 迴圈

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];
    }
}

輸出為

0 1 2
3 4 5

STL vector 函式庫

STL vector 與 array 不同，可以動態地改變容器長度，使用上比較方便。要先引入函式庫，函式庫的官方說明書在此 cplusplus.com std::vector。

#include <vector>

建立 vector

vector 的資料可以是所有內建的資料格式，例如 int、float、char、string，也可以使用自訂的資料格式。語法為

// 産生空的 vector
vector<資料格式> 名稱;
// 産生填入相同資料的 vector，資料可省略，預設值為 0
vector<資料格式> 名稱 (資料數量, 資料);
// 由 vector2 複製資料，也可以改變記憶體位置只複製部分內容
vector<資料格式> 名稱 (vector2名稱.begin(), vector2名稱.end());
// 由 vector2 複製資料
vector<資料格式> 名稱 (vector2名稱);
// 由已定義的 array 複製資料
vector<資料格式> 名稱 (array名稱, array名稱 + array長度);
// 産生陣列並指定資料
vector<資料格式> 名稱 {用逗號分隔的資料};
vector<資料格式> 名稱 = {用逗號分隔的資料};

例如以下的程式碼

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}

迭代器 iterator

迭代器可以用來取得物件對應的記憶體位址，有以下幾種：

名稱.begin();  // 回傳起點位址
名稱.end();    // 回傳終點位址
名稱.rbegin(); // 回傳終點位址，由後向前向讀取資料
名稱.rend();   // 回傳起點位址，由後向前向讀取資料
名稱.cbegin(); // 回傳起點位址，回傳值為常數
名稱.cend();   // 回傳終點位址，回傳值為常數
名稱.crbegin();// 回傳終點位址，由後向前向讀取資料，回傳值為常數
名稱.crend();  // 回傳起點位址，由後向前向讀取資料，回傳值為常數

迭代器的變數名稱通常是 it，寫法有兩種，例如以下的程式碼

vector<int> v = {0, 1, 2, 3, 4};
vector<int>::iterator it = v.begin();
auto it = v.begin();

但是 vector<int>::iterator 只能用在 begin()、end()，還是用 auto 會比較方便。如果要印出陣列中所有的資料，可以配合迭代器處理，例如以下的程式碼

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

填入資料

第一種語法為

名稱.assign(長度, 資料);

例如以下的程式碼

vector<int> v;
v.assign(5, 10);  // v 的內容為 {10, 10, 10, 10, 10}

第二種語法是由另一個 vector 中指定的記憶體位址複製資料，不包含終點位址。

名稱.assign(起點, 終點);

例如以下的程式碼

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}

第三種語法是由另一個 array 中指定的記憶體位址複製資料，不包含終點位址。

名稱.assign(array起點, array終點);

例如以下的程式碼

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}

從最後面填入資料

語法為

名稱.push_back(資料);

例如以下的程式碼

vector<int> v;
v.push_back(0);  // v 的內容為 {0}
v.push_back(1);  // v 的內容為 {0, 1}
v.push_back(2);  // v 的內容為 {0, 1, 2}

另一個工具是 emplace_back，語法為

名稱.emplace_back(資料);

看起來效果和 push_back 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼

vector<int> v;
v.emplace_back(0);  // v 的內容為 {0}
v.emplace_back(1);  // v 的內容為 {0, 1}
v.emplace_back(2);  // v 的內容為 {0, 1, 2}

於指定的位置插入資料

語法為

名稱.insert(記憶體位址, 資料);

要配合迭代器取得記憶體位址，例如以下的程式碼

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}

另一個工具是 emplace，語法為

陣列名稱.emplace(記憶體位址, 資料);

看起來效果和 instert 差不多，但是據說少了複製構造的步驟，所以效率更高。例如以下的程式碼

vector<int> v = {0, 1, 2, 3, 4};
v.emplace(v.begin()+1, -1);  // 於開頭處向後 1 格插入 -1，v 的內容變為 {0, -1, 1, 2, 3, 4}

刪除最後面的資料

語法為

名稱.pop_back();

不需要任何參數，沒有回傳值。例如以下的程式碼

vector<int> v = {0, 1, 2, 3, 4, 5};
v.pop_back();  // 刪除開頭處的資料，v 的內容變為 {0, 1, 2, 3, 4}

如果陣列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼

vector<int> v;
v.pop_back();

刪除指定範圍的資料

語法為

名稱.erase(起點位址, 終點位址);

不包含終點位址。例如以下的程式碼

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());  // 刪除所有資料

清除所有資料

語法為

名稱.clear();

不需要加上任何參數，清空資料後陣列長度為 0。

交換兩個 vector 的資料

語法為

名稱1.swap(名稱2);

取得最前面的資料

語法為

名稱.front();

不需要任何參數。例如以下的程式碼

vector<int> v = {0, 1, 2, 3, 4, 5};
int a = v.front();  // a 的內容為 0

如果陣列是空的，會回傳 0，例如以下的程式碼

vector<int> v;
int a = v.front();  // a 的內容為 0

取得最後面的資料

語法為

陣列名稱.back();

不需要任何參數。例如以下的程式碼

vector<int> v = {0, 1, 2, 3, 4, 5};
int a = v.back();  // a 的內容為 5

如果陣列是空的，會回傳程式記憶體區段錯誤，例如以下的程式碼

vector<int> v;
int a = v.back();

取得指定索引值的資料

語法有兩種，分別為

名稱[索引值];
名稱.at(索引值);

兩者有點差異，例如以下的程式碼

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

取得長度

語法為

名稱.size();

不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。

回傳最大長度

語法為

名稱.max_size();

不需要任何參數，回傳值格式為 size_t，沒有正負號的整數。在我使用的系統中回傳值為 2305843009213693951，為 $2^{61} - 1$。

調整長度

語法為

名稱.resize(長度, 資料);

將陣列調整成指定長度，資料參數可省略，預設值為 0。例如以下的程式碼

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}

調整使用的記憶體

語法為

名稱.shrink_to_fit();

不需要任何參數，沒有回傳值。例如以下的程式碼

vector<int> v (100); // v 的內容為 100 個 0
v.resize(10);        // v 的內容變為 10 個 0
v.shrink_to_fit();   // 調整 v 使用的記憶體

回傳使用的記憶體大小

語法為

名稱.capacity();

不需要任何參數，回傳值格式為 sizt_t。例如以下的程式碼

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

檢查 vector 是否為空

語法為

名稱.empty();

不需要任何參數，如果陣列為空回傳 1，如果有資料回傳 0。

二維 vector

二維 vector 很像把資料分布在 xy 平面上，每筆有兩個索引值，就像是 x、y 座標值。由於二維 vector 看起來很像數學中的矩陣，通常會沿用矩陣的講法，將 {{0, 1, 2}, {3, 4, 5}} 這樣的二維 vector 稱為 2 列 (row)、3 欄 (column)。産生二維 vector 的語法為

vector<vector <資料格式>> 名稱;
vector<vector <資料格式>> 名稱 = {{資料1, 資料2, 資料3, ...}, {資料4, 資料5, 資料6, ...}, ...};

如果使用第一種語法，通常搭配 for 迴圈及 push_back 填入資料，例如以下的程式碼

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 的內容為

{{0, 1, 2},
 {3, 4, 5}}

如果使用第二種語法，可以將資料寫在同一行，也可以將不同列的資料寫在不同行讓欄位對齊，例如以下的程式碼

vector<vector <int>> v = {{0, 1, 2},
                          {3, 4, 5}};

v 的內容為

{{0, 1, 2},
 {3, 4, 5}}

vector 與 array 不同之處，vector 並沒有要求每列的欄數相同，例如以下的程式碼

vector<vector <int>> v2 = {{0},
                           {1, 2},
                           {3, 4, 5},
                           {6, 7, 8, 9}};

v2 的內容為

{{0},
 {1, 2},
 {3, 4, 5},
 {6, 7, 8, 9}}

如果要印出二維 vector 的內容，也是利用 for 迴圈搭配索引值或是迭代器，例如以下的程式碼

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";
}

輸出為

0 1 2
3 4 5

結語

以上是我目前常用到的 array 及 vector 功能，如果之後有遇到其它需求會再補充內容。

參考資料

1. cplusplus.com Arrays
2. cplusplus.com std::vector

---

HackMD 版本連結：https://hackmd.io/@yizhewang/Sy4Coccsh