## 前言
> [name=hzzz]
>這是一個因為我突然心血來潮而想做的整理筆記，這一章是在討論C++STL，在我自己複習的同時，希望可以順便教教你們，~~讓我們一起進步~~。
>好總之如果底下筆記有任何錯誤都歡迎跟我說，我會~~鞭策自己然後~~修改成正確的版本ㄉ。
>還有如果有任何希望我整理的部份 ~~(C-style先不要 我不熟)~~ 也歡迎找我！
>幹話太多 嘻嘻
## 關於C++:
其實`C++`就是`Ｃ 語言`家族的成員之一。
他是 **1983 年**由貝爾實驗室(Bell Labs)的 Bjarne Stroustrup 所開發出來的，**`C++`第一個正式版`C++98`(於1998年發佈)**，之後又陸續推出，像是 11、14、17、20、23...，我們在學習或比賽中常用的版本是 **`C++14`** 或是 **`C++17`**。
`C++`的「**++**」來自於`C語言`的**遞增運算子(increment operator)**，代表他是`C 語言`的**加強版(C plus plus)**，他有許多`C 語言`沒有的強大功能。
## 什麼是STL？
`STL`是`C++`的 **`STL標準模板函式庫(Standard Template Library)`**，也是這個章節所討論的主題。
他是一個極為強大的函式庫，內含了許多現成的**資料結構**與**演算法**，許多`C語言`做起來非常麻煩的行為，`STL`都能快速達成，簡化`C語言`中極為複雜的**資料處理**及**邏輯撰寫**。
每次使用到不同容器都要 #include 不同函式庫會很麻煩，所以有個標頭檔，**涵蓋了幾乎所有`C/C++`函式庫**，只需要引入他就足夠，這樣才不會因為忘記 #include 些什麼而導致**編譯錯誤(compiler error)**，但在正式開發中不建議使用。
```cpp=
#include<bits/stdc++.h>
```
## 效能優化(I/O加速):
在我們開始之前，`C++`是`C語言`的**強化版**，任何`C語言`的語法`C++`都可以使用，像是輸入輸出`C`是`scanf printf`、`C++`是`cin cout`，**每次**程式輸入輸出，他都會訪問、同步`C語言`，讓你在程式中就算使用`scanf`輸入還是可以用`cout`輸出，雖然很方便，但這樣如果程式很多輸入輸出，一直不斷地訪問，會**嚴重拖慢程式的效能**，因此在程式碼上頭加入兩行，中斷`C`與`C++`的連結，**雖然不能混用了**，但是卻可以大幅提高效能，~~降低 **TLE(Time Limit Exceeded)** 地獄風險~~。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); // 很重要背起來
}
```
# STL 容器-基礎用法
## 容器四大分類
如果這一段看不懂，先往下滑看看容器的詳細介紹吧，看完再回來溫習。
|比較項目|序列容器<br>(sequence containers)|容器適配器<br>(container adapter)|關聯容器<br>(associative containers)|雜湊容器<br>(unordered containers)|
| ------- | ------- | ------- | ------- | ------- |
|成員|[vector](##vector(動態陣列)), [deque](##deque(雙向佇列)), [list](##list(雙向鏈結串列)), [forward_list](###補充-forward_list(單向鏈結串列)), [array](##array(靜態陣列))|[stack](##stack(堆疊)), [queue](##queue(佇列)), [priority_queue](###補充-priority_queue(優先佇列))|[set](##set(集合)), [map](##map(映射表)), [multiset](###補充-multiset(多重集合)), [multimap](###補充-multimap(多重映射))|[unordered_set](###unordered_set), [unordered_map](###unordered_map), [unordered_multiset](###unordered_multiset), [unordered_multimap](###unordered_multimap)|
|語意核心|順序儲存-><br>線性結構|包裝其他容器-><br>限制存取方式|基於紅黑樹-><br>自動排序|基於hash table-><br>快速查找|
|使用[]查找|✅([list](##list(雙向鏈結串列)), [forward_list](###補充-forward_list(單向鏈結串列))除外)|❌|❌|❌|
|使用iterator|✅|❌|✅|✅|
|排序性|❌(可用sort函式)|[priority_queue](###補充-priority_queue(優先佇列))✅|✅|❌|
### 序列容器(sequence containers)
**序列容器(sequence containers)** 是`STL`中一類根據**元素插入順序儲存資料**的容器。他們不會根據直進行排序，而是**保留插入順序**，適合用來**模擬陣列**、**佇列**、**堆疊**等結構。
|容器|結構|特性|適用場景|
| ------- | -------- | -------- | -------- |
|[vector](##vector(動態陣列))|動態陣列|支援隨機存取、尾端插入快|大量讀取、尾端操作|
|[deque](##deque(雙向佇列))|雙向佇列|支援頭尾插入、隨機存取|雙端佇列|
|[list](##list(雙向鏈結串列))|雙向鏈結串列|支援任意位置插入、刪除|插入/刪除頻繁|
|[forward_list](###補充-forward_list(單向鏈結串列))|單向鏈結串列|叫省空間，但只能向前走|僅需單遍歷|
|[array](##array(靜態陣列))|靜態陣列(固定大小陣列)|編譯期大小、支援隨機存取|固定長度資料|
### 容器適配器(container adapter)
**容器適配器(container adapter)** 是`STL`中一類**包裝現有容器**，改變其操作方式的工具。他們**不是獨立容器**，而是利用底層容器(如deque或vector)來模擬**特定資料結構行為**。
|適配器|特性|模擬結構|預設底層|
| -------- | -------- | -------- | ------- |
|[stack](##stack(堆疊))|只能操作頂端|堆疊(LIFO)|[deque](##deque(雙向佇列))|
|[queue](##queue(佇列))|只能操作前後|佇列(FIFO)|[deque](##deque(雙向佇列))|
|[priority_queue](###補充-priority_queue(優先佇列))|維持最大值在頂端|最大堆|[vector](##vector(動態陣列))|
### 關聯容器(associative containers)
**關聯容器(associative containers)** 是`STL`中一類根據**鍵值**排序儲存資料的容器。他們**不是根據插入順序**，而是根據**元素的「鍵」** 自動排序，底層通常是**紅黑樹**。
|容器|重複鍵|排序方法|適用場景|
| ------- | -------- | -------- | -------- |
|[set](##set(集合))|❌|自動排序|儲存唯一值且需排序|
|[map](##map(映射表))|❌|根據key排序|鍵值對儲存(唯一鍵)|
|[multiset](###補充-multiset(多重集合))|✅|自動排序|儲存可重複值且排序|
|[multimap](###補充-multimap(多重映射))|✅|根據key排序|鍵值對儲存(可重複鍵)|
### 雜湊容器(unordered containers)
**雜湊容器(unordered containers)** 是`STL`中速度最快的一群，根據**雜湊值**儲存資料的容器。他們不像關聯容器使用紅黑樹排序，而是使用**雜湊表(Hash Table)** 來快速存取資料。
|容器|重複鍵|排序方法|適用場景|
| ------- | -------- | -------- | -------- |
|[unordered_set](###unordered_set)|❌|無序|儲存唯一值且需排序|
|[unordered_map](###unordered_map)|❌|無序|鍵值對儲存(唯一鍵)|
|[unordered_multiset](###unordered_multiset)|✅|無序|儲存可重複值且排序|
|[unordered_multimap](###unordered_multimap)|✅|無序|鍵值對儲存(可重複鍵)|
## vector(動態陣列)
vector 是一個**動態陣列**，可**動態調整大小的陣列**，而且因為`C陣列`是用stack堆疊記憶體，只要陣列開太大`a[500][500]`左右，就會**爆掉**；而`vector`是heap分配，就算陣列開到非常大都不會爆。
基本上會使用到陣列的題目都會**建議使用`vector`**，所以這是`STL`中**極為重要的存在**。
此外`vector`提供了許多**函式**，讓我們在查找、儲存資料時較輕鬆。
### 宣告方法
`vector`「**<>**」中間放入想要儲存的**資料類型**，任何像是`int`, `long long`...都可以存入，甚至可以存入第二個`vector`成為**二維陣列**。
然後後面再接著這個陣列的變數名稱。
```cpp=
vector<int> v; // 存整數
vector<long long> v1; // 長整數
vector<string> v2; // 字串
vector<char> v3; // 字元
vector<bool> v4; // 布林值
vector<pair<int, int>> v5; // pair 存兩個 int
vector<tuple<int, int, int>> v6; // tuple 存多個 int
vector<vector<int>> v7; // 存入 vector 後面會講
```
關於二維vector -> [補充-二維vector](###補充-二維vector)
在**宣告陣列時**變數後面加上指定值，可以讓陣列在宣告時先幫你做好一些事。
```cpp=
vector<int> v(n); // 宣告n個空間的陣列 且每格初始值皆預設為0
vector<int> v(n, a); // 宣告n個空間的陣列 且每格初始值皆設為a
vector<int> v = {1, 2, 3}; // 直接指定內容
vector<int> v; // 如果什麼都不加 v.size() = 0 v[i]會錯誤(RE)
```
### 其他常用的函式
```cpp=
v.push_back(x); // 在陣列尾端插入x值
v.pop_back(); // 刪除最末端之值
v.front(); v.back(); // 取得第一項及最末項之值
v[i]; // 取得第i項之值
v.size(); // 取得陣列長度
v.empty(); // 判斷陣列是否為空 回傳true false
v.clear(); // 清空陣列
v.assign(n, 0); // 填充n個0
v.erase(v.begin() + i); // 移除第i+1項元素 v.begin()是迭代器 後面會教
v.erase(v.begin() + l, v.begin() + r); // 移除區間[l, r)的所有元素 (含l 不含r)
```
關於迭代 -> [iterator(迭代器)](##iterator(迭代器))
因此我們就可以透過上面那些函式，使用不同方法達成一樣效果。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
// 方案一: 每次向後新增一格
int n, a;
vector<int> v;
for (int i=0; i<n; i++) {
cin >> a;
v.push_back(a); // 一定要用push_back
}
for (int i=0; i<n; i++)
cout << v[i] << ' ';
//方案二: assign 預先分配大小
v.clear();
v.assign(n, 0);
for (int i=0; i<n; i++)
cin >> v[i]; // 可以直接存取
for (int i=0; i<n; i++)
cout << v[i] << ' ';
}
```
### zerojudge練習題
[a010.因數分解](https://zerojudge.tw/ShowProblem?problemid=a010)
[a038.數字翻轉](https://zerojudge.tw/ShowProblem?problemid=a038)
[c290.APCS 2017-0304-1秘密差](https://zerojudge.tw/ShowProblem?problemid=c290)
[b552. 3.找質數](https://zerojudge.tw/ShowProblem?problemid=b552)
[b266. 矩陣翻轉](https://zerojudge.tw/ShowProblem?problemid=b266)
[b838. 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838)
### 補充-二維vector
二維的vector跟C的二維陣列很像，差別較大的是**宣告方式**。
```cpp=
vector<vector<int>> v; // 不設定大小 很危險
vector<vector<int>> v(n, vector<int>(m)); // 建立一個 n×m 的陣列 預設全部項皆為0
vector<vector<int>> v(n, vector<int>(m, a)); // 建立 n×m 的陣列 每格填入a
```
剩下存取方式都一樣。 `v[a][b];`
會用`vector`二維是**為了避免陣列開太大C陣列記憶體爆掉**。
就算是二維的版本，也**可以**使用函式。
#### 但寫法不同:
```cpp=
v.push_back({1, 2, 3}); // 一次新增一整列(row)
v[0].push_back(a); // 第0列新增 a 元素
v.pop_back(); // 刪除最後一列
v[0].pop_back(); // 刪除第0列最後一項
v.assign(n, vector<int>(m, a)); // 所有空間填入a值
```
#### 二維vector使用範例:
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 3, m = 4;
vector<vector<int>> v(n, vector<int>(m, 0));
// 輸入資料
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> v[i][j];
// 輸出資料
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << v[i][j] << ' ';
cout << '\n';
}
}
```
### 延伸-C陣列 vs Vector
| 比較項目 | C陣列(int a[]) | vector|
| -------- | -------- | -------- |
|記憶體|stack(堆疊)|heap(堆區)|
|長度|固定 不可調整|可動態增減|
|宣告|int a[10];|vector<int> v(10);|
|初始值|未宣告 -> 可能是亂數|預設為0(如果使用v(n))|
|訪問方式|a[i]|v[i]|
|加入元素|無法新增|v.push_back(x)|
|刪除元素|手動覆蓋|v.pop_back()、 v.erase()|
|清除內容|for迴圈覆蓋|v.clear()|
|取得陣列大小|for迴圈手動計算|v.size()|
|複製行為|for迴圈新增|v2 = v1|
|適用於|大小固定 小量資料|不固定大小 大量資料|
## set(集合)
set的底層實作是**紅黑樹(Red-Black Tree)**，他是一種**自我平衡**的**二元搜尋樹(Binary search tree, BST)**，二分搜尋下一篇章(STL-algorithm)會講。
簡單來講，`set`會**自動將重複出現的數字刪除**，並維持**由小到大排列**，而且查找、刪除和插入的時間複雜度都只有$O(\log n)$，非常高效。
#### 排序原理:
1. 對原始陣列進行**排序**。
2. 取**中間值**作為根節點。
3. 將比根大的數放右邊，比根小的數反之。
4. 左右子樹重複以上動作(**遞迴**)，直到所有數字放入樹中。
這能保證整棵樹的**平衡**，讓查找與操作保持高效率。
底下這張圖應該可以幫助理解。
### 宣告方法
宣告方法跟`vector`一樣，「**<>**」可以放入任何想要儲存的類型。
但不能夠 `s4(n)`**分配空間**。
```cpp=
set<int> s; // 去重 由小排到大
set<int, greater<>> s1; // 去重 但由大到小排列
set<set<int>> s2; // 內外層都會由小到大
set<int> s3 = {1, 2, 3}; // 直接預設初始值
```
### 其他常用函式
如果想要插入的值`set`已經存在此值，則**不會插入**。
`set`元素不得使用`s[i]`存取，因為他是一棵樹，要用**iterator查找**。
```cpp=
s.insert(x); // 插入x元素
s.erase(x); // 刪除x元素
s.erase(pos); // 刪除迭代器pos指向的位置
s.find(x); // 查找x元素 回傳指向x的iterator 找不到時回傳 s.end()
s.count(x) // 查找x元素的數量
s.empty(); // 判斷是否為空 回傳true false
s.clear(); // 清空所有元素
s.size(); // 回傳元素數量
```
比較特別的是，`set`可以取**聯集**、**交集**、**差集**、**對稱差集**。
```cpp=
set<int> A = {1, 2, 3}, B = {2, 3, 4};
vector<int> res;
// 聯集 res = {1, 2, 3, 4};
set_union(A.begin(), A.end(), B.begin(), B.end(), back_inserter(res));
// 交集 res = {2, 3};
set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(res));
// A的差集 res = {1};
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(res));
// B的差集 res = {4};
set_difference(B.begin(), B.end(), A.begin(), A.end(), back_inserter(res));
// 對稱差集 res = {1, 4};
set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(res));
```
如果還不知道 `s.begin()` `s.end()` -> [iterator(迭代器)](##iterator(迭代器))
關於vector -> [vector(動態陣列)](##vector(動態陣列))
### zerojudge練習題
[n369. 3. 免費仔](https://zerojudge.tw/ShowProblem?problemid=n369)
[b130. NOIP2006 1.明明的随机数](https://zerojudge.tw/ShowProblem?problemid=b130)
[c508. 去蟲](https://zerojudge.tw/ShowProblem?problemid=c508)
[d583. 幼稚的企鵝](https://zerojudge.tw/ShowProblem?problemid=d583)
[i399. 1. 數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
[c294. APCS-2016-1029-1三角形辨別](https://zerojudge.tw/ShowProblem?problemid=c294)
### 補充-multiset(多重集合)
`multiset`跟`set`幾乎相同，差別是`multiset`允許存在**重複元素**，適合用在需要**儲存重複數據、統計**或**排序**的題目。
```cpp=
multiset<int> ms;
ms.insert(3);
ms.insert(3);
cout << ms.count(3); // 輸出 2
ms.erase(ms.find(3)); // 僅刪除其中一個 3
ms.erase(--ms.end()); // 刪除最大值(最後一項)
```
## stack(堆疊)
`stack`就像把盤子一層一層堆起來: **後進先出(LIFO, Last In First Out)**，每次只能取用**最上方top(最後放入之值)** 的值。
此外，`stack`通常用在**非遞迴型dfs(depth first search, 深度優先搜尋)**，下一章(STL-algorithm)會再介紹。
`stack`是以**容器適配器(container adapter)** 的形式實作，他不是一個**獨立容器**，而是**包裝其他容器**所形成的特殊結構。`stack`預設底層是`deque`，也可以替換成`vector`或`list`，主要是差在**效率與記憶體配置上**，輸出結果**完全相同**。
```cpp=
stack<int> st; // 預設使用deque
stack<int, deque<int>> st_d; // 明確指定使用deque
stack<int, vector<int>> st_v; // 改用vector 尾端插入較快
stack<int, list<int>> st_l; // 改用list 常用於指標操作、鏈結結構
```
### 宣告方法
都跟 `vector` 一樣。比較特別的是，因為他是**容器適配器**，所以可以**修改底層容器**，如上方範例。
但不能像`vector`一樣`st(n)`**預設空間**，也不能`st = {1, 2, 3}` **分配元素**。
```cpp=
stack<int> st;
stack<stack<int>> st1;
```
關於vector -> [vector(動態陣列)](##vector(動態陣列))
### 其他常用函式
```cpp=
st.push(x); // 放入x元素
st.top(); // 取得最上方元素
st.pop(); // 移除最上方元素
st.empty(); // 判斷是否為空 回傳 true false
st.size(); // 取得元素數量
```
### stack翻轉字串(Reverse String)
此題用到`stack` **後進先出(LIFO)** 的概念，~~雖然相信你們都知道有reverse函式。~~
此方法時間複雜度為$O(n)$，同`reverse`函式。
雖然函式方便，但還是用`stack`寫看看啦，當作一次練習。
#### 方法一: stack
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s = "abcde";
stack<char> st; // 建立儲存char的stack
for (int i=0; i<s.length(); i++)
st.push(s[i]); // 逐一加入
while (!st.empty()) {
cout << st.top();
st.pop(); // 從頂端輸出 記得pop
}
// 輸出: edcba
}
```
#### 方法二: reverse
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s = "abcde";
reverse(s.begin(), s.end());
cout << s;
// 輸出: edcba
}
```
### stack括號匹配(Parentheses Matching)
判斷一個字串中的括號是否「**左右配對正確**」。
這也是 stack 最常出現的考題之一。
下方範例`() (()) () ) ()`多一個右括號。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s = "()(())())()";
stack<char> st;
bool invalid = false;
for (char c : s) { // 使用範圍式遍歷字串 結果同上索引式
if (c == '(') {
st.push(c); // 如果是左括號 加入st
} else {
if (st.empty()) { // 如果st是空的 匹配失敗
invalid = true;
break;
}
st.pop(); // 配對成功 記得pop
}
}
if (!st.empty()) invalid = true; // 比對完還有剩括號 匹配失敗
cout << (invalid ? "No" : "Yes") << '\n';
// 三元運算子 如果invalid輸出no 如果!invalid則輸出yes
// 輸出: No
}
```
### zerojudge練習題
[c123. 00514 - Rails](https://zerojudge.tw/ShowProblem?problemid=c123)
[b923. stack 堆疊的模板題](https://zerojudge.tw/ShowProblem?problemid=b923)
[i213. stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213)
[b838. 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838)
[e924. pC. 括號配對](https://zerojudge.tw/ShowProblem?problemid=e924)
[c700. 壞掉的隊列(queue)](https://zerojudge.tw/ShowProblem?problemid=c700)
## queue(佇列)
`queue`像是在**排隊**，先排進去的會先出來: **先進先出(FIFO, First In First Out)**。
此外，`queue`常常用於**bfs(breadth first search, 廣度優先搜尋)**，一樣下一章(STL-algorithm)會講。
`queue`也是**容器適配器**，預設底層同為`deque`，但只能替換成`list`，不支援**替換`vector`**，`vector`不適用前端操作。
```cpp=
queue<int> q; // 預設deque
queue<int, deque<int>> q_d; // 明確指定deque
queue<int, list<int>> q_l; // 改用list
```
### 宣告方法
同**stack**。
一樣不能`q(n)`以及`q = {1, 2, 3}`。
關於stack -> [stack(堆疊)](##stack(堆疊))
### 其他常見函式
```cpp=
q.push(x); // 最末端加入x元素
q.pop(); // 刪除最前端(第一個)元素
q.front(); // 取得第一個元素
q.back(); // 取得最後一個元素
q.empty(); // 判斷是否為空 回傳true false
q.size(); // 取得所有元素數量
```
### zerojudge練習題
[e564. 00540 - Team Queue](https://zerojudge.tw/ShowProblem?problemid=e564)
[e447. queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447)
[b138. NOIP2005 1.陶陶摘苹果](https://zerojudge.tw/ShowProblem?problemid=b138)
[e155. 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155)
### 補充-priority_queue(優先佇列)
顧名思義，是有「**優先權**」的佇列，所以他不是**先進先出(FIFO)**，而是每次都讓**數值最大**的元素先出來。
`priority_queue`是基於**heap(堆積)** 實作的容器適配器。他會維持一個「heap結構」，讓最大(或最小)的元素永遠在**最上面**。而他的預設底層是vector。
#### 宣告方法
```cpp=
priority_queue<int> pq; // 預設: 最大值優先
priority_queue<int, vector<int>, greater<>> pq1; // 搭配vector 改成最小值優先
```
#### 其他常見函式
```cpp=
pq.push(x); // 加入x元素
pq.pop(); // 刪除優先權最大的元素
pq.top(); // 取得優先權最大的元素
pq.empty(); // 判斷是否為空 回傳true false
pq.size(); // 取得所有元素數量
```
#### priority_queue輸出最大值
輸出與`multiset`相同，但`multiset`刪除元素要用到**迭代器**。
~~但聰明的你一定會想到可以用**範圍式for迴圈**遍歷~~，但這樣輸出完ms還是有值在裡面就是了。
同一題有很多種撰寫方法，只要答案對用什麼方式都可以，**自己喜歡最重要**。
##### 方法一: 使用priority_queue
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
priority_queue<int> pq;
pq.push(25);
pq.push(100);
pq.push(60);
pq.push(60);
while (!pq.empty()) {
cout << pq.top() << ' ';
pq.pop();
}
// 輸出: 100 60 60 25
}
```
##### 方法二: 使用multiset
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
multiset<int> ms;
ms.insert(25);
ms.insert(100);
ms.insert(60);
ms.insert(60);
while (!ms.empty()) {
cout << *prev(ms.end()) << ' '; // 同*(--ms.end()) *ms.rbegin()
ms.erase(prev(ms.end())); // erase不吃反向迭代器 不能寫ms.erase(ms.rbegin())
}
// 輸出: 100 60 60 25
}
```
##### 方法三: 使用範圍式遍歷multiset
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
multiset<int, greater<>> ms1;
ms1.insert(25);
ms1.insert(100);
ms1.insert(60);
ms1.insert(60);
for (int i : ms1)
cout << i << ' ';
// 輸出: 100 60 60 25
}
```
關於`multiset` -> [補充-multiset(多重集合)](###補充-multiset(多重集合))
關於iterator -> [iterator迭代器](##iterator(迭代器))
關於遍歷方法 -> [延伸-for迴圈遍歷輸出](###延伸-for迴圈遍歷輸出)
### 延伸-stack vs queue vs priority_queue
|比較項目|stack|queue|priority_queue|
| -------- | -------- | -------- | ------- |
|主要概念|後進先出(LIFO)|先進先出(FIFO)|視優先權(最大或最小)|
|預設底層|deque|deque|vector|
|插入位置|最頂端|最末端|隨機插入 但會排列|
|刪除位置|最頂端|最前端|優先權最高|
|遍歷|❌|❌|❌|
|隨機訪問|❌|❌|❌|
|預設順序|❌|❌|由大到小|
|改變排序|❌|❌|vector<int>, greater<>|
|宣告方式|stack<int> st;|queue<int> q;|priority_queue<int> pq;|
## map(映射表)
`map`是**有鍵序值容器(ordered associative container)**，底層實作是**紅黑樹**，每個`key`都對應一個`value`，不允許重複`key`，適合用在查表、記錄資料。`map`預設由`key`值小到大排列，跟`value`沒有關係，也可以使用`greater<>`倒序。插入、查找、刪除時間複雜度皆為$O(\log n)$。
### 宣告方法
```cpp=
map<string, int> mp; // 第一項是key 第二項是value
map<int, vector<pair<int, int>> mp1; // value可以是容器
map<vector<int>, int> mp2; // key也可以是容器
map<int, int, greater<>> mp3;
```
### 其他常用函式
```cpp=
mp[x] = 10; // key是x value是10
mp[x] = 20; // x的value被修改成20
mp.insert({key, value}); // 插入此項 如果存在此key則不插入
mp.find(x); // 判斷是否存在此key 回傳iterator 不存在回傳end()
mp.count(x); // 判斷有沒有這個key 回傳1 0
mp.erase(key); // 刪除指定key
mp.erase(it); // 刪除iterator指向的位置
mp.clear(); // 清空map
mp.size(); // 取得有幾項
mp.empty(); // 判斷是否為空 回傳true false
```
### map計算單字出現次數
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
map<string, int> cnt;
vector<string> words = {"apple", "banana", "apple", "cat", "banana"};
for (string w : words)
cnt[w]++; // 如果沒有這個key 建立一個value為0的key 然後再++
for (auto o : cnt)
cout << o.first << " 出現 " << o.second << " 次\n"; // 範圍式遍歷map
// 輸出:
// apple 出現 2 次
// banana 出現 2 次
// cat 出現 1 次
}
```
關於範圍式for迴圈 -> [延伸-for迴圈遍歷輸出](###延伸-for迴圈遍歷輸出)
### 補充-multimap(多重映射)
`multimap`跟`map`很像，但`multimap`允許**重複鍵**，因此他的存取方法有點不同。
#### 宣告方法
同`map`。
#### 常用函式
```cpp=
mm.insert({key, value}); // 只能這樣插入值
mm.erase(x); // 刪除所有key為x的值
mm.erase(it); // 用iterator刪
mm.find(key); // 找到key第一次出現位置的iterator
mm.equal_range(x); // 找到所有key是x的範圍
mm.size(); // 回傳大小
mm.empty(); // 判斷是否為空 回傳true false
mm.clear(); // 清空multimap
```
⚠️施工中
## deque(雙向佇列)
⚠️施工中
## list(雙向鏈結串列)
### forward_list(單向鏈結串列)
⚠️施工中
## array(靜態陣列)
~~這絕對是最沒必要存在的容器~~
`array`是**靜態陣列**，必須在**編譯期**就設定大小(在編譯期時就知道數值)，所以後面**沒有辦法修改大小**，適合用在固定數值的陣列當中(像是: RGB, 方向dx dy, 一週七天等)，如果長度不固定還是推薦使用[vector](##vector(動態陣列))。
### 宣告方法
```cpp=
array<int, 5> arr; // 宣告大小為5的array
int n = 5;
array<int, n> arr1; // 不合法 n不是編譯期常數
constexpr int n1 = 5; // 編譯期常數
array<int, n1> arr2; // 這樣才能宣告
int n2;
cin >> n2; // 執行期變數
array<int, n2> arr3; // 這樣是不合法的 n2是執行期才知道的值
```
### 其他常用函式
因為他也是`STL`的一員，也可以使用**函式**、**iterator**和**範圍式for迴圈**。
```cpp=
arr.size(); // 回傳所有元素數量
arr.empty(); // 判斷是否為空 回傳 true false
arr.fill(x); // 填充x元素
arr.front(); // 取得第0項之值
arr.back(); // 取得最後一項之值
arr[i]; // 隨機存取位置
```
### 延伸-vector vs array vs C陣列
|比較項目|vector|array|C陣列|
| ------- | ------- | ------- | ------- |
|記憶體位置|heap|stack|stack|
|固定大小|❌|✅|✅|
|STL函式|✅|✅|❌|
|[]隨機存取|✅|✅|✅|
|範圍式for|✅|✅|✅(C++11以上 寫法不同)|
|編譯期常數<br>(constexpr)|❌|✅|❌|
## unordered(雜湊容器)
### unordered_set
### unordered_map
### unordered_multiset
### unordered_multimap
⚠️施工中
## iterator(迭代器)
迭代器是一種**抽象指標(abstract pointer)**，可以用來存取`STL`容器中的元素，讓你能夠不管容器的底層結構(例如: `vector`、`set`、`map`等)，都能夠用**同一種方式**遍歷他、進行排序等操作。
### 常用函式
#### 1. 迭代器
```cpp=
v.begin(); // 取得陣列第0項的指標
v.end(); // 取得陣列最後一項+1位置的指標
```
#### 2. 反向迭代器
```cpp=
v.rbegin(); // 取得陣列最後一項的指標
v.rend(); // 取得陣列第0項前一項的指標
```
#### 3. 常量迭代器
c表示const，與前兩個相同，但**不允許**透過迭代器**改變容器內容**，通常在單純遍歷資料時使用。
```cpp=
v.cbegin();
v.cend();
v.crbegin();
v.crend();
```
因為這些輸出的都是「**指標**」，如果要輸出實際那個位置的值，要加上 __*__ 在開頭(**解引用**)。
```cpp=
vector<int> v = {1, 2, 3};
cout << *v.begin() << '\n'; // 輸出1
cout << *(--v.end()); // 輸出3
// *v.end() 會RE 要記得-1
```
### 宣告方法
```cpp=
vector<int> v = {1, 2, 3, 4};
// 從v.begin()一直執行到v.end()前一項 因為v.end()指向陣列最後一項+1位置
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
cout << *it << ' '; // 解引用取得值
// 但這樣每次宣告iterator都很麻煩 所以
for (auto it = v.begin(); it != v.end(); it++)
cout << *it << ' ';
// 使用 auto 讓電腦判斷陣列形式
```
### 移動迭代器
```cpp=
auto it = v.begin();
advance(it, 3); // 移動 3 個位置
cout << *it;
auto it2 = next(v.begin(), 2); // 取得 begin() + 2 的迭代器
auto it3 = prev(v.end(), 1); // 取得 end() - 1 的迭代器
```
當然這些指標不只可以遍歷輸出，他們更常用在**函式**當中。
#### 像是:
```cpp=
sort(v.begin(), v.end()); //由小排到大
sort(v.begin(), v.end(), greater<>()); // 由大排到小
sort (v.rbegin(), v.rend()); // 由大排到小
reverse(v.begin(), v.end()); // 翻轉陣列
find(v.begin(), v.end(), x); // 尋找x元素的迭代器
count(v.begin(), v.end(), x); // 計算x出現的次數
copy(v.begin(), v.end(), dest); // 整個陣列複製到dest
```
### zerojudge練習題
[a233.排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
[a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
[d190. 11462 - Age Sort](https://zerojudge.tw/ShowProblem?problemid=d190)
[c015. 10018 - Reverse and Add](https://zerojudge.tw/ShowProblem?problemid=c015)
[a015. 矩陣的翻轉](https://zerojudge.tw/ShowProblem?problemid=a015)
[i400. 2. 字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
### 延伸-for迴圈遍歷輸出
既然學完`iterator`，我們有了更多的遍歷(traversal)方法，以下列出三種常見的輸出方法。
#### 1. 索引式(index-based): 僅vector, deque支援
```cpp=
vector<int> v = {1, 2, 3};
for (int i = 0; i < n; i++)
cout << v[i] << ' ';
// 輸出: 1 2 3
```
#### 2. 範圍式(range-based for): stack, queue, priority_queue不支援
`Ｃ++11`以上支援
```cpp=
// 不可修改值(複製一份後輸出)
for (int i : v)
cout << i << ' ';
// 輸出: 1 2 3
```
```cpp=
// 可修改陣列內容
for (int &i : v) {
cout << i << ' ';
i++;
}
// 輸出: 1 2 3
// 陣列更新為 v = {2, 3, 4};
```
```cpp=
// 不可修改值 但直接取用陣列內容 沒有複製成本
for (const auto &x : v)
cout << x << ' ';
// 輸出: 1 2 3
```
map 遍歷獨有
```cpp=
map<int, int> mp = {{1, 10}, {2, 20}, {3, 30}};
for (auto m : mp)
cout << m.first << ' ' << m.second << '\n';
// 輸出:
// 1 10
// 2 20
// 3 30
```
```cpp=
// Ｃ++17 以上(結構化綁定 structured binding)
for (auto [key, val] : mp)
cout << key << ' ' << val << '\n';
// 輸出:
// 1 10
// 2 20
// 3 30
```
#### 3. iterator: stack, queue, priority_queue不支援
```cpp=
vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); it++)
cout << *it << ' ';
// 輸出: 1 2 3
```
# 總結
對不起還在思考中 快要生出來了
Thinking...
## 特別感謝
**ChatGPT**、**Copilot**、**廣大的網路資料**、**最愛的同學Tu**。
Sign in with Wallet
Connect another wallet