STL (Standard Template Library) 是 C++ 標準庫的核心,提供**容器、算法、迭代器**三大組件,配合**配置器** 管理記憶體,體現**泛型程式設計** 思想。本文從歷史溯源、邏輯分層、六大組件交互、主流實現版本五個維度,建立 STL 完整認知框架。
┌─────────────────────────────────────┐ │ Algorithms (算法) │ sort, find, copy, transform... ~100 個 │ 操作「迭代器範圍」,不綁定具體容器 │ ├─────────────────────────────────────┤ │ Iterators (迭代器) │ 輸入/輸出/前向/雙向/隨機存取 五類 │ 統一容器訪問介面,抽象指針行為 │ ├─────────────────────────────────────┤ │ Containers (容器) │ 序列式/關聯式/容器適配器 │ vector, list, deque, map, set... │ ├─────────────────────────────────────┤ │ Allocators (配置器) │ 記憶體分配/釋放/構造/析構封裝 │ 使容器脫離具體記憶體模型 │ ├─────────────────────────────────────┤ │ Adaptors (適配器) │ stack, queue, priority_queue │ 改變容器介面行為 │ ├─────────────────────────────────────┤ │ Functors (仿函數) │ 謂詞、比較器、算術運算封裝 │ 使算法可參數化行為 │ └─────────────────────────────────────┘
CopyConstructible、LessThanComparable)Iterator、Container、RandomAccessIterator)vector::iterator 模型 RandomAccessIterator)這是**概念導向程式設計** 的雛形,後演進為 C++20 concepts。
| 類別 | 容器 | 底層結構 | 特點 | 典型場景 |
|---|---|---|---|---|
| 序列式 | vector | 動態陣列 | 隨機存取 O(1)、尾部增刪 O(1)、中間增刪 O(n)、緩存友好 | **首選默認容器** |
list | 雙向鏈表 | 任意位置增刪 O(1)、不支援隨機存取、記憶體碎片大 | 頻繁中間插刪、拼接 | |
deque | 分段連續陣列 | 雙端 O(1)、隨機存取 O(1)、中間增刪 O(n) | 雙端隊列、BFS | |
forward_list | 單向鏈表 | 單向、無 size()、記憶體最省 | 極簡單向遍歷 | |
| 關聯式 | map/multimap | 紅黑樹 | 鍵值對、鍵唯一/可重複、有序、O(log n) | 字典、索引 |
set/multiset | 紅黑樹 | 鍵即值、有序、唯一/可重複 | 去重、區間查詢 | |
unordered_map | 哈希表 | 平均 O(1)、無序、C++11 | 高頻查找、計數 | |
unordered_set | 哈希表 | 平均 O(1)、無序 | 高頻去重、存在性檢查 | |
| 適配器 | stack | deque/vector/list | LIFO、僅頂端操作 | 遞歸轉迭代、表達式求值 |
queue | deque/list | FIFO、雙端操作 | BFS、任務隊列 | |
priority_queue | vector + heap | 最大堆、O(log n) 入隊出隊 | Top-K、Dijkstra、Huffman |
| 容器 | 操作 | 失效迭代器 |
|---|---|---|
| vector | insert/emplace/push_back (可能擴容) | **全部失效** |
| vector | erase | 被刪除點及其後所有 |
| deque | insert/erase (非兩端) | **全部失效** |
| deque | push_front/back | 全部失效 |
| list/forward_list | insert/emplace | **無失效** |
| list/forward_list | erase | 僅被刪除者 |
| map/set/unordered_* | insert/emplace | **無失效** (C++11 保證) |
| map/set/unordered_* | erase | 僅被刪除者 |
| 實現 | 來源 | 特點 | 採用編譯器 |
|---|---|---|---|
| HP STL / SGI STL | HP/SGI | 原始參考實現,<stl_*.h> 風格 | GCC (早期)、研究教學 |
| libstdc++ | GNU | GCC 標準庫,基於 SGI STL 演進,支援並行算法、Debug 模式 | GCC, Clang (Linux) |
| libc++ | LLVM | 現代 C++11+ 重寫,模組化、快速編譯、優化友好 | Clang (macOS, FreeBSD, Fuchsia) |
| MSVC STL (Dinkumware) | Microsoft/P.J. Plauger | 商業級、Windows 整合、受保護迭代器、stdext::hash_map 等擴展 | MSVC (Windows) |
| STLPort | 社區 | 跨平台、高度可配、曾是嵌入式首選 | 舊版 Android NDK、嵌入式 |
| EASTL | Electronic Arts | 遊戲開發導向:固定記憶體、無異常、無 RTTI、內建 intrusive 容器 | 遊戲引擎、主機開發 |
vector**,除非有明確理由選其他std::ranges::sort(v)、std::ranges::find_if(v, pred)std::span (C++20) 替代指針+長度傳遞,不擁有所有權std::pmr::polymorphic_allocator 實現記憶體策略分離#include <ranges>、<algorithm>、<container> 模組化頭文件vector, map, unordered_map, string 基本操作sort, find_if, transform, accumulate, erase_if (C++20)auto 配合範圍 for<algorithm>、<iterator>、<memory> 標準庫源碼片段vector、allocator、iteratorSTL 不是工具箱,是**思維框架**。掌握「算法操作迭代器範圍、容器管理生命週期、配置器抽象記憶體」這三重分離,你就擁有了 C++ 泛型程式設計的核心鑰匙。