CS106L 第五讲的 PPT，我对着屏幕断断续续整理了两遍，最后得出的结论很直接：Containers 这一节是整个 C++ 标准库真正开始显山露水的地方，也是从“会用 C++ 写程序”迈向“理解 C++ 为什么这样设计”的分水岭。第五讲没有绕弯子，把你日常写算法题见惯了的 vector、map、unordered_map 全部摆上台面，一个一个拆开讲底层结构、性能边界和迭代器语义。如果你正在补 C++ 基础，或者刷题时总被 vector 扩容、map 底层、迭代器失效这类问题卡住，这讲笔记值得你认真看一遍。
很多人把容器单纯理解成“装数据的类”，但 CS106L 第五讲想纠正的恰恰是这个印象：容器不是孤立的工具，它们在设计上和迭代器、算法紧密咬合，你只有把这三样东西放在一起看，才能真正明白为什么某个容器适合某个场景，为什么另一个容器在特定操作上会慢到让你怀疑人生。下面就是我基于这讲 PPT 整理出来的完整笔记，包含底层原理解读、选择容器的思路，以及我实际写代码时踩过的坑。
1. 这讲到底在讲什么：先看懂容器的共性，才能看懂差异
1.1 从 PPT 的目录结构看重点
CS106L 第五讲被命名为 Containers，并不是简单地把各个容器类罗列一遍。PPT 的内容通常分成四块：第一块是容器的大分类，把顺序容器和关联容器摆出来，让大家知道标准库提供了哪些“工具箱”；第二块是逐个介绍具体容器，包括底层数据结构、复杂度、构造方式和常用操作；第三块是迭代器，因为容器只是数据的“房子”，迭代器才是让你安全进入这栋房子的通道；第四块是选择策略，告诉你碰到实际问题时应该优先考虑哪个容器。
这个结构本身就透露了一个关键信息：课程希望你建立的是“按需选型”的思维，而不是死记每个容器的 API。比如同样是“按键找值”，map 和 unordered_map 分别适合不同的场景，如果你只记住“用 map”，而不理解它底层是红黑树、查找复杂度是 O(log n)，那么面对最高频访问的缓存场景时，你很可能选错工具，导致性能差一个数量级。
我在整理笔记时还注意到一个细节：PPT 反复强调所有容器都有相似的接口风格，比如 size()、empty()、begin()、end()。这是一个非常刻意的设计，目的是让调用者不需要针对每种容器背一套完全不同的写法。也正是因为这种接口上的统一，STL 算法才能通过迭代器去操作任意容器。可以说，容器的“共性接口”和“底层差异”并存，才是这讲真正要教的东西。
1.2 为什么要先理解底层结构，而不是只背接口
很多初学者学容器时习惯只记“vector 尾部快”“list 中间插入快”，但这个结论背后是有前提的。vector 之所以尾部插入快，是因为它维护的是一块连续内存，push_back 时只需要在末尾构造元素；而中间插入要移动后续所有元素，所以是 O(n)。list 之所以中间插入快，是因为它是链表结构，插入操作只是改变相邻节点的指针，但代价是没有随机访问能力，取第 n 个元素必须从头遍历。
底层结构还会直接决定“迭代器失效”的范围。比如 vector 在扩容时，原来的所有迭代器、指针和引用都可能失效；而 list 插入新节点时，原来指向其他节点的迭代器一个都不会失效。这不是接口设计的问题，而是内存布局的必然结果。理解这一点后，很多看似莫名其妙的 bug 其实都可以直接推理出来，不需要靠运气去试。
我在实际工作中就遇到过类似情况：一个用 vector 保存数据、同时在外面保存了指向元素的迭代器，后来 push_back 触发了扩容，迭代器瞬间变成野指针。如果当时我脑子里有“vector 扩容会使迭代器失效”这条底层知识，就不会写出这种代码。CS106L 第五讲把这类问题放在前面讲，就是希望在源头上帮你建立这种意识。
2. 顺序容器逐个拆解：vector 不是唯一答案，但确实是默认答案
2.1 vector：动态数组的扩容机制，绝对不能只看 push_back
vector 是 C++ 里默认容器的首选，这一点没有任何争议。它的核心是一块连续内存，支持下标随机访问，复杂度是 O(1)，而且内存局部性好，遍历时 CPU 缓存利用率很高。但真正理解 vector，你必须把它看成两个数的组合：size 和 capacity。size 是当前实际元素个数，capacity 是在不重新分配内存的情况下最多能容纳的元素个数。你往 vector 里塞元素时，如果 size 达到 capacity，vector 就会申请一块更大的内存，把原有元素搬过去，然后释放旧内存。
这个“搬过去”的过程就是扩容。常见策略是每次 capacity 翻倍（有的实现是 1.5 倍），这样分摊下来，每次 push_back 的均摊复杂度是 O(1)。你可以用下面的代码观察扩容次数：
#include <vector> #include <cstdio> int main() { std::vector<int> v; int last_cap = 0; for (int i = 0; i < 100; ++i) { v.push_back(i); int cur = v.capacity(); if (cur != last_cap) { std::printf("capacity changed to %d at size %d\n", cur, v.size()); last_cap = cur; } } return 0; }运行之后你会看到 capacity 在 1、2、4、8、16……这样跳。这告诉你一件事：如果你事先知道大概要放多少元素，直接v.reserve(n)可以避免中间多次扩容和拷贝,尤其是元素类型是自定义 struct 且拷贝成本高的时候，效果非常明显。我写过一段处理百万级点的程序，加了 reserve 之后运行时间从 2.3 秒降到 0.4 秒，差距就是这么来的。
2.2 deque、list、forward_list：什么时候该“背叛”vector
vector 并不是万能的，deque、list、forward_list 各有各的生存空间。deque 的双端队列，底层是一段段连续的缓冲区，靠一个中控器把它们串起来，所以它既支持下标随机访问，又能在头部和尾部做 O(1) 的 push 和 pop。如果你需要一个能在两边同时增删的队列，deque 是比 vector 更合适的选择，因为 vector 在头部插入是 O(n) 的。
list 是双向链表，它最大的优势是“只要拿到了某个位置的迭代器，插入和删除就是 O(1)”，而且不会让其他迭代器失效。但它的劣势也很明显：内存开销大，每个节点通常要额外存储两个指针；遍历时因为内存不连续，缓存命中率差，跑起来往往比 vector 慢一个数量级。所以我在实际代码中很少用 list 做主力容器，除非我真的需要频繁在中间插入删除，并且需要保持元素引用稳定。
forward_list 是 C++11 引入的单向链表，内存开销比 list 更小，但没有 size() 成员，也不支持反向遍历。它适合非常极端的内存敏感场景，比如某种嵌入式环境。array 则是定长的连续数组，直接封装 C 风格数组，但不允许动态增长，适合编译期就知道元素个数的场景，比普通数组多了 begin()、end()、size() 等标准接口，可以丢到 STL 算法里用。
2.3 顺序容器的公共接口和边界行为
所有顺序容器都有相似的接口，但你要特别注意 begin() 和 end() 的语义。end() 指向的是最后一个元素的下一个位置，是一个“哨兵”，你永远不能解引用它。比如用迭代器遍历时，常见的写法是for (auto it = v.begin(); it != v.end(); ++it)，条件判断用的是 != 而不是 <，因为并不是所有容器的迭代器都支持 < 这种随机访问。
容器还提供 insert 和 erase 这类需要传迭代器的操作。vector 的 insert 在中间位置会把后续元素整体后移，迭代器全部失效；list 的 insert 只是改指针，不会失效。这些细节看起来琐碎，但等我到了第 4 节讲迭代器失效时，你会发现它们才是所有坑的根源。
我自己整理笔记时会在这一节补一个提醒：如果你只是想把一组数据放进容器里，不要急着选“看起来很顺眼”的容器，先想想你最频繁的操作是什么。是按下标访问？还是按值查找？还是在头部插入？还是删除中间某个知道迭代器的元素？顺序容器的选择，基本就是这几个问题的答案。
3. 关联容器：有序树与哈希表，同一需求的两条路线
3.1 map/set 的“有序”到底值多少钱
map 和 set 在标准库里通常用红黑树实现，这是一种自平衡的二叉搜索树，插入、删除、查找的复杂度都是 O(log n)，并且迭代时按键升序遍历。这里的“有序”不是白送的，它带来两个实际价值：第一，你可以用 lower_bound 和 upper_bound 做范围查询，比如“找出所有成绩在 80 到 90 分之间的记录”；第二，你可以直接从头到尾遍历得到一个排序好的结果，不需要再单独 sort 一次。
但如果你只是需要按键查值，并不关心顺序，map 就不是最优选。另一个常见的坑是 map 的 operator[] 会默认构造一个键对应的值并插入进去。看这段代码：
std::map<std::string, int> counts; counts["hello"]++; // 如果 "hello" 不存在，会先插入一个 int(0)，再做自增这个行为在很多场景下很方便，但如果你只是想判断某个键是否存在，用 operator[] 就会意外污染容器。正确做法是先 find 或 count，再做下一步处理：
auto it = counts.find("hello"); if (it != counts.end()) { // 键存在，it->second 就是对应值 }multimap 和 multiset 允许重复键，遍历时会把相同键的元素放在相邻位置，一般配合 equal_range 获取这一段范围。不过 C++ 里如果你真的想“键到多个值”，我建议先考虑std::map<Key, std::vector<Value>>这种结构，因为 multimap 的 equal_range 写法容易出错，而且分组操作很不方便。
3.2 unordered_map/unordered_set：哈希平均 O(1) 背后的代价
unordered_map 和 unordered_set 底层是哈希表，理想情况下查找、插入、删除都是平均 O(1)，但这不是没有条件的。它们要求键类型可以哈希，并且支持相等判断。标准库为基本类型和 string 提供了默认哈希，但自定义类型必须你自己实现哈希函数。C++11 之后可以这样写：
#include <unordered_map> #include <string> struct Person { std::string name; int age; }; struct PersonHash { std::size_t operator()(const Person& p) const { std::size_t h1 = std::hash<std::string>{}(p.name); std::size_t h2 = std::hash<int>{}(p.age); return h1 ^ (h2 << 1); } }; std::unordered_map<Person, int, PersonHash> m;哈希表的平均 O(1) 建立在“哈希函数足够均匀”和“负载因子不太高”的前提下。当元素数量超过 bucket 数量的一定比例时，容器会触发 rehash，也就是重新分配桶数组，把已有元素重新放到新桶里。rehash 期间所有迭代器都会失效，而且这是一个很昂贵的操作。如果你预先知道大概要存多少元素，可以用m.reserve(n)提前开好桶，减少 rehash 次数。
unordered_map 最大的另一个特点是迭代顺序不稳定。同一组键值，在不同版本的编译器、甚至不同插入顺序下，遍历顺序都不一样。所以任何依赖遍历顺序的逻辑都不要用无序容器。
3.3 有序还是无序？两个维度决定选择
选择 map 还是 unordered_map，我通常会问自己两个问题：第一，我是否需要对键做范围查询？第二，我是否能容忍最坏情况下的性能波动？哈希表在最坏情况下（哈希冲突严重）查找会退化成 O(n)，而红黑树是稳定的 O(log n)。对于普通业务代码，平均 O(1) 通常很香；但对于实时系统、安全敏感的代码，稳定的 O(log n) 可能更重要。
内存占用上，map 的每个节点需要存储左右子树指针、颜色标记和键值对象，开销较大；unordered_map 的 bucket 数组加节点链表也有额外开销。实际差距并不绝对，但你可以通过一个简单测试感受：插入一千万个整数，map 明显比 unordered_map 慢；但如果你用的是一个设计很差的哈希函数，unordered_map 也可能跑得比 map 还慢。所以别听别人说“unordered_map 快”就无脑用，还是要回到你自己的数据和操作特征。
另外一点：如果你把对象作为 unordered_map 的键插入后，又修改了这个对象的“哈希相关字段”，那么哈希值就变了，但容器并不知道，后续查找就会失败。要修改键，必须是先 erase 再 insert。这个细节属于那种“知道的人秒懂，不知道的人很难查”的坑。
4. 容器适配器和迭代器失效：那些一旦崩溃很难查的问题
4.1 stack/queue/priority_queue 只是包装，不是新容器
PPT 里通常会把 stack、queue、priority_queue 单独提出来，但它们并不是独立的数据结构，而是容器适配器，也就是说它们内部“包”了一个我们前面说的容器，只对外暴露受限的接口。stack 默认用 deque 做底层，queue 也默认用 deque，priority_queue 默认用 vector。
stack 就是后进先出，push 压栈、pop 出栈，没有遍历接口。queue 是先进先出，front 取队首、back 取队尾。priority_queue 则是优先队列，底层是 vector 上的堆结构，插入 O(log n)，取最大元素 O(1)。在写 BFS、Dijkstra 这类算法时，priority_queue 非常常用。
这里有一个很值得注意的点：适配器刻意隐藏了底层容器的接口，所以你不能通过迭代器去遍历它们。这不是缺陷，而是设计目的，它保证你只会用“栈该有的方式”操作 stack，不会因为多余的能力写出错误代码。所以我建议你在业务代码里也用同样的思路：能用适配器表达意图，就不要直接暴露 vector + 手动维护逻辑。
4.2 迭代器失效，一张表说清楚
迭代器失效是容器操作里最阴险的问题，因为它不一定立刻崩溃，往往是在几次操作之后才出现难以解释的内存错误。CS106L 第五讲对这块讲得很细，我把常见的失效场景整理成了一张表：
| 容器 | 插入操作后迭代器情况 | 删除操作后迭代器情况 |
|---|---|---|
| vector | 如果触发扩容，全部失效；如果只插在中间，插入点之后失效 | 被删元素及之后所有迭代器失效 |
| deque | 插入在两端，不影响；插入在中间，全部失效 | 删除在中间，全部失效；删除在两端，指向被删元素的失效 |
| list / forward_list | 除指向被插入节点的迭代器外，其他不失效 | 只有指向被删元素的迭代器失效 |
| map / set | 不影响其他迭代器 | 只有指向被删元素的迭代器失效 |
| unordered_map / unordered_set | 如果触发 rehash，全部失效；否则不影响 | 只有指向被删元素的迭代器失效 |
这张表不需要背，它可以从底层结构推理出来：凡是“元素移动位置”或“内存重新分配”的操作，都会让原有迭代器失效；凡是“只修改指针”的操作，通常不会影响其他迭代器。比如 list 删除一个节点，只是改变前后节点的指针，理论上其他节点的地址没有变化，所以迭代器依然有效。
4.3 用迭代器安全操作容器的原则
在循环里删除元素，很多新手会写出这样的错误代码：
for (auto it = v.begin(); it != v.end(); ++it) { if (*it % 2 == 0) { v.erase(it); // 危险！erase 后 it 已经失效 } }正确做法是让 erase 返回下一个有效迭代器：
for (auto it = v.begin(); it != v.end(); ) { if (*it % 2 == 0) { it = v.erase(it); } else { ++it; } }不过我更推荐用 erase-remove 惯用法，因为它语义清晰，而且不会在遍历过程中移动迭代器：
v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }), v.end());这个惯用法的原理是先通过 remove_if 把所有要删除的元素移动到末尾，然后统一 erase。它避免了在遍历时频繁移动元素，性能通常也更好。
另一个原则是：不要长期保存一个容器内部的迭代器。vector 可能随时扩容，unordered_map 可能随时 rehash，这些都会让迭代器变成野指针。如果你需要一个长期稳定的“指向某个元素的句柄”，可以退而求其次存下标，或者干脆改用 list/deque 这类对迭代器更友好的容器。我在做链表型数据结构时选择 list 作为底层就是出于这个原因。
5. 容器选择的决策指南：我整理这讲 PPT 时写下的方法论
5.1 一张速查表直接抄作业
第五讲 PPT 最大的价值之一，是帮我把散落在各处的容器知识点收敛成一张选型表。下面这张表我写在了笔记首页，平时写代码前会快速过一眼：
| 容器 | 底层结构 | 随机访问 | 增删特点 | 查找效率 | 适用场景 |
|---|---|---|---|---|---|
| vector | 连续内存动态数组 | 支持 O(1) | 尾部 O(1)；中间 O(n) | 按值 O(n) | 默认首选，适合频繁随机访问 |
| deque | 分段连续缓冲区 | 支持 O(1) | 两端 O(1)；中间 O(n) | 按值 O(n) | 双端队列、任务队列 |
| list | 双向链表 | 不支持 | 已知位置 O(1) | 按值 O(n) | 需要稳定迭代器、频繁中间插入删除 |
| forward_list | 单向链表 | 不支持 | 头部 O(1) | 按值 O(n) | 内存受限、单向前进场景 |
| array | 定长连续数组 | 支持 O(1) | 不支持增删 | 按值 O(n) | 编译期定长数据 |
| map | 红黑树 | 不支持（按键找值 O(log n)） | O(log n) | O(log n) | 需要按键有序遍历、范围查询 |
| set | 红黑树 | 不支持 | O(log n) | O(log n) | 去重、有序集合 |
| unordered_map | 哈希表 | 不支持 | 均摊 O(1) | 均摊 O(1) | 只需要按键查值，不关心顺序 |
| unordered_set | 哈希表 | 不支持 | 均摊 O(1) | 均摊 O(1) | 去重、快速成员判断 |
这张表对我的帮助在于，它强迫我把“查找”和“增删”分开思考。有时候你需要频繁增删但很少查找，那 list 或 deque 可能更好；有时候你几乎不做增删，只需要查询，那 unordered_map 通常更合适。
5.2 从需求反推容器：五问法
我不建议直接背表，更好的方式是拿到问题后按顺序问自己几个问题。我现在写代码前都会过一遍这套“五问”：
- 我需要随机访问吗？如果需要，就只能在 vector、deque、array 里选；如果不需要，才轮到 list、set、map 这些。
- 我需要在头部和尾部都增删吗？如果是，deque 比 vector 更适合；如果只是尾部增删，vector 就够了。
- 我需要在中间频繁插入删除，并且希望已有迭代器不被破坏吗？如果是，list 或 forward_list 最合适。
- 我需要按键找值吗？如果需要，再问自己：要不要按 key 排序或范围查询？要就 map，不要就 unordered_map。
- 我需要快速判断某个值是否存在吗？如果需要，set 或 unordered_set 比遍历 vector 强很多。
这套方法让我从“看到容器就选 vector”的状态走了出来。比如实现 LRU Cache 时，我需要快速判断 key 是否存在，又需要维护访问顺序，所以我选择了 unordered_map 存储 key 到链表节点的映射，配合 list 维护顺序，这样 O(1) 完成读写。如果一开始就只用 map 或只用 list，都不可能达到这个性能。
5.3 实际性能感受和内存开销
我自己的实测数据是：插入 1000 万个整数，vector 的 push_back 比 list 的 push_back 快接近一个数量级，原因就是连续内存的缓存局部性。list 每个节点分配在小块内存上，遍历时 CPU 要频繁换缓存行，慢得肉眼可见。所以很多场景下“list 插入 O(1)”并不等于“list 更快”，因为 O(1) 只是操作次数，不包含内存分配开销和缓存命中率的影响。
另一个经验是，尽量使用emplace_back替代push_back。比如存储自定义结构体时，push_back(Person{...})会先构造一个临时对象再拷贝/移动进容器，而emplace_back(...)可以直接在容器内存里构造对象，少一次移动。代码可读性上差别不大，但对性能敏感的程序来说，这个习惯值得养成。
还有一点要提醒：不要为了炫技使用很冷门的容器。如果项目里其他人看到 forward_list 会发怵，那即便它更省内存，维护成本也可能超过收益。做工程不是做题，代码是给人读的，容器的选择要兼顾性能和团队可读性。
6. 实战中的常见坑与排查技巧
6.1 vector 是一个特例，别当 bool 数组用
CS106L 的 PPT 如果够细，应该会提到std::vector<bool>是一个特殊实现。标准库为了节省内存，把它做成了位压缩存储，也就是每个 bool 只占 1 bit，但这样一来，它的元素并不是真正的 bool 对象，返回的是一个代理对象，你不能像普通 bool 那样取引用：
std::vector<bool> flags(10); auto& b = flags[0]; // 编译错误或行为异常如果你需要能取地址的 bool 数组，可以用vector<std::uint8_t>或vector<char>，虽然每个元素占 1 字节，但行为更符合常规预期。这个问题在实际开发中不算高频，但一旦遇到，排查起来很让人抓狂，因为报错信息并不会直接告诉你“vector 是特殊实现”。
6.2 map 的 operator[] 会偷偷插入元素
前文提过map::operator[]在键不存在时会插入一个默认构造的值。这在统计词频时确实很方便，但如果你是要做判断，这会引入额外开销，甚至改变程序逻辑。举个典型例子：
if (m["some_key"] > 0) { ... }如果"some_key"不存在，这段代码会先插入一个 0，再判断 0 > 0，结果是 false。看起来没问题，但容器已经被污染了。更隐蔽的是，如果默认构造函数非常昂贵，或者类型根本没有默认构造函数，这里直接编译不过。我建议默认只在需要“插入并修改”时使用 operator[]，所有“查询”场景都用 find 或者 C++20 的contains（如果编译器支持）。
6.3 使用 STL 算法配合容器，少用手写循环
容器和算法是 STL 的一体两面。当你发现自己在手写 for 循环数元素、找最大值、统计满足条件的个数时，大概率有更简洁的算法替代。比如：
#include <numeric> #include <algorithm> std::vector<int> v = {1, 2, 3, 4}; int sum = std::accumulate(v.begin(), v.end(), 0); auto it = std::find_if(v.begin(), v.end(), [](int x) { return x > 2; }); int cnt = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });这些写法不仅代码更短，而且不容易出现迭代器失效问题，因为算法内部已经帮你处理了边界。另一个很实用的点是：在 C++11 的范围 for 里不要直接修改容器结构。范围 for 本质上持有容器的 begin 和 end 迭代器，如果你在循环体内 insert 或 erase，迭代器可能失效，轻则跳过元素，重则崩溃。需要修改结构时，还是用显式迭代器循环，并且遵守第 4 节的删除规范。
我在 CS106L 这讲笔记的末尾给自己写了三句话：默认用 vector，需要排序键值对就考虑 map，追求平均 O(1) 查找就选 unordered_map；每次不确定迭代器状态时，先在 cppreference 上查迭代器失效表，不要靠记忆硬扛；能用 emplace_back 就不用 push_back，能用算法就不要手写循环。这些经验不是课程考试重点，但它们让我在之后写 C++ 项目时少加了很多班。最后分享一个小习惯：每次拿到一个新的容器场景，我会先把这个容器的 size、capacity、迭代器类型打印出来观察一遍，跑完再下结论。你亲手看到一次 vector 扩容和 unordered_map rehash 的代价，比听十遍理论都管用。
