# C++ STL Containers 收納器簡單整理

###### tags: `C++`
###### Ref: https://docs.microsoft.com/zh-tw/cpp/standard-library/stl-containers?view=vs-2019
###### Ref: www.cplusplus.com

> 這些收納器都是透過 Template 實現的，因此可以裝任何型態的資料。

## Sequence Containers
> 有序收納器，存放的順序為使用者自訂。

### std::array
長度固定，存放空間為連續，支援 random access。

### std::vector
可以把 Vector 想像成一個會自動伸縮的 Array，它存放在一塊連續的空間，因此也可以透過平移 (offset) 指標的方式來搜尋。

Vector 是透過動態分配 array 空間的方式來實現的，因此如果超過了一定的 size (這個 size 可以透過 *capacity* 函數來查詢)，它必須要重新分配一塊新的更大的空間並把資料複製過去，這個過程非常耗時。也因此，Vector 所佔用的 memory 空間是比 Array 更大的，因為他會預留一些空間來減少重新分配的次數。

比起其他的收納器，Vector 的優勢在於它的 random access 以及對尾端的新增或刪除都很有效率。

### std::deque
Deque 即 double-ended queue，在 C++ 中通常是透過動態且多組的 array 來實作。

也就是說，它同樣支援 random access，且長度也是動態增長，但相較於起點固定的 Vector，Deque 的兩端都可以有效地插入及刪除。

和 Vector 最大的不同在於，Deque 並沒有存在連續的 memory 中，這意味著如果藉由指標的平移來試圖搜尋的話，這個動作的結果是無法預期的 (undefined behavior)。同時，Deque 的動態增長相較於 Vector 來說更有效，因為它並不需要複製全部的內容，但這也代表系統需要更多空間來儲存這些分散的區塊如何分配的。

### std::list
C++ 的 List 是 doubly linked list，不支援 random access，但對於任何位置的插入、刪除或移動，甚至串連兩段不同的 List 都非常有效率，在儲存空間的使用上不僅節省也很彈性。

但由於它的連續性是儲存在內部的，因此如果要存取某個位置 i 時，必須經過前 i-1 個節點 (或從後面出發) 才能找到。

### std::forward_list
這就是單向的 list，若要找到最後一個點，必須經過所有的點才行。

### Comparison
| | Vector | Deque | List |
| -------------- | ---------------- | -------------- | ----------- |
| 實現方法 | 連續陣列 | 不連續陣列 | 鏈結串列 |
| 隨機存取 | 可以 | 可以 | 無法 |
| 優勢 | 可隨機存取 可平移指標搜尋 | 可隨機存取 兩端皆可插入刪除 | 任何位置皆可插入或刪除 |
| 缺點 | 只有尾端可以操作 | 不可透過指標平移查找 | 不支援隨機存取 |
| 使用時機 | 不常新增資料 需要大量的隨機存取 | 需要從兩端操作 且需要隨機存取 | 不需要隨機存取 需要大量的新增或刪除 |

***

## Associative Containers
> 關聯性收納器，存放的順序視收納器而定，例如依大小存放等。

### std::map
Map 存放的是一組 (key, value) 數組 (key-value pair)，key 值用於排序及索引。

Map 是透過二元紅黑樹的資料結構實現，內部結構是有序的，因此支援一些基於排序的函數，如 *lower_bound*，*upper_bound*，*equal_range* 等。此外，Map 支援雙向的 iterator。

因此如果有範圍搜尋的需求的話，選用 *std::map*。

### std::unordered_map
除了二元樹之外，C++ 也有這個透過 hash 實現的 map，它內部是無序的，因此沒有上述的功能，但 hash 查找的時間為常數時間，是所有搜尋中最快的。然而，unordered_map 僅支援單向的 iterator。

因此如果不需要範圍搜尋的話，採用 *std::unordered_map*。

### std::set
Set 和 Map 最大的不同點，就是 Set 本身的 value 就是 key，換句話說，Set 排序及索引的依據即是存放的值本身。

其餘性質和 Map 類似。

### std::unordered_set
同理，unordered_set 和 unordered_map 類似，皆是無序的 hash 索引。

### 存放多組資料
無論是 Map 還是 Set 都只能存放一組資料，並不允許儲存重複的資料，例如 Map 中同樣的 key 只能對應一個 value，Set 中一個 value 只能儲存一次。

如果有儲存多組資料的需求的話，選用 *std::multimap*，*std::unordered_multimap*，*std::multiset*，*std::unordered_multiset*。