STL 提供豐富容器，選擇正確容器是性能與開發效率的關鍵。本文總結 15 種容器的底層結構、時間複雜度、迭代器失效規則、適用場景，助你快速決策。
1. 序列容器
| 容器 | 底層結構 | 隨機訪問 | 頭/尾增刪 | 中間增刪 | 迭代器失效規則 | 典型場景 |
|---|
| vector | 動態數組 | O(1) | 尾 O(1) / 頭 O(n) | O(n) | 擴容/插入/刪除導致後續元素失效 | 默認首選、隨機訪問多、尾部操作多 |
| deque | 分段數組 | O(1) | 頭尾 O(1) | O(n) | 任何插入導致所有失效；頭尾刪除僅當前失效 | 雙端隊列、需頭尾高效增刪 |
| list | 雙向循環鏈表 | 不支持 | O(1) | O(1) (有迭代器) | 插入不失效；刪除僅當前失效 | 頻繁中間增刪、無需隨機訪問 |
| slist | 單向鏈表 | 不支持 | 僅頭部 O(1) | O(1) | 同 list | 內存敏感、單向遍歷場景 |
2. 容器適配器（基於序列容器封裝）
| 適配器 | 默認底層 | 特點 | 適用場景 |
|---|
| stack | deque | LIFO、只能訪問頂部、不可遍歷 | 函數調用棧、表達式求值、DFS |
| queue | deque | FIFO、只能訪問前後、不可遍歷 | BFS、任務隊列、生產消費 |
| priority_queue | vector | 堆實現、首元素最大、不可遍歷 | 任務調度、Top-K、Dijkstra |
3. 關聯容器（基於 RB-Tree / Hash Table）
| 容器 | 底層 | 鍵值關係 | 鍵唯一性 | 有序性 | 查找/插入/刪除 | 迭代器失效 |
|---|
| set | RB-Tree | key=value | 唯一 | 升序 | O(log n) | 刪除當前失效，其它不失效 |
| multiset | RB-Tree | key=value | 可重複 | 升序 | O(log n) | 同 set |
| map | RB-Tree | key≠value | 唯一 | 按 key 升序 | O(log n) | 同 set |
| multimap | RB-Tree | key≠value | 可重複 | 按 key 升序 | O(log n) | 同 set |
| hash_set | Hash Table | key=value | 唯一 | 無序 | 平均 O(1) | 同 set |
| hash_multiset | Hash Table | key=value | 可重複 | 無序 | 平均 O(1) | 同 set |
| hash_map | Hash Table | key≠value | 唯一 | 無序 | 平均 O(1) | 同 set |
| hash_multimap | Hash Table | key≠value | 可重複 | 無序 | 平均 O(1) | 同 set |
4. 選擇決策樹
- 需隨機訪問、尾部操作多 → vector
- 需頭尾高效增刪 → deque
- 頻繁中間增刪、無隨機訪問 → list
- 需鍵值映射、有序遍歷 → map/set
- 需鍵值映射、極致查找速度、無序可接受 → unordered_map/set (C++11)
- 需棧/隊列/優先隊列語義 → stack/queue/priority_queue
5. 避坑提示
vector 預留 reserve() 避免頻繁擴容deque 迭代器失效積極，遍歷中增刪需謹慎- 關聯容器迭代器穩定，適合長期持有
- C++11 優先用
unordered_map/set 替代 hash_*（非標準）
總結
容器無優劣，只有適不適合。掌握底層結構與複雜度，根據訪問模式、修改頻率、有序需求、內存限制選型，是 C++ 工程師必備基本功。
