10.1 C++ STL

在刷題時，我們幾乎一定會用到各種資料結構來輔助我們解決問題，因此我們必須熟悉各種資料結構的特點。C++ STL 提供的資料結構包括（實際底層細節可能因編譯器而異）：

順序容器（Sequence Containers）：維持順序的容器。
1. vector：動態陣列，是我們最常使用的資料結構之一，用於 $O(1)$ 的隨機讀取。因為大部分演算法的時間複雜度會大於 $O(n)$ ，因此我們經常新建 vector 來儲存各種資料或中間變數。由於在尾部增刪的複雜度是 $O(1)$ ，我們也可以把它當作 stack 來用。
2. list：雙向鏈結串列，也可以當作 stack 和 queue 來使用。由於 LeetCode 的題目多用 Node 來表示鏈結串列，且鏈結串列不支援快速隨機讀取，因此我們很少用到這個資料結構。一個例外是經典的 LRU 問題，我們需要利用鏈結串列的特性來解決，我們在後文會遇到這個問題。
3. deque：雙端佇列，這是一個非常強大的資料結構，既支援 $O(1)$ 隨機讀取，又支援 $O(1)$ 時間的頭部增刪和尾部增刪（因此可以當作 stack 和 queue 來使用），不過有一定的額外開銷。也可以用來近似一個雙向鏈結串列來使用。
4. array：固定大小的陣列，一般在刷題時我們不使用。
5. forward_list：單向鏈結串列，一般在刷題時我們不使用。
容器適配器（Container Adaptors）：基於其他容器實現的容器。
1. stack：後進先出（LIFO）的資料結構，預設基於 deque 實現。stack 常用於深度優先搜尋、一些字串匹配問題以及單調堆疊問題。
2. queue：先進先出（FIFO）的資料結構，預設基於 deque 實現。queue 常用於廣度優先搜尋。
3. priority_queue：優先佇列（最大值先出的資料結構），預設基於 vector 實現堆結構。它可以在 $O(n \log n)$ 的時間排序陣列， $O(\log n)$ 的時間插入任意值， $O(1)$ 的時間獲得最大值， $O(\log n)$ 的時間刪除最大值。priority_queue 常用於維護資料結構並快速獲取最大值，並且可以自定義比較函數；比如通過儲存負值或者更改比較函數，即可實現最小值先出。
有序關聯容器（Ordered Associative Containers）：有序的關聯容器。
1. set：有序集合，元素不可重複，底層實現預設為紅黑樹，即一種特殊的二元搜尋樹（BST）。它可以在 $O(n \log n)$ 的時間排序陣列， $O(\log n)$ 的時間插入、刪除、查找任意值， $O(\log n)$ 的時間獲得最小或最大值。需要注意的是，set 和 priority_queue 都可以用於維護資料結構並快速獲取最大最小值，但它們的時間複雜度和功能略有區別，如 priority_queue 預設不支援刪除任意值，而 set 獲得最大或最小值的時間複雜度略高，具體使用哪個取決於需求。
2. multiset：支援重複元素的 set。
3. map：有序映射或有序表，在 set 的基礎上增加映射關係，可以對每個元素 key 存一個值 value。
4. multimap：支援重複元素的 map。
無序關聯容器（Unordered Associative Containers）：無序的關聯容器。
1. unordered_set：雜湊集合，可以在 $O(1)$ 的時間快速插入、查找、刪除元素，常用於快速判斷某元素是否在容器內。
2. unordered_multiset：支援重複元素的 unordered_set。
3. unordered_map：雜湊映射或雜湊表，在 unordered_set 的基礎上增加映射關係，可以對每一個元素 key 存一個值 value。在某些情況下，如果 key 的範圍已知且較小，我們也可以用 vector 代替 unordered_map，用位置表示 key，用每個位置的值表示 value。
4. unordered_multimap：支援重複元素的 unordered_map。

由於這並不是一本講解 C++ 原理的書，更多的 STL 細節請讀者自行搜尋。只有理解了這些資料結構的原理和使用方法，才能更輕鬆地解決算法和資料結構問題。