---
tags: Cpp
---

# C++ STL 筆記

此筆記最終目標是完整介紹 STL（Standard Template Library，標準模板庫）的相關項目和功能，若有任何建議、疑問（例如難以閱讀的地方）或錯誤還請希望告知。

基本上大多資料搬運自 [C++ reference](https://en.cppreference.com/w/cpp)（他們的資料太完整了，感恩讚歎）。
另外加上部分來自社群的討論，以及少部分自己的理解。

:::warning
:warning: 目前此項目僅完成 container 部分，並且有可能隨時會進行修改或重新編排；此外更有可能繁忙或懶惰棄坑導致未能修正錯誤，因此請將本文作爲引索或參考，再去詳閱相關的專文是比較建議的做法。
:::

## Container
Container 幾乎可以說是 STL 中最重要的功能。各種 library 以及官方的演算法都是圍繞 STL 容器展開的。C++ reference 將容器分爲底下幾種。

- Sequence containers
- Associative containers
- Unordered associative containers
- Container adaptors

### Sequence containers
基本的資料結構，sequential 雖然直翻是序列的，但大致上可以想像成資料是以線性（一個接一個有順序，而不會像樹一樣分叉）的排列方式儲存，因此可以「按照順序」去讀寫。

- `array` (C++11): static contiguous array
- `vector`: dynamic contiguous array
- `deque`: double-ended queue
- `forward_list` (C++11): singly-linked list
- `list`: doubly-linked list

既然都是線性的排列儲存，那麼這幾種的差別在哪？基本上是根據資料是否需要滿足：

- 記憶體配置：
- 只有 `array` 和 `vector` （since C\+\+03）保證連續排列。
- 只有 `array` 不能動態配置（但需要的額外記憶體最少）。
- 隨機存取效率 v.s. 隨機插入/刪除效率：
- `array`, `vector` 和 `deque` 皆可進行 `O(1)` 隨機存取。
- `list` 和 `forward_list` 有較好的 `O(1)` 隨機插入/刪除效率（連續插入/刪除優勢尤其明顯）。
- 迭代器 (iterator) 穩定性：
- 不同的容器可能會造成迭代器在不同的行爲（例如插入/刪除）後失效。
- 由於這個問題的細節相當複雜，建議需要時可以參考 [Stackoverflow - Iterator invalidation rules for C++ containers](https://stackoverflow.com/q/6438086)
- 反向迭代
- 很明顯的 `forward_list` 不能反向迭代，但比 `list` 省空間。
- 資料開頭插入/刪除
- `vector` 的開頭操作和隨機插入/刪除一樣爛。

:::info
:information_source: 有些人可能會發現，爲什麼在這裡有 `std::deque`，但 `std::queue` 這個容器反而被放到後面的 adaptor 分類去了。這不也是一個 sequential container 嗎？
::: spoiler
在 STL 裡，`stack`, `queue` 這類的抽象概念容器是以「高階容器」的概念被實作；相對的 `vector`, `deque`, `list` 之類的則是相對底層的容器——高階容器的底層是用他們來實作的。

對於 `stack`, `queue` 來說，只要有符合對應概念的操作手段的容器，就能被用來當作高階容器的底層實作。

Ref: [c++ deque vs queue vs stack](https://stackoverflow.com/a/2248063)
:::

### Associative containers
關聯容器，實作了一些可以以 `O(log n)` 複雜度進行搜尋的資料結構。這裏的「關聯」特別指的是能夠進行「比較」的排序關係 (ordering relation)，而不是指像 `std::map` 中 key-value 之間的關聯。

由於這個容器是「有序」的，因此資料搜尋可以在 `O(log n)` 的複雜度下完成。

但另一方面就是在刪除和插入資料時會需要額外的 `O(log n)` 排序（或是以樹來說的話則是有平衡的行爲）——這點對於我們只是想單純的儲存（而不需要搜尋時）時通常反而是一個缺點。

- `set`: collection of unique keys, sorted by keys
- `map`: collection of key-value pairs, sorted by keys, keys are unique
- `multiset`: collection of keys, sorted by keys
- `multimap`: collection of key-value pairs, sorted by keys

實作上常用[紅黑樹 Red–black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree)實作，但只要能符合條件的實作都可以，不見得要是紅黑樹。

### Unordered associative containers (since C++11)
無序關聯容器（這裏的關聯指的是 key-hash 的關聯），同樣可以快速搜尋在容器內的資料。

由於是透過 hash 函數實作，因此搜尋的複雜度最佳情況下爲 `O(1)`，最糟爲 `O(n)`。同時 key 和 key 之間缺少了「比較」關係（hash 不需要這個性質），資料在儲存時自然不會維持某種排列順序。反過來說資料會被「分散」到不同的「桶子」中儲存。決定分配到哪個桶子則是由 hash 計算後的結果決定。

計算 hash 是 `O(1)`，因此搜尋、插入、刪除「平均」來說都是 `O(1)`。

- `unordered_set`
- `unordered_map`
- `unordered_multiset`
- `unordered_multimap`

### Container adaptors

直到 C\+\+20 爲止，container adaptors 有 `stack`, `queue` 和 `priority_queue` 共 3 種。（C\+\+23 則增加了 `flat_set`, `flat_map`... 等。）

Container adaptors 顧名思義，是用其他容器（基本上就是前面提到的 sequential container）來實作，並沒有獨立的實作叫做 `queue` 或 `stack`，只是提供一個方便使用的「介面」讓大家方便使用而已。

宣告 `stack` 和 `queue` 時，也可以指定底層使用什麼容器，只要這個底層容器能符合要求：例如 `stack` 需要可以使用 push, pop, top 來操作的底層容器。

- `stack`: adapts a container to provide stack (LIFO data structure)
- `queue`: adapts a container to provide queue (FIFO data structure)
- `priority_queue`: adapts a container to provide priority queue

值得注意的是 `priority_queue` （預設）會將資料由大到小排成序列，因此需要是能夠定義大小的資料。插入和取出時也會是 `O(log n)` 的複雜度。