Vector

常見

vector 的優點

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

vector 的原理

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

img

提醒

重新申請的記憶體容量依照編譯器不同通常為 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]
注意

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

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

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

記憶體管控

  • 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

小測驗

vector 可以宣告後再調整大小?