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_backvector 是 C 里默认容器的首选这一点没有任何争议。它的核心是一块连续内存支持下标随机访问复杂度是 O(1)而且内存局部性好遍历时 CPU 缓存利用率很高。但真正理解 vector你必须把它看成两个数的组合size 和 capacity。size 是当前实际元素个数capacity 是在不重新分配内存的情况下最多能容纳的元素个数。你往 vector 里塞元素时如果 size 达到 capacityvector 就会申请一块更大的内存把原有元素搬过去然后释放旧内存。这个“搬过去”的过程就是扩容。常见策略是每次 capacity 翻倍有的实现是 1.5 倍这样分摊下来每次 push_back 的均摊复杂度是 O(1)。你可以用下面的代码观察扩容次数#include vector #include cstdio int main() { std::vectorint 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什么时候该“背叛”vectorvector 并不是万能的deque、list、forward_list 各有各的生存空间。deque 的双端队列底层是一段段连续的缓冲区靠一个中控器把它们串起来所以它既支持下标随机访问又能在头部和尾部做 O(1) 的 push 和 pop。如果你需要一个能在两边同时增删的队列deque 是比 vector 更合适的选择因为 vector 在头部插入是 O(n) 的。list 是双向链表它最大的优势是“只要拿到了某个位置的迭代器插入和删除就是 O(1)”而且不会让其他迭代器失效。但它的劣势也很明显内存开销大每个节点通常要额外存储两个指针遍历时因为内存不连续缓存命中率差跑起来往往比 vector 慢一个数量级。所以我在实际代码中很少用 list 做主力容器除非我真的需要频繁在中间插入删除并且需要保持元素引用稳定。forward_list 是 C11 引入的单向链表内存开销比 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::mapstd::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::mapKey, std::vectorValue这种结构因为 multimap 的 equal_range 写法容易出错而且分组操作很不方便。3.2 unordered_map/unordered_set哈希平均 O(1) 背后的代价unordered_map 和 unordered_set 底层是哈希表理想情况下查找、插入、删除都是平均 O(1)但这不是没有条件的。它们要求键类型可以哈希并且支持相等判断。标准库为基本类型和 string 提供了默认哈希但自定义类型必须你自己实现哈希函数。C11 之后可以这样写#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::hashstd::string{}(p.name); std::size_t h2 std::hashint{}(p.age); return h1 ^ (h2 1); } }; std::unordered_mapPerson, 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 也默认用 dequepriority_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::vectorbool是一个特殊实现。标准库为了节省内存把它做成了位压缩存储也就是每个 bool 只占 1 bit但这样一来它的元素并不是真正的 bool 对象返回的是一个代理对象你不能像普通 bool 那样取引用std::vectorbool flags(10); auto b flags[0]; // 编译错误或行为异常如果你需要能取地址的 bool 数组可以用vectorstd::uint8_t或vectorchar虽然每个元素占 1 字节但行为更符合常规预期。这个问题在实际开发中不算高频但一旦遇到排查起来很让人抓狂因为报错信息并不会直接告诉你“vector 是特殊实现”。6.2 map 的 operator[] 会偷偷插入元素前文提过map::operator[]在键不存在时会插入一个默认构造的值。这在统计词频时确实很方便但如果你是要做判断这会引入额外开销甚至改变程序逻辑。举个典型例子if (m[some_key] 0) { ... }如果some_key不存在这段代码会先插入一个 0再判断 0 0结果是 false。看起来没问题但容器已经被污染了。更隐蔽的是如果默认构造函数非常昂贵或者类型根本没有默认构造函数这里直接编译不过。我建议默认只在需要“插入并修改”时使用 operator[]所有“查询”场景都用 find 或者 C20 的contains如果编译器支持。6.3 使用 STL 算法配合容器少用手写循环容器和算法是 STL 的一体两面。当你发现自己在手写 for 循环数元素、找最大值、统计满足条件的个数时大概率有更简洁的算法替代。比如#include numeric #include algorithm std::vectorint 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; });这些写法不仅代码更短而且不容易出现迭代器失效问题因为算法内部已经帮你处理了边界。另一个很实用的点是在 C11 的范围 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 的代价比听十遍理论都管用。 
长河君 · 2026/10/9 4:16:48 · 阅读 1.2k C++容器底层原理与选型：从vector到unordered_map
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_backvector 是 C 里默认容器的首选这一点没有任何争议。它的核心是一块连续内存支持下标随机访问复杂度是 O(1)而且内存局部性好遍历时 CPU 缓存利用率很高。但真正理解 vector你必须把它看成两个数的组合size 和 capacity。size 是当前实际元素个数capacity 是在不重新分配内存的情况下最多能容纳的元素个数。你往 vector 里塞元素时如果 size 达到 capacityvector 就会申请一块更大的内存把原有元素搬过去然后释放旧内存。这个“搬过去”的过程就是扩容。常见策略是每次 capacity 翻倍有的实现是 1.5 倍这样分摊下来每次 push_back 的均摊复杂度是 O(1)。你可以用下面的代码观察扩容次数#include vector #include cstdio int main() { std::vectorint 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什么时候该“背叛”vectorvector 并不是万能的deque、list、forward_list 各有各的生存空间。deque 的双端队列底层是一段段连续的缓冲区靠一个中控器把它们串起来所以它既支持下标随机访问又能在头部和尾部做 O(1) 的 push 和 pop。如果你需要一个能在两边同时增删的队列deque 是比 vector 更合适的选择因为 vector 在头部插入是 O(n) 的。list 是双向链表它最大的优势是“只要拿到了某个位置的迭代器插入和删除就是 O(1)”而且不会让其他迭代器失效。但它的劣势也很明显内存开销大每个节点通常要额外存储两个指针遍历时因为内存不连续缓存命中率差跑起来往往比 vector 慢一个数量级。所以我在实际代码中很少用 list 做主力容器除非我真的需要频繁在中间插入删除并且需要保持元素引用稳定。forward_list 是 C11 引入的单向链表内存开销比 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::mapstd::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::mapKey, std::vectorValue这种结构因为 multimap 的 equal_range 写法容易出错而且分组操作很不方便。3.2 unordered_map/unordered_set哈希平均 O(1) 背后的代价unordered_map 和 unordered_set 底层是哈希表理想情况下查找、插入、删除都是平均 O(1)但这不是没有条件的。它们要求键类型可以哈希并且支持相等判断。标准库为基本类型和 string 提供了默认哈希但自定义类型必须你自己实现哈希函数。C11 之后可以这样写#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::hashstd::string{}(p.name); std::size_t h2 std::hashint{}(p.age); return h1 ^ (h2 1); } }; std::unordered_mapPerson, 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 也默认用 dequepriority_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::vectorbool是一个特殊实现。标准库为了节省内存把它做成了位压缩存储也就是每个 bool 只占 1 bit但这样一来它的元素并不是真正的 bool 对象返回的是一个代理对象你不能像普通 bool 那样取引用std::vectorbool flags(10); auto b flags[0]; // 编译错误或行为异常如果你需要能取地址的 bool 数组可以用vectorstd::uint8_t或vectorchar虽然每个元素占 1 字节但行为更符合常规预期。这个问题在实际开发中不算高频但一旦遇到排查起来很让人抓狂因为报错信息并不会直接告诉你“vector 是特殊实现”。6.2 map 的 operator[] 会偷偷插入元素前文提过map::operator[]在键不存在时会插入一个默认构造的值。这在统计词频时确实很方便但如果你是要做判断这会引入额外开销甚至改变程序逻辑。举个典型例子if (m[some_key] 0) { ... }如果some_key不存在这段代码会先插入一个 0再判断 0 0结果是 false。看起来没问题但容器已经被污染了。更隐蔽的是如果默认构造函数非常昂贵或者类型根本没有默认构造函数这里直接编译不过。我建议默认只在需要“插入并修改”时使用 operator[]所有“查询”场景都用 find 或者 C20 的contains如果编译器支持。6.3 使用 STL 算法配合容器少用手写循环容器和算法是 STL 的一体两面。当你发现自己在手写 for 循环数元素、找最大值、统计满足条件的个数时大概率有更简洁的算法替代。比如#include numeric #include algorithm std::vectorint 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; });这些写法不仅代码更短而且不容易出现迭代器失效问题因为算法内部已经帮你处理了边界。另一个很实用的点是在 C11 的范围 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 的代价比听十遍理论都管用。