「學習筆記」vector

本文並不是 vector 的入門教學。

定義

std::vector 是封裝動態陣列的順序容器。

vector 通常佔用多於靜態陣列的空間，因為要分配更多記憶體以管理將來的增長。如果元素數量已知，可以使用 reserve() 函數提前分配記憶體。

操作函數

由於 vector 大家比較熟悉了，這裡給大家帶來一些其他不太常用的操作。

1. at(x)

存取元素，相當於 []，但是 at() 會進行越界判斷，如果越界，會返回異常（即 return 3;），程式停止。
常數比 [] 稍大，即速度稍慢，但是偵錯的時候會比較方便。由於 [] 不會進行越界處理，且 DEV-C++ 有程式保護，所以你會存取到一個奇怪的元素，在 OJ 上提交，最終導致答案錯誤，而不是 RE，會對查錯產生干擾。

2. resize(x, y)

這個函數與 reserve 函數很像，都是分配空間的。
resize() 函數還會改變容器大小，並進行賦值，resize(n, 1) 就是將 vector 的長度和空間改為 \(n\)，且複製元素為 \(1\)；但是 reserve 並不會賦值，因此 vector 裡面是隨機的元素。
強烈建議：如果想進行賦值操作，最好是先用 clear() 函數清空 vector，在使用 resize() 來定長賦值。

3. swap()

交換兩個 vector 中的元素，但是是常數複雜度，不是 \(O_n\) 的。
在寫長鏈剖分優化 DP，合併 DP 陣列時有用過，因為複雜度比較優秀。

4. emplace() 與 emplace_back()

它們的功能相當於 insert() 與 push_back()，但是也有區別。
就拿 emplace_back() 與 push_back() 舉例：
push_back()：向容器中加入一個右值元素(臨時物件)時，首先會呼叫建構函式構造這個臨時物件，然後需要呼叫拷貝建構函式將這個臨時物件放入容器中。原來的臨時變數釋放。這樣造成的問題就是臨時變數申請資源的浪費。
emplace_back()：引入了右值參照，轉移建構函式，在插入的時候直接構造，只需要構造一次即可。
簡化一點：push_back() 會先在插入時構造一個臨時變數，再拷貝進入 vector，而 emplace_back() 則直接在插入時構造並放入 vector 中，沒有拷貝的過程。
因此，emplace_back() 會比 push_back() 快，但也正是由於建構函式使用的區別，兩者在一些情況下的使用並不一樣。

(1) 一般情況下直接插入單個元素

vector<int> a;
a.push_back(1);
a.emplace_back(1);

兩者的用法是一樣的。

(2) 當變數型別為 pair 時

vector<pair<int, int> > a;
a.push_back({1, 2});
a.emplace_back(1, 2);

由於 emplace_back() 是直接構造，因此，只需要按照元素的順序依次插入即可（元素要一一對應！），而 push_back() 則是將 {1, 2} 放入一個臨時的 pair 型別的變數中，再拷貝進去。

(3) 當變數型別是結構體型別時

struct node {
	int u, v, w;
};

vector<int> a;

a.push_back(node{1, 2, 3});
a.emplace_back(1, 2, 3);

push_back() 函數沒有任何問題，但是，emplace_back() 就無法通過編譯。
遇到這種情況，我們需要為這個結構體寫一個建構函式，才可以使用 emplace_back()，像這樣

struct node {
	int u, v, w;
	
	node(int a, int b, int c) {
		u = a, v = b, w = c;
	}
	
// 或者這樣
//	node(int a, int b, int c) : u(a), v(b), w(c) {};
};

vector<int> a;

a.push_back(node{1, 2, 3});
a.emplace_back(1, 2, 3);

這樣就是對的了。

5. 輸入元素

這是一個慢但是看著很高階的寫法。

vector<int> a;
a.resize(10);
for (auto &i : a) {
	cin >> i;
}

後記

關於 vector，我個人覺得這是個非常好用的 STL，方便，但是，這正因為是 STL，因此會帶有常數，很可能被卡。
儘管如此，我還是很喜歡 vector。
此外，關於 emplace 這個東西，deque、queue 等別的 STL 容器也有，用法都是一樣的，但是，請不要搞混了。
emplace() 對應 insert 或者 push 再或者一些特殊 STL 的插入 (例如 map)
emplace_back() 對應 push_back()
emplace_front() 對應 push_front()
在 map 中還有 emplace_hint() 函數，用法與 emplace() 差不多。