[CPP] STL 簡介

STL 即標準模板庫（Standard Template Library），是 C++ 標準庫的一部分，裡面包含了一些模板化的通用的資料結構和演算法。STL 基於模版的實現，因此能夠支援自定義的資料結構。STL 中一共有 6 大元件：- 容器 (container)- 迭代器 (iterator)- 演算法 (algorithm)- 分配器 (allocator)- 仿函式 (functor)- 容器介面卡 (container adapter)參考資料：+ [1] https://oi-wiki.org/lang/csl/container/+ [2] https://en.cppreference.com/w/cpp/container+ [3] http://c.biancheng.net/view/409.html## 仿函式仿函式 (Functor) 的本質就是**在結構體中過載 `()` 運算子**。例如：```cppstruct Print{ void operator()(const char *s) const { cout << s << endl; } };int main(){ Print p; p("hello");}```這一概念將會在 `priority_queue` 中使用（在智慧指標的 `unique_ptr` 自定義 deleter 也會用到）。## 容器容器 (Container) 在 STL 中又分為序列式容器 (Sequence Containers) ，關聯式容器 (Associative Containers) 和無序容器 (Unorderde Containers) . ### 序列式容器常見的序列式容器包括有：`vector, string, array, deque, list, forward_list` .**vector/string**底層實現：`vector` 是**記憶體連續、自動擴容的陣列**，實質還是定長陣列。特點：- 隨機訪問：過載 `[]` 運算子- 動態擴容：插入新元素前，如果 `size == capacity` 時，那麼擴容為當前容量的 2 倍，並拷貝原來的資料- 支援 `==, !=, <, <=, >, >=` 比較運算 - C++20 前，通過上述 6 個過載運算子實現；C++20中，統一「封裝」為一個 `<=>` 運算子 (aka, [three-way comparsion](https://en.cppreference.com/w/cpp/language/operator_comparison#Three-way_comparison) )。 - 不難理解，時間複雜度為 $O(n)$ 。PS：`string` 的底層實現與 `vector` 是類似的，同樣是記憶體連續、自動擴容的陣列（但擴容策略不同）。-----**array (C++11)**底層實現：`array` 是**記憶體連續的** 、 **固定長度**的陣列，其本質是對原生陣列的直接封裝。特點（主要是與 `vector` 比較）：- 支援 6 種比較運算子，支援 `[]` 隨機訪問- 丟棄自動擴容，以獲得跟原生陣列一樣的效能- 不支援 `pop_front/back, erase, insert` 這些操作。 - 長度在編譯期確定。`vector` 的初始化方式為函式引數（如 `vector v(10, -1)`，長度可動態確定），但 `array` 的長度需要在編譯期確定，如 `array a = {1, 2, 3}` .需要注意的是，`array` 的 `swap` 方法複雜度是 $\Theta(n)$ ，而其他 STL 容器的 `swap` 是 $O(1)$，因為只需要交換一下指標。----**deque**又稱為“雙端佇列”。底層實現：**多個不連續的緩衝區，而緩衝區中的記憶體是連續的**。而每個緩衝區還會記錄首指標和尾指標，用來標記有效資料的區間。當一個緩衝區填滿之後便會在之前或者之後分配新的緩衝區來儲存更多的資料。特點：- 支援 `[]` 隨機訪問- 線性複雜度的插入和刪除，以及常數複雜度的隨機訪問。-----**list**底層實現：雙向連結串列。特點：- 不支援 `[]` 隨機訪問- 常數複雜度的插入和刪除**forwar_list (C++11)**底層實現：單向連結串列。特點：- 相比 `list` 減少了空間開銷- 不支援 `[]` 隨機訪問- 不支援反向迭代 `rbegin(), rend()`### 關聯式容器關聯式容器包括：`set/multiset`，`map/multimap`。`multi` 表示鍵值可重複插入容器。底層實現：紅黑樹。特點：- 內部自排序，搜尋、移除和插入擁有對數複雜度。- 對於任意關聯式容器，使用迭代器遍歷容器的時間複雜度均為 $O(n)$ 。自定義比較方式：- 如果是自定義資料型別，過載運算子 `<` - 如果是 `int` 等內建型別，通過仿函式```cppstruct cmp { bool operator()(int a, int b) { return a > b; } };set s;```### 無序容器無序容器 (Unorderde Containers) 包括：`unordered_set/unordered_multiset`,`unordered_map/unordered_multimap` .底層實現：雜湊表。在標準庫實現裡，每個元素的雜湊值是將值對**一個質數**取模得到的，特點：- 內部元素無序- 在最壞情況下，對無序關聯式容器進行插入、刪除、查詢等操作的時間複雜度會**與容器大小成線性關係** 。這一情況往往在容器內出現**大量雜湊衝突**時產生。在實際應用場景下，假設我們已知鍵值的具體分佈情況，為了避免大量的雜湊衝突，我們可以自定義雜湊函式（還是通過仿函式的形式）。```cppstruct my_hash { size_t operator()(int x) const { return x; } };unordered_map my_map;unordered_map , int, my_hash> my_pair_map;```### 小結四種操作**的平均時間複雜度**比較：- 增：在指定位置插入元素- 刪：刪除指定位置的元素- 改：修改指定位置的元素- 查：查詢某一元素| Containers | 底層結構 | 增 | 刪 | 改 | 查 || :--------------------------------------------------------: | :--------------------------------------------: | :----------: | :----------: | :----------: | :----------: || `vector/deque` | vector: 動態連續記憶體
deque: 連續記憶體+連結串列 | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$ || `list` | 雙向連結串列 | $O(1)$ | $O(1)$ | $O(1)$ | $O(n)$ || `forward_list` | 單向連結串列 | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ || `array` | 連續記憶體 | 不支援 | 不支援 | $O(1)$ | $O(n)$ || `set/map/multiset/multimap` | 紅黑樹 | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ | $O(\log{n})$ || `unordered_{set,multiset}`
`unordered_{map,multimap}` | 雜湊表 | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |## 容器介面卡容器介面卡 (Container Adapter) 其實並不是容器（個人理解是對容器的一種封裝），它們不具有容器的某些特點（如：有迭代器、有 `clear()` 函式……）。常見的介面卡：`stack`，`queue`，`priority_queue`。對於介面卡而言，可以指定某一容器作為其底層的資料結構。**stack**- 預設容器：`deque`- 不支援隨機訪問，不支援迭代器- `top, pop, push, size, empty` 操作的時間複雜度均為 $O(1)$ 。指定容器作為底層資料結構：```cppstack s; // 使用 Container 作為底層容器```**queue**- 預設容器：`deque`- 不支援隨機訪問，不支援迭代器- `front, push, pop, size, empty` 操作的時間複雜度均為 $O(1)$ 。指定容器：```cppqueue > q;```**priority_queue**又稱為 “優先佇列” 。- 預設容器：`vector`- $O(1)$：`top, empty, size`- $O(\log{n})$ : `push, pop`模版引數解析：```cpppriority_queue , Compare = less > q;// 通過 Container 指定底層容器，預設為 vector// 通過 Compare 自定義比較函式，預設為 less，元素優先順序大的在堆頂，即大頂堆priority_queue , greater > q;// 傳入 greater 那麼將構造一個小頂堆// 類似的，還有 greater_equal, less_equal```## 迭代器迭代器 (Iterator) 實際上也是 GOF 中的一種設計模式：**提供一種方法順序訪問一個聚合物件中各個元素，而又不需暴露該物件的內部表示。**迭代器的分類如下圖所示。 ### 各容器的迭代器STL 中各容器/介面卡對應使用的迭代器如下表所示。| Container | Iterator || :-----------------------: | :------------: || array | 隨機訪問迭代器 || vector | 隨機訪問迭代器 || deque | 隨機訪問迭代器 || list | 雙向迭代器 || set / multiset | 雙向迭代器 || map / multimap | 雙向迭代器 || forward_list | 前向迭代器 || unordered_{set, multiset} | 前向迭代器 || unordered_{map, multimap} | 前向迭代器 || stack | 不支援迭代器 || queue | 不支援迭代器 || priority_queue | 不支援迭代器 |### 迭代器失效迭代器失效是因為向容器插入或者刪除元素導致容器的空間變化或者說是次序發生了變化，使得原迭代器變得不可用。因此在對 STL 迭代器進行增刪操作時，要格外注意迭代器是否失效。網路上搜索「迭代器失效」，會發現很多這樣的例子，在一個 `vector` 中去除所有的 2 和 3，故意用一下迭代器掃描（~~大家都知道可以用下標~~）：```cppint main(){ vector v = {2, 3, 4, 6, 7, 8, 9, 3, 2, 2, 2, 2, 3, 3, 3, 4, 5, 6}; for (auto i = v.begin(); i != v.end(); i++) { if (*i==2 || *i==3) v.erase(i), i--; // correct code should be // if (*i==2 || *i==3) i=v.erase(i), i--; } for (auto i = v.begin(); i != v.end(); i++) cout << *i << ' ';}```我很久之前用 Dev C++ （應該是內建了很古老的 MinGW）寫程式碼的時候，印象中也遇到過這種情況，`v.erase(i), i--` 這樣的操作是有問題的。 `erase(i)` 會使得 `i` 及其後面的迭代器失效，從而發生段錯誤。但現在 MacOS (clang++ 12), Ubuntu16 (g++ 5.4), Windows (mingw 9.2) 上測試，這段程式碼都沒有問題，並且能輸出正確結果。編譯選項為：```g++ test.cpp -std=c++11 -O0```實際上也不難理解，因為是連續記憶體，`i` 指向的記憶體位置，在 `erase` 之後被其他資料覆蓋了（這裡的行為就跟我們使用普通陣列一樣），但該位置仍然在 `vector` 的有效範圍之內。在上述程式碼中，當 `i = v.begin()` 時，執行 `erase` 後，對 `i` 進行自減操作，這已經是一種未定義行為。我猜應該是 C++11 後（或者是後來的編譯器更新），對迭代器失效的這個問題進行了優化。雖然能夠正常執行，但我認為最好還是嚴謹一些，更嚴格地遵循迭代器的使用規則：`if (*i==2 || *i==3) i=v.erase(i), i--;` . 以下為各類容器可能會發生迭代器失效的情況：- 陣列型 (`vector, deque`) - `insert(i)` 和 `erase(i)` 會發生資料挪動，使得 `i` 後的迭代器失效，建議使用 `i = erase(i)` 獲取下一個有效迭代器。 - 記憶體重新分配：當 `vector` 自動擴容時，**可能**會申請一塊新的記憶體並拷貝原資料（也有可能是在當前記憶體的基礎上，再擴充一段連續記憶體），因此所有的迭代器都將失效。- 連結串列型 (`list, forward_list`)：`insert(i)` 和 `erase(i)` 操作不影響其他位置的迭代器，`erase(i)` 使得迭代器 `i` 失效，指向資料無效，`i = erase(i)` 可獲得下一個有效迭代器，或者使用 `erase(i++)` 也可（在進入 `erase` 操作前已完成自增）。- 樹型 (`set/map`)：與連結串列型相同。- 雜湊型 (`unodered_{set_map}`)：與連結串列型