###### tags: `STL`
# STL Container
介紹各種container對應Insertion、Access、Erase、Find四種操作的相關成員函式及複雜度。
## Sequence containers:
### vector
相較於c/c++原生array，功能更加強大的動態array。
- Initial
| 初始化範例 | 解釋 |
| -------- | -------- |
| <ul><li> vector<int> first | 宣告空的 vector，沒有任何元素 |
| <ul><li> vector<int> second(4,10) | 四個數值為10的整數 |
| <ul><li> vector<int> third(10) | 建立一個長度為10的 vector |
| <ul><li> vector<int> v = {1, 2, 3};| 建立一個含有 1, 2, 3 的 vector |
1. Insertion
* push_back
* emplace_back
* insert
* emplace
* ***[emplace vs. without emplace](https://clay-atlas.com/blog/2022/11/29/cpp-vector-push-back-difference-emplace-back/)***
2. Access
* operator\[]
* at
* front
* back
* ***operator\[] vs. at***
在取到不存在的元素時，operator\[]會直接取得該index對應的記憶體值。而at則是會執行*throw std::out_of_range*，強制外部應用程式處理該錯誤。
3. Erase
* pop_back
* erase
* clear
4. Find
5. Size
* size
* max_size
取得當前系統允許的最大size上限。
* resize
* capacity
* reserve
* shrink_to_fit
將capacity壓到與size同等大小。

### deque
可以想像成是雙向的queue，對於deque來說，特色是在最前與最後push與pop元素都是非常快速的。
1. Insertion
* push_back
* emplace_back
* **push_front**
* **emplace_front**
* insert
* emplace
2. Access
* operator\[]
* at
* front
* back
3. Erase
* pop_back
* **pop_front**
* erase
* clear
4. Find
5. Size
* size
* max_size
取得當前系統允許的最大size上限。
* resize
* shrink_to_fit
將capacity壓到與size同等大小。
### list
類似雙向的link list，在任何位置新增及刪除元素都相當快速，但不支援random access。
1. Insertion
* push_back
* emplace_back
* push_front
* emplace_front
* **insert**
* emplace
2. Access
* **front**
* **back**
3. Erase
* pop_back
* pop_front
* **erase**
* clear
4. Find
5. Size
* size
* max_size
取得當前系統允許的最大size上限。
## Container adaptors:
### stack
對應資料結構裡的stack，特性是FILO，只支援access最頂端的元素。
1. Insertion
* push
* emplace
2. Access
* **top**
3. Erase
* pop
* clear
4. Find
5. Size
* size
### queue
對應資料結構裡的stack，特性是FIFO。
1. Insertion
* push
* emplace
2. Access
* **front**
* **back**
3. Erase
* pop
* clear
4. Find
5. Size
* size
### priority_queue
對應資料結構裡的heap，特性是可以保持權重最高的元素永遠在第一個，可以視為會自我排序的queue。
1. Insertion
* push
* emplace
2. Access
* **top**
3. Erase
* pop
* clear
4. Find
5. Size
* size
## Associative containers:
### set
類似於數學的集合，也可以視為value就是key的map。同樣的元素只會在set內有一個，也就是插入多個相同元素set內也只會有一個。set可以快速的插入、尋找及刪除元素。
1. Insertion
* insert
* emplace
2. Access
3. Erase
* erase
* clear
4. Find
* find
* count
* **lower_bound**
回傳set內第一個大於等於該元素的iterator
* **upper_bound**
回傳set內第一個大於該元素的iterator
* equal_range
6. Size
* size
* max_size
### map
類似於數學的fuction，每個在map內的key都會對應到一個value，map可以快速的插入、尋找及刪除元素。
1. Insertion
* insert
* emplace
* **operator\[]**
2. Access
* **operator\[]**
* at
4. Erase
* erase
* clear
5. Find
* find
* count
* lower_bound
回傳map內第一個大於等於該元素的iterator
* upper_bound
回傳map內第一個大於該元素的iterator
* equal_range
6. Size
* size
* max_size
## 總結圖表
<img src="https://miro.medium.com/v2/resize:fit:875/1*o3JJU8ZvHqbrvBZ134Ir7w.png">

# Reference:
* [cplusplus.com](https://cplusplus.com/)
* [STL container特性介紹](https://wither23265.medium.com/stl-container%E7%89%B9%E6%80%A7-cc28fd8bc246)
* [\[C++\] vector 中使用 push_back() 和 emplace_back() 的差別](https://clay-atlas.com/blog/2022/11/29/cpp-vector-push-back-difference-emplace-back/)