完整STL - HackMD

# 完整STL `第10週社課` ## 先備知識不懂的請一定要問(~~  結果真的變成訓練自學能力了QQ  ~~) 指標的取值：http://kaiching.org/pydoing/cpp-guide/unit-4-pointer-and-reference.html ### 隨機存取如果一個資料結構可以直接取第幾項的值，則稱它為可隨機存取(random access)，例如陣列，要取第幾項都可以。否則它就是循序存取(sequential access)，對於目前所在的那一項，只能移動到與它相鄰的那一項。 ## 目錄點擊可以直接跳到該項目 * <a href="##關於上次的補充" style="color: black; ">關於上次的補充</a> * <a href="##stack" style="color: black; ">stack</a> * <a href="##queue" style="color: black; ">queue</a> * <a href="##deque" style="color: black; ">deque</a> * <a href="##priority-queue" style="color: black; ">priority queue</a> * <a href="##set" style="color: black; ">set</a> * <a href="##multiset" style="color: black; ">multiset</a> * <a href="##map" style="color: black; ">map</a> * <a href="##multimap" style="color: black; ">multimap</a> * <a href="##bitset" style="color: black; ">bitset</a> * <a href="##iterator" style="color: black; ">iterator</a> ## 關於上次的補充 ### push_back 如果你想要push_back一個pair到vector中，千萬不要這樣做： ```cpp vector<pair<int, int>> v; v.pb(1,2); // 編譯錯誤 ``` 你應該： ```cpp vector<pair<int, int>> v; v.pb({1,2}); // 方法1 v.pb(make_pair(1,2)); // 方法2 ``` 因為make_pair函式會自動把int轉成long long、float轉成double(由編譯器判斷變數類型)，就可能導致程式出錯，所以我們通常都是用大括號的寫法(對tuple一樣有用)，而且也比較方便。 ### size() 觀察以下程式的輸出： ```cpp #include <bits/stdc++.h> using namespace std; int main() { vector<int> v; cout << v.size() << endl; cout << v.size() -1 << endl; } ``` 為什麼不是輸出-1呢？因為v.size()的回傳值型態是unsigned int！(對所有STL資料結構都一樣) 所以減一會造成溢位！！ ## stack ### 功能堆疊，就像堆盤子一樣，從上方放盤子，取盤子也是從上方取，因此後放的盤子會在先放的盤子的上面，具有後進先出的性質(LIFO,Last in First Out)。 ### 宣告 ``` stack<type> St; ``` type : 內容物型別 St : stack名稱 ### 使用 ```cpp // 取得頂端元素 St.top() // 加入元素到頂端 St.push(x); // 刪除頂端元素 St.pop(); // 取得大小(元素個數) St.size() // 回傳是否為空(bool) St.empty() ``` ### 迴圈遍歷基本上沒有，只能邊取值邊刪值 ```cpp while(!St.empty()){ cout << St.top() << " "; St.pop(); } ``` 因為永遠只能知道頂端的元素，因此為不可隨機存取 ### 例題 * <a href="https://zerojudge.tw/ShowProblem?problemid=c123">ZJ c123</a> * <a href="https://zerojudge.tw/ShowProblem?problemid=a565">ZJ a565</a> * <a href="https://zerojudge.tw/ShowProblem?problemid=a813">ZJ a813</a> * <a href="https://codeforces.com/problemset/problem/1428/C">CF 1428C</a> ## queue ### 功能佇列(隊列)，就像排隊一樣，先排的人先出去，具有先進先出的性質(FIFO,First in First Out)。實際上來說，就是先塞入的數值會先被取出(使用)。 ### 宣告 ``` queue<type> Q; ``` type : 內容物型別 Q : queue名稱 ### 使用 ```cpp // 取得前端元素 Q.front() // 從後方加入元素 Q.push(x); // 刪除前端元素 Q.pop(); // 取得大小(元素個數) Q.size() // 回傳是否為空(bool) Q.empty() ``` ### 迴圈遍歷基本上沒有，只能邊取值邊刪值 ```cpp while(!Q.empty()){ cout << Q.front() << " "; Q.pop(); } ``` 因為永遠只能知道前端的元素，因此為不可隨機存取 ### 例題 * <a href="https://zerojudge.tw/ShowProblem?problemid=c249">ZJ c249</a> * <a href="https://zerojudge.tw/ShowProblem?problemid=e447">ZJ e447</a> ## deque ### 功能雙端佇列(double-ended queue)，就是能夠從兩邊推入數值與取值的queue(以取名來說是這樣，但功能不只如此)，實際能做到的是是雙向vector(可隨機存取)，差別：如果從vector前方加入數值，會需要$O(n)$的操作，但deque是$O(1)$。 ### 宣告 ``` deque<type> dq; ``` type : 內容物型別 dq : deque名稱 ### 使用 ```cpp // 取得前端元素 dq.front() // 從前方加入元素 dq.push_front(x); // 刪除前端元素 dq.pop_front(); // 取得後端元素 dq.back() // 從後方加入元素 dq.push_back(x); // 刪除後端元素 dq.pop_back(); // 取得大小(元素個數) dq.size() // 回傳是否為空(bool) dq.empty() // 清除整個deque dq.clear(); // 在deque中索引值為i的值(用法同一般陣列) dq[i] ``` 基本上vector有的函式deque都有，可以直接把它看成是功能更多的vector(但相對占用記憶體較大) ### 迴圈遍歷如vector，不在此贅述 ## priority queue ### 功能優先佇列，就是能夠維持最大(小)值的堆(heap)，每次取出(讀取)的值都是整個堆中的最大(小)值，和queue, stack不同，為了維護最大(小)值，插入和刪除操作都需要$O(\log n)$的時間，$n$為priority queue的大小。 ### 宣告 ``` priority_queue<type, con, cmp> pq; ``` type : 內容物型別 pq : priority queue名稱 con : 實作的容器種類，通常填入vector<type> cmp : 比較函式，跟sort函數一樣可以自定義 ### 使用 ```cpp // 取得大小(元素個數) pq.size() // O(1) // 取得最大(小)的元素 pq.top() // O(1) // 插入元素 pq.push(x); // O(log n) // 刪除最大(小)的元素 pq.pop(); // O(log n) ``` 如果忘記取出的順序，可以現場實驗 ```cpp // 優先取出最大值 priority_queue<int, vector<int>, less<int> > pq1; // 優先取出最小值 priority_queue<int, vector<int>, greater<int> > pq2; ``` ### 自定義cmp 這段程式的cmp函式會先把first由小到大排，然後再把second由大到小排。 ```cpp #include <bits/stdc++.h> #define loop(i,a,b) for(int i=a;i<b;i++) #define pii pair<int,int> #define ff first #define ss second #define pb push_back #define debug cout << "test\n"; using namespace std; struct cmp{ bool operator()(const pii &a, const pii &b){ return (a.ff > b.ff) || (a.ff > b.ff && a.ss < b.ss); } }; int main(){ int n; pii tmp; cin >> n; priority_queue<pii, vector<pii>, cmp> pq; loop(i,0,n){ cin >> tmp.ff >> tmp.ss; pq.push(tmp); } loop(i,0,n){ cout << pq.top().ff << "," << pq.top().ss << endl; pq.pop(); } } ``` ### 迴圈遍歷基本上沒有，只能邊取值邊刪值 ```cpp while(!pq.empty()){ cout << pq.top() << " "; pq.pop(); } ``` ### 例題 * <a href="https://zerojudge.tw/ShowProblem?problemid=b606">ZJ b606</a> * <a href="https://zerojudge.tw/ShowProblem?problemid=d221">ZJ d221(同一題)</a> ## set C++以紅黑樹(有興趣可以自己去查)實作 ### 功能顧名思義，用來維護一個元素是否出現過，因此保證同一個元素不會重複出現，插入元素與查詢元素的複雜度都是$O(\log n)$，$n$為set的大小。 ### 宣告 ``` set<type> S; ``` type : 內容物型別 S : set名稱 ### 使用 ```cpp // 取得元素x的指標，若不存在則返回S.end() S.find(x); // O(log n) // 加入元素x S.insert(x); // O(log n) // 回傳是否為空(bool) S.empty() // O(1) // 清除整個set S.clear(); // O(n) // 取得大小(元素個數) S.size() // O(1) // 回傳set中出現x的次數(只會是0或1) S.count(x) // O(log n) // 刪掉該指標指向的位置的值 S.erase(set<type>::iterator itr); // O(1) // 刪掉一個元素 S.erase(x); // O(log n) // 刪掉介於區間[first, last)的元素(O(distance(first, last))) S.erase(set<type>::iterator first, set<type>::iterator last); // 回傳set中第一個大於等於x的元素的指標，如果沒有則回傳S.end() S.lower_bound(x) // O(log n) // 回傳set中第一個大於x的元素的指標，如果沒有則回傳S.end() S.uppper_bound(x) // O(log n) ``` lower_bound和upper_bound函數會在之後有更深入的介紹 ### 迴圈遍歷 #### STL 正向(必由小到大) ```cpp for (auto i = S.begin(); i != S.end(); i++) { cout << *i << " "; } ``` 反向(必由大到小) ```cpp for (auto i = S.rbegin(); i != S.rend(); i++) { cout << *i << " "; } ``` #### auto 由小到大 ```cpp for (auto &i : S) { cout << i << " "; } ``` ## multiset ### 功能可以有多個元素重複的set，通常用來當作是插入、刪除後仍然維持排序的資料結構。 ### 宣告 ``` multiset<type> ms; ``` type : 內容物型別 ms : multiset名稱 ### 使用大部分的功能和set相同，但有一些差別： ```cpp // 取得「其中一個」元素x的指標，若不存在則返回S.end() ms.find(x); // 刪掉「所有」元素x ms.erase(x); // 刪掉該指標指向的位置的值 ms.erase(set<type>::iterator itr); // O(1) // 回傳multiset中出現x的次數 ms.count(x) ``` 如果只想刪掉其中一個元素x，可以這樣寫： ```cpp auto it = ms.find(x); if(it != ms.end()) ms.erase(it); ``` ### 迴圈遍歷同set，不再贅述 ## map C++以紅黑樹實作，內部以pair來儲存鍵值(key)與資料(value)，實際上只是一種特殊的set，以pair的第一項來進行搜尋。 ### 功能類似python 的dict，可以想像成一個單映射函數，也就是一個鍵值(key)對應一個資料(value)，因此鍵值絕不重複改值、取值都是$O(\log n)$時間，$n$是map的大小。 ### 宣告 ``` map<type1, type2> mp; ``` type1 : 鍵值型別 type2 : 對應到的資料型別 mp : map名稱 ### 使用 ```cpp // 使x(type1)對應到y(type2) mp[x] = y; // 取得x對應到的值，如果原本不存在對應值就把它設為0 mp[x] // 刪除x和其對應的值(y) mp.erase(x); // 清空整個map mp.clear(); // 回傳鍵值的指標，如果鍵值x不存在，則回傳mp.end()，可用來判斷一個鍵值是否存在對應值 auto it = mp.find(x); if(it == mp.end()) cout << "There is no value corresponded by key " << x << ".\n"; else cout << "mp[" << x << "] is " << it->second; ``` 註：<code>it->second</code> 相當於 <code>(*it).second</code> ### 迴圈遍歷依序遍歷到的值必定是鍵值由小到大，且型別是pair<type1, type2> ```cpp for(auto &i:st){ cout << i << "\n"; } ``` 或是 ```cpp for(auto i = st.begin(); i != st.end(); i++){ cout << *i << "\n"; } ``` ## multimap C++以紅黑樹實作 ### 功能類似python 的set ### 宣告 ``` multimap<type1, type2> mp; ``` type12 : 內容物型別 mp : multimap名稱 ### 使用因為multimap支援一對多的功能，因此它不存在用<code>[]</code>取值、改值的功能。 ```cpp // 刪除x和其所有的對應的值(y) ms.erase(x); // 刪掉該指標指向的位置的值 ms.erase(multimap<type>::iterator itr); // 清空整個map ms.clear(); // 回傳鍵值的指標，如果鍵值x不存在，則回傳ms.end()，可用來判斷一個鍵值是否存在對應值 auto it = ms.find(x); if(it == ms.end()) cout << "There is no value corresponded by key " << x << ".\n"; else cout << "ms[" << x << "] is " << it->second; // 回傳multimap中出現鍵值x的次數 ms.count(x) ``` ## bitset 同vector<bool>一樣有位元儲存的性質，但是整體常數更佳，而且多神奇的功能。缺點：初始化時不可以用變數設定它的大小 ```cpp const int N = 50; // declare bitset<N> bs, a, b, c; // set value bs = 10; // 0101000...0000 bs[10] = 1; bs[3] = 0; cout << bs.to_string(); cout << bs.to_ullong(); a = 10, b = 25; c = a + b; cout << c.to_ullong(); ``` 小技巧：可以直接拿來輸出變數的二進位表示值 ```cpp int x = -1; bitset<32> bs1(x); cout << bs1 << "\n"; float y = 0.3; bitset<32> bs2(*(int*)&y); cout << bs2 << "\n"; ``` ## iterator 迭代器，是指標的一種，指向的位置有你的元素，很像傳統的指標陣列的指標，有著非常廣泛的用途，有待讀者自行使用發現有分以下幾種iterator 1. 隨機存取迭代器:支援+,-,++,-- (vector, deque) 2. 循序存取迭代器:支援++,-- (set, map) ```cpp vector<int> a(20); int b[20]; vector<int>::iterator itr = a.begin() + 7; for (int i = 0; i < 20; ++i) a[i] = b[i] = i; cout << *(++itr) << *(b + 8); ```