# STL 在C++裡面的函式中，有一些內建好用資料結構，這些資料結構都是用一種叫型別模板(template)的東西去包裝，而這些資料結構包裝起來就變成了標準模板庫(standard template library) 那STL裡面有什麼呢？ 首先我們先來講解STL的三大容器 vector、deque跟list ## vector ### vector介紹 原生C++的陣列是使用一連串的記憶體位置來儲存資料，但是當我們宣告完陣列大小後就沒辦法再修改了。 這時候我們就可以用STL裡的vector!! vector簡單來講就是一個可以變長變短的陣列。在某些情況下，可以伸縮的陣列在解題上可以方便許多。 首先，我們來宣告一個vector，以下是一些常見的vector宣告方法 ```cpp= vector<int> vec; //一般的宣告 vector<int> vec = {1, 2, 3}; //宣告一個有1,2,3的vector vector<int> vec(10); //宣告長度為10的vector vector<int> vec(10,1); //宣告長度為10的vector，並將全部填為1，如果後面沒有參數，則填入0 ``` 如果我們已經知道資料的大小是多少的話，就可以把vector當一般陣列一樣。 那如果我們不知道要輸入多大的資料，我們可以使用push_back(emplace_back)來自動新增元素並配置記憶體到vector的尾端 ```cpp= vector<int> vec; vec.push_back(1); vec.emplace_back(1); ``` push_back跟emplace_back是差不多的東西，但在某些地方上有些微的不同 以pair當作例子來看 ```cpp= vector<pair<int,int>> v; //before C++11 v.push_back(make_pair(1, 1)); v.push_back({1, 1}); //C++11 v.emplace_back(1, 1); ``` push_back是先建構一個臨時的物件，複製到容器尾端裡後再釋放臨時物件的記憶體 而emplace_back是直接呼叫建構函式建構在容器尾端 所以通常emplace_back的效率會比push_back還來的好 以下是vector常用的操作 `vec.size()` 回傳vector的大小 $O(1)$ `vec.reserve(size)`預留size大小的空間 如果要重新配置記憶體 $O(n)$，否則 $O(1)$ `vec.empty()` 回傳一個布林值，如果vector是空的就回傳true，否則回傳false， $O(1)$ `vec.clear()` 清空vector，$O(n)$ ### vector常見用途 以下兩種是vector的遍歷方式 ```cpp= vector<int> vec = {1, 2, 3}; for(int i=0;i<v.size();i++) cout << v[i] << ' '; for(int i: vec) cout << i << ' '; // C++11 以上 ``` 可以看個人喜好或是情況來決定要用哪一種遍歷方式 vector的迭代器是屬於隨機存取迭代器，所以說我們可以把兩個vector的指標做運算，再搭配二分搜求出任一個數字在第幾個位置 ```cpp= vector<int> vec; vec.begin() //vector的第一個位置 vec.end() //vector最後一個位置的後一位 int N = vec.end() - vec.begin(); //算出vec的size ``` 迭代器也可以拿來遍歷vector ```cpp= for(auto it = vec.begin(); it != vec.end(); it++) cout << *it; ``` vector也可以拿來當作連接串列，用來存圖上的邊和權重 ```cpp= vector<int> vec1[N]; for (int i = 0; i < m; ++i) { //無權單向 int a, b; cin >> a >> b; vec[a].push_back(b); } vector<pair<int,int>> vec2[N]; for (int i = 0; i < m; ++i) { //有權雙向 int a, b, w; cin >> a >> b >> w; vec2[a].push_back(make_pair(b, w)); vec2[b].push_back(make_pair(a, w)); } ``` ### 注意事項 vector在配置記憶體時蠻花時間的，如果確定好大小的話，先reserve()後再用push_back，效率會比較好 ### 習題 [TOJ 575](https://toj.tfcis.org/oj/pro/575/) [zerojudge b298](https://toj.tfcis.org/oj/pro/575/) :::spoiler 解答 TOJ 575 ```cpp= #include <bits/stdc++.h> using namespace std; #define bobotou ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define F first #define S second using pii = pair<int, int>; const int MAXN = 1000005; vector<int> vec[MAXN]; vector<pii> peo; signed main(){ bobotou; int N, K; cin >> N >> K; for (int i = 0; i < K; i++){ int tmp1, tmp2; cin >> tmp1 >> tmp2; peo.emplace_back(tmp1, tmp2); } for(int i = 0; i < K; i++){ vec[peo[i].F].emplace_back(peo[i].S); vec[peo[i].S].emplace_back(peo[i].F); } for(int i = 1; i <= N; i++){ sort(vec[i].begin(),vec[i].end()); for(int j = 0; j < vec[i].size(); j++){ if(j != 0) cout << ' '; cout << vec[i][j]; } cout << '\n'; } } ``` zerojudge b298 (vector + queue) ```cpp= #include <bits/stdc++.h> using namespace std; #define bobotou ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pb(x) push_back(x) #define F first #define S second const int MAXN = 100005; vector<int> vec[MAXN]; bool poll[MAXN]; signed main(){ bobotou; int N, M , L , Q; int tmp1, tmp2; cin >> N >> M >> L >> Q; for(int i = 0; i < M; i++){ cin >> tmp1 >> tmp2; vec[tmp1].pb(tmp2); } queue<int> q; for(int i = 0; i < L; i++){ cin >> tmp1; q.push(tmp1); while(!q.empty()){ int x = q.front(); q.pop(); if(poll[x]) continue; poll[x] = true; for(auto i : vec[x]) q.push(i); } } for(int i = 0; i < Q; i++){ cin >> tmp1; cout << (poll[tmp1] ? "TUIHUOOOOOO\n" : "YA~~\n"); } } ``` ::: ## deque deque 念法(ㄉㄟˋㄎㄜˇ ) 中文叫雙向隊列 宣告寫法 ```cpp= deque<int> dq; ``` 簡單來講就是可以在首尾新增、刪除元素的vector 大致上跟vector差不多，所以就直接講用途 `dq.push_front()` 在最前面放入元素 `dq.push_back()` 在最後面放入元素 `dq.pop_front()` 移除前面的元素 `dq.pop_back()` 移除後面的元素 `dq.front()` 回傳最前面的元素 `dq.back()` 回傳最後面的元素 `dq.size()` 回傳deque的大小 `dq.empty()` 回傳一個bool，如果為空true，否則false 同樣的也可以像vector一樣用emplace來壓常數 跟vector一樣也是隨機存取迭代器，所以也可以把兩個迭代器指標做運算 ### deque常見用途 sliding window DP的單調對列優化 ### 注意事項 deque雖然比vector的功能還要來的多，但是deque卻比vector還要慢很多，所以能用vector達成的盡量用vector來達成。 後面提到的適配器(Container Adapters)很多內建也都是deque，所以我們可以把那適配器容器改成vector來增加效率。 ### 例題 ## list STL的list是由一種叫連結串列(linked-list)來包裝 但是list其實在競程中沒有很常用到 而且在解題時我們也可以用陣列+struct來取代list 如果想要知道更多list的內容的話可以看[這篇文章](https://hackmd.io/@Zero871015/H12vTu8aX?type=view) ### 例題 ## stack 一種先進後出的資料結構，由資料的同一端開口加入資料(push)或刪除資料(pop)。 ### 實作 ```cpp= ``` 生活上的例子:賣場的推車(由同個方向加入推車或拿走推車) ## queue 與stack語法類似，最大的不同是stack是後進先出，而queue則是先進先出 ## priority_queue ## set ## map ## pair ## bitset