2021 Week2 - C++

--- tags: 成大高階競技程式設計 2021 --- # 2021 Week2 - C++ 註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。 --- 本篇將介紹一些 C++ 的常見用法，尤其是 [STL](#標準模板庫（Standard-Template-Library）) 的部分。 --- # 演算法效率（Algorithmic efficiency） > 演算法與資料結構息息相關，一同影響著時間與空間的效率。 ## 複雜度（computational complexity）競程題目規模通常很大（e.g., $10^5$），我們更在意的是複雜度，而 2 倍、3 倍、甚至 10 倍的常數倍優化通常不是重點。 :::warning **大 O 符號（Big O notation）**： $f(n)=O(g(n)){\;\iff\;}\exists\;k\gt 0,n_0, \forall\,n\ge n_0 {\;\;}s.t.{\;\;}f(n)\le kg(n)$ ::: 意思是說當 $n$ 足夠大時，存在一個正數 $k$，使得 $kg(x)$ 大於 $f(x)$，所以在 $n$ 夠大的情況下，計算所需資源（時間、空間）不會超過 $g(n)$ 的量級。 > 透過一個較簡單的函數 $g(n)$，為 $f(n)$ **提供一個上界**。 :::spoiler 範例假設一個程式碼片段如下， ```cpp! int mx{v[0]}, mn{v[0]}; for (int i{1}; i < n; ++i) if (v[i] > mx) mx = v[i]; for (int i{1}; i < n; ++i) if (v[i] < mn) mn = v[i]; ``` 簡單估計，二個變數宣告加上二個迴圈，則 $f(n)=2+2n=O(n)$。 ::: <br> 常見的複雜度： $O(1){\;\le\;}O(\log{n}){\;\le\;}O(n){\;\le\;}O(n\log{n}){\;\le\;}O(n^k){\;\le\;}O(k^n){\;\le\;}O(n!){\;\le\;}O(n^n)$ > k 為大於 $1$ 的常數 <hr class="dashed"> ## 合理的複雜度 > 無特別強調時，複雜度通常是在說時間複雜度，但空間複雜度一樣需要考慮。 ### 時間複雜度時間限制以秒為單位（e.g., $1$ 秒、$3$ 秒、$10$ 秒），但我們會考慮題目規模與複雜度，估計出一個計算量，通常 $1$ 秒不超過 $10^7$（只是大約的範圍）。 > 假設設計的演算法複雜度為 $O(n\log_2{n})$，而 $n\le10^5$， > 計算量就大約為 $2\times10^6$，足以通過時間限制。 <hr class="dotted"> ### 空間複雜度空間複雜度比較不會有問題，但還是需要確認一下，影響的因素主要就是變數與遞迴深度。 <hr class="dotted"> ### 均攤分析（Amortized Analysis）:bulb: > **Amortized analysis differs from average-case analysis in that probability is not involved; > an amortized analysis guarantees the average performance of each operation in worst case.**[^CLRS] 這邊透過最淺顯易懂，並能具象化表現其概念的記帳法（Accounting method），來分析 [`std::vector`](#stdvector) 的效率。 #### `push_back()` 的行為 > 為了簡化分析，將 `vector` 的操作侷限於 `push_back()`， > 在空間不足時，會將配置的記憶體擴增成兩倍。如果還有剩餘空間，直接把新元素放入尾端；如果沒有剩餘空間，則配置一個兩倍大小的空間，將所有元素移動過去，再將新元素放入尾端。 #### 開始分析 > 令 $n$ 為目前元素個數，每次進行 `push_back()` 後，$n$ 變為 $n+1$。當還有剩餘空間時，操作花費 $3$ 個硬幣，其中花費「$1$ 個硬幣放入新元素」，剩下 $2$ 個硬幣把它儲存在這個位置；等到沒有剩餘空間的時候，這次操作花費 $4$ 個硬幣，先用「$1$ 個硬幣配置新的空間」，接下來可以發現，區間 $[\frac{n}{2}:n)$ 的每個位置都存有 $2$ 個硬幣，總共有 $n$ 個硬幣，這些「預支的硬幣剛好足以移動所有元素」，接著用「$1$ 個硬幣放入新元素」，剩下二個硬幣一樣存起來。每次 `push_back()` 只會花費 $3$ 或 $4$ 個硬幣，所以**均攤成本（amortized cost）為 $O(1)$**。 > 硬幣常用術語應為 credits。 **均攤複雜度不需特別看待，可視為其真實花費。** --- # 基本型態（Fundamental types） * `bool` * 常量（Literal）：`true`, `false` * `char` * 常量（Literal）：`'c'` * `int` * 常量（Literal）：`0` * 範圍：$x\;{\le}\;2^{31}-1{\;\approx\;}2.14{\times}10^{9}$ * `long long` * 常量（Literal）：`0ll`, `0LL` * 範圍：$x{\;\le\;}2^{63}-1{\;\approx\;}9.22{\times}10^{18}$ > `int` 與 `long long` 需要注意整數溢位（integer overflow）的問題。 * `float` * 常量（Literal）：`0.f` * 範圍：共 6 位精確度 * `double` * 常量（Literal）：`0.`, `0.0`, `2e9` ($2\times10^9$) * 範圍：共 15 位精確度 > double 與 float 的精確度取決**整數位數+小數位數**， > 關於浮點數（floating-point number）的更多說明，請參閱 [IEEE 754](https://en.wikipedia.org/wiki/IEEE_754)。 --- # 輸入輸出（Input/Output） ## [`std::cin`](https://en.cppreference.com/w/cpp/io/cin) / [`std::cout`](https://en.cppreference.com/w/cpp/io/cout) C++ 的標準輸入輸出流，不需要型態，會根據變數自動判別。 `cin` 可以轉為 `bool`，用來判斷輸入是否出現狀況，例如遇到 EOF (End-of-file) 等等。 ```cpp! int x; while (std::cin >> x) { // 一直讀取整數直到 EOF std::cout << "cin got " << x << std::endl; } ``` <hr class="dashed"> ## fast I/O [`std::ios_base::sync_with_stdio()` ](https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio) 決定 C++ 的標準輸入輸出流（`std::cin, std::cout, ...`），是否與 C 的標準輸入輸出流（`stdin, stdout, ...`，也就是 `scanf()/printf()`）同步。在**關閉後，不可與 `scanf()/printf()` 混用**。 ```cpp! std::ios_base::sync_with_stdio(false); ``` `cin` 在建構時，會與 `cout` 綁定，也就是 `cin` 在進行讀取前，會呼叫 `cout.flush()`，在競程這是不必要的，還會增加執行時間。 > 輸入輸出頻繁的題目，可能導致 TLE。 ```cpp! std::cin.tie(nullptr); ``` 所以在競程中，我們通常會加上這兩行，提升 `cin/cout` 的效率。 <hr class="dotted"> ## [`std::endl`](https://en.cppreference.com/w/cpp/io/manip/endl) 除了換行還會呼叫 `os.flush();`，**濫用**會導致效能低落；一般使用 `'\n'` 較佳。 <hr class="dotted"> ## [fixed](https://en.cppreference.com/w/cpp/io/manip/fixed) & [setprecision](https://en.cppreference.com/w/cpp/io/manip/setprecision) 透過 `fixed` 與 `setprecision` 可以控制要輸出的小數點位數。 ```cpp! double x{1. / 3.}; os << fixed << setprecision(10) << x << '\n'; // 輸出到小數點下第 10 位 ``` > os 是一個 `std::ostream` 的物件（e.g., `cout`）。 --- # 初始化（Initialization）:bulb: > **Uniform and general initialization using {}-lists**[^TC++PL] C++ 核心指南（C++ Core Guidelines）中也提到 [ES.23:Prefer the {}-initializer syntax](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-list)。 * `T object { arg1, arg2, ... };` * `function({ arg1, arg2, ... });` * `return {arg1, arg2, ... };` 更多用法請參考 [List initialization](https://en.cppreference.com/w/cpp/language/list_initialization)。 --- # 標準函數庫（Standard Library）標準函數庫內的東西均定義在 `std` 這個命名空間（namespace）中， `using namespace std;` 可將所有 `std` 中的東西引入到當前的命名空間，，通常是全域命名空間（global namespace），下方程式片段不再加上 `std::`。除了介紹一些重要的基本概念外，以下內容著重在一些常見的使用方式，完整的內容請讀者自行查看文件。 > 有些內容是 C\+\+14 或 C\+\+17 標準後才推出的，請注意版本上的問題。 > （g++ 編譯參數可使用 `-std=c++17`）推薦的參考網站有 [C++ reference](https://en.cppreference.com/w/)、[cplusplus.com](http://www.cplusplus.com/)。 > 絕大部分涉及區間的操作，區間表示一律為「**左閉右開**」[^INTERVAL]。 <hr class="dashed"> ## [標準模板庫（Standard Template Library](https://en.wikipedia.org/wiki/Standard_Template_Library)）標準模板庫是一個 C++ 的函數庫，透過模板（template）實現泛型編程（[Generic programming](https://en.wikipedia.org/wiki/Generic_programming)），使得一份程式碼能夠與不同型態一起使用，主要由演算法（Algorithms）、容器（Containers）、函數（Functions）、迭代器（Iterators）四個部分組成，並非標準函數庫的一部分。不過它對於標準函數庫影響深遠，現在也已經加入了幾乎一樣的內容，所以此處的 **STL 代指標準函數庫中任何與模板有關的部分**。 <hr class="dashed"> ## 函數（Functions）:bulb: #### [`<functional>`](https://en.cppreference.com/w/cpp/header/functional) > A function object is any **object** for which **the function call operator, operator(), is defined.**[^cppFO] 函數物件（function object）是一個擁有函數呼叫運算子（`operator()`）的物件，可以像函數一樣使用。函數物件的好處： * 雖然函數跟函數物件都有類型，但函數物件的類型可以對應到特定功能的函數物件，而函數的類型只與參數與回傳值的型態有關，所以函數物件透過模板，即可決定特定的功能 * 函數物件本質還是物件，可以攜帶狀態（透過資料成員（member data））競程使用的機率不高，較常用的是 [`std::greater`](https://en.cppreference.com/w/cpp/utility/functional/greater)。 > **範例參見 [`std::priority_queue`](#stdpriority_queue)**。 :::spoiler 自己寫函數物件下方是一個函數物件，回傳第幾次被呼叫。 ```cpp! struct myFunctor { int t{0}; int operator()() { return ++t; } }; ``` ```cpp! myFunctor func1{}, func2{}; for (int i{0}; i < 10; ++i) cout << func1() << ' '; // < 1 2 3 ... 10 cout << func2(); // < 1 ``` ::: <hr class="thin"> ### [匿名函數（Lambda expressions）](https://en.cppreference.com/w/cpp/language/lambda):bulb::bulb: 匿名函數（Lambda expressions）是一個函數物件，大致分為三個部分，其中參數（`params`）與函數主體（`body`）與一般函數一樣，下方僅針對 `captures` 做說明。 `[ captures ] ( params ) { body }` `captures` 中宣告哪些變數可以被存取，主要分為二種， capture by reference 與 capture by copy。 * capture by reference * `&var` * `&`：全部變數 * capture by copy * `var` * `=`：全部變數 * 預設為 `const`，加上 `mutable` 宣告字可改變 :::spoiler 範例 ```cpp! int a, b, c; [](){}; // no capture [&b](){}; // b captured by reference [c](){}; // c captured by copy, const [c]() mutable {}; // c captured by copy [&](){}; // a, b, c captured by reference [&, a](){}; // b, c captured by reference // a captured by copy, const [=](){}; // a, b, c captured by copy [=, &a](){}; // b, c captured by copy, const // a captured by reference ``` ::: <hr class="dashed"> ## [迭代器（Iterators）](https://en.cppreference.com/w/cpp/iterator) #### [`<iterator>`](https://en.cppreference.com/w/cpp/header/iterator) 迭代器與容器有很大的關聯，不同容器的資料結構並不相同，如何進行操作是一大難題，所以迭代器為此提供一個共同的介面。 > 可以用指標（pointer）的概念去理解迭代器，某些迭代器可能就真的是指標， > 不過迭代器大多是一個類別（class），透過運算子重載（operator overloading）， > 實現了很多與指標類似的操作。迭代器之間是有分級的（hierarchical），可以簡單地分為三類， * 單向迭代器 * 可以進行遞增（`++`）（incrementable） * 在競程中很少見 * 雙向迭代器 * 可以進行遞增（`++`）（incrementable） * 可以進行遞減（`--`）（decrementable） * 隨機存取迭代器 * 可以進行常數時間的移動（`+`, `-`, ...）迭代器的類型（type）跟容器 C 有關，為 `C::iterator`，寫起來較為繁瑣，一般會用 [`auto`](https://en.cppreference.com/w/cpp/language/auto) 自動判別（e.g., `auto it{c.begin()};`）。 <hr class="thin"> * `next(it);` * 回傳 `it` 的下一個迭代器 * `prev(it);` * 回傳 `it` 的前一個迭代器（`it` 需為雙向迭代器） * `advance(it, n);` * 將 `it` 的前進 `n` 次 * 若 `n` 為負數，`it` 需為雙向迭代器 * `distance(it, it2);` * 回傳 `it` 到 `it2` 的距離 * 若 `it` 為隨機存取迭代器，`it2` 可以在 `it` 前面 <hr class="dashed"> ## [容器（Containers）](https://en.cppreference.com/w/cpp/container) > A Container is an **object used to store other objects.**[^cppCtr] 容器是用來儲存其他資料的物件，可以分為三個類型，循序容器（Sequence containers）、關聯容器（Associative containers）、無序關聯容器（Unordered associative containers），另外還有容器改寫器（Container adaptors）。不同容器提供的操作可能相同，但複雜度卻會有所差異，請盡量**了解容器內部的實作原理**，即可知道其複雜度。 <hr class="dotted"> ### 共通函數 > 一些函數成員是大多數容器都有的。 * `c.begin();` * 容器開頭的迭代器 * `c.end();` * 容器結尾下一個位置的迭代器（an iterator to the element following the last element） * `c.empty();` * 容器是否為空 * `c.size();` * 元素個數 * `c.clear();`[^clear] * 清空容器 * `c.swap(c2);` / `swap(c, c2);` * 交換二個容器（大多為常數時間）容器因為都有 `begin()` / `end()`，可透過 [Range-based for loop](https://en.cppreference.com/w/cpp/language/range-for) 來遍歷所有元素。 > **push 相關函數，幾乎都有 emplace 版本替代**， > 參數由 T 改為 T 的建構子（constructor）參數即可。 > `c.push({arg1, arg2, ...});` $\to$ `c.emplace(arg1, arg2, ...);` <hr class="dotted"> ### 循序容器（Sequence containers） > 可以被循序（sequentially）存取的資料結構 <hr class="gradient"> #### [`<vector>`](https://en.cppreference.com/w/cpp/header/vector) <hr class="thin"> ### [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) `std::vector` 為動態配置陣列（dynamic allocated array），儲存空間會自動動態擴增，使用上與一般的陣列（C-style array）很像。 ```graphviz digraph { rankdir=LR; vector [style=rounded, shape=box, fixedsize=true, width=0.8, height=0.5]; memory [shape=none, label= <<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> <TR> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" WIDTH="15" HEIGHT="15"></TD> <TD COLSPAN="1" WIDTH="15" HEIGHT="15"></TD> </TR> </TABLE>> ]; vector :s -> memory :w; } ``` 常見用法： * 建構子（constructor） * `vector<T> v;` / `vector<T> v{};` * 空的 `vector` * `vector<T> v(n);` * 有 `n` 個元素的 `vector` * `vector<T> v(n, val);` * 有 `n` 個元素的 `vector`，且元素的值為 `val` * `v.resize(n);` * 把 `vector` 的大小調整為 `n` * `v.assign(n, val);` * 把 `vector` 的內容改為 `n` 個元素，且元素的值為 `val` * `v.push_back(val);` * 將 `val` 插入尾端 * `v.pop_back();` * 刪除尾端元素 `vector<int> v{10}` 與 `vector<int> v{10, -1}` 分別會得到長度為 1 與 2 的 `vector`， **使用 `vector` 時，請改用 `()`。** ```cpp! vector<int> v(5, 0); // 5 個 0 v.assign(10, -1); // 10 個 -1 for (int i{0}; i < 10; ++i) v[i] = i + 1; // 1 2 3 4 5 6 7 8 9 10 v.pop_back(); v.pop_back(); // 1 2 3 4 5 6 7 8 v.resize(6); // 1 2 3 4 5 6 v.push_back(10); // 1 2 3 4 5 6 10 for (auto& x : v) cout << x << ' '; cout << endl; // 輸出所有元素 ``` <hr class="gradient"> #### [`<array>`](https://en.cppreference.com/w/cpp/header/array) <hr class="thin"> ### [`std::array`](https://en.cppreference.com/w/cpp/container/array):bulb: `std::array` 只是將固定大小的陣列封裝成一個類別（class），並且提供一些簡單的函數。 ```graphviz digraph { subgraph cluster { style=rounded; margin=5.0; label="array"; memory [shape=none, label= <<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> <TR> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="20" HEIGHT="20"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="20" HEIGHT="20"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="20" HEIGHT="20"></TD> <TD COLSPAN="1" BGCOLOR="Gray" WIDTH="20" HEIGHT="20"></TD> </TR> </TABLE>> ]; } } ``` 用法： * 建構子（constructor） * `array<T, N> a;` / `array<T, N> a{};` * 一個長度為 `N` 的 `array`，`N` 必須為定值 * `a.fill(val);` * 將 `a` 填滿 `val` 假設需要一個 `vector`，每個元素固定為 4 個長整數。 ```cpp! vector<array<long long, 4>> v(10); // 有 10 個長度固定為 4 的 array for (int i{0}; i < v.size(); ++i) v[i].fill(i); ``` <hr class="gradient"> #### [`<list>`](https://en.cppreference.com/w/cpp/header/list) <hr class="thin"> ### [`std::list`](https://en.cppreference.com/w/cpp/container/list):bulb: `std::list` 為雙向鏈結串列（doubly-linked list）。 ```graphviz digraph { rankdir=LR; node [style=rounded, shape=record, fixedsize=true, width=1, height=0.3, label="{<prev>|data|<next>}"]; n0 :ne -> n1 :nw; n1 :sw -> n0 :se; n1 :ne -> n2 :nw; n2 :sw -> n1 :se; } ``` 常見用法： * 建構子（constructor） * `list<T> lst;` / `list<T> lst{};` * `lst.push_front(val);` / `lst.push_back(val);` * 在前端（尾端）插入 `val` * `lst.insert(pos, val);` * 在 `pos` 前插入 `val`（`pos` 是一個迭代器） * `lst.pop_front();` / `lst.pop_back();` * 刪除前端（尾端）元素 * `lst.erase(pos);` * 刪除 `pos` 位置的元素（`pos` 是一個迭代器） ```cpp! list<int> lst{}; lst.push_front(1); lst.push_front(2); lst.push_front(3); // 3 2 1 auto it{lst.begin()}; // it 指向 3 advance(it, 2); // it 為雙向迭代器，不能進行 +/- // it 指向 1 lst.insert(it, 4); // 3 2 4 1 ``` <hr class="gradient"> #### [`<deque>`](https://en.cppreference.com/w/cpp/header/deque) <hr class="thin"> ### [`std::deque`](https://en.cppreference.com/w/cpp/container/deque):bulb::bulb: 雙端佇列（Double-ended queue）是種抽象資料結構，可以進行頭尾的插入移除； `std::deque` 是雙端佇列的實作，**支援常數時間的頭尾操作**，但遠遠不如此。 <hr class="thin"> 內部結構通常由一堆大小固定的陣列（這邊簡稱**區塊**）組成，另外有一個**紀錄陣列**，指向這一堆區塊。每次在擴增記憶體時，會把紀錄陣列變大二倍，並將目前的區塊移動到紀錄陣列的**中間**，使得紀錄陣列前後，都有空間加入新的區塊，透過均攤分析，頭尾插入複雜度為 $O(1)$，因為動到的是區塊在記錄陣列中的位置，不像 `vector` 需要移動每一個元素，常數較小。其餘使用與 `vector` 相似，複雜度也大多相同，但常數大小有所差異，像是索引（`operator[]`）較慢，因為要經過紀錄陣列，再到區塊中的某個位置。 ```graphviz digraph { rankdir=LR; subgraph cluster { style=rounded; label="deque"; map [shape=record, fixedsize=true, width=1, height=1, label="|<c0>chunk 0|<c1>chunk 1|<c2>chunk 2|"]; begin [shape=box, label="begin()"]; end [shape=box, label="end()"]; } c0 [shape=record, fixedsize=true, width=0.5, height=1, label="<0>|<1>|<2>[0]|<3>[1]"]; c1 [shape=record, fixedsize=true, width=0.5, height=1, label="<0>[2]|<1>[3]|<2>[4]|<3>[5]"]; c2 [shape=record, fixedsize=true, width=0.5, height=1, label="<0>[6]|<1>|<2>|<3>"]; map:c0 -> c0:n; map:c1 -> c1:n; map:c2 -> c2:n; begin -> c0:2; end -> c2:1; } ``` [^DQ] <hr class="dotted"> ### 關聯容器（Associative containers） > 排序好的資料結構，提供 $O(\log n)$ 的搜尋複雜度，一般以紅黑樹（red-black tree）， > 一種平衡的二元搜尋樹（balanced binary search tree），來實作。 ```graphviz digraph { splines=false; nodesep=0.8; node [style=dashed, shape=record, fixedsize=true, width=0.5, height=0.5] n13 [label="{13|{<left>|<right>}}"]; n7 [label="{7|{<left>|<right>}}"]; n2 [label="{2|{<left>|<right>}}"]; n6 [label="{6|{<left>|<right>}}"]; n12 [label="{12|{<left>|<right>}}"]; n20 [label="{20|{<left>|<right>}}"]; n16 [label="{16|{<left>|<right>}}"]; n27 [label="{27|{<left>|<right>}}"]; n24 [label="{24|{<left>|<right>}}"]; n23 [label="{23|{<left>|<right>}}"]; n31 [label="{31|{<left>|<right>}}"]; edge [style=dashed, arrowhead=o]; n13:left -> n7; n7 :left -> n2; n2 :right-> n6; n7 :right -> n12; n13:right -> n20; n20:left -> n16; n20:right -> n27; n27:left -> n24; n24:left -> n23; n27:right -> n31; } ``` <hr class="gradient"> #### [`<set>`](https://en.cppreference.com/w/cpp/header/set) <hr class="thin"> ### [`std::set`](https://en.cppreference.com/w/cpp/container/set) `std::set` 是一個集合，元素不能重複。常見用法： * 建構子（constructor） * `set<T> s;` / `set<T> s{};` * `s.insert(k);` * 插入 `k` * `s.erase(k);` * 刪除 `k` * `s.find(k);` * 尋找等於 `k` 的元素，回傳此元素的迭代器（若不存在則回傳 `s.end()`） * `s.count(k);` * 回傳等於 `k` 的元素個數（0 或 1，因為元素不能重複） * `s.lower_bound(k);` * 尋找第一個不小於 `k` 的元素 * `s.upper_bound(k);` * 尋找第一個大於 `k` 的元素 ```cpp! set<char> s{}; s.insert('s'); s.insert('o'); s.insert('r'); s.insert('t'); // 's' 'o' 'r' 't' if (s.find('?') == s.end()) s.insert('?'); // 's' 'o' 'r' 't' '?' auto it{s.lower_bound('a')}; // it 指向 'o' for (auto& x : s) cout << x; cout << endl; // 輸出所有元素 // < ?orst ``` `set` 是由小到大排序好的，因此可用 **`s.begin()`，`prev(s.end())`（`s.rbegin()`）**，找到集合中**最小與最大值**。 <hr class="thin"> #### [`std::multiset`](https://en.cppreference.com/w/cpp/container/multiset) `std::multiset` 與 `set` 幾乎一樣，差別只在元素可以重複。 **`erase(k)` 會刪除所有等於 `k` 的元素，** 如果只要刪除一個，請用刪除某個迭代器的方式進行。 ```cpp! s.erase(s.find(k)); ``` <hr class="gradient"> #### [`<map>`](https://en.cppreference.com/w/cpp/header/map) <hr class="thin"> ### [`std::map`](https://en.cppreference.com/w/cpp/container/map) `std::map` 是一個字典，儲存鍵-值對（key-value pairs），鍵（key）不能重複；元素類型為 [`std::pair`](#stdpair)， `first` 存放鍵（key），`second` 存放值（value）。常見用法： * 建構子（constructor） * `map<K, V> mp;` / `map<K, V> mp{};` * `K` 為鍵的類型 * `V` 為值的類型 * `mp.insert({k, v});` * 插入一個元素，為 `k` - `v` * `mp.erase(k);` * 刪除鍵為 `k` 的元素 * `mp.find(k);` * 尋找鍵等於 `k` 的元素，回傳此元素的迭代器（若不存在則回傳 `mp.end()`） * `mp[k];` :bulb: * 回傳「值的參考（reference）」，若不存在則插入一個元素，鍵為 `k` * **建議夠熟悉再使用。** ```cpp! map<int, string> mp{}; mp.insert({0, "I'll"}); mp.insert({2, "this"s}); mp.insert({3, "class"s}); // {0, "I'll"} {2, "this"} {3, "class"} mp[1] = "fail"s; // {0, "I'll"} {2, "this"} {3, "class"} {1, "fail"} mp[1] = "passed"s; // {0, "I'll"} {2, "this"} {3, "class"} {1, "passed"} auto it{mp.find(1)}; if (it != mp.end()) it->second = "pass"s; // {0, "I'll"} {2, "this"} {3, "class"} {1, "pass"} for (auto& [k, v] : mp) cout << v << ' '; cout << endl; // 輸出所有元素 // < I'll pass this class ``` <hr class="thin"> #### [`std::multimap`](https://en.cppreference.com/w/cpp/container/multimap) `std::multimap` 也與 `map` 幾乎一樣，差別只在於鍵可以重複。 <hr class="dotted"> ### 無序關聯容器（Unordered associative containers）:bulb: * 搜尋的均攤複雜度 $O(1)$，最差情況可能為 $O(n)$ * 透過雜湊表（hash table）實現 > 競程中較少用到，因為一般 $O(\log n)$ 的複雜度就足夠， > 且牽涉到雜湊函數（hash function），其餘使用與關聯容器幾乎相同， > 此處就不進行介紹。 <hr class="dotted"> ### 容器改寫器（Container adaptors） > 提供容器一個不同的介面。 <hr class="gradient"> #### [`<stack>`](https://en.cppreference.com/w/cpp/header/stack) <hr class="thin"> ### [`std::stack`](https://en.cppreference.com/w/cpp/container/stack) `std::stack` 是一個後進先出（LIFO, Last-In-First-Out）的資料結構。 > 預設改寫自 `deque`，因為它支援較快的尾端插入。 ```graphviz digraph { rankdir=LR; subgraph cluster { style=rounded; margin=40.0; label="stack"; memory [style=filled, shape=record, fixedsize=true, width=1.6, height=1.6, label="<top>top()|||"]; } node [style="filled, dashed", shape=box, width=1.6, height=0.4, label=""]; edge [style=dashed, arrowhead=o]; push :e -> memory:top :n [label="push"]; memory:top :e -> pop :w [label="pop"]; } ``` 常見用法： * 建構子（constructor） * `stack<T> stk;` / `stack<T> stk{};` * `stk.push(val);` * 在頂端插入 `val` * `stk.pop();` * 移除頂端元素 * `stk.top();` * 回傳頂端元素的參考 ```cpp! stack<double> stk{}; stk.push(0.); stk.push(1.414); stk.push(1.732); stk.push(2.223); // 0. 1.414 1.732 2.223 while (!stk.empty()) { double x{stk.top()}; stk.pop(); cout << x << ' '; } cout << endl; // 輸出所有元素 // < 2.223 1.732 1.414 0 ``` <hr class="gradient"> #### [`<queue>`](https://en.cppreference.com/w/cpp/header/queue) <hr class="thin"> ### [`std::queue`](https://en.cppreference.com/w/cpp/container/queue) `std::queue` 是一個先進先出（FIFO, First-In-First-Out）的資料結構。 > 預設改寫自 `deque`，因為它支援快速的頭尾操作。 ```graphviz digraph { rankdir=LR; subgraph cluster { style=rounded; margin=20.0; label="queue"; memory [style=filled, shape=record, fixedsize=true, width=3, height=1.5, label="{<back>|||||<front>f\nr\no\nn\nt\n()}"]; } node [style="filled, dashed", shape=box, fixedsize=true, width=0.5, height=1.5, label=""]; edge [style=dashed, arrowhead=o] push :s -> memory:back [label="push"]; memory:front -> pop :n [label="pop"]; } ``` 常見用法： * 建構子（constructor） * `queue<T> qu;` / `queue<T> qu{};` * `qu.push(val);` * 在尾端插入 `val` * `qu.pop();` * 移除第一個元素 * `qu.front();` * 回傳第一個元素的參考 ```cpp! qu<double> qu{}; qu.push(0.); qu.push(1.414); qu.push(1.732); qu.push(2.223); // 0. 1.414 1.732 2.223 while (!qu.empty()) { double x{qu.front()}; qu.pop(); cout << x << ' '; } cout << endl; // 輸出所有元素 // < 0 1.414 1.732 2.223 ``` <hr class="thin"> ### [`std::priority_queue`](https://en.cppreference.com/w/cpp/container/priority_queue) `std::priority_queue` 是一個二元堆積（Binary heap），支援常數時間取得最值（absolute extrema）。預設改寫自 `vector`，因為有較快的存取速度。 > **預設為最大堆積（max heap）**，意即最大值在頂端。 ```graphviz digraph { node [style=rounded, shape=box, fixedsize=true, width=0.4, height=0.3]; array [shape=record, fixedsize=true, width=3, height=0.4, label="<0>10|<1>9|<2>7|<3>8|<4>5|<5>6|<6>3|<7>1|<8>4|<9>2"]; subgraph cluster_tree { edge [style=bold, dir=forward]; 10 -> 9; 10 -> 7; 9 -> 8; 9 -> 5; 7 -> 6; 7 -> 3; 8 -> 1; 8 -> 4; 5 -> 2; } top [shape=none, label="top()"]; top -> array:0 [style=dotted, arrowhead=o]; edge [style=dashed, dir=none]; array:0 -> 10; array:1 -> 9; array:2 -> 7; array:3 -> 8; array:4 -> 5; array:5 -> 6; array:6 -> 3; array:7 -> 1; array:8 -> 4; array:9 -> 2; } ``` 常見用法： * 建構子（constructor） * `priority_queue<T> pq;` / `priority_queue<T> pq{};` * `priority_queue<T, vector<T>, Cmp> pq{};` * `Cmp` 為比較函數的類別 * `pq.push(val);` * 插入 `val` * `pq.pop();` * 移除最值 * `pq.top();` * 回傳第一個元素的參考 ```cpp! priority_queue<int, vector<int>, greater<int>> pq{}; // 使用 greater 可改為最小堆積（min heap） pq.push(6); pq.push(2); pq.push(9); pq.push(4); // 6 2 9 4 while (!pq.empty()) { auto x{pq.top()}; pq.pop(); cout << x << ' '; } cout << endl; // 輸出所有元素 // < 2 4 6 9 ``` <hr class="dashed"> ## [演算法（Algorithms）](https://en.cppreference.com/w/cpp/algorithm) 一般大多用於 `vector`（`array`, `deque`）這些擁有隨機存取迭代器的容器，否則複雜度過高。 <hr class="gradient"> #### [`<algorithm>`](https://en.cppreference.com/w/cpp/header/algorithm) <hr class="thin"> ### [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) 對區間元素進行排序。 * `sort(c.begin(), c.end());` * 由小排到大 * `sort(c.rbegin(), c.rend());` * 利用反向迭代器 * 由大排到小 * `sort(c.begin(), c.end(), cmp);` * 自行給比較函數 * `cmp` 比較結果為真（`true`）的元素，會被放在較前面。也就是如果 `cmp` 給了「大於」這樣的函數，就會由大排到小。函數指標也符合 [C++ FunctionObject](https://en.cppreference.com/w/cpp/named_req/FunctionObject) 的定義；為何不用寫 `&cmp` 而是 `cmp` 就足夠，可參考 [Everything you need to know about pointers in C](https://boredzo.org/pointers/#function_pointers)。 ::: spoiler function ```cpp! bool cmp(const int& a, const int& b) { return a > b; } sort(v.begin(), v.end(), cmp); ``` ::: ::: spoiler function object ```cpp! struct { bool operator()(int a, int b) { return a > b; } } cmp{}; sort(v.begin(), v.end(), cmp); ``` ::: :::spoiler lambda ```cpp! sort(v.begin(), v.end(), [](int a, int b){return a > b;}); ``` ::: <br> 指向陣列的指標也符合 [C++ LegacyRandomAccessIterator](https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator)。 :::spoiler C-style array ```cpp! int arr[100]; sort(arr, arr + 100); ``` ::: <hr class="thin"> ### [`std::min`](https://en.cppreference.com/w/cpp/algorithm/min) / [`std::max`](https://en.cppreference.com/w/cpp/algorithm/max) 回傳較小（大）值。 * `mn = min(mn, x);`, `mx = max(mx, x);` * `min(0, x);`, ... <hr class="thin"> ### [`std::reverse`](https://en.cppreference.com/w/cpp/algorithm/reverse) 反轉整個區間。 * `reverse(c.begin(), c.end());` <hr class="thin"> ### [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound) / [`std::upper_bound`](https://en.cppreference.com/w/cpp/algorithm/upper_bound) / [`std::equal_range`](https://en.cppreference.com/w/cpp/algorithm/equal_range):bulb: **區間必須為排序好的**（實際上依照 $val$ 進行分隔（partition）即可），概念為二分搜尋（binary search）。找尋區間中第一個不小於（大於） $val$ 的元素，回傳迭代器。 * `lower_bound(c.begin(), c.end(), val);` * 回傳第一個不小於 `val` 的元素的迭代器 * `upper_bound(c.begin(), c.end(), val);` * 回傳第一個大於 `val` 的元素的迭代器 * `equal_range(c.begin(), c.end(), val);` * 回傳一個 `std::pair`，包含上述二者 * 可視為 `val` 的左閉右開區間 **如果容器為 `set`，請用 `set` 的函數成員！** <hr class="thin"> ### [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/next_permutation):bulb::bulb: 將區間排序變為字典序（lexicographic order）的下一個。（沒有的話則變為字典序的第一個，並回傳 `false`） * `next_permutation(c.begin(), c.end());` ```cpp! vector<int> v{1, 3, 2, 4}; sort(v.begin(), v.end()); // 先回到字典序的第一個 do { for (auto& x : v) cout << x; cout << '\n'; } while (next_permutation(v.begin(), v.end())); // 輸出所有排列情況 // < 1234 // < 1243 // < 1324 // < ... // < 4321 ``` > 所有排列的平均複雜度 $O(1)$；最差情況複雜度為 $O(n)$。 <hr class="thin"> ### [`std::nth_element`](https://en.cppreference.com/w/cpp/algorithm/nth_element):bulb::bulb: 選擇演算法（selection algorithm），平均複雜度為 $O(n)$。 * `nth_element(c.begin(), it, c.end());` * 將 `it` 指向的位置元素變為排序完應該在此位置的元素（`it` 前面的不比 `it` 大；`it` 後面的不比 `it` 小） ```cpp! vector<int> v{5, 6, 9, 0, 8, 7, 2, 0}; nth_element(v.begin(), v.begin() + 1, v.end(), greater<int>{}); // 將第二個位置排好 // 第一個元素必為最大值 for (auto& x : v) cout << x << ' '; cout << endl; // < 9 8 7 6 0 5 2 0 ``` <hr class="dashed"> ## [字串（String）](https://en.cppreference.com/w/cpp/string) C++ 將字串的概念抽象化（Abstraction），並提供一系列的操作介面。 <hr class="gradient"> #### [`<string>`](https://en.cppreference.com/w/cpp/header/string) <hr class="thin"> * `stoi(str);` * 將字串 `str` 轉為整數（`int`） * `to_string(x);` * 將數字 `x` 轉為字串 <hr class="thin"> ### [`std::string`](https://en.cppreference.com/w/cpp/string/basic_string) `std::string` 有點類似於 `vector`，也有不少相同的函數。（有時可用 `vector<char>` 替代） * 常量（Literal） * `"string"s` * `""s` 代表是 `string` <font class="cpp14">`C++14`</font> * 建構子（constructor） * `string str;` / `string str{};` * 空字串 * `string str{a};` * 建構跟 `a` 相同的字串 * `str += a;`, `str + a;`, `str == a;`, `str > a;`, ... * 透過運算子重載，使運算子符合字串的意義 * `os << str;`, `os >> str;` * 可以直接輸入輸出字串 ```cpp! string s1{}; string s2{}; cin >> s1 >> s2; // > str1 // > str2 string str{s1 + '+' + s2}; // "str1+str2"s for (int i{0}; i < str.length(); ++i) if (str[i] == '+') str[i] = '#'; str += "\n"s; cout << str; // < str1#str2 ``` <hr class="thin"> ### [`std::getline`](https://en.cppreference.com/w/cpp/string/basic_string/getline):bulb: * `getline(is, str);` / `getline(is, str, delim);` * 從輸入流 `is` 讀進 `str`，直到遇到定界符 `delim`（預設為換行 `'\n'`）為止 * 定界符 `delim` 會被從輸入流 `is` 取出但不放入 `str` 中 **一般透過 `operator>>` 讀取過後，會有殘留的空白或換行，請特別注意。** #### [`std::basic_istream::ignore()`](https://en.cppreference.com/w/cpp/io/basic_istream/ignore) * `is.ignore();` * 拋棄輸入流 `is` 的一個字元 * `is.ignore(numeric_limits<streamsize>::max(), '\n');` * 拋棄輸入流 `is` 中的字元直到遇到換行（`'\n'`） * 換行也會被拋棄 #### [`std::ws`](https://en.cppreference.com/w/cpp/io/manip/ws) * `is >> ws;` * 拋棄輸入流 `is` 前端任何的空白字元（e.g., `' '`, `'\n'`, `'\t'`, ...） <hr class="gradient"> #### [`<sstream>`](https://en.cppreference.com/w/cpp/header/sstream) <hr class="thin"> ### [`std::stringstream`](https://en.cppreference.com/w/cpp/io/basic_stringstream):bulb::bulb: `std::stringstream` 透過 `string` 建立一個輸入輸出流。 > **常用於讀取不定個數的輸入。** ```cpp! int n; cin >> n; cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 避免 n 後面還有空白，把上一行剩餘內容全部捨棄 // 一般使用 cin.ignore() 捨棄換行即可 cin >> ws; // 或使用 ws // 沒有空白字元的話，相當於沒有進行操作 // 所以在這邊可以正常執行 string s{}; getline(cin, s); // 讀取一整行 // > 1 2 4 8 stringstream ss{s}; // 創建輸入流 vector<int> v{}; while (ss >> n) v.push_back(n); // 讀到輸入流 ss 結束 for (auto& x : v) cout << x << ','; cout << endl; // < 1,2,4,8, ``` <hr class="dashed"> ## [工具（Utility）](https://en.cppreference.com/w/cpp/utility) #### [`<utility>`](https://en.cppreference.com/w/cpp/header/utility) <hr class="thin"> ### [`std::swap`](https://en.cppreference.com/w/cpp/algorithm/swap) 將二個變數的值交換。 <hr class="thin"> ### [`std::pair`](https://en.cppreference.com/w/cpp/utility/pair) `std::pair` 將可以存放二個值（類型可以不相同）。 * 建構子（constructor） * `pair<T1, T2> pr;` / `pair<T1, T2> pr{a, b};` * `make_pair(a, b);` * 根據 `a`, `b` 的類型創建一個 `pair` 並回傳 * `pr.first;` / `pr.second;` * 存取第一（第二）個值 * `pr1 > pr2;` * 先比較 `first`，相同再比較 `second` * `first` 與 `second` 皆要為可比較的類型 <hr class="gradient"> #### [`<tuple>`](https://en.cppreference.com/w/cpp/header/tuple):bulb: <hr class="thin"> ### [`std::tuple`](https://en.cppreference.com/w/cpp/utility/tuple) `pair` 是 `std::tuple` 的特例，`tuple` 可以存放多個值。 * 建構子（constructor） * `tuple<T1, ...> tp;` / `pair<T1, ...> tp{a, ...};` * `make_tuple(a, ...);` * `get<i>(tp);` * 存取第 `i` 個值（`i` 必須為常數） * `tp1 > tp2;` * 從前面的元素開始比較 * 所有元素必須為可以比較的類型 <hr class="thin"> ### [Structured binding declaration](https://en.cppreference.com/w/cpp/language/structured_binding) :bulb:<font class="cpp17">`C++17`</font> 下方給一些常用的範例。 ```cpp! pair<int, char> pr{0, 'a'}; auto [fi, se]{pr}; fi = 1, se = 'b'; cout << pr.first << pr.second << endl; // < 0a auto& [fi_r, se_r]{pr}; fi_r = 2, se_r = 'c'; cout << pr.first << pr.second << endl; // < 2c ``` ```cpp! vector<tuple<int, string, double>> v{}; v.emplace_back(0, "e"s, 2.71); v.emplace_back(1, "pi"s, 3.14); for (auto& [idx, name, value] : v) cout << idx << ' ' << name << ' ' << value << '\n'; // < 0 e 2.71 // < 1 pi 3.14 ``` <hr class="gradient"> #### [`<optional>`](https://en.cppreference.com/w/cpp/header/optional) <hr class="thin"> ### [`std::optional`](https://en.cppreference.com/w/cpp/utility/optional):bulb: <font class="cpp17">`C++17`</font> `std::optional` 將一個型態包裝起來，提供它存在與不存在兩種狀態，在某些情境能夠更輕易的表達想法。 > 類似於 `pair<bool, T>`。 * 建構子（constructor） * `optional<T> x{};` / `optional<T> x{nullopt};` * 建構一個物件，裡面沒有值 * `optional<T> x{val};` * 建構一個物件，裡面的值是 `val` * `bool(x);` / `x.has_value();` * 判斷裡面有沒有值 * 在某些地方會自動轉型 * `x.value();` / `x.value_or(val2);` * 值的參考 * `x.value()` 只能在 `x.has_value()` 為 `true` 時呼叫 * `x.reset();` * 初始（變為沒有值的狀態） * `x = y;` * 賦值，`y` 的類型可以是 `T` 或 `optional<T>` <hr class="dotted"> ### [`std::move()`](https://en.cppreference.com/w/cpp/utility/move):bulb::bulb: C++ 的 [Value categories](https://en.cppreference.com/w/cpp/language/value_category) 分為五類。 Primary categories : * lvalue * has identity and cannot be moved from * xvalue * an “eXpiring” value * has identity and can be moved from * pvalue * “pure” rvalue * has identity and can be moved from Mixed categories : * glvalue * “generalized” lvalue * either lvalue or xvalue * rvalue * either prvalue or xvalue ```graphviz digraph { rankdir=UD lvalue [shape=plaintext]; glvalue [shape=plaintext]; xvalue [shape=plaintext]; rvalue [shape=plaintext]; prvalue [shape=plaintext]; lvalue -> glvalue :nw [style=dashed, arrowhead=curve]; xvalue -> glvalue :ne [style=dashed, arrowhead=curve]; xvalue -> rvalue :nw [style=dashed, arrowhead=curve]; prvalue -> rvalue :ne [style=dashed, arrowhead=curve]; } ``` > std::move is used to indicate that an object t may be "moved from", i.e. allowing the efficient transfer of resources from t to another object.[^cppmove] 簡單來說，`std::move()` 就是將物件轉為一個 xvalue expression，代表說這個物件的已經過期（expiring）了，資源可以重複利用。常用於容器，使用 move constructor 或 move assignment。（透過 rvalue reference (`T&&`) 與 lvalue reference (`T&`) 型態上的差別，選擇不同的重載（overloading）函數，關於 reference 可參考 [Reference declaration](https://en.cppreference.com/w/cpp/language/reference)。）像是 `vector`，可以將內部配置的陣列直接轉移給另外一個 `vector`。 > 雖然沒有明確規範，但大多實作下，`v` 都會變成空的 `vector`。 > > Unless otherwise specified, all standard library objects that have been moved from are placed in a "valid but unspecified state".[^cppmove] ```cpp! vector<int> v(10, 0); vector<int> v2{move(v)}; // move constructor assert(v.empty()); assert(v2.size() == 10); vector<int> v3(5, -1); v3 = move(v2); // move assignment assert(v2.empty()); assert(v3.size() == 10); ``` > :bulb::bulb::bulb: 如果有人好奇為什麼 `std::move()` 的參數只有 `T&&`， > 可以參考 [Template argument deduction](https://en.cppreference.com/w/cpp/language/template_argument_deduction)。 > > If P is an rvalue reference to a cv-unqualified template parameter (so-called forwarding reference), and the corresponding function call argument is an lvalue, the type lvalue reference to A is used in place of A for deduction.[^cppTAD] > > > > 註：P is the parameter's type; A is the argument's type. <hr class="dashed"> ## [數值（Numerics）](https://en.cppreference.com/w/cpp/numeric) #### [`<numeric>`](https://en.cppreference.com/w/cpp/header/numeric) <hr class="thin"> ### [`std::gcd`](https://en.cppreference.com/w/cpp/numeric/gcd) / [`std::lcm`](https://en.cppreference.com/w/cpp/numeric/lcm) <font class="cpp17">`C++17`</font> 計算最大公因數（greatest common divisor），最小公倍數（least common multiple）。 <hr class="gradient"> #### [`<cmath>`](https://en.cppreference.com/w/cpp/header/cmath) <hr class="thin"> ### [`std::abs`](https://en.cppreference.com/w/cpp/numeric/math/abs) 取絕對值（absolute value）。 <hr class="thin"> ### [`std::sqrt`](https://en.cppreference.com/w/cpp/numeric/math/sqrt) 計算開根號，**參數與回傳值皆為浮點數**，請注意精度問題。 > std::sqrt is required by the IEEE standard to be exact. After rounding to the return type (using default rounding mode), the result of std::sqrt is indistinguishable from the infinitely precise result.[^cppsqrt] <hr class="dashed"> ## 數值限制（Numeric limits） #### [`<limits>`](https://en.cppreference.com/w/cpp/header/limits) <hr class="thin"> ### [`std::numeric_limits`](https://en.cppreference.com/w/cpp/types/numeric_limits):bulb: `std::numeric_limits` 定義一些算術類型（arithmetic types）的性質。 ```cpp! cout << numeric_limits<int>::max() << '\n'; // < 2147483647 ``` --- 標準函數庫中還有許多函數，雖然有些很簡單，可以自己寫，不過**標準函數就如同一種語言**，能夠幫助我們更輕易地表達，希望讀者再日後的使用中，能夠逐漸熟悉標準函數庫的使用。 --- # References * Stroustrup, Bjarne (2012). "The C++ Programming Language (Fourth Edition)"(https://en.cppreference.com/w/) * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)". * [C++ reference] --- # 練習題 | Problem | Tags | |:-:|:- | | [字典](https://zerojudge.tw/ShowProblem?problemid=a541) | `set` | | [文字抄寫 II](https://zerojudge.tw/ShowProblem?problemid=d518) | `map` | | [今晚打老虎](https://zerojudge.tw/ShowProblem?problemid=a091) | `map` or `multiset` | | [p&q的邂逅](https://zerojudge.tw/ShowProblem?problemid=a565) | `stack` | | [Waiting In Line](https://zerojudge.tw/ShowProblem?problemid=d718) | `queue` | | [手續費 (Fee)](https://tioj.ck.tp.edu.tw/problems/1424) | `priority_queue` | | [成績指標](https://zerojudge.tw/ShowProblem?problemid=b964) | `sort` | | [Sort! Sort!! and Sort!!!](https://zerojudge.tw/ShowProblem?problemid=d750) | `sort` | | [二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) | `lower_bound` | | [The Hamming Distance Problem](https://zerojudge.tw/ShowProblem?problemid=d790) | `next_permutation` | | [提款卡密碼](https://zerojudge.tw/ShowProblem?problemid=a065) | `string` | | [一串加](https://zerojudge.tw/ShowProblem?problemid=b581) | `stringstream` | [^TC++PL]: Stroustrup, Bjarne (2012). "The C++ Programming Language (Fourth Edition)", p.1268. [^CLRS]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)", p.451. [^INTERVAL]: [Why numbering should start at zero](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html) [^clear]: [What is the complexity of std::vector<T>::clear() when T is a primitive type?](https://stackoverflow.com/questions/11235975/what-is-the-complexity-of-stdvectortclear-when-t-is-a-primitive-type) [^DQ]: [https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl](https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl) [^cppCtr]: [C++ named requirements: Container](https://en.cppreference.com/w/cpp/named_req/Container) [^cppFO]: [Function objects](https://en.cppreference.com/w/cpp/utility/functional) [^cppsqrt]: [std::sqrt](https://en.cppreference.com/w/cpp/numeric/math/sqrt) [^cppmove]: [std::move](https://en.cppreference.com/w/cpp/utility/move) [^cppTAD]: [Template argument deduction](https://en.cppreference.com/w/cpp/language/template_argument_deduction) <style> .cpp14 { font-size: 0.7em; color: #228B22; } .cpp17 { font-size: 0.7em; color: #B22222; } hr.thin { height: 0.5px; } hr.dotted { border-top: dotted; height: .0em; color: #777777; background-color: #ffffff; } hr.dashed { border-top: dashed; height: .0em; color: #777777; background-color: #ffffff; } /* Gradient transparent - color - transparent */ hr.gradient { border: 0; height: 1px; background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0)); } /* Flaired edges, by Tomas Theunissen */ hr.flaired { overflow: visible; height: 30px; border-style: solid; border-color: black; border-width: 1px 0 0 0; border-radius: 20px; background-color: #ffffff; } hr.flaired:before { /* Not really supposed to work, but does */ display: block; content: ""; height: 30px; margin-top: -31px; border-style: solid; border-color: black; border-width: 0 0 1px 0; border-radius: 20px; } /* h1, h2, h3, h4, h5, h6, span { background-image: linear-gradient(to right, red, orange, yellow, green, blue, indigo, purple); -webkit-background-clip: text; -webkit-text-fill-color: transparent; } */ </style>

Read more

C++S's CODEBOOK

2021 Week12 - Graph (BCC, SCC, LCA)

2021 Week17 - Matching

2021 Week17 - Cover & Independent set