STL - HackMD

# 標準模板庫 # STL ---- ## 概要 STL常用容器與用法整理搭配[基礎資結](https://hackmd.io/@PixelCat/SyRGa24pO)、[複雜度](https://hackmd.io/@PixelCat/S1ZVa3Eau)服用，風味更佳 --- ## STL是什麼 ---- ### S tandard ### T emplate ### L ibrary 根本沒解釋到 = =" ---- STL提供一些寫好的簡單常見資料結構不管什麼型別的資料都能裝本篇將介紹 1. 什麼是模板 (template關鍵字) 2. 如何用STL裝資料 (STL容器) 3. 如何從容器裡取出資料 (STL迭代器) 4. 關於仿函數 (函數物件) ---- 僅列出跟競賽相關和/或我有用過的內容想當C++大師的同學請自行挖[文](https://cplusplus.com/reference/stl/)[件](https://cplusplus.com/reference/iterator/iterator/)或[google](https://www.google.com/search?q=c%2B%2B+STL) ---- 有些不常用或太不初學的內容也有寫出來初學者看到[迭代器](#/15)或[仿函數](#/16)基本上可以跳過那些都算進階用法了 --- ## template 關鍵字 ---- 假設我們想自己實作一個 `max` 函數 ```cpp= int myMax(int a, int b){ if(a > b) return a; else return b; } long long int myMax(long long int a, long long int b){ if(a > b) return a; else return b; } double myMax(double a, double b){ if(a > b) return a; else return b; } //..... ``` 型別這麼多，根本沒完沒了可是他們都在做一樣的事情啊 ---- 模板函數的語法 ```cpp= template<typename T> T myMax(T a, T b){ if(a > b) return a; else return b; } int main(){ int a = myMax<int>(3, 4); //OK string b = myMax<double>(3.6, 2.5); //OK } ``` 我們創造出了萬能的 `max` 函數! ---- 同樣的想法也能用在結構體上 ```cpp= template<typename T1, typename T2> struct TwoInOne{ T1 var1; T2 var2; }; int main(){ TwoInOne<int, string> a; //OK a.var1 = 5; a.var2 = "owo"; TwoInOne<char, bool> b; //OK b.var1 = 'z'; b.var2 = true; } ``` 只要宣告的時候用角括號包起來這個結構體可以裝任意型態的兩個變數 ---- template的精神在於既然這個函數/物件對任何型別都有用那**乾脆把型別也當成一個參數** 這樣就不用管型別的問題了 ---- > STL提供一些寫好的簡單常見資料 > 結構，不管什麼型別的資料都能裝於是通常STL容器都會跟著角括號一起出現表示STL什麼都可以裝 --- ## std::pair ---- 可以把兩個東西包在一起而不用自己寫一個struct 不算在STL，跟STL很像就一起講吧 ---- ### 宣告角括號裡面分別放兩個東西的型別名稱 ```cpp= pair<int, int> p1; pair<string, char> p2; ``` ---- ### 建構建構函數(constructor)也就是初始化函數(initializer) 決定這個物件一開始長怎樣 ```cpp= pair<int, int> p3(1, 2); //宣告同時指定初始值 ``` ---- ### 操作 `first`、`second` 分別存取兩個元素 ```cpp= pair<int, char> p(10, 'c'); p.second = 'a'; //第二個元素 cout << p.first << "," << p.second << "\n"; // 10,a ``` ---- ### 其他 pair有內建比較運算先比first再比second 都一樣就一樣 ```cpp= pair<int, int> a(2, 4), b(3, 3); cout << (a > b) << "\n"; // 0 swap(a.first, a.second); cout << (a <= b) << "\n"; // 0 ``` ---- `make_pair` 製造一個新的pair ```cpp= pair<int, char> p; p = make_pair(5, 'c'); p = pair<int, char>(5, 'c'); ``` 兩行效果完全一樣個人偏好問題 ~~教派戰起來，我要看到血流成河~~ ---- pair有個兄弟[tuple](https://en.cppreference.com/w/cpp/utility/tuple) 可以裝不只兩個東西不過我是沒用過，偏好自己寫struct --- ## std::vector ---- 可變長度的陣列 vector直翻是向量，可是std::vector跟向量完全不像 \_( \_-w-)\_ ---- ### 宣告角括號裡放你要裝的型別 ```cpp= std::vector<int> v1; //整數陣列 ``` ---- ### 建構 ```cpp= std::vector<int> v2(size); //初始長度 std::vector<int> v3(size, value); //初始長度、初始值 ``` ---- ### 操作在尾端新增一個元素，陣列變長一格，$\mathcal{O}(1)$ ```cpp= v1.push_back(value); v1.emplace_back(value); ``` 從尾端刪除一個元素，陣列變短一格，$\mathcal{O}(1)$ ```cpp= v1.pop_back(); ``` 若pop時陣列為空，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作回傳目前陣列長度，$\mathcal{O}(1)$ ```cpp= v1.size() ``` 回傳目前陣列長度是否為零，$\mathcal{O}(1)$ ```cpp= v1.empty() ``` ---- ### 操作把陣列清空(長度變成0)，$\mathcal{O}(N)$ ```cpp= v1.clear(); ``` 重新指定陣列長度，$\mathcal{O}(N)$ ```cpp= v1.resize(newSize); ``` 複雜度中的 $size$ 代表目前陣列長度 $\Delta size$ 代表長度變化量 ---- ### 操作取得第一個元素，$\mathcal{O}(1)$ ```cpp= v1.front() ``` 取得最後一個元素，$\mathcal{O}(1)$ ```cpp= v1.back() ``` 若此時陣列為空，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作中括號用法跟一般陣列一樣，$\mathcal{O}(1)$ ```cpp= v1[index] ``` 若index超出目前陣列大小，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作取得指向 `v1[0]` 的迭代器，$\mathcal{O}(1)$ ```cpp= v1.begin() ``` 取得指向 `v1[k]` 的迭代器，$\mathcal{O}(1)$ ```cpp= v1.begin() + k ``` 取得指向 `v1[v1.size()]` 的迭代器，$\mathcal{O}(1)$ ```cpp= v1.end() ``` ---- ### 其他 begin和end常用在[這些](https://hackmd.io/@nehs-iced-7th/rk7moqETd#/4/5)函數上 ```cpp= std::vector<int> v4 = {2,4,3,1}; // v: 2 4 3 1 sort(v4.begin(), v4.end()); // v: 1 2 3 4 auto it = upper_bound(v4.begin(), v4.end(), 2); // v: 1 2 3 4 // it: ^ cout << it - v4.begin() << "\n"; // 2 ``` --- ## std::deque ---- 雙端隊列 {++**d**++|}ouble {++**e**++|}nded {++**que**++|}ue 音近 _deck_ 簡單來說就是兩邊都能新增刪除的vector (正常的隊列 aka. queue 在後面) ---- ### 宣告角括號裡放你要裝的型別 ```cpp= std::deque<int> dq1; //整數陣列 ``` ---- ### 建構建構函數(constructor)也就是初始化函數(initializer) 決定這個物件一開始長怎樣 ```cpp= std::deque<int> dq2(size); //初始長度 std::deque<int> dq3(size, value); //初始長度、初始值 ``` ---- ### 操作在尾端新增一個元素，陣列變長一格，$\mathcal{O}(1)$ ```cpp= dq1.push_back(value); dq1.emplace_back(value); ``` 從尾端刪除一個元素，陣列變短一格，$\mathcal{O}(1)$ ```cpp= dq1.pop_back(); ``` 若pop時陣列為空，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作在前端新增一個元素，陣列變長一格，$\mathcal{O}(1)$ ```cpp= dq1.push_front(value); dq1.emplace_front(value); ``` 從前端刪除一個元素，陣列變短一格，$\mathcal{O}(1)$ ```cpp= dq1.pop_front(); ``` 若pop時陣列為空，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作回傳目前陣列長度，$\mathcal{O}(1)$ ```cpp= dq1.size() ``` 回傳目前陣列長度是否為零，$\mathcal{O}(1)$ ```cpp= dq1.empty() ``` ---- ### 操作把陣列清空(長度變成0)，$\mathcal{O}(size)$ ```cpp= dq1.clear(); ``` 重新指定陣列長度，$\mathcal{O}(\Delta size)$ ```cpp= dq1.resize(newSize); ``` 複雜度中的 $size$ 代表目前陣列長度 $\Delta size$ 代表長度變化量 ---- ### 操作取得第一個元素，$\mathcal{O}(1)$ ```cpp= dq1.front() ``` 取得最後一個元素，$\mathcal{O}(1)$ ```cpp= dq1.back() ``` 若此時陣列為空，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作中括號用法跟一般陣列一樣，$\mathcal{O}(1)$ ```cpp= dq1[index] ``` 若index超出目前陣列大小，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作取得指向 `dq1[0]` 的迭代器，$\mathcal{O}(1)$ ```cpp= dq1.begin() ``` 取得指向 `dq1[k]` 的迭代器，$\mathcal{O}(1)$ ```cpp= dq1.begin() + k ``` 取得指向 `dq1[dq1.size()]` 的迭代器，$\mathcal{O}(1)$ ```cpp= dq1.end() ``` ---- ### 其他 begin和end常用在[這些](https://hackmd.io/@nehs-iced-7th/rk7moqETd#/4/5)函數上 ```cpp= std::deque<int> dq4 = {2,4,3,1}; // v: 2 4 3 1 sort(dq4.begin(), dq4.end()); // v: 1 2 3 4 auto it = upper_bound(dq4.begin(), dq4.end(), 2); // v: 1 2 3 4 // it: ^ cout << it - dq4.begin() << "\n"; // 2 ``` ~~全部從vector那邊複製過來，好耶~~ ---- ### 其他 deque看起來可以完全取代vector 然而deque的執行速度比vector稍慢在某些題目中可能會有TLE的風險所以能用vector就用vector吧 --- ## std::list ## std::forward_list ---- `std::list` 是雙向連結串列 `std::forward_list` 是單向連結串列 ---- 兩個都沒人在用，跳過 --- ## std::queue ---- 正常的隊列後面進去前面出來所以叫FIFO (first in first out) 詳情左轉[基礎資結](https://hackmd.io/@nehs-iced-7th/SyRGa24pO) 可以完全被[deque](#/5)取代 ---- ### 宣告角括號裡放你要裝的型別 ```cpp= std::queue<int> que; //整數隊列 ``` ---- ### 建構我[一個都沒用過](https://cplusplus.com/reference/queue/queue/queue/) ---- ### 操作新增元素排最後面，隊伍長度變長一格，$\mathcal{O}(1)$ ```cpp= que.push(value); que.emplace(value); ``` 砍掉最前面的元素，隊伍長度變短一格，$\mathcal{O}(1)$ ```cpp= que.pop(); ``` 假如都沒人了你還硬要砍，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作回傳目前隊伍長度，$\mathcal{O}(1)$ ```cpp= que.size() ``` 回傳目前隊伍是不是沒人，$\mathcal{O}(1)$ ```cpp= que.empty() ``` ---- ### 操作回傳隊伍最前面的元素，$\mathcal{O}(1)$ ```cpp= que.front() ``` 假如隊伍現在沒人，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 其他 queue裡面的東西(例如排第二個是誰)是看不到的要偷看請用[deque](#/5) ---- ### 其他 queue沒有自帶clear，要清空請這樣 ```cpp= while(!que.empty()) que.pop(); ``` --- ## std::stack ---- 堆疊後面進去後面出來所以叫LIFO (last in first out) 詳情左轉[基礎資結](https://hackmd.io/@nehs-iced-7th/SyRGa24pO) 可以完全被[vector](#/4)或[deque](#/5)取代 ---- ### 宣告角括號裡放你要裝的型別 ```cpp= std::stack<int> stk; //整數堆疊 ``` ---- ### 建構 [一個都沒用過](https://cplusplus.com/reference/stack/stack/stack/) ---- ### 操作新增元素排最後面，堆疊長度變長一格，$\mathcal{O}(1)$ ```cpp= stk.push(value); stk.emplace(value); ``` 砍掉最後面的元素，堆疊長度變短一格，$\mathcal{O}(1)$ ```cpp= stk.pop(); ``` 假如都沒人了你還硬要砍，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作回傳目前堆疊長度，$\mathcal{O}(1)$ ```cpp= stk.size() ``` 回傳目前堆疊是不是沒東西，$\mathcal{O}(1)$ ```cpp= stk.empty() ``` ---- ### 操作回傳堆疊最後面的元素，$\mathcal{O}(1)$ ```cpp= stk.top() ``` 假如堆疊現在沒東西，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 其他 stack裡面的東西(例如排第二個是誰)是看不到的要偷看請用[vector](#/4)或[deque](#/5) ---- ### 其他 stack沒有自帶clear，要清空請這樣 ```cpp= while(!stk.empty()) stk.pop(); ``` ~~又是從前面複製貼上，好耶~~ --- ## std::priority_queue ---- 優先隊列每個元素丟進去之後在裡面比大小最贏的最先被丟出來也就是一個heap 詳情左轉[基礎資結](https://hackmd.io/@nehs-iced-7th/SyRGa24pO) 預設是越大的越先出來內部實作使用小於運算子做比較也可以自訂判斷條件像[這樣](#/9/8)[這樣](#/16) ---- ### 宣告角括號指定資料型別 ```cpp= std::priority_queue<int> pq1; //整數優先隊列 ``` ---- ### 操作新增一個元素，$\mathcal{O}(\log (size))$ ```cpp= pq1.push(value); pq1.emplace(value); ``` 把容器裡最大的元素砍掉，$\mathcal{O}(\log (size))$ ```cpp= pq1.pop(); ``` 假如都沒人了你還硬要砍，還是{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} 複雜度中的size代表目前容器裡有多少元素 ---- ### 操作回傳目前容器裡有幾個元素，$\mathcal{O}(1)$ ```cpp= pq1.size() ``` 回傳目前容器是否為空，$\mathcal{O}(1)$ ```cpp= pq1.empty() ``` ---- ### 操作回傳容器裡最大的元素，$\mathcal{O}(1)$ ```cpp= pq1.top() ``` 假如容器現在是空的，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 其他常見的寫法是 ```cpp= priority_queue<int, vector<int>, greater<int>> pq3; ``` 內建的仿函數 `greater<int>` 等同於 `operator >` 代表 `pq3` 中數字越小越早跑出來這種優先隊列的用法非常常見 ---- ### 其他 priority_queue也沒有自帶clear，要清空請這樣 ```cpp= while(!pq1.empty()) pq1.pop(); ``` --- ## std::set ---- 沒有重複元素的集合可以 1. 插入元素 2. 刪除元素 3. 查詢集合裡有沒有某元素 4. 集合裡自動對元素排序 ---- ### 宣告角括號指定資料型別 ```cpp= std::set<int> s1; //整數集合 ``` ---- ### 操作插入一個新元素，$\mathcal{O}(\log (size))$ ```cpp= s1.insert(value); s1.emplace(value); ``` 刪除一個元素，$\mathcal{O}(\log (size))$ ```cpp= s1.erase(value); //刪除value這個值 ``` 假如沒這個值給你刪，什麼都不會發生 ---- ### 操作檢查一個值有沒有在集合裡出現，$\mathcal{O}(\log (size))$ ```cpp= s1.count(value) ``` ---- ### 操作回傳目前容器裡有幾個值，$\mathcal{O}(1)$ ```cpp= s1.size() ``` 回傳目前容器是否為空，$\mathcal{O}(1)$ ```cpp= s1.empty() ``` 清空容器，$\mathcal{O}(size)$ ```cpp= s1.clear(); ``` ---- ### 操作取得頭尾迭代器，$\mathcal{O}(1))$ ```cpp= s1.begin() s1.end() ``` :::spoiler 依照慣例 `end()` 指向的是虛無我自己在測試的時候 `*s1.end()` 總是跟s1的大小相等不知道是不是巧合總之可以確定這個值不是s1裡的任何一個元素 ::: ---- ### 操作尋找一個元素，$\mathcal{O}(\log (size))$ 假如找到了，回傳指向那個元素的迭代器假如沒找到，回傳 `s1.end()` ```cpp= s1.find(value) ``` 也可以用迭代器刪除元素，$\mathcal{O}(1)$ ```cpp= s1.erase(iter); ``` ```cpp= s1.erase(value); //這兩行 s1.erase(s1.find(value)); //效果相同 ``` 假如你去erase一個指向虛無的迭代器，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作 set裡面的元素是自動排序好的(由小到大) 所以可以[二分搜](https://hackmd.io/@nehs-iced-7th/S1bNH5YB_#/9)找東西? 可是直接用 `std::XXXer_bound` 的速度也是不行的請用set自己的 `XXXer_bound` 才是$\mathcal{O}(\log (size))$ ```cpp= lower_bound(s1.begin(), s1.end(), value); //turtle speed s1.lower_bound(value); //speedyyy upper_bound(s1.begin(), s1.end(), value); //turtle speed s1.upper_bound(value); //speedyyy ``` ---- ### 其他注意跟vector、deque不一樣 set的迭代器只能往前往後移例如我們想指向set裡第k小的元素這樣是不行的 ```cpp= auto iter = s1.begin() + k; //OAO ``` 要這樣 ```cpp= auto iter = s1.begin(); for(int i = 0; i < k; i++) iter++; ``` ---- ### 其他迭代器不能加法，那可以減法嗎? :::spoiler 天底下哪有這麼好的事 {有人|我}還真的在比賽中試圖這麼做想當然耳{他|我}失敗了 ::: ```cpp= // value 是第幾小? auto iter = s1.lower_bound(value); cout << (iter - s1.begin()) << "\n"; // error: no match for 'operator-' ``` ---- ## std::map ---- 直翻是映射 map裡面裝很多組 (key, value) 所有key滿足前面set的性質效果類似一個索引值任意的萬能陣列在內部每一組(key, value)以一個 `std::pair` 儲存 ---- <image src="https://i.imgur.com/a3tPode.png" height=500px></image> ---- ### 宣告角括號指定key和value的型別 ```cpp= map<int, string> m1; //從整數映射到字串 ``` ---- ### 操作插入一個pair，$\mathcal{O}(\log (size))$ p.first當key，p.second當value 假如key已經存在，什麼事都沒發生 ```cpp= m1.insert(p); //p is of type std::pair ``` 移除一個key(和他對應的value)，$\mathcal{O}(\log (size))$ ```cpp= m1.erase(key); ``` 假如沒這個key給你刪，什麼都不會發生 ---- ### 操作中括號可以用key找他對應的value，$\mathcal{O}(\log (size))$ ```cpp= m1.insert(make_pair(key1, value1)); cout << m1[key1] << "\n"; // value1 ``` 假如戳一個不存在的key，會自動建立一個新的因此insert也可以不用這麼麻煩 ```cpp= m1.insert(make_pair(key2, value2)); m1[key2] = value2; //一樣意思，常用 ``` ---- ### 操作檢查一個key是否存在，$\mathcal{O}(\log (size))$ ```cpp= m1.count(key) ``` ---- ### 操作回傳目前容器裡有幾組(key, value)，$\mathcal{O}(1)$ ```cpp= m1.size() ``` 回傳目前容器是否為空，$\mathcal{O}(1)$ ```cpp= m1.empty() ``` 清空容器，$\mathcal{O}(size)$ ```cpp= m1.clear(); ``` ---- ### 操作取得頭尾迭代器，$\mathcal{O}(1))$ ```cpp= m1.begin() m1.end() ``` ---- ### 操作用key尋找一對(key, value)，$\mathcal{O}(\log (size))$ 假如找到了，回傳指向那個元素的迭代器假如沒找到，回傳 `m1.end()` ```cpp= m1.find(key) ``` 也可以用迭代器刪除元素，$\mathcal{O}(1)$ ```cpp= m1.erase(iter); ``` ```cpp= m1.erase(key); //這兩行 m1.erase(find(key)); //效果相同 ``` 假如你去erase一個指向虛無的迭代器，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作跟set一樣有`lower_bound`、`upper_bound` 但是幾乎沒用過反正set有什麼功能同樣的事情基本上也可以用在map的key上面 ---- ### 其他 map的迭代器規則跟set[一模一樣](#/10/10) \_( \_-w-)\_ --- ## std::multiset ## std::multimap ---- 可以容納重複元素的set/map multiset有用 multimap從來沒用過所以不理他 ---- multiset大部分用法跟正常set一模一樣唯一要注意的是erase會把所有一樣的值刪光光只刪一個的話請用find ```cpp= multiset<int> ms; //... ms.erase(value); //erase all 'value' ms.erase(ms.find(value)); //erase one 'value' ``` ---- 剩下的自己看[前面](#/10)吧 --- ## std::bitset ---- 幾乎等同一個bool陣列不太像STL，無家可歸所以在這裡一起寫 ---- 正常的bool理論上只需要1個位元但是記憶體以 8位元 = 1 byte 為單位所以正常的bool佔1 byte浪費了其他7倍的空間 bitset除了壓縮空間以外還可以一次對很多位元做相同的操作因此執行速度也比陣列快幾十倍 ---- ### 宣告角括號裡是一個整數，代表陣列大小 (單位: 位元) 之後就不能再改大小了 ```cpp= std::bitset<64> bs; //64 bits ``` ---- ### 操作中括號用法跟陣列一樣，$\mathcal{O}(1)$ ```cpp= bs[63] = 1; ``` 假如戳到bitset外面，{**++↑不↑↓可↓↑預↑↓期↓++**|未定義行為} ---- ### 操作各種你想得到的位元運算包括 `&`、`|`、`^`、`~`、`<<`、`>>` `&=`、`|=`、`^=`、`>>=`、`<<=` 複雜度是 $\mathcal{O}(\dfrac{size}{B})$ B通常估個30~60左右 ---- ### 操作還有其他運算 `==`、`!=` 輸入的`cin >> bs`、輸出的`cout << bs` ---- ### 操作整個bitset全部設成0，可能是 $\mathcal{O}(\dfrac{size}{B})$ ```cpp= bs.reset(); ``` 算算看有多少個bit是1，可能是 $\mathcal{O}(\dfrac{size}{B})$ ```cpp= bs.count() ``` 根據實測count比reset稍微慢一些 --- ## 迭代器 iterator ---- 迭代器聽起來超炫炮基本上就只是一個弱化的指標容器可能會有奇怪的結構也不給你偷看裡面長怎樣，此時迭代器幫你存取容器裡的資料 ---- 每一種容器有各自的迭代器名字都是 `容器型別::iterator` 例如 ```cpp= map<int, int>::iterator it; ``` 不想打字的我們更常用`auto`順便給初始值 ```cpp= auto it = m1.begin(); //must give a value with 'auto' ``` ---- 你可以(經常)對迭代器做的事有 1. `it--` 把迭代器往前移一格 2. `it++` 把迭代器往後移一格 3. `*it` 把it指向的東西抓出來 4. `it1 == it2`、`it1 != it2` 檢查兩個迭代器是不是指向同一個咚咚 ---- ### 情境(1): 把map裡面的東西輸出前面提到map中存的是(key, value)的pair 所以map的迭代器指向的就是這個pair `it->first`等同於`(*it).first`是key `it->second`等同於`(*it).second`是value ```cpp= map<int, int> mp; //... auto it = mp.begin(); while(it != mp.end()){ cout << "(" << it->first << "," << it->second << ")\n"; it++; } ``` 不需要知道map裡面長怎樣，一路`++`過去就好了! ---- ### 情境(2): 把整個vector排序 [內建的`std::sort`](https://hackmd.io/@nehs-iced-7th/rk7moqETd#/4/5)可以把\[l,r)區間排序正好\[begin, end)就是整個vector，所以 ```cpp= vector<int> v; //... sort(v.begin(), v.end()); ``` ---- ### 情境(3): 把set中，小於k的最大的值刪掉還記得lower_bound指向>=k的第一個數字嗎? ```cpp= set<int> st; //... auto it=st.lower_bound(k); if(it==st.begin()){ //all >= k }else{ st.erase(prev(it,1)); } ``` `prev(it, n)`回傳it前面第n個迭代器類似地`next(it, n)`是往後數第n個 ---- ### 情境(4): 輸出multiset中第一個比k大的數字不用解釋了吧 ```cpp= multiset<int> ms; //... cout << *ms.upper_bound(k) << "\n"; ``` ---- 就這樣迭代器在競賽中的使用很單純他就是一個封裝好的指標，幫你忽略容器的結構，專心對付資料本身 ---- 現在可以解釋for auto了... ```cpp= set<int> st; //(1) for(auto i:st){ //... } //(2) auto it = st.begin(); for(; it != st.end(); it++){ auto i = *it; //... } ``` 兩種寫法是完全一樣的也就是讓`i`跑過st裡的每個元素 --- ## 以上 ---- STL博大精深這裡只寫出競賽常用的一小部分 ---- 第一次嘗試把這些語法的東西寫下來可能摻雜了太多太冷僻的內容假如看不懂就自己做實驗或直接跳過吧語法進步總是靠觀摩實作堆起來的多寫，多試，多查多看別人寫的程式都會比看十次我的講義還有用 ---- 最重要的 > 常用的自然會記起來 > 不常用的記了也沒用