C++ STL 核心組件深度總結：容器、迭代器、算法與適配器

STL（Standard Template Library）是 C++ 標準庫的核心體現泛型編程思想的部分。它通過模板實現數據結構與算法的解耦，提供工業級效能的可復用組件。本文系統梳理 STL 六大組件，重點解析容器分類、迭代器體系、算法分類及容器適配器用法。

STL 六大組件

1. 容器：管理數據集合的類模板（vector, list, map...）。
2. 迭代器：泛化指針，提供統一遍歷接口，連接容器與算法。
3. 算法：操作容器數據的函數模板（sort, find, copy...），通過迭代器實現與容器無關。
4. 仿函數：重載 operator() 的類，行為類似函數，可保存狀態，用於算法策略定製。
5. 適配器：修改接口以適配特定需求（容器適配器 stack/queue、迭代器適配器、仿函數適配器）。
6. 空間配置器：封裝內存分配/釋放與對象構造/析構（allocator），容器底層內存管理核心。

1. 容器詳解

序列式容器

關聯式容器（基於紅黑樹 RB-tree）

無序關聯容器（C++11）：unordered_set/map 基於哈希表，平均 O(1) 查找，無序。

2. 迭代器體系

迭代器是智能指針，統一了容器遍歷語法。按能力分五類，能力遞增：

Input Iterator  →  Output Iterator
       ↓
Forward Iterator  (可多遍歷、只讀/寫)
       ↓
Bidirectional Iterator (雙向 ++)
       ↓
Random Access Iterator (支援 +n, -n, [n], <, >)

容器支援的迭代器類別

常用操作

// 聲明
vector<int>::iterator it;
list<string>::const_reverse_iterator rit;

// 關鍵操作
*it, ++it, --it, it == it2, it != it2        // 所有
it + n, it - n, it[n], it < it2              // 隨機訪問

3. 算法分類總覽（<algorithm>, <numeric>, <functional>）

核心算法示例

// 查找
auto it = find(v.begin(), v.end(), 42);
auto it = find_if(v.begin(), v.end(), [](int x){ return x > 10; });

// 排序
sort(v.begin(), v.end(), greater<int>()); // 降序
stable_sort(v.begin(), v.end());          // 穩定排序

// 修改
transform(v1.begin(), v1.end(), v2.begin(), back_inserter(v3), plus<int>());
replace_if(v.begin(), v.end(), [](int x){ return x < 0; }, 0);

// 刪除（需配合 erase）
v.erase(remove(v.begin(), v.end(), 3), v.end()); // Erase-Remove 慣用法

// 數值
int sum = accumulate(v.begin(), v.end(), 0);

4. 容器適配器

適配器封裝底層容器（默認 deque/vector），提供特定語義接口，不支援迭代器。

stack (LIFO)

#include <stack>
stack<int> s;              // 底層 deque
stack<int, vector<int>> s2; // 指定 vector
s.push(1); s.top(); s.pop(); s.empty(); s.size();

queue (FIFO)

#include <queue>
queue<int> q;              // 底層 deque
queue<int, list<int>> q2;   // 指定 list
q.push(1); q.front(); q.back(); q.pop(); q.empty(); q.size();

priority_queue (優先級隊列，默認大頂堆)

#include <queue>
priority_queue<int> pq;                    // less，大頂堆
priority_queue<int, vector<int>, greater<int>> pq2; // 小頂堆

// 自定義類型需重載 operator< 或提供比較仿函數
struct Node { int val, pri; };
struct Cmp { bool operator()(const Node& a, const Node& b) { return a.pri < b.pri; } };
priority_queue<Node, vector<Node>, Cmp> pq3;

選擇指南

• 默認用 vector；需雙端操作用 deque；需頻繁中間插刪用 list。
• 需快速查找/去重/有序遍歷 → set/map；允許重複鍵 → multiset/multimap。
• 海量數據、極致查找速度、不需有序 → unordered_set/map（自定義類型需提供 hash 與 ==）。
• 棧/隊列/優先隊列語義明確 → 直接用適配器。
• 算法優先用標準庫（std::sort, std::find 等），僅在極特殊場景手寫。