核心理解
STL 不是“容器合集”，而是一套可组合的泛型编程框架：容器保存数据，迭代器统一访问，算法处理区间，函数对象定制行为，适配器改变接口，分配器管理内存。
6.1 STL 整体结构
组件 | 作用 | 常见对象 |
容器 | 保存数据 | vector、list、map |
迭代器 | 表示元素位置与访问方式 | begin()、end() |
算法 | 对迭代器区间执行操作 | sort、find |
函数对象 | 定制比较或处理规则 | less、lambda |
适配器 | 在现有组件上包装新接口 | stack、queue |
分配器 | 分配、释放原始内存 | allocator |
一条典型调用链如下：
容器 → 迭代器区间 [begin, end) → 算法 → 函数对象定义规则这里
vector 保存数据，迭代器给出左闭右开区间，sort 负责排序，greater 规定降序。6.2 序列容器
序列容器按插入顺序保存元素。选择容器时，先看主要操作，不要按名字凭感觉选。
容器 | 内存布局 | 随机访问 | 中间插删 | 典型用途 |
array | 连续、固定长度 | O(1) | 不支持扩容 | 编译期确定大小 |
vector | 连续、动态扩容 | O(1) | O(n) | 默认首选 |
deque | 分段连续 | O(1) | 中间 O(n)，两端 O(1) | 频繁操作首尾 |
list | 双向链表 | O(n) | 已知位置 O(1) | 频繁移动节点 |
forward_list | 单向链表 | O(n) | 已知前驱 O(1) | 极简链表场景 |
经验规则
没有明确理由时先用
vector。它连续存储、缓存友好，实际性能常常优于“理论插删更快”的链表。6.3 关联容器
关联容器通常由平衡搜索树实现，元素始终按键有序，查找、插入和删除通常为 O(log n)。
set：只存键，键唯一。
multiset：只存键，允许重复。
map：存键值对，键唯一。
multimap：存键值对，允许重复键。
map[key] 在键不存在时会创建默认值。只想查询时，应使用 find、contains（C++20）或 at。6.4 无序关联容器
unordered_set 与 unordered_map 基于哈希表：平均查找 O(1)，最坏 O(n)，并且不保证遍历顺序。哈希冲突不可避免：多个键可能落到同一个桶中。性能取决于哈希函数、负载因子和扩容次数。
需求 | 推荐 |
需要按键有序遍历 | map / set |
主要做快速查找，不关心顺序 | unordered_map / unordered_set |
键可能重复 | 对应的 multi* 容器 |
6.5 容器适配器
适配器不提供新的底层存储结构，而是限制并重组已有容器的接口。
适配器 | 规则 | 默认底层容器 | 关键接口 |
stack | 后进先出 LIFO | deque | top、push、pop |
queue | 先进先出 FIFO | deque | front、back |
priority_queue | 最高优先级先出 | vector | top、push、pop |
6.6 迭代器
迭代器是容器与算法之间的统一接口。STL 普遍使用左闭右开区间
[first, last)：包含 first，不包含 last。[begin, end) = 元素 0 → 元素 1 → … → 最后一个元素 | end类别 | 能力 | 代表容器 |
输入 / 输出迭代器 | 单向读取或写入 | 流迭代器 |
前向迭代器 | 可重复单向遍历 | forward_list |
双向迭代器 | 支持 ++、-- | list、map |
随机访问迭代器 | 支持加减与下标 | vector、deque |
连续迭代器（C++20） | 元素物理连续 | array、vector |
迭代器失效
容器结构变化后，旧迭代器可能不再有效：
vector扩容：全部迭代器、指针和引用失效。
vector擦除：被删位置及其后的迭代器失效。
list/map擦除：通常只有指向被删元素的迭代器失效。
unordered_*重新哈希：迭代器失效。
安全删除写法：
6.7 算法
算法操作的是迭代器区间，而不是某一种容器，因此同一算法可以复用于数组、
vector 等不同结构。常用算法可按目的记忆：
- 查找与统计：
find、count、any_of。
- 修改序列：
transform、copy、remove。
- 排序与二分：
sort、lower_bound、binary_search。
- 数值与集合：
accumulate、set_union。
- 排列：
next_permutation。
经典陷阱：remove 并不真正删除元素
remove 只把保留元素前移，并返回新的逻辑结尾；还要调用容器的 erase。6.8 分配器
分配器把两件事分开：
- 分配与释放原始内存。
- 在内存中构造与销毁对象。
日常开发通常使用容器的默认分配器即可。只有内存池、共享内存、实时系统或性能分析证明默认策略不合适时，才值得自定义；否则是在拿复杂度换一种写法。
6.9 Boost
Boost 是 C++ 的扩展库集合，许多标准库能力曾先在 Boost 中成熟，例如智能指针、正则表达式和文件系统。
使用前依次检查：
- 标准库是否已经提供同等能力。
- Boost 是否显著降低实现和维护成本。
- 项目能否接受额外依赖、编译时间与版本管理成本。
最终选择顺序
标准库能解决 → 优先标准库；标准库缺失且 Boost 方案成熟 → 使用 Boost；两者都不合适 → 再考虑自研。
小结：一张表完成选型
场景 | 首选 |
通用动态序列 | vector |
固定长度连续数据 | array |
频繁操作序列两端 | deque |
有序键值查询 | map |
无序快速查询 | unordered_map |
去重集合 | set / unordered_set |
后进先出 | stack |
先进先出 | queue |
动态取最大值或最小值 | priority_queue |
真正需要掌握的不是把接口背完，而是回答三个问题：数据如何存、主要操作是什么、哪些操作会让迭代器失效。
