開啟章節選單
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
函式的時間複雜度是 ,這是因為在插入或刪除元素時,後面的元素也都必須移動,因此效能較差。若需要頻繁的插入或刪除操作,請考慮換個作法或使用其他資料結構。
雖然 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
小測驗
vector 可以宣告後再調整大小?