<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
## STL and Commonly Used Function
----
<div style="font-size:21px">
- Commonly Used Function
- math related function
- min / max / swap
- fill
- sort
- compare function
- reverse
- next / prev_permutation
- islower / isupper / isdigit / isalpha / tolower / toupper
- nth_element
- lower_bound / upper_bound
- unique
- STL
- iterator
- pair / tuple
- vector
- priority_queue
- stack / queue
- set / multiset
- map / multimap
- bitset
- list
</div>
----
## 語法查詢網站
- [Cplusplus](https://cplusplus.com/)
- [Cppreference](https://en.cppreference.com/w/)
---
## math related function
- abs(x) 回傳x的絕對值
- sqrt(x) 回傳x的平方根(浮點數)
- pow(a,x) 回傳a的x次方浮點數)
- ceil(x)/floor(x)/round(x) 回傳x向上取整/向下取整/四捨五入
----
## 三角函數
三角函數 cos(x) sin(x) tan(x)
反三角函數 acos(x) asin(x) atan(x) atan2(y, x)
數值單位全部都是弧度(radians)
角度 = 弧度 / (2π)*360
常用 pi = acos(-1)
```
#define PI acos(-1)
```
----
## 對數系列
- exp(x) 自然底數 e 的 x 次方
- log(x) 以 e 為底的對數
- log10(x) 以 10 為底的對數
- log2(x) 以 2 為底的對數
要換底請用換底公式
---
## sort
```cpp
#include<algorithm>
```
- 排序區間 [l, r) 的資料，複雜度為 $O(n\log n)$
- l, r 為指標或者迭代器
input
```
3 9 4 1 5
```
result
```
1 3 4 5 9
```
----
# 比大小
## min/max
```cpp=
#include<algorithm>//min/max
min(a, b)
min({a, b, c})
max(a, b)
max({a, b, c, d});
```
----
## 交換值
```cpp=
#include<algorithm>
swap(a, b)
```
----
## GCD 最大公因數
(需 c++14 後才能使用)
```cpp=
#includ<algorithm> //gcd
#include<iostream>
int main(){
int a, b; cin >> a >> b;
cout << __gcd(a, b) << endl;
}
```
a 和 b 的最小公倍數 = a * b / gcd(a, b)
----
## fill
把區間 [l, r) 的值都設成 x，l, r 為指標或者迭代器
```
#include<iostream>
#include<algorithm>
int main(){
int n = 5;
int arr[8]={0,1,2,3,4,5,6,7};
fill(arr+1, arr+5, 10);
}
```
arr 的結果為 {0,10,10,10,10,5,6,7}
----
## sort 用法
排序區間 [l, r)，l, r 為指標或者迭代器
```
sort(l, r);
```
### 範例
```cpp=
#include<iostream>
#include<algorithm> // sort
int arr[48763]={4, 8, 7, 6, 3};
int main(){
sort(arr,arr+5);
}
```
結果為 3, 4, 6, 7, 8
----
## 自訂比較關係
如果不想由小排到大，想由大排到小?
----
寫一個函式，
告訴編譯器你要怎麼排!
----
## compare function
傳入兩個參數 lhs, rhs，作為比較對象
lhs(left hand side) 代表較左邊的元素
rhs(right hand side) 代表較右邊的元素
可以想成希望在左邊的元素大於右邊的元素，
```cpp=
#include<iostream>
#include<algorithm> // sort
bool cmp(int lhs, int rhs){ // compare function
return lhs > rhs;
}
int arr[5] = {3, 2, 7};
int main(){
sort(arr, arr+3, cmp);
}
```
----
## 例題
### [UVA11321 — Sort! Sort!! and Sort!!!](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2296)
給你 $n$ 個整數與整數 $m$，排序順序如下 :
1. 按照 ```mod m``` 由小到大
2. 餘數相等則奇數在偶數前面
3. 如果同為奇數則由大到小
4. 如果同為偶數則由小到大
----
## 比較函式
1. 按照 ```mod m``` 由小到大
2. 餘數相等則奇數在偶數前面
3. 如果同為奇數則由大到小
4. 如果同為偶數則由小到大
```cpp=
bool cmp(int lhs, int rhs){
if((lhs % m) != (rhs % m)) return (lhs % m) < (rhs % m);
if ((lhs&1) != (rhs&1)) return (lhs&1) > (rhs&1);
if(lhs&1) return lhs > rhs;
else return lhs < rhs;
}
```
----
## reverse
把區間 [l, r) 翻轉，l, r 為指標或迭代器
```cpp=
#include<algorithm> //reverse
int arr[5] = {1,2,3,4,5};
reverse(arr, arr+5);
```
arr 的結果為 \{5,4,3,2,1\}
----
## next / prev_permutation
- next_permutation 產出的下一個排列都會比原本的字典序還大，而 prev_permutation 則相反
- 如果一開始的排列是字典序最小的，就可以用 next_permutation 產生出全部的排列。
----
## 用法
產生區間 [l, r) 的下一個排列，若不存在則回傳 false，反之回傳 true
均攤複雜度 $Ω(1)$，最差 $O(n)$
input
```
1 3 2
```
result
```
2 1 3
```
----
```cpp=
#include<algorithm>
int arr[4] = {3,2,4,1};
next_permutation(arr, arr+4);
```
result
```
3 4 1 2
```
----
### 產生所有排列
如果序列一開始為最小字典序，
透過 next_permutation 不斷變成下一大的順序，
可以產生所有排序
```cpp=
int n = 3;
int arr[3] = {1, 2, 3};
do{
for(int i = 0; i < n; i++) cout << arr[i] << " \n"[i+1==n];
} while(next_permutation(arr, arr + n));
```
#### 輸出：
```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```
----
## 判斷/轉換字元
```cpp=
#include<cctype>
```
- islower\(c\) 判斷字元 c 是否為小寫字母
- isupper\(c\) 判斷字元 c 是否為大寫字母
- isalpha\(c\) 判斷字元 c 是否為字母
- isdigit\(c\) 判斷字元 c 是否為數字
- tolower\(c\) 回傳字元 c 的小寫字母
- toupper\(c\) 回傳字元 c 的大寫字母
----
## nth_element
```nth_element(l, l+k, r)```
將此區間 [l, r) 第 k 小的數放在左邊數來第 k 個位置，
且 [l , k) 皆比 k 小，(k , r) 皆比 k 大，
但這兩個區間內是無序的
----
## 範例
```cpp=
int arr[1e5+5]={};
bool cmp(int x,int y){
return x>y; //更改為降序排列
}
int main(){
for(int i=1;i<=100;i++) arr[i]=i;
nth_element(arr+1,arr+50+1,arr+100+1);
}
```
結果 : 1~49 (無序排列) , 50 , 51~100 (無序排列)
- 複雜度為平均 $O(n)$
- 可以加入第四個函數傳入自訂比較函數 ```nth_element(l, l+k, r, cmp)```
----
## 例題 --- [CF 412B](https://codeforces.com/problemset/problem/412/B)
題意:
給你 N 個數字，以及 K，求出第 K 大的數字是多少
```
6 4
100 20 40 20 50 50
```
答案為40
----
## 實作
```cpp=
#include<iostream>
#include<algorithm>
int n,k,arr[100005];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
nth_element(a+1,a+k,a+n+1,greater<int>());
cout<<a[k-1];
return 0;
}
```
greater<> 為內建的大於比較函式
----
## lower_bound / upper_bound
### lower_bound(l, r, x)
找到區間 [l, r) 範圍內第一個**大於等於** x 的值的位置。
### upper_bound(l, r, x)
找到區間 [l, r) 範圍內第一個**大於** x 的值的位置。
<br>
以上兩個函數裡面所尋找的區間必須為已排序的才可以正常使用
如果沒找到則會回傳位置 r (最後一項的下一項)
----
## 範例
時間複雜度 $O(\log n)$
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005];
int main(){
int n,x;
cin>>n;
for(int i=0;i<n;++i)cin>>a[i];
sort(a,a+n);
cin>>x;
cout<<lower_bound(a,a+n,x)-a<<'\n';
cout<<upper_bound(a,a+n,x)-a<<'\n';
//通過找到的位置減去起始位置begin,得到索引值
return 0;
}
```
一樣可以使用自訂比較函式
lower_bound ( first , last , value , cmp)
upper_bound ( first , last , value , cmp)
----
## unique
把區間內連續相同元素刪除到只留一個，
回傳值為沒被刪除的元素的下一項 指標/迭代器
複雜度 $O(n)$
input
```
4 2 1 1 1 5 2 2 4 4
```
result
```
4 2 1 5 2 4 x x x x
```
注意原陣列大小不會改變，相異元素之後的值無法保證為何
----
## 用法
unique(l, r) // 將區間 [l, r) 內連續相同元素刪除到只留一個，
```cpp=
#include<iostream>
#include<algorithm>
int n = 10;
int arr[10] = {4, 2, 1, 1, 1, 5, 2, 2, 4, 4};
int main(){
sort(arr, arr+n);
int k = unique(arr, arr+n) - arr;
cout << k << endl;
for(int i = 0; i < k; i++) cout << arr[i] << " \n"[i+1==k];
}
```
result
```
6
4 2 1 5 2 4
```
----
常用於離散化，把一段的區間 [l, r) 的資料只留下相異的元素各一個
作法
1. sort 區間 [l, r)
2. unique [l, r) 並記錄回傳的指標/迭代器
----
結果為原始陣列所有相異元素並且已排序
```cpp=
#include<iostream>
#include<algorithm>
int n = 10;
int arr[10] = {4, 2, 1, 1, 1, 5, 2, 2, 4, 4};
int main(){
sort(arr, arr+n);
int k = unique(arr, arr+n) - arr;
cout << k << endl;
for(int i = 0; i < k; i++) cout << arr[i] << " \n";
}
```
result
```
4
1 2 4 5
```
---
## Iterator & STL container
- pair / tuple
- iterator
- vector
- stack / queue
- set / multiset
- map / multimap
- priority_queue
- bitset
- list
----
### pair / tuple
分別在 \<utility\> 和 \<tuple\> 中
偷懶用資料結構，分別是可以用來宣告裝 2 個東西/多個東西的變數
----
### pair
常用來儲存二維平面上的點 (x, y) 之類
* 宣告
```cpp
pair<int,int>
pair<double,int>
```
* 取值
```cpp=
pair<int,int> a
a.first (可以取到第一個值)
a.second (可以取到第二個值)
```
----
對 pair 的元素 sort，會先比較 first 大小，相同再比較 second 的大小
```
#include<iostream>
#include<utility>
using namespace std;
pair<int, int> point[10];
int main(){
for(int i = 0; i < 5; i++) cin >> point[i].first >> point[i].second;
sort(point, point+5);
int a, b;
point[0] = make_pair(a, b);
}
```
----
### 使用範例：tuple
* 宣告
```cpp
tuple<int, int, int>
tuple<double, int, long double, ...(還可以塞很多東西)>
```
* 取值
```cpp=
tuple<int, int, int> a
get<0>(a) (可以取到第一個值)
get<2>(a) (可以取到第三個值)
----
make_tuple 可以把元素合併成 tuple
```cpp
#include<iostream>
#include<tuple>
using namespace std;
tuple<string, int, int, double> item[10];
int main(){
string s; int a, b; double d;
for(int i = 0; i < 5; i++){
cin >> s >> a >> b >> d;
item[i] = make_tuple(s, a, b, d);
}
sort(item, item+5);
tie(s, a, b, d) = item[0];
cout << s << " " << b << " " << d << " " << get<0>(item[1]) << endl;
}
```
----
### Iterator 迭代器
迭代器是用來遍歷容器的東西，由於有些容器不像陣列能用下標 (index) 遍歷，迭代器便能用來遍歷這類容器。
----
c++ 的迭代器皆被實作的與指標相似，用遞增運算子 (\+\+it \/ it\+\+) 來移動到下一項，且用反指標運算子(*it)來取得當前項的值。
多數還支援遞減運算子(\-\-it \/ it\-\-) 移動到前一項(稱作雙向迭代器)
有些支援隨機存取(random access)， +\/- 運算子(it+k \/ it-k) 一次能移動多項
----
對於一個容器，分別有代表頭尾的迭代器，其中頭代表首項，而尾代表最後一項的下一項，因此遍歷方式通常是for(it=begin;it!=end;it++)
對於陣列 (C-style array)，其迭代器就是指標，且頭尾分別是 arr/arr+n，對於 STL 內的容器，其迭代器是C::iterator，且頭尾分別是arr.begin() / arr.end()
此外STL內還有實作反向迭代器用來從最後一項開始往前遍歷，其形態是 C::reverse_iterator 頭尾分別是 arr.rbegin() / arr.rend()
----
### vector
```
#include<vector>
```
動態陣列。有時候我們無法預估陣列所需要宣告的長度，又必須宣告陣列，這時會選用 vector
----
- vector 的常用函式 : push_back , pop_back , size , empty , begin , end
clear, resize, assign
- 須注意的是若等到 vector 空間不夠裝，vector 會自動安排記憶體，但這麼做常數比較大，所以通常在使用前會先預設一些記憶體位置給 vector
* 我們會使用 reserve() 。e.g. `vector.reserve(100005)`
* 或是直接在宣告時用建構元 (constructor) 指定大小。 e.g. `vector<int> vec(n)`
- insert, erase 複雜度為 $O(n)$ ，請勿亂用
----
實際演練 : 常用函式
```cpp=
#include <iostream>
#include <vector> // vector 的標題檔
using namespace std;
int main() {
vector<int> Mega;
//宣告一個 vector 名稱叫 Mega 用來裝 int 元素
//裡面的容器是空的
for (int i=1; i<=5; i++) Mega.push_back(i);
for (int i=5; i>=1; i--) Mega.push_back(i);
cout << Mega.size() << "\n";
for (int i=1; i<=4; i++) Mega.pop_back();// 將 vector 尾端元素刪掉
cout << Mega.size() << "\n";
cout << Mega.empty() << "\n";
// empty() 函式為查詢 vector 裡面是否有元素
// 回傳值為 bool 1 裡面沒有元素 0 則是有
Mega.clear();
cout << Mega.empty() << "\n";
}
```
----
實際演練 : 使用 index 遍歷
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<char> roy;
for (int i=0; i<26; i++) {
char c = i + 'A';
roy.push_back(c);
}
for (int i=0; i<roy.size(); i++) {
cout << roy[i] << " ";
}
cout << roy[5] << "\n";
cout << roy[0] << "\n";
// 查詢單一個元素可用陣列方式查詢
}
```
----
實際演練 : 遍歷 iterator 遍歷
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vt;
vector<int>::iterator iter;
for (int i=95; i<=100; i++) {
vt.push_back(i);
}
iter = vt.begin();
for(iter = vt.begin(); iter != vt.end(); iter++) {
cout << *iter << "\n";
// 一定要 「 * 」 號
}
}
```
----
### stack
```
#include<stack>
```
堆疊是一種先進後出的結構，像是疊盤子一樣，先放下去的會最慢被拿出來。
----
- stack的常用函式 : emplace(push) , size , empty , top , pop .
- 不支援隨機存取：O(N) 查找速度慢：O(N) 在集合中增刪元素很快：O(1)
----
實際演練:
```cpp=
#include <iostream>
#include <stack> // stack 的標題檔
using namespace std;
int main() {
stack<int> Stk;
//宣告一個 stack 名稱叫 stk 用來裝int元素
//一開始裡面的容器是空的
for (int i=4; i<=10; i++) {
Stk.push(i);
}
cout << Stk.top() << "\n";
// 輸出 stack 最上層的元素，所以會輸出 10
Stk.pop();
// 刪除 stack 最上層的元素
cout << Stk.top() << "\n";
// 輸出 stack 最上層的元素，所以會輸出 9
cout << "裡面有多少元素" <<Stk.size() << "\n";
// 查詢 stk 裡面有幾個元素，裡面元素有 4 5 6 7 8 9共六個，所以會輸出 6
cout << Stk.empty() << "\n";
// empty() 函式為查詢 stack 裡面是否有元素
// 回傳值為bool 1 裡面沒有元素 0 則是
//清除 stack的元素
while(Stk.size() != 0) { // 或是 while(Stk.empty == 0)
Stk.pop();
}
cout << "裡面有多少元素" << Stk.size() << "\n";
cout << Stk.empty() << "\n";
}
```
----
# 超\*經典例題
stack之括弧匹配
想法:
給予一個字串並包含了括號 '[', ']', '(', ')' 和 '{', '}'，請驗證該字串中的括號是否合法配對。
也就是 "([])", "{()}", "[]" 為合法配對，但是 "(]", 或 "([)]" 就是不合法配對。
規律:
* 括號數量一定是偶數
* 有左邊系列括號，就一定有右邊系列括號
* 越慢出現的左邊括號，他的右邊括號就越早出現(順序相反)。
----
### queue
```cpp
#include<queue>
```
佇列是一種先進先出的結構，像是水管一樣的單向道，最早進去的會最先通出來。
----
- queue的常用函式 : push , size , empty , front , pop .
- 不支援隨機存取：O(N) 查找速度慢：O(N) 在集合中增刪元素很快：O(1)
- 常用在BFS
----
實際演練:
```cpp=
#include <iostream>
#include <queue> // queue 的標題檔
using namespace std;
int main() {
queue<int> que;
//宣告一個 queue 名稱叫 que 用來裝int元素
//一開始裡面的容器是空的
for (int i=4; i<=10; i++) {
que.push(i);
}
cout << que.front() << "\n";
// 輸出 queue 最上層的元素，所以會輸出 4
que.pop();
// 刪除 queue 最上層的元素
cout << que.front() << "\n";
// 輸出 queue 最上層的元素，所以會輸出 5
cout << "裡面有多少元素" <<queue.size() << "\n";
// 查詢 queue 裡面有幾個元素，裡面元素有 5 6 7 8 9 10共六個，所以會輸出 6
cout << que.empty() << "\n";
// empty() 函式為查詢 queue 裡面是否有元素
// 回傳值為bool 1 裡面沒有元素 0 則是
//清除 queue的元素
while(que.size() != 0) { // 或是 while(que.empty == 0)
que.pop();
}
cout << "裡面有多少元素" << que.size() << "\n";
cout << que.empty() << "\n";
}
```
----
### 經典例題環節:
使用兩個 stack 去實作出 queue 的功能
作法:
始終維護 s1 作爲存儲空間，以 s2 作爲臨時緩衝區。
入隊時，將元素壓入 s1。
出隊時，將s1的元素逐個“倒入”（彈出並壓入）s2，將 s2 的頂元素彈出作爲出隊元素，之後再將 s2 剩下的元素逐個“倒回” s1。
----
### priority_queue
可以很快很方便的加入元素 或 取出當前最優先的元素
常用於優化複雜度
----
* 在標頭檔 queue 裡面
* priority_queue 裡面可以塞 int , string , long long , 實作原理是 max_heap 在運作
* 為一序列容器 是一個帶優先級的 queue
* priority_queue 的常用函式 : push , size , empty , top , pop .
----
### priority_queue 複雜度分析
* push() 新增元素，複雜度 O(log n)
* size() 取得目前元素數量，複雜度 O(1)
* top() 取得目前最高優先（數值最大）的元素（不會刪掉），複雜度 O(1)
* pop() 刪掉目前最高優先（數值最大）的元素，複雜度 O(log n)
----
實際演練:
```cpp=
#include <queue>
priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > pq1; //從小到大 變成min_heap
pq.push(5);
pq.push(8);
pq.push(4);
// 元素可重複，會個別保留
pq.push(5);
cout << pq.size() << "\n";
cout << pq.top() << "\n";
pq.pop();
cout << pq.size() << "\n";
cout << pq.top() << "\n";
cout << pq.empty() << "\n";
```
----
### 題目演練 --- 動態中位數
對每一個輸入，請輸出到現在為止已輸入的數的中位數。
```
輸入: 輸出:
1 1
3 2
4 3
60 3
70 4
50 27
2 4
```
----
## 中位數
維護兩個 pq(priority_queue)，
其中一個 pq 維護大於等於中位數的數值
另一個 pq 維護小於中位數的數值
如此一來，中位數必定為大於等中位數那堆的最小值
----
## 取中位數
大於等中位數的 pq 每次取最小值
即為中位數
```cpp
priority_queue<int, vector<int>, greater<int>> big;
cout << big.top() << endl;
```
----
## 加入一個新元素
判斷當前加入的新元素 x 如果小於中位數，則加入維護小的 pq
否則加入維護大的 pq
```cpp
if(x < big.top()) small.push(x);
else big.push(x);
```
----
## 維護兩個 pq 的大小
為了讓中位數固定在比較大的那堆的最小值，
兩堆 pq 的大小至多只能差一
因此每次新增完元素，
如果小的那堆太多要把最大的元素丟過去大的那堆
反過來則大的最小丟去小的那堆
```cpp
priority_queue<int> small;
priority_queue<int, vector<int>, greater<int>> big;
while(small.size() >= big.size()) big.push(small.top()), small.pop();
while(small.size()+1 < big.size()) small.push(big.top()), big.pop();
```
----
### set (集合)
```
#include<set>
```
- 插入一個元素
- 從集合中刪除一個元素
- 查詢元素有沒有在集合裡面
- 查詢集合內最小/大值
- 查詢集合內 $> x$ 或 $\ge x$ 中的最小元素
----
- set 是有序的，對 set 遍歷時，會以定義的大小順序遍歷，預設是由小到大
- 大多數操作皆為 $O(\log N)$
- set 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound
----
### 使用範例 --- 插入、刪除元素
```cpp
set<int> s; // []
s.insert(1); // s = [1]
s.insert(5); // s = [1, 5]
s.insert(3); // s = [1, 3, 5]
s.insert(2); // s = [1, 2, 3, 5]
s.insert(1); // s = [1, 2, 3, 5]
s.erase(3); // s = [1,2,5]
```
----
### 使用範例 --- 插入、查詢元素
```cpp
set<pair<int,int> > s; //[]
s.insert({1, 2}); // [{1, 2}]
s.insert({2, 1}); // [{1, 2}, {2, 1}]
s.insert({2, 1}); // [{1, 2}, {2, 1}]
s.insert({3, 5}); // [{1, 2}, {2, 1}, {3, 5}]
s.count({2, 1}); //return 1，代表 {2, 1} 有在集合內;
s.count({5, 3}); //return 0
```
----
### 使用範例 --- 插入元素、找最小/大值
```cpp
set<int> s; // []
s.insert(1); // s = [1]
s.insert(5); // s = [1, 5]
s.insert(3); // s = [1, 3, 5]
s.insert(2); // s = [1, 2, 3, 5]
cout << *s.begin() << endl; // 1
cout << *s.rbegin() << endl; // 5
```
----
### 使用範例 --- 插入元素、找第一個大於等於 x 的元素
如果沒找到則回傳 end()
```cpp
set<int> s; // []
s.insert(1); // s = [1]
s.insert(5); // s = [1, 5]
s.insert(3); // s = [1, 3, 5]
s.insert(2); // s = [1, 2, 3, 5]
if(s.lower_bound(3) != s.end())
cout << s.lower_bound(3) << endl;
else
cout << "NOT FOUND" << endl;
```
----
### 使用範例 --- 插入元素、找第一個大於 x 的元素
如果沒找到則回傳 end()
```cpp
set<int> s; // []
s.insert(1); // s = [1]
s.insert(5); // s = [1, 5]
s.insert(3); // s = [1, 3, 5]
s.insert(2); // s = [1, 2, 3, 5]
if(s.lower_bound(3) != s.end())
cout << s.upper_bound(3) << endl;
else
cout << "NOT FOUND" << endl;
```
* lower_bound(s.begin(), s.end(), x) **複雜度為 $O(n)$**
* s.lower_bound(x) 複雜度才是 $O(\log n)$
----
### map
```
#include<map>
```
映射，基本上就是多了個對應值的set，單位型態為 pair<key,value>
用法跟 set 很像，但多了 operator[] 可以取值或存值。
----
* 大多操作皆為 $O(\log n)$
* map 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound.
----
### 使用範例：
```cpp
map<int, int> mp;
mp[3] = 1; //[3] = 1,
mp[2] = 2; //[2] = 2, [3] = 1;
mp[3] = 5; //[2] = 2, [3] = 5;
```
<!-- 加個 string 當 key 的粒子-->
----
### 使用範例：
```cpp
map<string,int> mp; // map 還可以用 string 當 key
mp["qwer"] = 1;
mp["abc"] = 2;
```
----
### multiset / multimap
* key 可以重複的 set / map
* 由於 key 會重複，因此少了 [ ]operator
* 大多操作皆為 $O(\log n)$
* 函式與 set / map 類似
----
### 使用範例：
```cpp
multiset<int> s; //[]
s.insert(1); // [1]
s.insert(2); // [1, 2]
s.insert(3); // [1, 2, 3]
s.insert(1); // [1, 1, 2, 3]
s.count(1); //return 2;
s.erase(1); //[2, 3]
```
使用 erase(x) 會把全部值為 x 的元素刪除
如果只要刪除一個可以使用 s.erase(s.find(x)) 刪除
----
### 使用範例：
```cpp
multimap<int, string> mp; //[]
mp.insert({1, "c8763"});
mp.insert({1, "38763"});
mp.insert({2, "1234"});
mp.insert({4, "mpmp"});
mp.count(1); // return 2
```
----
### bitset
```cpp
#include<bitset>
```
可看作是 bool 陣列，支援位元運算，且成員函數多為位元相關函數，
用在位元運算常數非常小，
沒有要做位元運算別亂用(用 vector\<bool\> 就好)
----
- 但長度必須是常數
- 常用函式：count、size、test、any、none、all、set、reset、flip。
----
### 使用範例：
```cpp
#include<bitset> //bitset
#include<iostream>
bitset<10> a = 7;
bitset<10> b(10);
bitset<10> c("10010");
int main(){
b = 5; //101
b >>= 1; //10
cout << b << endl;
cout << (a|c) << " " << (a&c) << " " << (a^c) << endl;
}
```
----
## list
```cpp
#include<list>
```
C++ 內建的 linked-list，可以在 O(1) erase, insert
但沒有支援隨機存取(random access)， 無法使用 index 查詢
----
常用函數: push_back, push_front, pop_back, pop_front, insert, erase, size
----
## 範例
```cpp
#include<list>
#include<iostream>
using namespace std;
int main(){
list<int> arr;
arr.push_back(3); // [3]
arr.push_back(4); // [3, 4]
list<int>::iterator iter = prev(arr.end()); // 儲存 arr 最後一個元素的iterator
arr.push_back(1); // [3, 4, 1]
arr.push_front(10); // [10, 3, 4, 1]
arr.erase(iter); //[10, 3, 1]
}
```
----
## 例題 --- 刪除元素
- 給一個長度為 $n$ 的排列，有 $q$ 筆操作，操作為每次把數字 x 以及左右相鄰的元素刪除，求最後序列的樣子
input
```
8 2
1 5 8 3 6 4 7 2
3
4
````
output
```
1 2
```
[1 5 8 3 6 4 7 2] $\to$ [1 5 4 7 2] $\to$ [1 2]
----
暴力找某個元素的位置最差情況需要遍歷整個序列 $O(n)$
但太慢了
因此通常會搭配 map，把每個元素儲存在 list 中的位置儲存在 map 中
```cpp
#include<list>
#include<iostream>
using namespace std;
int main(){
list<int> arr;
map<int, list<int>::iterator> mp;
int n; cin >> n;
for(int i = 0, x; i < n; i++){
cin >> x;
arr.push_back(x);
mp[x] = prev(arr.end());
}
}
```
----
移除操作 --- 把數字 x 以及左右相鄰的元素刪除
```cpp=
void remove(int x){
list<int>::iterator it = mp[x];
if(it != arr.begin()) arr.erase(prev(it));
if(next(it) != arr.end()) arr.erase(next(it));
arr.erase(it);
}
```
----
map 維護儲存、查詢為 $O(\log n)$，
$q$ 筆操作總複雜度為 $O(q\log n)$
---
建議每種語法都套過題目一遍試試看，
以免比賽中要用到不會用
也不用硬背起來，要用到再查語法，多寫幾次自然後就記得了。
[Problem List](https://vjudge.net/contest/576017)
{"title":"STL and Commonly Used Function","contributors":"[{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":22772,\"del\":3551}]","description":"Commonly Used Function"}