---
# System prepended metadata

title: STL Container
tags: [STL]

---

###### 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/)

