Vector

vector 的優點

在學習一個新方法前，我們勢必要反問自己「它的優點是什麼？他能解決什麼問題？」。 vector 簡單來說是一種可動態調整大小的陣列，在一些問題上特別方便；同時 vector 還提供了更多元的陣列操作功能，舉例來說像是在陣列中間插入數值、刪除數值等。

vector 的原理

vector 作為 C++ 標準函式庫中的一個容器，可以完成所有傳統陣列能做的事。要理解 vector 的原理首先我們要先定義兩個名詞「大小」與「容量」，大小指的是 vector 中實際存放資料的大小，並會隨著資料的增刪而調整；而容量是程式分配給 vector 的記憶體空間，與傳統陣列一樣必須是一段連續的記憶體空間，而資料大小必須小於等於容量，當資料大小超過容量時，vector 會自動重新申請一塊更大的記憶體空間，並將舊資料搬移到新的記憶體空間中。

提醒

重新申請的記憶體容量依照編譯器不同通常為 1.5 至 2 倍。重新申請意味著必須將舊資料進行搬移，將會造成額外的效能負擔。因此建議一開始先推測資料大小，將容量開大一點。或者是使用下面介紹的 reserve 函式來手動的調整容量。

宣告與初始化

vector 是包含在 vector 的標頭檔中，當然，如果你使用 bits/stdc++.h 這個萬用標頭檔，就不需要另外引入 vector 了。

#include <vector>

vector 的宣告語法為：

vector<資料型態> 變數名稱(初始化參數);

常見的實際寫法如下：

// 不同型態
vector<int> v; // 宣告一個名為 v 的整數 vector
vector<string> v; // 宣告一個名為 v 的字串 vector

// 宣告初始長度
vector<int> v(5); // 初始化大小為 5
vector<int> v(n); // 初始化大小為變數 n

// 初始化陣列中的數值
vector<int> v(5, -1); // 陣列中的 5 個數的值皆為 -1

// 使用數組初始化
vector<int> v({5, 2, 0}); // 直接填入初始數值

Vector 與 Iterator

vector 也可以使用 Iterator 來進行操作，這樣可以更方便的操作 vector 中的元素。兩個內建的迭代器叫做 begin() 跟 end()，就是分別指向「第一個元素」跟「最後一個元素的後面」 ( 這很容易記錯>< )。

vector<int> v({5, 2, 0});

// 使用 Iterator 進行操作
vector<int>::iterator it = v.begin(); // 指向開頭

// 使用 * 取值
cout << *it << endl; // 5

// 使用 ++ 移動
it++;

// 獲取結尾的 Iterator
vector<int>::iterator end = v.end();

注意

注意，end() 是指向「最後一個元素的後面」，所以絕對不要這樣寫：

cout << *v.end();

如果要取得最後一個元素，應該使用 end() - 1：

cout << *(v.end() - 1);

同理可證，你當然也可以輸出 *(v.begin()+3)（第三個）、*(v.end()-5) （倒數第五個）。

接下來，我們可以使用 Iterator 搭配迴圈來遍歷 vector 中的元素：

vector<int> v({5, 2, 0});

for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
    cout << *it << " ";
}

其中，vector<int>::iterator 是一種資料型態，就是指 vector 裡的迭代器。從 vector 的頭開始看，指到最後面就代表沒有東西，並且可以離開回圈了。如果還沒指到底，就用 i++ 的方式輸出更後面的數字。

但是看起來非常冗長？但沒關係，我們可以使用 auto 來自動判斷資料型態，讓程式碼更簡潔（省去 vector<int>::iterator 的宣告）：

vector<int> v({5, 2, 0});

for (auto it = v.begin(); it != v.end(); it++){
    cout << *it << " ";
}

蛤什麼？你還是覺得很冗長？！你也太貪心了吧！

不過好消息是，真的有更簡潔的寫法！

在 C++11 之後，我們可以使用範圍迴圈（Range-based for loop）來更方便的遍歷 vector 中的元素，這樣可以省去 Iterator 的宣告與判斷。

vector<int> v({5, 2, 0});

// 使用範圍迴圈
for (int i : v){
    cout << i << " ";
}

// 上面的程式碼就等同於下面的程式碼
for (auto it = v.begin(); it != v.end(); it++){
    cout << *it << " ";
}

// 也等於下面的程式碼
for (int i = 0; i < v.size(); i++){
    cout << v[i] << " ";
}

這東西其實是從 for_each 這個東西來的，有興趣可以看看 CPP Reference 的解釋。簡單來說，前面那個 int i 指的是說，我現在會跑過 v 裡面的每個東西，然後 i 代表我現在跑到誰，好比說我有個 vector 裡面有 { 1, 2, 3 }，那 i 就會從 1 變成 2 再變成 3。這就是為什麼下面的 cout 把 * 拿掉了。

當然如果你想的話，也可以使用 auto 來取代 int：

vector<int> v({5, 2, 0});

for (auto i : v){
    cout << i << " ";
}

補充

auto 是一種非常神奇的資料型態叫「自動變數類型」，他可以自動判斷你初始化它的東西是什麼資料類型。當然，auto 並不只能用在 vector 上，只要有辦法推斷出型態的地方都可以使用 auto。比如以下幾個例子：

// 相當於 int a = 5;
auto a = 5;

// 相當於 double b = 5.0;
auto b = 5.0;

其實也可以把範圍迴圈這個技巧用在 string 上，因為 string 也是一種容器，所以也可以用這個方法來遍歷 string 中的字元：

string s = "Hello, World!";

for (char c : s){
    cout << c << " ";
}

輸出結果就會是：

H e l l o ,   W o r l d !

好用的函式

如同傳統陣列底下「好用的函式」部分，vector 也可以幾乎通用所有的函式，只要把 vector 的開頭 v.begin() 與結尾 v.end() 填入即可。以下是一個簡單的示範：

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

// 反轉 vector
reverse(v.begin(), v.end()); // [4, 1, 3, 2, 5]

// 找最大值
int max = *max_element(v.begin(), v.end()); // 5

// 找最小值
int min = *min_element(v.begin(), v.end()); // 1

// 填入相同的值
fill(v.begin(), v.end(), 1); // [1, 1, 1, 1, 1]

// 計算某個值出現的次數
int count = count(v.begin(), v.end(), 1); // 5

// 找到某個值的第一次的出現位置
auto it = find(v.begin(), v.end(), 1); // 1
int index = distance(v.begin(), it); // 0

// 複製 vector
vector<int> v2(5);
copy(v.begin(), v.end(), v2.begin()); // [1, 1, 1, 1, 1]

常見成員函式

在 vector 中，有許多好用的「成員函式」，這些函式可以讓我們更方便的操作 vector。

陣列狀態

size()
- 獲取目前 vector 大小
- 即 vector 中的元素數量、長度
- 回傳一個整數
empty()
- 獲取陣列是否為空
- 回傳布林值，true 表示陣列為空，false 表示陣列不為空
capacity()：
- 獲取目前 vector 容量
- 即 vector 中的元素最大數量
- 回傳一個整數

cout << v.size() << endl; // 5

// 獲取陣列是否為空
cout << v.empty() << endl; // false

// 獲取目前 vector 容量
cout << v.capacity() << endl; // 5

注意

size() 的回傳值是 size_t，這是一種 unsigned 的整數型態，所以如果你要將 size() 的回傳值做運算時要非常小心。如果陣列前是空的，size() 會回傳 0，那如果你剛好將 size() 的回傳值減 1，那結果就會是一個很大的數字，這可能會造成不可預期的錯誤。

資料獲取

at(i)
- 取得第 i 個元素
- 和 [] 很像，不過這個函式會檢查索引是否越界，若越界會拋出錯誤訊息，而不是直接 Runtime Error
- 回傳值的型態和 vector 的宣告時指定的型態相同
front()：
- 獲取頭的值
- 也就是第一個元素，若陣列為空則可能會造成 Runtime Error）
- 回傳值的型態和 vector 的宣告時指定的型態相同
back()：
- 獲取尾的值
- 最後一個元素，若陣列為空則可能會造成 Runtime Error
- 回傳值的型態和 vector 的宣告時指定的型態相同

// 取得第 i 個元素
cout << v.at(0) << endl; // 0

// 獲取頭的值
cout << v.front() << endl; // 0

// 獲取尾的值
cout << v.back() << endl; // 0

資料操作

push_back(x)
- 將資料加到陣列最後面
- 傳入一個參數 x，是要加入的值
- 這個函式會將資料加到陣列的最後面，並且會自動調整陣列的大小
pop_back()
- 刪除最後面的數值
- 這個函式會將陣列最後面的數值刪除，並且會自動調整陣列的大小
- 若陣列為空則可能會造成 Runtime Error
insert(ite, val)
- 插入元素
- 傳入兩個參數，分別是插入的位置（型態為 Iterator）與插入的值
- 這個函式可以在陣列中的任意位置插入元素
erase(ite)
- 刪除元素
- 傳入一個參數，是要刪除的位置（型態為 Iterator）
- 這個函式可以在陣列中的任意位置刪除元素

vector<int> v(5, 0); // 宣告一個大小為 5，且初始值為 0 的 vector

// 將資料加到陣列最後面
v.push_back(1); //[0, 0, 0, 0, 0, 1]

// 刪除最後面的數值
v.pop_back(); // [0, 0, 0, 0, 0]

// 插入元素
v.insert(v.begin() + 2, 2); // [0, 0, 2, 0, 0]

// 刪除元素
v.erase(v.begin() + 2); // [0, 0, 0, 0]

注意

vector 的 insert 與 erase 函式的時間複雜度是 $O(n)$ ，這是因為在插入或刪除元素時，後面的元素也都必須移動，因此效能較差。若需要頻繁的插入或刪除操作，請考慮換個作法或使用其他資料結構。

雖然 3 級或以下的 APCS 檢定中幾乎不會遇到這類的問題，但如果你的目標是 APCS 實作 4 級以上，就必須注意上述的效能問題，以免在實作時遇到 Time Limit Exceeded（超時）的問題。

時間複雜度的概念我們會在之後的章節詳細介紹，這邊只是提醒大家如果可以的話就盡量避免使用 insert 與 erase 函式。

記憶體管控

reserve()
- 預先配置容量
- 也就是會改變 capacity() 的值
- 預先配置一個容量，避免在插入元素時需要重新配置記憶體，以提高效能
shrink_to_fit()
- 收縮多餘的容量
- 也會改變 capacity() 的值

vector<int> v(5, 0); // 宣告一個大小為 5，且初始值為 0 的 vector

// 預先配置容量
v.reserve(10); // 預先配置 10 的容量
cout << v.capacity() << endl; // 10

// 收縮多餘的容量
v.shrink_to_fit(); // 收縮多餘的容量
cout << v.capacity() << endl; // 5