# STL introduction By Yu-Chi Lai <style> code { color: #C4D9FF } </style> ---- ## STL + Standard Template Library (標準樣板函式庫) + 兩種類型 + Container (容器) + Algorithm (演算法) + 很實用 --- ## Prior Knowledge 仙貝知識 ---- ### 複習: Pointer 指標 + 指向變數的位址 + ptr++, ptr-\- 都是合法的 + NULL / nullptr 不指向任何一塊有效的記憶體位址 + \* 取值、& 取址 + 複習可以看之前的[簡報](https://hackmd.io/@richardlaiis/CSTutorForNTUCSIE)，或許我有介紹(?) ---- ### 樣板 template 撰寫 library 時要怎麼應對多個型別? template/generic 可以解讀成 compiler 做的複製貼上! ```cpp= #include <iostream> #include <string> using namespace std; template <typename T> T add(T a, T b) { return a + b; } int main() { cout << add<int>(5, 7) << endl; cout << add<double>(3.14, 7.99) << endl; cout << add<string>("Hello", "World!!!!!") << endl; } ``` ---- ### 迭代器 iterator 具有指標的特性 (例如 `*v.begin()` 可以取第 0 項的值)，可以用來遍歷 container 裡面的所有元素 ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, i; vector<int> v; while (cin >> n) { v.resize(n); for (i=0; i<n; i++) { cin >> v[i]; } sort(v.begin(), v.end()); for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it) { cout << *it << "\n"; } } return 0; } ``` ---- ### 型別自動判別 auto iterator 的宣告太長了... ```cpp= vector<int> v; for (auto it=v.begin(); it!=v.end(); ++it) { // ... } ``` ```cpp= for (auto i:v) { cout << i << endl; } ``` ----  ---- ### 萬用標頭檔 ```cpp= #include <bits/stdc++.h> ``` 記住他 --- ## vector ~~向量~~ 比較好用的陣列 ---- ```cpp= #include <vector> #include <algorithm> // 排序 ``` ---- ### 宣告 ```cpp= vector<int> v; vector<char> v(n); v.resize(n) // 宣告完 vector 後才能用 vector<int> v(n, 10) // 長度為 n，初始值為 10 的陣列 ``` ---- ### 加入/刪除元素 ```cpp= vector<int> v; v.push_back(10); v.emplace_back(45); ``` 兩個函式沒有差別，後者稍快一點 ```cpp= v.pop_back(); // 刪除最後一項元素 ``` ---- ### 取得大小 ```cpp= cout << v.size() << endl; // v 目前有幾項 if(v.empty()) cout << "v is empty!!!\n"; // 判斷 v 是否為空 ``` ---- ### 排序 ```cpp= int arr[] = {2, 1, 3, 8, -15}; vector<int> v = {2, 1, 3, 8, -15}; sort(v.begin(), v.end()); sort(arr, arr+5); ``` sort 裡面放的是 pointer/iterator 排序的詳細用法請看[這裡](https://emanlaicepsa.github.io/2020/11/16/0-13/) ---- ### 找出最小元素 ```cpp= vector<int> v = {2, 1, 3, 8, -15}; cout << *min_element(v.begin(), v.end()) << '\n'; cout << min_element(v.begin(), v.end()) - v.begin() << '\n'; ``` 如果沒有加 `*`，`min_element` 回傳的是**位址** ---- ### 反轉 ```cpp= vector<int> v = {2, 1, 3, 8, -15}; reverse(v.begin(), v.end()); ``` `reverse` 裡面放的參數是一段區間 (pointer/iterator) ---- ### 練習題 + [a915.二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915) + [TOJ.vector練習](https://toj.tfcis.org/oj/pro/575/) + 任何陣列能做的題目 --- ## pair 對 ---- ### struct 可以用 struct 實作 ```cpp= struct Point { int x; int y; }; Point a; a.x = 5; a.y = 4; ``` ---- ### Usage ```cpp= pair<int, int> p; pair<int, int> pi[10]; pair<int, vector<int>> pii; pair<pair<int, int>, pair<int, vector<int>>> wtf; ``` ```cpp= cout << p.first << p.second << endl; ``` ---- ### Usage ```cpp= pair<int, int> p; // p = 5, 4 WRONG p = make_pair(5, 4); p = {8, 9}; cout << p.first << " " << p.second << "\n"; ``` note\: 不能直接輸出一個 pair ---- ### Sorting ```cpp= vector<pair<int, int>> v; .... sort(v.begin(), v.end()); for(int it:v) { cout << it.first << " " << it.second << endl; } ``` 排序 pair 的規則是先排 first，再比 second ---- ### 比較函式 ```cpp= bool cmp(int a, int b) { return a > b; } sort(arr, arr+n, cmp); // 由大排到小 ``` ```cpp= bool cmp(pair<int, int> a, pair<int, int> b) { if(a.first != b.first) return a.first > b.first; else return (a.first+b.first) > (a.second+b.second); } pair<int, int> arr[n]; sort(arr, arr+n, cmp); ``` 利用比較函式，我們可以自訂排序的條件。 --- ## queue / deque 佇列/雙向佇列 ---- ### Queue + FIFO (First in first out) + 不能隨機存取 ---- ### Usage ```cpp= #include <queue> ``` ```cpp= queue<int> q; q.push(5); q.push(3); q.push(4); q.pop(); // 5 is poped out cout << q.front() << endl; // 3 int n = q.size(); bool flag = q.empty() ``` ---- ### Deque + 有沒有一個可以從前面、從後面都能插入元素的資結? + 有! 甚至還支援 random access + 缺點是超慢，比 vector 慢三倍 ---- ### Usage ```cpp= deque<int> dq; dq.push_back(77); dq.push_front(6); dq.push_back(4); dq.pop_back(); dq.pop_front(); ``` 但沒事不要用到 ---- ### 練習題 + [ZJ.e155](https://zerojudge.tw/ShowProblem?problemid=e155) + [ZJ.a565](https://zerojudge.tw/ShowProblem?problemid=a565) --- ## stack 堆疊 (FILO) ---- ### Usage ```cpp= #include <stack> ... stack<int> stk; stk.push(1); stk.push(3); stk.pop(); cout << stk.top(); ``` 就...這樣 ---- ### 練習題 + LeetCode #155 + LeetCode #20 --- ## priority_queue 優先佇列 ---- ### feature + 支援加入元素、查詢最大/小元素、刪除最大/小元素這幾個操作 + 用 [heap](https://medium.com/starbugs/%E4%BE%86%E5%BE%81%E6%9C%8D%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E5%90%A7-%E6%90%9E%E6%87%82-binary-heap-%E7%9A%84%E6%8E%92%E5%BA%8F%E5%8E%9F%E7%90%86-96768ea30d3f) (堆)實作 + 刪除/插入 $O(\log{n})$，查詢 $O(1)$ ---- ### Usage ```cpp= priority_queue<int> pq; pq.push(1); // 插入 cout << pq.top() << '\n'; //查詢最大值 pq.pop(); // 刪除最大值 ``` ```cpp= priority_queue<int, vector<int>, greater<int>> pq; // 資料型態, 容器, 比較函式 // 預設的宣告其實就是: // priority_queue<int, vector<int>, less<int>> pq ``` ---- ### 練習題 + [TIOJ 1161](https://tioj.ck.tp.edu.tw/problems/1161) --- ## set 集合 ---- ### Usage ```cpp= set<int> s; s.insert(5); s.insert(7); s.erase(5); s.erase(s.begin()); // 必定指向最大值 ``` ---- ### Usage ```cpp= if(s.find(3) != s.end()) cout << "3 is in the set!" << endl; else cout << "QwQ" << endl; ``` ```cpp= if(s.count(3)) cout << "3 is in the set!" << endl; ``` ---- ### 練習題 + 輸入 n 個數，問共有幾個**相異**的數? + 試著了解 unordered_set 和 multiset 的語法 + [ZJ b938](https://zerojudge.tw/ShowProblem?problemid=b938) --- ## hash map map / unordered_map 的用法 ---- ### 用途 + 想使用 key 不為整數的陣列 + Dictionary + 插入、刪除、查詢的複雜度皆為 $O(\log(n))$ ---- ### Usage ```cpp= map<string, string> author, publisher; author["Le Petit Prince"] = "Antoine de Saint-Exupéry"; publisher["Le Petit Prince"] = "Gallimard"; cout << author["Le Petit Prince"] << " " << publisher["Le Petit Prince"] << '\n'; ``` ---- ### 新增與指派 ```cpp= map<int, int> mp; mp[5] = 45; ``` 如果 key 不存在，則這就變成了**新增**動作 note\: 你不能針對一個不存在的 key 操作 ---- ### 查詢 ```cpp= cout << mp[5] << '\n'; cout << mp[0] << '\n'; ``` ---- ### 刪除與遍歷 ```cpp= map<int, int> mp; mp[5] = 45; mp[7] = 0; mp.erase(7); // erase specific key and its value cout << mp[0] << '\n'; for(auto i:mp){ cout << i.first << " " << i.second << '\n'; } ``` ---- ### 補充: [hash](https://zh.wikipedia.org/zh-tw/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8) ---- + [ZJ d518](https://zerojudge.tw/ShowProblem?problemid=d518) --- ## [bitset](https://emanlaicepsa.github.io/2020/12/14/0-25/) 優化過的 boolean container --- ### 參考資料 https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FS11uDpiuH