# STL ---- [偷](https://slides.com/wenian/basic-stl/) --- # 什麼是STL [你很會看cpp reference](https://cppreference.com/) ---- ## Standard Template Library - Algorithm/Container/Function/Iterator - 如果你不是怪人(你用bits/stdc++.h)正常可以直接用 --- # 結構類 ---- ## 資料結構 - 裝一坨東西 - 有一坨好性質 - 支援一坨操作 - STL幫你寫好一堆 --- # `pair` 你懶得寫兩個屬性的`struct`可以用 ---- ```cpp pair<int[8], string> some_pair = { {1, 1, 4, 5, 1, 4, 8, 1}, "TOI" }; // 或make_pair({1, 1, 4, 5, 1, 4, 8, 1}, "TOI") int iio_koio[8] = some_pair.first; string TOI = some_pair.second; ``` 喔然後某些人會`#define fs first`和`#define sc second` --- # 串列 ---- # `list` 誰愛用誰用，我不愛用 ---- # `array` ~~好好用C array不行嗎~~ 有iterator的C array ```cpp array<int, 8> idk; ``` ---- # `vector` 超酷的陣列 ```cpp vector<int> yjsp(24, 114514); // 放滿24個114514 // 114514不填他會幫你放滿預設值 vector<int> ahhhhhh = {1, 9, 1, 9, 8, 1, 0}; vector<int> idk(yjsp.begin() + (1 - 1 + 4 - 5 + 1 + 4), yjsp.end() - 5); // . . . .[. . . . . . . . . . . . . . .]. . . . . // ^yjsp.begin() yjsp.end()^ assert(ahhhhhh[4] == 8); assert(yjsp.size() == 24); // 丟掉最後一個 O(1) ahhhhhh.pop_back(); // 1, 9, 1, 9, 8, 1 // 塞到最後一個 O(1) ahhhhhh.push_back(114514); // 1, 9, 1, 9, 8, 1, 114514 // 塞在中間是O(n)(包含前面)，除非你知道你在幹嘛 // 不是很常用 // 第一個參數填塞在哪個位置 ahhhhhh.insert(ahhhhhh.begin() + 1, 14514); // 1, 14514, 9, 1, 9, 8, 1, 114514 auto it_a = ahhhhhh.begin(); // O(1)，正常+-也是 it_a += 2; // O(1) assert(*it_a == 9); ahhhhhh.erase(it_a); // 1, 14514, 1, 9, 8, 1, 114514 auto it_b = yjsp.begin() + 16; auto it_c = yjsp.begin() + 9; assert(it_b > it_c); assert(it_b - it_c == 7); ``` ---- # `stack` 想像一坨東西疊起來然後你在上面做事 有人說`vector`常數比較小，隨便啦，都可以用 ```cpp stack<int, vector<int>> _better_const; stack<string> deck; // 疊東西上去 O(1) deck.push("Club 3"); deck.push("Diamond 5"); // ♣3 [♦5] // 看最上面是啥 O(1) assert(deck.top() == "Diamond 5") // 中間懶得寫，而且佔版面 // 假設現在牌堆像下面這樣 // ♣3 ♦5 ♣7 ♥J ♦A ♥A [♠2] // 看牌堆有多少張牌 O(1) assert(deck.size() == 7); assert(deck.top() == "Spade 2"); // 丟掉最上面的東西 O(1) deck.pop(); // ♣3 ♦5 ♣7 ♥J ♦A [♥A] assert(deck.top() == "Heart A"); ``` ---- # `queue` 想像一坨人在排隊 ```cpp // 假設早餐部只會排一條(真實情況通常會排兩條) queue<int> zao_can_bu; // 加一個人進來排隊 O(1) zao_can_bu.push(11200567); zao_can_bu.push(11300765); zao_can_bu.push(11400514); // 看隊伍多長 O(1) assert(zao_can_bu.size() == 3); // 假設現在早餐部排滿了人但還沒開門 // [11200567] 11300765 11400514 11200312 11400114 11300255 (真實情況後面會更多人) assert(zao_can_bu.size() == 7); // 看隊伍最前面是誰 O(1) assert(zao_can_bu.front() == 11200567); // 11200567終於排到了 O(1) zao_can_bu.pop(); // [11300765] 11400514 11200312 11400114 11300255 ``` ---- # `deque` 雙端佇列 你可以想成 痾 只有一個人能過的隧道？ 反正我懶得打扣了 支援從前面和後面$O(1)$拿東西和放東西 還有$O(1)$看`size` [cpp&](https://cppreference.com/w/cpp/container/deque.html) update: 我重看之後發現可以$O(1)$隨機存取(直接當陣列用)，也太好 update:  ---- # `bitset` 比較快的`bool[]`? ```cpp bitset<17> wow = 0b11011111101010010; // O(1) assert(wow[0] == false); ``` 可以做位元運算 ---- 打完上面那坨才發現忘記放了 很多東西後面都能加`.empty()`檢查是不是空的 ~~雖然我都用`!something.size()`~~ --- # Iterator 指向某個位置會用到 可以想成容器裡面的指標 大部分東西都會提供`begin`和`end` ---- # 還記得箭頭嗎 ```cpp vector<pair<int, int>> points = {{1, 2}, {-4, 3}}; auto it = points.begin(); int first_x = it->first; // 1 ``` ---- [是酷語法我們有救了](https://cppreference.com/w/cpp/language/range-for.html) --- # 這裡要放什麼啊 不會下標題 ---- # `priority_queue` 酷酷的東西 ```cpp priority_queue<int> a; a.push(1); a.push(1); a.push(4); a.push(5); a.push(1); a.push(4); // O(1) // 猜猜這會輸出什麼？ cout << a.top(); // O(log n) a.pop(); ``` 你懶得`sort`後面一坨東西的話可以拿這個來排序 ---- # `map` 不是地圖 把一個東西打到一個東西 有`multimap`把一個東西打到一堆東西但基本沒用過 排版好像燒雞了所以我扣丟下一頁 ---- ```cpp map<int, string> name; // O(log n * cmp) name[11400514] = "田所浩二"; // 或name.insert(11400514, "田所浩二"); // 看有多少人 O(1) assert(name.size() == 1); // O(log n)，可以++和--(理論上都是O(log n)) auto it = name.find(11400514); assert(*it == make_pair(11400514, "田所浩二")); // 讀不到會跑出end assert(name.find(12345678) == name.end()); // O(log n) name.erase(it); assert(name.find(11400514) == name.end()); assert(name[11400514] == ""); // default value ``` 喔然後還有`lower_bound`和`upper_bound`，我等下講到`set`和`multiset`的時候一起講 ---- # `set`、`multiset` 你很會數學 ```cpp set<int> primes; // O(log n) primes.insert(2); primes.insert(3); primes.insert(5); primes.insert(7); primes.insert(9); cout << "該死，放錯了"; // O(log n)，一樣可以++或--(O(log n)) auto it = primes.find(9); primes.erase(it); primes.insert(10); cout << "又放錯了"; primes.erase(10); // O(log n) primes.insert({12, 14, 16, 18, 20}); cout << "誰當偶數集放了"; it = primes.lower_bound(12); primes.erase(it, primes.end()); // it後面的全部丟掉 ``` 然後`multiset`一樣的東西可以放很多個 ---- # `unordered_*` 上面從map開始的東西都可以放在`*` 基本上所有操作都變成`O(1)`，沒有iterator、`lower_bound`、`upper_bound` 但常數很大，建議別用 --- # 程序類 --- # 數學 不會數學，被嗆 ---- # `min`、`max` ~~不會用`if`喔~~ 字面上意思 反正我覺得寫起來比較好看 超過兩個可以塞`{}`裡面 ---- # `gcd` 好東西  ---- # `__gcd` 編譯器內部實作用到的，正常來說你不會碰到這個，可是湊著用還不錯 大部分情況下可能都是用這個 但是如果你用到怪編譯器... ---- # 隨堂考試 請利用基礎語法課程習得的知識寫出一個能利用輾轉相除法算出兩數最大公因數的函式。 聽說是$O(\log\min(a, b))$，但我不會證 --- # `vector`操作 ---- # `reverse`、`sort` 字面上意思 `reverse`是$O(n)$，`sort`是$O(n \log n)$ 有`stable_sort`保證比較次數(和原本順序(根據定義)) 都是放一個範圍的iterator，成功嗆到C array `sort`可以自訂比較函式 ```cpp array<pair<int, int>, 5> points = {{114, 514}, {1919, 810}, {-4, 3}, {8, 7}, {0, 0}}; sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b){ return a.first * a.first + a.second * a.second < b.first * b.first + b.second * b.second; }); // (0, 0), (-4, 3), (8, 7), (114, 514), (1919, 810) ``` ---- ## `lower_bound`、`upper_bound` 記得排序 $[lower, upper)$會是你指定的值出現的範圍 $O(\log n)$ ```cpp vector<int> a = {1, 1, 1, 4, 4, 5}; // ^ auto l = lower_bound(a.begin(), a.end(), 4); assert(l - a.begin() == 3); // ^ auto r = upper_bound(a.begin(), a.end(), 4); assert(r - a.begin() == 5); ``` 之後講到二分搜可能會再說 ---- # `unique` 為什麼不用`set`😡 [cpp&](https://en.cppreference.com/w/cpp/algorithm/unique.html) ----  [cpp&](https://en.cppreference.com/w/cpp/algorithm/next_permutation.html) 窮舉很好用 --- # 快樂寫題時間 ---- 偷上一份的題 ---- # CSetES 排序或是可以用pq做的太常見了我懶得找 [Distinct Numbers](https://cses.fi/problemset/task/1621) [Concert Tickets](https://cses.fi/problemset/task/1091) [Traffic Lights](https://cses.fi/problemset/task/1163) 誰要寫traffic lights，不如寫 ---- # [顏子喬出的大好題](https://ojdl.ck.tp.edu.tw/contest/32/problem/F) ~~真的喔~~ 反正你會寫traffic lights你就會寫這題