06 · STL 容器与迭代器

定位：STL 是 C++ 八股第三大块，vector/map/unordered_map 的底层实现、迭代器失效、扩容是必考。 学完标准：能把 7 大容器“底层结构/复杂度/迭代器是否失效/适用场景”做成一张表讲出来。

---

1. 容器总览（先背这张表）

容器	底层结构	查找	插入/删除	随机访问	迭代器失效	内存
vector	动态连续数组	O(n)	尾 O(1)★，中间 O(n)	✅ O(1)	push_back 扩容全失效；insert/erase 插入点/被删点及其后失效	连续
deque	分段连续(中控器)	O(n)	头尾 O(1)★	✅ O(1)	头尾插入：迭代器全失效、引用不失效；中间插入/删除：全失效	多段
list	双向链表	O(n)	O(1)（已知位置）	❌	除被删元素外不失效	节点分散
forward_list	单向链表	O(n)	O(1)	❌	同上	节点分散
set/multiset	红黑树	O(log n)	O(log n)	❌	不失效（节点式）	节点分散
map/multimap	红黑树	O(log n)	O(log n)	❌	不失效	节点分散
unordered_set/map	哈希表(链地址)	平均 O(1)	平均 O(1)	❌	rehash 时全失效	桶数组+节点

★ = 摊还复杂度。

选择金句：

• 需要随机访问 + 频繁尾部增删 → vector
• 需要头尾插入（队列）→ deque
• 需要大量中间插入/删除 → list
• 需要有序且查找快 → map/set（红黑树）
• 只查快、不在乎顺序 → unordered_map
• 元素唯一 → set/map；可重复 → multiset/multimap

---

2. vector 底层（必考细节）

2.1 结构

struct vector {
    T* start;        // 首元素
    T* finish;       // 尾后（size）
    T* end_of_storage; // 容量边界（capacity）
};

连续内存，三个指针管理 size 和 capacity。

2.2 扩容机制（高频）

std::vector<int> v;
for (int i = 0; i < 100; i++) v.push_back(i);
// 容量变化示例（GCC 增长因子 2）：1,2,4,8,16,32,64,128；（MSVC 1.5）：1,2,3,4,6,9,13,19

流程：容量满了 → 分配 2 倍新内存 → 把旧元素移动/拷贝到新内存 → 释放旧内存 → 更新指针。

• 增长因子：GCC 2 倍，MSVC 1.5 倍。
• 摊还复杂度 O(1)：n 次 push_back 总拷贝次数是 O(n)，平均每次 O(1)。
• 扩容时迭代器/指针/引用全部失效（内存搬家了）。
• 为什么指数增长？ 保证摊还 O(1)；线性增长（+固定大小）总代价 O(n²)。

2.3 push_back vs emplace_back

struct Point { Point(float x, float y){} };

v.push_back(Point(1, 2));    // 先构造临时 Point，再拷贝/移动到容器（可能两步）
v.emplace_back(1, 2);        // 直接以 (1,2) 原地构造，零拷贝

• emplace_back 转发参数原地构造，省一次临时对象构造+移动/拷贝。
• 面试点：emplace 不一定总是更好——参数已是现成对象时两者差不多；emplace 是直接初始化，通常可以使用 explicit 构造函数，但 emplace_back({1,2}) 这类列表解析容易踩坑。面试说“emplace_back 通常更高效”即可。

2.4 reserve vs resize

v.reserve(100);   // 只扩 capacity=100，size 不变，不构造元素（快）
v.resize(100);    // 改变 size=100，多余元素默认构造（默认值填充）
v.shrink_to_fit(); // 把 capacity 缩到 size

金句：reserve 提前申请内存避免多次扩容；resize 改变元素数量。知道要加 n 个元素 → reserve + push_back。

2.5 迭代器失效（vector 必背）

操作	迭代器/指针/引用情况
push_back 触发扩容	全部失效（内存搬走）
push_back 未触发扩容	已有元素的迭代器/引用不失效（end() 失效）
insert	插入点及之后全部失效（元素后移）
erase	被删元素及之后全部失效
尾部 pop_back	被删元素的迭代器/引用和 end() 失效

for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);   // erase 返回下一个有效迭代器
    else ++it;
}
// 注意：不要在 for 里用 v.erase(it) 然后 it++ —— erase 后 it 已失效！

---

3. list / deque

3.1 list（双向链表）

• 每个节点独立分配（Node = 数据 + prev/next 指针）。
• 插入/删除（已知位置）O(1)，迭代器不失效（除非删除该节点本身）。
• 缺点：无随机访问、缓存不友好（节点分散，遍历命中率低）、内存碎片。
• splice（O(1) 拼接另一个 list 的一段）是 list 独有操作。

3.2 deque（双端队列）

• 分段连续：多段定长连续缓冲区 + 中控器（map，存各段首地址的指针数组）。
• 支持 operator[]（先定位段再定位元素，两次间接，比 vector 稍慢）。
• 头尾插入 O(1)，中间插入 O(n)。
• 头尾插入：所有迭代器失效，但元素引用不失效（元素不搬家）；删除头/尾只失效被删元素和 end()；中间插入/删除：迭代器和引用全失效。
• 应用：作为 std::queue、std::stack 的默认底层。

---

4. map / set（红黑树）

4.1 底层：红黑树

• 自平衡二叉搜索树：任意节点红黑染色 + 5 条性质保证最长路径 ≤ 2×最短路径。
• 所有操作 O(log n)，有序（中序遍历有序）。
• 为什么用红黑树而不是 AVL？
  • AVL 更严格平衡（左右子树高度差 ≤ 1），查询略快但插入/删除旋转多；
  • 红黑树平衡要求松，插入/删除旋转次数少、常数小，整体统计性能好。通用容器选红黑树。

4.2 map 的特性

• key 有序，要求 key 支持 <（或提供比较器）。
• 迭代器指向 pair<const Key, T>，key 不可修改（改 key 会破坏红黑树性质）。
• operator[]：key 不存在会插入默认值（副作用）！判断存在用 find/contains(C++20)。

std::map<std::string, int> m;
m["a"] = 1;                       // 不存在 → 插入 "a" 再赋值
if (m.count("b")) { }             // count 返回 0/1（检查存在）
auto it = m.find("b");            // 找不到返回 end()

4.3 set 与 multiset/multimap

• set：有序唯一集合（插入已有元素不插入）。
• multiset/multimap：允许重复 key（用 equal_range 取所有重复）。

---

5. unordered_map（哈希表）

5.1 底层

• 哈希表 + 链地址法：一个桶数组（bucket array），每个桶挂链表。主流标准库实现是“贯穿所有节点的单链表 + 桶指针数组”；桶内转红黑树是 Java 8 HashMap 的行为，C++ 没有。
• 平均 O(1) 查找：hash(key) → 定位桶 → 桶内线性比较。
• 要求 key 提供 hash 函数 + ==（自定义类型需自己提供）。

5.2 哈希冲突（必背）

解决方式	说明
链地址法（separate chaining）	冲突的元素挂同一桶的链表上，std::unordered_map 用这个
开放寻址（open addressing）	冲突后按探测序列找下一个空位（线性/二次探测、双重哈希）

负载因子（load factor） = 元素数 / 桶数。超过阈值（std 默认 1.0）→ rehash：扩容桶数组并重新计算所有元素的桶位置（O(n)，全迭代器失效）。

5.3 map vs unordered_map 选择（必背）

	map	unordered_map
底层	红黑树	哈希表
复杂度	O(log n) 稳定	平均 O(1)，最坏 O(n)（冲突多时）
有序性	有序（中序遍历）	无序
key 要求	<（或比较器）	hash + ==
常数	每次操作 O(log n) 稳定、无最坏退化	平均 O(1) 常数小，但 hash 计算有开销、最坏 O(n)
适用	需要有序遍历/范围查询、元素少	大量查找、无需有序、key 好 hash

金句：元素少时 map 可能更快（红黑树 O(log n) 稳定、无退化），元素多且查找频繁用 unordered_map。

---

6. 迭代器分类（概念性考点）

类别	能力	代表
输入/输出迭代器	单向读写一次	istream_iterator
前向迭代器	单向多次遍历	forward_list
双向迭代器	可 ++ –	list/set/map
随机访问迭代器	+n、-n、[]、比较	vector/deque/array
连续迭代器(C++20)	保证内存连续	vector

用模板时按最弱需求声明参数类型（算法只依赖需要的类别，提高复用性）。

---

7. 高频面试题 Q&A

Q1：vector 扩容机制？增长因子？ 容量满 → 分配新内存（GCC 2 倍、MSVC 1.5 倍）→ 移动/拷贝元素 → 释放旧内存。摊还 O(1)。指数增长保证摊还复杂度。

Q2：为什么 vector 扩容不线性增长？ 线性增长总拷贝是 O(n²)；指数增长摊还 O(1)。

Q3：vector 迭代器什么时候失效？ 扩容后全部失效；insert/erase 至少使插入点/被删元素及其后失效（扩容则全部）；注意“先 erase 再 ++“的经典错误。

Q4：map 为什么用红黑树？ 自平衡 + 有序 + 插入删除常数比 AVL 好，整体统计性能最优。

Q5：unordered_map 冲突怎么解决？负载因子是什么？ 链地址法；负载因子 = 元素/桶数，超过阈值 rehash（全失效）。

Q6：emplace_back 和 push_back？ emplace 原地构造省一次临时对象拷贝/移动。

Q7：reserve 和 resize？ reserve 只扩容量不建元素；resize 改变元素个数并构造。

Q8：map 的 operator[] 有什么坑？ 不存在的 key 会被插入默认值；只查不用 find/contains。

Q9：list 和 vector 场景选择？ list 频繁中间插入、迭代器稳定；vector 随机访问、缓存友好、尾部增删。

Q10：为什么 vector 比 list 遍历快？ 连续内存缓存命中率高（顺序预取）；list 节点分散，每次访问都缓存未命中。

Q11：vector 存对象 vs 存指针？ 存对象：连续、缓存好、但移动/拷贝元素成本高、插入删除搬移对象；存指针：搬移成本低但缓存差 + 管理生命周期。性能关键型存对象。

Q12：如何避免 vector 频繁扩容？ reserve 预估容量。

---

8. 本章自测（12 题）

1. 写出 vector 扩容的完整流程（含迭代器失效）。

2. map 和 unordered_map 各举一个选它的场景。

3. 为什么红黑树而不是 AVL？

4. `for(auto it=v.begin(); it!=v.end(); ++it){ v.erase(it); }` 有什么问题？怎么改？

5. unordered_map 什么时候 rehash？

我的原答：rehash 后迭代器会怎样？

6. emplace_back 省了什么？

7. deque 为什么叫"分段连续"？

8. map 里迭代器指向的 key 为什么不能改？

9. list 的迭代器为什么 insert 后不失效？

10. vector 为什么比 list 快（遍历）？

11. 什么情况用 vector 存指针更好？

12. `std::array` 和 vector 区别？

📖 答案提示（先自己答完再展开）

1. 扩容 → 全失效（搬内存）；见 2.2。
2. map：需要有序/范围查询；unordered_map：海量查找、无序、好 hash。
3. 平衡度要求松 → 旋转少、常数小，统计性能好。
4. erase 后迭代器失效 → 用 it = v.erase(it)。
5. 负载因子超阈值 → rehash → 全部迭代器失效。
6. 省临时对象的构造 + 拷贝/移动。
7. 多段定长连续缓冲区 + 中控器指针数组。
8. key 是 const，改 key 会破坏红黑树有序性质。
9. 节点式结构，插入只改指针，内存地址不变。
10. 连续内存缓存友好。
11. 对象太大、移动昂贵、需要稳定地址时（指针本身搬移便宜）。
12. array 是固定大小的内嵌数组、不动态分配；vector 动态扩容、元素在堆上。

---

## 9. 进阶追问

• 自定义类型作为 unordered_map 的 key 要提供什么？（std::hash<T> 特化 + operator==）
• vector<bool> 为什么特殊？（按位压缩，operator[] 返回 proxy 不是 bool&）
• 什么是 allocator？游戏引擎怎么自定义分配器让 STL 用内存池？（std::allocator 接口）
• std::map 的 emplace_hint、lower_bound/upper_bound/equal_range 的用途？