STL 的组成
C++ 标准模板库（STL）由三部分组成：容器负责存储数据，迭代器提供统一的访问接口，算法（sort、find、accumulate 等）只依赖迭代器、不关心具体容器。所以同一套算法可以作用于 vector、list、map 等所有容器。
用 STL 的核心不是背 API，而是理解每个容器的时间复杂度与适用场景。选错容器，性能差一个数量级。
序列容器
vector：默认首选
连续内存的动态数组。随机访问 O(1)，尾部插入/删除摊还 O(1)，中间插入/删除 O(n)。
#include <vector>
std::vector<int> v = {1, 2, 3};
v.push_back(4); // 尾部插入，摊还 O(1)
v.pop_back(); // 尾部删除，O(1)
v[0]; // 随机访问 O(1)，越界不检查
v.at(0); // 带边界检查，越界抛 std::out_of_range
v.insert(v.begin() + 1, 5); // 中间插入，O(n)
v.erase(v.begin() + 1); // 中间删除，O(n)
需要频繁在头部插入/删除时不要硬扛 vector——用 deque，或干脆逆序存储。
deque：双端队列
头尾插入/删除都是 O(1)，支持随机访问 O(1)。底层是分段连续内存，缓存友好度略低于 vector，但”两头都要操作”的场景它是正解。
list：双向链表
已知迭代器时插入/删除 O(1)，但没有随机访问；每个节点单独分配内存、地址分散，遍历时缓存命中差。大多数”想用链表”的场景，vector 或 deque 实际更快。list 真正的价值只有一个：插入/删除不使已有迭代器失效。
array 与 forward_list
std::array：定长数组的容器封装，栈上分配，接口与 vector 一致但没有扩容。std::forward_list：单向链表，最省空间，但能力最弱，工程里少见。
关联容器
map / set：有序，红黑树
增删查都是 O(log n)，按键升序遍历零成本。
#include <map>
std::map<std::string, int> m;
m["Alice"] = 25; // operator[]：不存在则默认构造后赋值
m.insert({"Bob", 30}); // 已存在则不覆盖
m.count("Alice"); // 0 或 1；C++20 之后可用 contains
for (const auto& [k, v] : m) { // 按键升序遍历
// ...
}
multimap / multiset 允许重复键，代价是没有 operator[]，接口受限。
unordered_map / unordered_set：哈希表
平均 O(1) 查找，最坏 O(n)（哈希冲突导致桶链退化，特定输入可被构造出这种场景）。元素无序。
选型判断：需要有序遍历、lower_bound 范围查询、找前驱后继 → map/set；只是按键查找 → unordered 系列，平均更快。
容器适配器
适配器是受限接口的封装：stack 后进先出，queue 先进先出，priority_queue 堆。底层默认 deque（priority_queue 用 vector）。
#include <stack>
#include <queue>
std::stack<int> st; // 后进先出：push / top / pop
std::queue<int> q; // 先进先出：push / front / pop
std::priority_queue<int> pq; // 默认大顶堆：push / top / pop，O(log n)
// 小顶堆：自定义比较器
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
常用算法
<algorithm> 里的算法只要求迭代器级别：sort 要随机访问迭代器（list 用不了，得用 list::sort），find 只要 input 级别，所有容器通用。
#include <algorithm>
#include <numeric>
std::sort(v.begin(), v.end()); // 排序
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序
std::reverse(v.begin(), v.end()); // 反转
std::fill(v.begin(), v.end(), 0); // 填充
// 去重：先排序，再 erase-remove 惯用法
v.erase(std::unique(v.begin(), v.end()), v.end());
// 数值算法
int sum = std::accumulate(v.begin(), v.end(), 0); // 求和
std::partial_sum(v.begin(), v.end(), out.begin()); // 前缀和
std::iota(nums.begin(), nums.end(), 10); // 生成递增序列
迭代器与 Lambda
迭代器按能力分五类：input / output → forward → bidirectional → random-access。vector/deque 是随机访问迭代器；list/map/set 是双向迭代器。算法对迭代器级别的要求决定了它能用在哪些容器上。
for (auto it = v.begin(); it != v.end(); ++it) { } // 正向
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) { } // 反向
// Lambda 作比较器：降序
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
// 按条件删除（erase-remove 惯用法）：删掉所有偶数
v.erase(std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; }), v.end());
常见陷阱
- 迭代器失效：vector/deque 插入或扩容后旧迭代器全部失效；unordered 系列扩容时失效；list/map 插入不失效，删除只失效指向被删元素的迭代器。失效迭代器的解引用是未定义行为。
- 批量插入前 reserve：
v.reserve(n)避免反复扩容搬移。连续 push_back 几万次而不 reserve，实测能慢好几倍。 - emplace 优于 push：
v.emplace_back(1, "one")原地构造，比先构造临时对象再拷贝/移动省一次。 - 循环里逐个 erase 是 O(n²)：删除满足条件的元素一律用 erase-remove 惯用法一次性清理。
- range-for 忘了写 &：遍历大对象容器时
for (auto x : v)会拷贝整个元素，内存和耗时翻倍。默认写const auto&，要修改才去掉 const。
选型口诀
默认 vector；两头操作 deque；需要迭代器稳定 list；按键查找 unordered_map；要有序遍历、范围查询 map；堆就用 priority_queue。容器选对了，九成性能问题根本不会出现。
