开篇先把我这几周的进度交代一下。最近在啃斯坦福的 CS106L，这门课和纯讲数据结构的 CS106B 不一样，它走的是“ C++ 标准库怎么用、为什么这么设计”的路子。Lecture 5 正好把 STL 的 Containers 从头到尾过了一遍，我用 PPT 原笔记做底，配合自己实际跑代码验证的结论，整理成这篇结构化笔记。
笔记适合三类人：准备系统过一遍 STL 的 C++ 学习者、写工程时经常在 vector 和 list 之间纠结的开发者、以及想弄明白 map 和 unordered_map 到底该怎么选的人。我不会一个容器一个容器地念函数签名，而是按照 Lecture 5 的思路，把容器家族拆成几条设计主线：内存布局决定性能边界、有序与哈希是两种不同的取舍、迭代器失效是所有容器的共同考点。下面直接进入正文。
1. 先说清楚：Lecture 5 讲容器的方式和普通文档完全不同
1.1 这门课为什么不是“每个容器列一遍 API”
市面上绝大多数 STL 教程，结构都是“vector 有哪些方法、list 有哪些方法、set 有哪些方法”，看完感觉记住了很多函数名，真正写项目时还是不知道用哪个。CS106L 的讲法不一样，它默认你已经会写 C++ 基础代码，然后直接站到“标准库设计者”的视角：每个容器解决的是哪一类内存管理痛点，它的插入、删除、查找操作背后对应多少真实代价。
以 vector 为例，文档只会告诉你“尾部插入均摊 O(1)”。但 Lecture 5 会追问一句：为什么是均摊 O(1)？这就需要理解 capacity 翻倍扩容的机制。你看完才能真正明白 reserve 函数存在的意义，而不是把它当成一个无关紧要的优化选项。这种“从实现反推接口”的思路，贯穿整个 PPT。
1.2 理解容器的三条主线
我在消化这份笔记时，自己总结了三条主线，后面所有章节都围绕它们展开：
- 内存布局决定复杂度：vector、deque、list 底层内存结构完全不同，直接决定了随机访问、头部插入、中间插入谁快谁慢。
- 有序性与查找速度的取舍：set/map 用红黑树保证有序，unordered 系列用哈希表换取 O(1) 查找，代价是失去顺序。
- 迭代器失效规则是容器使用中的头号暗坑：很多线上崩溃和诡异 bug 都源于对失效规则的不清晰认识。
这三条线串起来之后，容器就不是零散知识点了，而是一张可推导的决策图。
2. 容器家族全景：一张表看清 STL 的整个分类体系
2.1 五大类容器的系统划分
标准库容器按组织方式可以分成序列容器、有序关联容器、无序关联容器、容器适配器、以及其他特殊容器这几类。先给一张全景表，建议收藏起来当速查：
| 分类 | 容器名称 | 底层数据结构 | 有序性 | 关键特征 |
|---|---|---|---|---|
| 序列容器 | vector | 连续内存动态数组 | 按插入顺序 | 尾部增删极快，随机访问 O(1) |
| 序列容器 | array | 固定大小原生数组 | 按插入顺序 | C++11 引入，栈上固定大小，无动态扩容 |
| 序列容器 | deque | 分段连续内存 | 按插入顺序 | 头尾增删都是 O(1) |
| 序列容器 | list | 双向链表 | 按插入顺序 | 任意位置插入删除 O(1)，但随机访问 O(n) |
| 序列容器 | forward_list | 单向链表 | 按插入顺序 | 比 list 更省内存，只能单向遍历 |
| 有序关联容器 | set / multiset | 红黑树 | 自动排序 | 元素唯一（set），查找 O(log n) |
| 有序关联容器 | map / multimap | 红黑树 | 按键自动排序 | 键值对存储，按键查找 O(log n) |
| 无序关联容器 | unordered_set / unordered_multiset | 哈希表 | 无序 | 平均 O(1) 查找，元素无序 |
| 无序关联容器 | unordered_map / unordered_multimap | 哈希表 | 无序 | 键值对，哈希存储，无顺序概念 |
| 容器适配器 | stack | 底层封装 deque 或 vector | 后进先出 | 只暴露 push/pop/top |
| 容器适配器 | queue | 底层封装 deque | 先进先出 | 只暴露 push/pop/front/back |
| 容器适配器 | priority_queue | 底层封装 vector + 堆 | 按优先级 | 最大元素始终在顶部 |
2.2 适配器不是新型容器，而是“行为约束层”
stack、queue、priority_queue 在 Lecture 5 里被单独提出来讲，是因为它们本质上不拥有自己的存储结构，而是把已有的序列容器包装起来，只暴露出受限的接口。stack 默认底层是 deque，也可以显式传入 vector；priority_queue 默认底层是 vector，通过堆算法维持“最大元素在顶”的性质。
这里有个值得思考的设计意图：适配器存在的意义是防止误用。你如果拿 vector 当栈用，调用方可能不小心用下标访问中间元素，破坏栈的语义。包一层 stack 之后，接口直接锁死，编译期就不允许越权操作。项目里如果只是临时需要一个栈结构，直接写 stack 比手搓 vector 加 push_back/pop_back 要清晰得多。
2.3 一个重要澄清：STL 容器和部署领域的 Container 不是一回事
搜索“Containers”很容易混进操作系统和云原生领域的容器概念，比如 Windows Server 上的容器部署方案。这里明确区分一下：STL 的 Container 是 C++ 标准库中对“存储并管理一组同类型对象”的抽象；部署领域的 Container 是操作系统层面的进程隔离与打包方案。两者连技术栈都不同，一个是模板类，一个是内核特性。CS106L 整节课讲的都是前者，我在写这篇笔记时也把注意力完全放在 C++ 容器家族上，避免术语混淆。
3. vector、deque、list：三种序列容器的内存哲学
3.1 vector 的扩容机制与均摊 O(1) 是怎么算出来的
先看一段最普通的代码，我建议你在自己的环境里跑一下，观察 capacity 的变化：
#include <vector> #include <iostream> int main() { std::vector<int> v; for (int i = 0; i < 16; ++i) { v.push_back(i); std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << '\n'; } return 0; }在主流编译器的实现里，输出容量变化大致是1, 2, 4, 8, 16，也就是每次扩容都翻倍。为什么标准不规定具体增长倍数？因为标准只要求 push_back 的均摊复杂度为 O(1)，实现只要满足这个要求，具体因子自选。倍数太小（比如 1.1 倍）会导致频繁申请内存和搬运元素，倍数太大（比如 4 倍）又会浪费大量空间，工程实现普遍在 1.5 到 2 倍之间。
推导均摊复杂度也很简单：假设从空 vector 连续插入 n 个元素，capacity 依次翻倍到 1、2、4、8……直到不小于 n。扩容时把旧元素全部拷贝到新内存，累计拷贝次数大约是1 + 2 + 4 + ... + 2^k ≈ 2n。也就是说插入 n 次总共只付出了约 2n 次元素拷贝，平摊下来每次插入的拷贝量是常数。这才是“均摊 O(1)”的真正含义。
正因为扩容代价隐藏在这个“均摊”里，如果你预先知道元素规模，直接调用v.reserve(n)可以彻底避免中途扩容带来的大量重复拷贝。这算是我在实际项目中收获最大的一条经验：高频插入前先 reserve，是性价比最高的容器优化，没有之一。
3.2 deque 的分段连续结构：为什么它能让头尾插入都成为 O(1)
deque 的全称是 double-ended queue，它同时支持头尾两端的高效插入删除。它的底层不是完整连续的内存，而是由一小段一小段的连续缓冲区组成，这些缓冲区的指针再统一存放在一个中央 map 里。访问元素时，先通过 map 定位到所在缓冲区，再通过偏移量定位到具体元素，所以随机访问仍然是 O(1)。但要注意，这个 O(1) 比 vector 的 O(1) 多了一次间接寻址，常数因子更大。
在讲 PPT 时有一个很好的生活化类比：vector 就像一块完整的地基，想加长就得整体搬迁；deque 就像一串连在一起的集装箱，需要在前头开门时，只需要新增一个集装箱并挂到链上。所以如果你的核心场景是“频繁在头部插入、在尾部删除”，deque 比 vector 合适得多。
需要强调的坑是：deque 并非所有插入都高效。在中间位置插入元素，仍然要移动大量元素来腾出空位，复杂度 O(n)。很多初学者把 deque 理解成“处处 O(1)”的万能容器，这是明显的认知偏差。
3.3 list 的代价：为什么 O(1) 插入却不一定更快
list 是双向链表，只要拿到某个位置的迭代器，插入和删除都是 O(1)，因为它只需要改几个指针。这看起来很强势，但 Lecture 5 的代码演示里其实给过很关键的提醒：list 的 O(1) 是在“你已经有迭代器指向那个位置”的前提下才成立。如果要先找到那个位置，查找本身就是 O(n)。
更隐蔽的问题是缓存友好性。vector 里的元素在内存中连续排列，遍历时 CPU 缓存命中率极高；list 的节点分散在各处，遍历时每次访问下一个节点都可能触发缓存缺失。实测在数据量较大时，vector 的“低效中间插入”加“来回搬数据”综合起来，很多时候反而比 list 的“高效插入但缓存全废”更快。这也是现代 C++ 工程里有一个共识的原因：默认用 vector，只有在迭代器必须长期稳定、频繁中间增删且元素本身很大时，才认真考虑 list。
4. 有序与哈希的博弈：set/map 与 unordered 家族的选型逻辑
4.1 红黑树容器为什么能自动有序
set 和 map 底层是红黑树，这是一种自平衡二叉查找树。它保证每个节点的左右子树高度差不超过一定范围，从而让查找、插入、删除都稳定在 O(log n)，并且中序遍历的结果天然有序。
你可能会问：既然哈希表能做到平均 O(1)，为什么还要红黑树？核心原因是顺序本身是需求。如果你需要按键从小到大遍历、需要求某个范围内的所有元素、需要拿到最小或最大键，红黑树可以直接做到，而哈希表把元素打散到各个桶里后完全没有顺序概念。map 的典型场景是“需要按下标顺序输出统计结果”，这个时候 map 就是天然的选择。
另一个细节是 multiset 和 multimap 的存在意义：普通 set/map 要求键唯一，如果你需要存储重复键并对重复键做统计，multiset/multimap 允许重复键且仍然保持有序。它们底层是同一棵树，只是插入时不拒绝重复键。
4.2 unordered 容器的哈希原理与负载因子
unordered 系列的底层是哈希表，用一个数组作为桶数组，元素通过哈希函数映射到某个桶。如果多个元素落到同一个桶，就在桶内用链表或者更复杂的结构串联，这就是哈希冲突。
哈希表最核心的性能参数是负载因子（load factor），定义为元素个数除以桶数量。负载因子越高，冲突概率越大，查找可能退化成链表遍历；负载因子太低，则浪费内存。标准库默认的 load factor 上限通常是 1.0，当超过这个阈值时会自动 rehash，也就是桶数量翻倍并重新分布所有元素。rehash 导致所有迭代器失效，这一点在工程中要格外小心：不要在持有 unordered_map 的迭代器时往里大量插入新元素，否则迭代器可能瞬间全废。
使用自定义类型作为键时，必须提供哈希函数和相等判断。Lecture 5 里给过一个典型示例思路：为自定义结构特化std::hash并重载operator==。我后面第三节实操部分会给出完整可复现代码。
4.3 map 的 [] 运算符陷阱和现代替代接口
map 中operator[]的行为比看起来危险得多：如果键不存在，它不会报错，而是自动插入一个默认构造的值，然后返回引用。这个设计在写map[key]++做统计时很方便，但如果你的本意只是“查一下这个键存不存在”，就会在不经意间向容器中添加了大量垃圾键值对。
一个真实场景：有一段日志分析代码用if (m.find(key) != m.end())判断条件时改成if (m[key])，逻辑上没有立刻出错，但 map 的 size 在不断增长，内存持续膨胀。排查了半天才发现是[]自动插入了默认值。所以查找时请使用find或者 C++11 引入的at，后者在键不存在时直接抛out_of_range异常。
C++17 又给了两个更好用的接口：insert_or_assign和try_emplace。前者做到“存在则更新、不存在则插入”，后者可以在键不存在时才原地构造 value，避免不必要的临时对象构造。如果工程是 C++17 及以上，建议优先用这两个接口替代[]和emplace。
5. 实操经验：三步完成容器选型，再用两个 API 释放性能
5.1 一套能直接落地的选型决策流程
我自己在项目里做容器选型，很少直接背表格，而是问下面四个问题，顺序固定：
- 要存储的是单个元素还是键值对？键值对直接进入 map 或 unordered_map 的赛道；单元素进入序列容器赛道。
- 需不需要自动排序或范围查询？需要就用 set/multiset/map/multimap；不需要就考虑 unordered 系列或者序列容器。
- 要求的操作集中在哪一端？只在尾部增删用 vector；头尾都要高频增删用 deque；经常在中间插入且插入位置往往已知用 list。
- 是否要求迭代器长期稳定？vector 扩容会让迭代器全部失效，deque 在两端的操作不影响迭代器，list 只要不删除当前节点迭代器基本稳定。
把这个流程做成一张速查表：
| 核心需求 | 推荐容器 | 原因 |
|---|---|---|
| 按下标随机访问，尾部追加 | vector | 连续内存，CPU 缓存友好 |
| 头部和尾部都要高频增删 | deque | 双端 O(1) 操作 |
| 经常在中间插入，元素大 | list | 节点插入不搬移元素本体 |
| 需要按键从小到大遍历 | map / set | 红黑树天然有序 |
| 只求极快查找，不在乎顺序 | unordered_map / unordered_set | 哈希表平均 O(1) |
| 固定大小数组，不想动态扩容 | array | 编译期定长，栈上分配 |
| 只需要先进后出或先进先出 | stack / queue | 封装底层容器，接口受限防误用 |
5.2 reserve 与 emplace 的组合拳
这段是 Lecture 5 实操价值浓度最高的部分。先看代码：
#include <vector> #include <string> #include <iostream> struct Product { int id; std::string name; Product(int i, std::string n) : id(i), name(std::move(n)) {} }; int main() { std::vector<Product> products; products.reserve(1000); // 预分配，避免多次扩容拷贝 for (int i = 0; i < 1000; ++i) { products.emplace_back(i, "product_" + std::to_string(i)); } std::cout << "size: " << products.size() << ", capacity: " << products.capacity() << '\n'; return 0; }emplace_back和push_back的关键差异在参数传递方式上。push_back需要先构造一个 Product 临时对象，再拷贝或移动到容器内；emplace_back直接把构造参数传给容器的内存，在容器内部完成原地构造，省掉一次临时对象的构造和移动。当元素类型包含 string、vector 这类重重量级成员时，前者白花的成本不小。
组合reserve和emplace_back是我实际压测里看到的最突出的一组优化：往 vector 里插入 10 万个自定义对象，不 reserve 时因为反复扩容加临时对象构造，耗时可能多出 30% 以上；先 reserve 预估容量，再用 emplace 原地构造，整体耗时立刻下来一大截。而且代码读起来更紧凑，语义也更明确。
5.3 自定义类型进 unordered_set/容器，必须手动补两个零件
把自定义类型放进哈希容器，代码会直接编译失败，因为标准库不知道怎么计算你的类型的哈希值。解决办法是补两个零件：std::hash的特化和operator==的重载。
#include <unordered_set> #include <string> struct User { int uid; std::string nickname; bool operator==(const User& other) const { return uid == other.uid && nickname == other.nickname; } }; namespace std { template <> struct hash<User> { size_t operator()(const User& u) const { size_t h1 = hash<int>{}(u.uid); size_t h2 = hash<string>{}(u.nickname); return h1 ^ (h2 << 1); } }; } int main() { std::unordered_set<User> users; users.insert(User{1, "admin"}); return 0; }两个隐藏问题值得展开：
第一，哈希函数的组合为什么用h1 ^ (h2 << 1)？因为直接h1 ^ h2会让两个只交换字段顺序的对象哈希相同，容易冲突；把第二个哈希左移一位再异或，能有效减少对称碰撞。工程中也可以用hash_combine这类成熟方法。
第二，operator==必须判断所有关键字段。如果只比较uid，两个 nickname 不同但 uid 相同的对象会被视为相等，语义会出现严重错误。哈希容器先通过哈希值定位桶，再在桶内用operator==精确比较，两个零件缺一不可。
6. 常见问题与排查技巧实录
6.1 迭代器失效场景速查表
这条是容器使用里最容易被背刺的部分。我把常见容器的失效规则整理成表：
| 容器 | 操作 | 失效范围 |
|---|---|---|
| vector | push_back 触发扩容 | 所有迭代器、引用、指针全部失效 |
| vector | push_back 未触发扩容 | 只有 end() 迭代器失效 |
| vector | insert / erase（中间位置） | 插入或删除位置之后的全部失效 |
| deque | 头尾 push/pop | 所有迭代器失效，但引用和指针不失效 |
| deque | 中间 insert / erase | 全部迭代器、引用、指针失效 |
| list / forward_list | insert / erase（非当前节点） | 操作节点外的所有迭代器仍然有效 |
| unordered_map | rehash | 所有迭代器失效 |
我踩过的典型坑是：在 vector 循环里 push_back 新元素，同时拿着之前获取的引用继续读写。扩容发生时，旧内存被释放，旧引用访问到的是一块已归还给系统的内存，读出来是垃圾数据，写进去直接造成越界。解决思路很简单：需要频繁插入且要持有元素地址时，要么用 list，要么先 reserve 到足够容量，保证扩容不发生。
6.2 erase 和 remove 配错导致“删了却还在”
这是一个 C++ 经典新坑。std::remove并不会真的删除元素，它只是把符合条件的元素移到序列末尾，并返回新的逻辑 end 迭代器。如果只调用 remove 而不接 erase，vector 的 size 不会变化，打印出来元素“还在”。
正确写法是erase-remove 惯用法：
#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> v{1, 2, 3, 2, 4, 2, 5}; v.erase(std::remove(v.begin(), v.end(), 2), v.end()); for (int x : v) std::cout << x << ' '; return 0; }这里 remove 把不等于 2 的元素往前挪，把等于 2 的元素堆到尾部；之后 erase 把从新逻辑结尾到真结尾这段空间的数据一次性清理并缩小容器。整个过程是两层配合，单用任何一个都不行。
C++20 之后标准库为所有序列容器提供了统一的成员函数std::erase，比如std::erase(v, 2)，一行就能完成同样效果且不用记惯用法。如果编译器允许 C++20，建议优先用这个。
6.3 容量只增不减：shrink_to_fit 和 swap 技巧
vector 的 capacity 会自动增长，但不会主动缩减。哪怕你清空了所有元素，capacity 仍然占据大量内存。如果这是个长期运行的服务器进程，一次快速增长的峰值容量可能让内存占用迟迟降不下来。
遇到这种情况，有两个常用手段。一是调用v.shrink_to_fit()，这是 C++11 提供的非强制请求，建议实现会尝试把容量缩减到当前 size；二是用交换临时对象的方式，这个技巧更传统也更可控：
std::vector<int>().swap(v); // 清空并释放所有内存它的原理是用一个空 vector 与 v 交换底层缓冲区，临时对象析构时把大内存带走。要清空且释放内存时，不管clear()还是resize(0)都做不到，只有交换式释放才是真正还给系统。做服务器端开发的朋友，如果观察到内存仪表盘持续走高，优先怀疑这类“capacity 守着旧时空”的问题。
一点个人体会
把 Lecture 5 完整消化完再回头看自己以前的代码，最大的改变是：不再迷信某个容器“绝对好”。vector 很强，list 听起来很优雅，unordered_map 很快，但如果脱离了具体场景，这些结论都可能误导你。我在实际开发中最常遇到的依然是把 vector 当万能容器用，等到规模上来之后才想起 reserve 和 emplace；而一旦涉及键值查找，又常常忘了[]的隐式插入给 map 带来多少垃圾数据。
整理这份笔记时，我又花了一周时间在本地跑完每一条扩容、失效、哈希冲突的实验，亲眼看到 capacity 的变化曲线和 rehash 后的迭代器失效，才对 PPT 里的复杂度分析有了真正的体感。如果这篇笔记能帮你少走一次迭代器失效的弯路、少一次因为没 reserve 产生的白工，那这次整理就值了。
