# STL
## iterator
又稱迭代器，幾乎每個STL容器都有iterator。內部是一個指標，指向容器內的元素。XXX.begin()代表該容器的第一個元素的迭代器，XXX.end()代表該容器的最後一個元素的後一個代迭器。大部分的iterator支援 ++ , -- , == , != 等運算子，少部分(如vector)可以支援 + , - , > , < 等
## pair
儲存兩個元素，第一個為first，第二個是second
適合拿來存座標等等兩個一組的東西
```cpp
pair<int,int> a; //創建一個pair，第一項與第二項都存int
pair<int,int> b{45,67}; //創建b，並指定1,2項(沒指定的話是0)
a.first=1; //a的第一項設為1
```
## vector
簡單來說就是陣列。內部實作也跟陣列相同，但是支援更多功能，如刪除、新增、迭代器等
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v; //創建一個存放int的空陣列
vector<double> v2(100); //創建一個存放double,長度為100的陣列(每項預設為0)
vector<int> v3(30,-1); //創建一個存放int,長度為30的陣列(每項預設為-1)
vector<int> v4={1,2,3,4,5}; //創建v4並指定內容
v4.push_back(1); //在v4陣列尾端放入1
cout<<v4[0]; //輸出v4陣列索引為0的元素(第1個)
v4.pop_back(); //刪除v4陣列尾端元素
v4.insert(v4.begin()+10,5); //在v4的第10項插入5
v4.erase(v4.begin()+9); //刪除v4的第9項
v4.erase(v4.begin(),v4.begin()+5); //刪除v4的第0到5項
v.clear(); //清空v
return 0;
}
```
因為vector與陣列一樣，資料是放在連續的記憶體中。
如果要新增第二項，必須創建一個更大的記憶體空間，並把所有元素移過去，所以時間複雜度為$O(n)$。插入也是一樣道理。
但是vector有一個特殊的機制，名為capacity(容量)
他與size不同，是預先留好的空間。這麼一來，push_back或是pop_back等最尾端的操作，就可以直接使用預留的空間而不需要搬動其他資料。複雜度$O(1)$
[圖源](https://shengyu7697.github.io/std-vector/)
常用操作:
```
v.reserve(100); //將容量設為100
v.resize(10); //將size設為10
v.resize(10,1); //將size設為10,每一項設為1
v.size(); //取出size
v.capacity(); //取出capacity
```
## list
STL的linked list(鏈結串列)。鏈結串列由node(節點)組成，每個節點當中存放value(值)以及指向下一個節點的指標
[圖源](https://www.softwaretestinghelp.com/linked-list/)
因為資料並不是存在連續的記憶體中，所以不支援隨機存取。
例如要存取list的第9項時，必須從1,2,3...的順序一路走到9
，所以複雜度為$O(n)$，十分難用。
但是因為每一個節點只關聯到前一個及後一個節點，所以刪除時只需要把前一個的指標指向後一個就好，複雜度$O(1)$，插入同理。
基本用法與vector相同，只是不能用list[i]來取出第i項。如果要取第i項可以把 list.begin() ++ i次
## stack
又稱堆疊，LIFO(後進先出)的資料結構。就像一疊盤子，每次要新增只能放在最上面，而要拿走也只能拿最上面的。通常可以用vector或是linked list來實作stack
[圖源](https://www.geeksforgeeks.org/stack-meaning-in-dsa/)
常用操作:
```cpp
stack<int> s; //創建一個堆疊
s.push(1); //新增元素1(在最上方)
cout<<s.top(); //輸出最上方的元素
s.pop(); //刪除最上方元素
```
顯而易見的，每項操作都是$O(1)$。雖然感覺很像劣化版vector，沒有什麼用處，但是需要LIFO時，因為操作比vector少，寫起來比較簡單，所以還是有一點用。
註:因為只能存最上面的那一項，所以沒有iterator
## queue
又稱貯列，FIFO(先進先出)的資料結構，就像排隊一樣，要加入的必須從最後面開始，離開的必須在最前面。跟stack同樣，可以用vector或list實作，也沒有iterator。所有操作皆為$O(1)$
```cpp
queue<int> q; //創建一個佇列
q.push(1); //新增元素1(最後方)
cout<<q.front(); //輸出最前方的元素
q.pop(); //刪除最前方元素
```
## unordered_map
STL中的hash table(雜湊表)。雜湊表由key跟value組成。key紀錄了value存放的位置。key可以是 int , double , string 等等。而把string轉成索引值(value存放的位置)的東西稱為hash_function(雜湊函數)，像是解碼器一樣。
[圖源](https://joe-chang.medium.com/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-hash-table-%E9%9B%9C%E6%B9%8A%E8%A1%A8-ffec829a4116)
那你可能會想，不會有兩個不同的key算出同一個索引值的情況嗎?
畢竟函數是可以多對一的。這種情況稱為碰撞，處理碰撞有數種方法，都已經寫在unordered_map裡面打包送你，雜湊函數也包含在裡面，我們只需要知道概念就好了。
常見操作:
```cpp
unordered_map<string,int> h(100); //創建一個雜湊表，key類型string，value類型int，大小100
h["kspgc"]=100; //把kspgc的value設為100
cout<<h["kspgc"]; //輸出kspgc的value
h.erase("kspgc"); //移除kspgc
cout<<h["kspgc"]; //找不到kspgc，會輸出0
```
插入、查詢、刪除只需要經過一次hash_func計算，複雜度$O(1)$
註:unordered_map的迭代器指向一個pair{key,value}
## map/set
BST(二元搜尋樹)，想法類似二分搜。由節點組成，每個裡面存key,value以及左右子節點。首先有一個根節點，插入的時候，如果新節點的key比較小，就往根節點的左節點移動，如果該節點沒有左節點，那新的節點就會成為他的左節點，反之則往右。
[圖源](https://blog.twshop.asia/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E4%BA%8C%E5%85%83%E6%A8%B9-binary-tree/)
查詢的時候，跟插入同樣，比該節點小就往左。因為每次可以走就可以刪掉比那個節點大/小的所有數字，複雜度是$O(\log n)$。刪除的時候需要分成三種狀況，但是複雜度仍然是$O(log n)$。
但是如果二元樹的太傾斜，如斜曲二元樹:
[圖源](http://yhhuang1966.blogspot.com/2018/06/c.html)
那麼每次查詢都要走完整條，時間複雜度會變成$O(n)$。於是就誕生了二元平衡樹，也就是會動態調整的二元樹，確保左邊跟右邊的數量是差不多的。而紅黑樹是二元平衡樹的一種，原理十分複雜，我也搞不懂，但是他很快，而且確保複雜度都是$O(log n)$。
而map跟set就是STL提供的紅黑樹，其中set的value跟key完全相同，所以只需要設定一個就好了。
常用操作:
```cpp
map<int,string> m; //創建m，key為int,value為string
set<int> s; //創建s，存int
m.insert({10,"jasper"}); //插入key=10,value="jasper"的元素
s.insert(100); //插入100
m.find(10); //找到key為10的節點，會回傳一個iterator
s.find(100); //找到100，會回傳一個iterator
m.erase(10); //把key=10的點刪掉
s.erase(100); //把100的刪掉
m.begin(); //最小節點的iterator
s.begin(); //最小值的iterator
```
map的iterator++為找到下一個大於他的最小值，花費$O(1)$
註:map的迭代器指向一個pair{key,value}
## multi map/set
如果新插入的key原本就存在map中時，map會自動把新的去掉，確保裡面沒有重複。而multimap則是允許重複的map，大部分的操作與map相同，除了:
```cpp
m.erase(10); //刪除所有key=10的資料
m.erase(m.find(10)); //刪除第一個key=10的資料
m.count(10); //key=10的節點數量
```
### 練習
[cses: Two Sum](https://cses.fi/problemset/task/1640)
[cses: Concert Tickets](https://cses.fi/problemset/task/1091)
## 排序/二分搜
STL內建的排序sort，複雜度$O(n\log n)$，(似乎)只能用在vector或陣列上
```cpp
vector<int> v={1,3,5,2,4,6,9};
sort(v.begin(),v.end(),greater<int>()); //從大到小牌
sort(v.begin(),v.end(),less<int>()); //從小到大排
sort(v.begin(),v.end()); //沒有寫就是less
```
### 練習
[zj:a104](https://zerojudge.tw/ShowProblem?problemid=a104)
[TCIRC:d010](https://judge.tcirc.tw/ShowProblem?problemid=d010)
[TCIRC:d011](https://judge.tcirc.tw/ShowProblem?problemid=d011)
### 自訂排序方式
如果你想用一些奇怪的規則排序，例如用個位數的大小排序:
```cpp
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a%10<b%10;
}
int main()
{
vector<int> v={91,43,25,52,74,86,109};
sort(v.begin(),v.end(),cmp);
return 0;
}
```
結果:
練習:[zj:a528](https://zerojudge.tw/ShowProblem?problemid=a528)
### 二分搜
限定已排序的資料。每次查找資料中間，太大往左，太小往右。每次保證刪掉一半的資料，複雜度$O(\log n)$
[圖源](https://ithelp.ithome.com.tw/articles/10280844)
STL內建兩種二分搜(記得先sort):
```cpp
lower_bound(v.begin(), v.end(), 10); //回傳v中"大於或等於"10的最小值的數的iterator
upper_bound(v.begin(), v.end(), 10); //回傳v中"大於"10的最小值的數的iterator
//如果找不到會回傳v.end()
```
### 練習
[TCIRC:b063](https://judge.tcirc.tw/ShowProblem?problemid=b063)
[ZJ:b315](https://zerojudge.tw/ShowProblem?problemid=b315)
[CSES: Factory Machines](https://cses.fi/problemset/task/1620)
[CSES: Multiplication Table](https://cses.fi/problemset/task/2422)
[APCS:牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)
[APCS:基地台](https://zerojudge.tw/ShowProblem?problemid=c575)
[TOI 初選:裁員風暴](https://zerojudge.tw/ShowProblem?problemid=k185)
[高市賽:開票策略](https://zerojudge.tw/ShowProblem?problemid=f430)
Sign in with Wallet
Connect another wallet