---
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>
Sign in with Wallet
Connect another wallet