1. 为什么要专门写一篇容器全景聊到 C STL绕不开的就是容器。很多人学 STL 是从 vector 入手的用熟了 vector 之后list、deque、set 往往只是“听说过、用过一点、但不太清楚什么时候该换”。结果就是项目里几乎所有场景都用 vector遇到性能问题也不知道是不是容器选的锅。这一篇算是系列里的承上启下之作——把 vector、list、deque、set 四个最常用的容器放一起从底层数据结构、适用场景、性能特征到实际写法全部过一遍力求让你看完之后能对“我这行代码该用哪个容器”有一个比较靠谱的判断。这篇文章适合两类人一类是刚把语法过完、开始写实际项目的同学另一类是已经写了一阵子 C、但发现自己每次选容器都是靠直觉的开发者。我会尽量少讲抽象的理论多讲“这个容器底层是怎么存的、这一步操作实际做了什么、什么情况下它会变慢”因为只有把这几件事想明白才算真正会用容器而不是会查文档。需要提前说明的是本文默认你的编译环境支持 C11 及以上的标准个别示例会用到 C17 的特性比如 structured binding、string_view如果你还在用老标准代码上稍作调整即可核心思路完全不受影响。另外性能数据我会给出结论性的东西不贴具体的计时代码——容器性能在不同标准库实现、不同平台上的差异本来就不小去做微基准实测的意义有限更重要的是理解操作复杂度和内存访问模式。2. vector大多数场景下的首选但别让它变成万能药2.1 vector 底层到底是怎么存的vector 的底层是一块连续的内存空间它维护三个指针start、finish、end_of_storage分别指向已用空间的起始、已用空间的末尾、以及当前已分配容量的末尾。这个设计和 C 数组本质上是同一套东西只是 vector 额外帮你管理了扩容和生命周期。正因为底层是连续内存vector 具备两个其他容器难以比拟的优势一是随机访问极快下标操作就是一次指针偏移时间复杂度 O(1)二是缓存友好度极高CPU 加载连续内存时预取效率远高于跳着访问这在现代计算机体系结构下对程序性能的影响往往比时间复杂度更大。我们来看一个最简单的例子感受一下 vector 的声明和基本操作#include vector #include string #include algorithm #include iostream struct User { int id; std::string name; }; int main() { std::vectorUser users; users.reserve(100); // 预留容量避免频繁扩容 users.push_back({1, Alice}); users.push_back({2, Bob}); users.push_back({3, Charlie}); // 随机访问 std::cout users[1].name \n; // 排序 std::sort(users.begin(), users.end(), [](const User a, const User b) { return a.id b.id; }); // 删除指定条件的元素erase-remove 惯用法 users.erase(std::remove_if(users.begin(), users.end(), [](const User u) { return u.id 2; }), users.end()); }2.2 扩容机制你以为的 push_back 背后发生了什么vector 的 push_back 在容量不足时会触发扩容扩容的策略通常是倍数增长比如 1.5 倍或 2 倍具体取决于标准库实现。这意味着它要重新申请一块更大的内存然后把旧元素移动或拷贝过去最后释放旧内存。这个过程是 O(n) 的但均摊下来每次 push_back 仍然是 O(1)——因为扩容的次数随着容量增大呈对数增长大部分 push_back 都不需要扩容。但是扩容有两个隐蔽的成本很多人没意识到。第一扩容时所有迭代器、指针、引用都会失效如果你在遍历的同时保存了元素的地址扩容后它们全变成悬空指针第二对于非平凡类型比如含有 string、vector 的类扩容涉及移动构造或拷贝构造这个开销可能相当可观。所以我们看到生产代码里常见的做法是如果能预估元素数量就先用 reserve 把容量准备好把扩容次数降到最低。std::vectorint plain; std::vectorint reserved; reserved.reserve(10000); for (int i 0; i 10000; i) { plain.push_back(i); reserved.push_back(i); }上面这段代码reserved 的版本在整个循环中只分配一次内存而 plain 则可能触发十几次或更多次扩容和搬运。虽然 int 的搬运很便宜但换成重量级对象之后差距会非常明显。2.3 头插和中间插入vector 的软肋vector 的内存布局决定了它在头部插入一个元素时必须把后面所有元素都往后挪一位。一次 push_front 的时间复杂度是 O(n)如果你循环 n 次在头部插入元素总复杂度就是 O(n²)这在数据量一大时直接就卡死了。所以 vector 的适用场景非常明确读多写少只需要尾部添加元素需要频繁随机访问需要频繁按区间遍历一旦你的场景变成“频繁在头部插入”或者“频繁在中间插入删除”就应该考虑别的容器。这里有一个容易踩的点很多人觉得 vector 有 insert 接口所以可以直接用它做中间插入数据量小的时候确实没问题但数据量一旦上千每次插入都要搬移大量元素性能会迅速劣化。2.4 配合 reserve / resize / shrink_to_fit 的实操细节reserve 只改容量不改 sizeresize 会改变 size——如果新的 size 大于当前 size新元素会被值初始化。这两个东西经常被搞混我实际见过有人用 resize(0) 代替 clear()这个可以但 resize 如果参数写错了比如把 resize(10000) 写成 reserve(10000)后续逻辑再依赖 size 判断就会出问题。还有一个不常用但很实用的操作 shrink_to_fit它请求把容量缩减到当前大小。注意是“请求”——标准库可以不执行。在 C11 里它是非绑定的但在主流实现中比如常见的几个标准库调用之后通常确实会把多余容量释放掉。它的典型适用场景是一个容器在某个阶段被填充了海量数据之后长期保留但只有少量元素此时 shrink_to_fit 能帮你把内存还回去。std::vectorint v(1000000, 0); v.clear(); v.shrink_to_fit(); // 容量降到 0内存被释放不过实话实说我很少主动调用 shrink_to_fit因为内存回收给操作系统这种事本来就未必能立竿见影而且如果之后又要从此前的状态继续增长shrink 之后再扩容的开销反而更亏。它更适合那种“一次性大容量用途结束后长期存留”的场景。3. list双向链表的真实面貌以及它被高估的删除效率3.1 list 的底层结构非连续内存的代价和收益list 在标准库中是双向链表每个节点包含三个部分数据、指向前一个节点的指针、指向后一个节点的指针。没有随机访问不能用下标甚至不能只传一个迭代器给 sort——list 提供的是成员函数 sort因为它没有随机访问迭代器通用的 std::sort 根本用不了。很多人觉得链表“插入删除是 O(1)所以肯定快”这句话只对了一半。插入删除的 O(1) 指的是在已知位置的情况下修改几个指针的开销它省掉的是 vector 搬移元素的成本。但随之而来的代价是每一个节点都是独立分配的内存遍历时完全无法预取缓存命中率很低。在数据量小比如几百个元素以内的时候list 的遍历性能往往比 vector 差一个数量级因为连续内存的 cache 友好度对性能的影响远大于 big-O 复杂度。来看一个具体例子模拟在中间位置反复插入的场景#include list #include iostream int main() { std::listint l {1, 2, 3, 4, 5}; // 找到值为 3 的位置O(n) auto it std::find(l.begin(), l.end(), 3); // 在它前面插入O(1) l.insert(it, 99); // 删除值为 99 的节点 auto it2 std::find(l.begin(), l.end(), 99); l.erase(it2); for (int x : l) std::cout x ; }这看起来很好用但要找“值为 3”的位置本身就花了 O(n)。所以 list 的插入删除能到 O(1)前提是你已经持有指向那个位置的迭代器——大多数实际场景下这个前提很难成立。3.2 什么时候该用 list什么时候不该用用 list 的合理场景有这么几类对迭代器稳定性有硬性要求——插入删除不会让其他迭代器失效这在某些复杂数据结构算法里很关键频繁在任意位置插入删除而且你已经持有迭代器需要常数时间的拼接操作splice把一段链表从一条移到另一条头插也是 list 的强项push_front 是 O(1)这正好补上 vector 的短板。如果你的核心需求就是高频头插且不需要随机访问list 是合理选择。但要警惕一个反向场景你只是需要一个线性序列中间偶尔插入删除其余时间都是遍历。这种时候 vector 几乎总是更快哪怕它中间插入是 O(n)——因为那个 n 很小而链表遍历慢的特性是全量无差别的。说白了数据量小的时候 vector 全方面碾压 list数据量大的时候又只有特定模式持有迭代器的频繁增删才真正需要 list。3.3 迭代器失效规则的对比list 是相对的优等生迭代器失效是 C 容器里最让人头大的问题之一。vector 只要发生扩容全部迭代器失效插入导致元素移动时从插入位置到末尾的迭代器全部失效erase 之后被删位置后面的迭代器全部失效。list 在这方面友好得多insert 不导致任何迭代器失效erase 只让被删节点的迭代器失效。这意味着你可以放心地在遍历过程中删除当前元素——只要先把迭代器保存为 next再 erase 当前。这个操作在 list 中不需要任何特殊技巧std::listint l {1, 2, 3, 4, 5}; for (auto it l.begin(); it ! l.end();) { if (*it % 2 0) { it l.erase(it); // 返回下一个有效迭代器 } else { it; } }注意这里不能直接把 erase(it) 后面加 it因为 erase 之后 it 已经失效。但在 list 上 erase 返回下一个迭代器所以这种写法最稳妥。这也是为什么很多对迭代器稳定性敏感的数据结构会用 list 作为基础——它能在遍历时安全地做结构性修改。3.4 list 的 sort、merge、splice 成员函数值得分开说list 自带的 sort 和 merge 有时候会被忽略但它们其实很有用。list 没有随机访问迭代器所以不能用 std::sort但它的成员函数 sort 使用了归并排序的变体复杂度是 O(n log n)稳定性也有保证。merge 要求两个 list 都已排序结果仍然是排序的这个操作是 O(n)而且可以通过指针调整完成不需要新建节点。splice 是 list 独有的能力把一段链表从一条 list 平移到另一条整个操作只改指针是真正的 O(1)在已知位置的情况下而且不涉及拷贝或移动。这在某些调度算法、任务队列设计里非常好用。我个人做项目时见到的最大误用是把 splice 当成 insert 用——如果只是插入单个节点从哪条 list 移到哪条 list注意先确认被移出的 list 不会在后续被析构否则节点就没了。4. deque两头都能操作但也别忽略它的中间地带4.1 deque 的底层设计分段连续而不是你以为的循环数组deque 的底层是一个分段连续缓冲区通常由一块块固定大小的内存块block组成这些内存块由中控器map统一管理。每块内存内部是连续存储的块之间通过指针串联。这样设计的好处是既不像 vector 那样需要整体搬移扩容也不像 list 那样每个元素都单独分配内存。因为内部是分段连续deque 支持 O(1) 的 push_back 和 push_front同时支持高效的随机访问——注意只是“高效”不是“极快”。随机访问 deque 需要先计算出元素在哪一块再计算块内偏移比 vector 的下标运算多了一步间接寻址。所以随机访问性能上 vector 快于 deque但差距通常不大遍历性能方面 deque 也稍逊于 vector但远好于 list。4.2 push_front 是 deque 的主场但它的扩容代价不一样deque 在头部插入时如果当前块还有空位就直接放进去没有空位就新分配一块然后只更新中控器的指针。这里值得强调的是deque 的插入不会导致已有元素的内存地址改变——元素搬不搬分情况。如果插入发生在两端已有元素完全不动但如果插入发生在中间那和 vector 一样需要搬移元素。分别来看几个操作#include deque #include iostream int main() { std::dequeint d; d.push_back(1); d.push_front(0); // O(1) d.push_front(-1); // O(1) // 随机访问比 vector 稍慢 std::cout d[0] d[2] \n; // 头部弹出是常数时间 d.pop_front(); for (int x : d) std::cout x ; }这和工作机制有关deque 两端的插入不会导致其他元素的内存位置变动所以迭代器失效范围比 vector 小得多——push_back、push_front 一般只让对应的迭代器失效某些实现中也可能让其他迭代器失效标准没有强制保证而 erase 两端时也只影响被删元素。4.3 deque 的适用场景消息队列、滑动窗口、双端处理我实际项目里最常用到 deque 的地方是实现双端队列比如消息队列中的待处理列表可能同时有高优先级任务插到队首、普通任务追加到队尾。另一个典型场景是滑动窗口类问题需要维护一个窗口右端不断加入新元素左端不断移除旧元素。这种情况下 deque 的两端 O(1) 操作优势非常明显vector 做不到头插太慢list 虽然能两头操作但缓存性能差、内存开销大每个节点额外两个指针。要注意 deque 的元素存储不像 vector 那样完全连续如果你需要把容器中的数据直接传给一个接受数组指针的 C 接口deque 是不行的——它没有连续内存的保证。这种场景要么用 vector要么先把 deque 的内容拷进 vector。4.4 双端插入效率实测以及 reserve 的缺席deque 没有 reserve但你不需要 reserve——因为它两端插入本来就是 O(1)不需要像 vector 那样预留连续空间来避免搬移。它的内存增长方式是按块扩展的和 vector 的“一次性大块内存”思路完全不同。这就导致一个有意思的现象deque 比 vector 在“高频两端插入”场景下表现好但偶尔需要空间被释放时又不像 vector 那样可以整块释放——deque 的空间分配是以块为单位管理的如果大量元素被弹出后不会再增长deque 占用的内存未必会及时归还。所以在内存占用比较敏感的场景下如果只是尾部插入、且能预估数据量vector 优先如果两头都要高频插入、又不想为每次头插付出 O(n) 的代价deque 是最合适的选择。5. set有序集合的底层逻辑与定制化玩法5.1 set 的底层实现红黑树与平衡带来的代价set 在标准库中的实现普遍是红黑树一种自平衡二叉查找树。红黑树保证从根到叶子的最长路径不超过最短路径的两倍这保证了查找、插入、删除的最坏时间复杂度都是 O(log n)不会退化成链表。set 的元素是唯一的默认按 less升序排列。它的迭代器遍历结果是升序的这一点在有“需要保持元素有序”的需求时非常方便——你在插入之后不需要额外排序随时遍历都是排好的。但代价也很直接红黑树的每个节点要存储左子指针、右子指针、父指针、颜色位以及数据本身内存开销远超 vector 一个元素所占的空间。来看一个基本示例#include set #include iostream int main() { std::setint s; s.insert(5); s.insert(3); s.insert(8); s.insert(1); s.insert(5); // 重复插入不会生效 // 遍历即是升序 for (int x : s) std::cout x ; std::cout \n; auto it s.find(3); if (it ! s.end()) { std::cout found: *it \n; } }5.2 什么时候 set 比排序 vector 更好什么时候更差这是非常经典的对比问题。一种常见替代方案是把元素放进 vector排个序然后二分查找。这种方法的查找复杂度是 O(log n)和 set 一样内存上 vector 连续紧凑远小于红黑树节点而且缓存友好度高。那 set 的优势在哪在于动态插入删除时仍然保持有序且无需搬移元素。如果你的数据是一次性全部放进去、之后很少改变、主要是查询那么排序后的 vector 比 set 快得多——不仅有内存与缓存优势而且 std::sort std::binary_search 的实现非常成熟高效。如果你的数据是在程序生命周期内不断插入删除、同时随时需要有序遍历set 则更加合适因为 vector 在中间插入的 O(n) 搬移代价很快就会显现。这种“到底用谁”的判断我直说大部分“需要唯一有序集合”的场景如果你能接受构建期一次性插入排序 vector 是最优选只有需要频繁增删时才上 set。5.3 set 的增删查操作返回值、效率与迭代器失效特性set 的 insert 返回一个 pairfirst 是指向插入位置的迭代器second 是 bool表示是否为新插入如果元素已存在second 为 false。这个返回值在实际处理“去重”场景时非常有用。set 的 erase 不会导致任何其他迭代器失效因为它不搬移元素只是调整树结构。这又是和 vector 完全不同的体验你可以持有指向元素 A 的迭代器然后插入删除其他元素A 的迭代器仍然安全。这个特性在需要“长期保存指向容器内部元素”的场合是 set 的一个加分项。std::setint s {4, 1, 7}; auto [it, inserted] s.insert(5); if (inserted) { // 5 插入了 } else { // 5 本来就存在 }5.4 自定义比较器、lower_bound / upper_bound 和 multisetset 默认用 less 排序自定义类型想放进 set 需要重载 operator 或传入自定义比较器。自定义比较器不是随便写的它必须符合严格弱序strict weak ordering规则自反性、非对称性、传递性。如果你写的比较器违反了这些规则set 的插入查找行为可能直接错乱甚至出现逻辑错误排查起来非常痛苦。lower_bound 和 upper_bound 在 set 上有不同含义lower_bound 返回第一个不小于目标值的元素迭代器upper_bound 返回第一个大于目标值的元素迭代器。两者配合可以用来获取一个区间。multiset 则允许重复元素适合“需要把重复值也保留并按顺序维护”的场景。但在需要统计频次时我通常宁可选择 map键到计数的映射或者 unordered_map也比 multiset 更直接——multiset 本质上是在树上存重复节点如果同一值出现上千次树的形状和查找效率都不是最优的。6. 四个容器放在一张表里看怎么选才不纠结到这里四个容器已经各自盘了一遍但没有一个容器是十全十美的选型的关键在于把“你要什么能力”和“容器擅长什么能力”对齐。下面是基于实际经验整理的选择对照表需求特征推荐容器核心原因高频随机访问、缓存友好、主要尾部添加vector连续内存下标 O(1)遍历极快大量头部插入、不需要随机访问deque 或 listdeque 头插 O(1) 且缓存优于 list频繁在持有迭代器的位置插入删除list真正 O(1)且不使其他迭代器失效要求数据始终有序、动态增删多set平衡树保证 O(log n)自动排序数据一次性构建、之后只查询排序 vector内存紧凑、缓存友好查询更快双端操作、队列/滑动窗口deque两端均 O(1)只做查找、不要求有序unordered_set不在本文范畴但值得提均摊 O(1) 查找选型的时候还有一个必须经常问自己的问题这个容器填满了之后还会不会大规模改动结构如果答案是否定的尽量用 vector 排序方案如果答案是肯定的才需要考虑 set、list 这类结构操作更灵活的容器。很多人习惯于“我数据结构课学过的都要用上”的思维实际工程里最好的容器往往是最朴素的那个。这里补充一个经验之谈容器选型不是一步到位的决定你可以先用 vector 写出可运行版本然后用性能分析工具看瓶颈在哪再决定要不要换成更复杂结构。在一个真实项目中代码可读性和可维护性的权重往往不亚于微基准测试里那几微秒的差距。7. 常见坑与排查实录我踩过的和你们会踩的7.1 vector 扩容导致的迭代器失效遍历的时候删除最容易踩的坑之一就是在 vector 上边遍历边 erase然后因为当前位置被删、后续元素前移导致迭代器跳过了不该跳过的元素或者直接越界。正确写法是配合 erase remove_if或者手动维护索引递增逻辑。std::vectorint v {1, 2, 3, 4, 5}; // 错误写法示例 // for (auto it v.begin(); it ! v.end(); it) { // if (*it % 2 0) v.erase(it); // 迭代器失效 // } // 正确做法从后往前删 for (auto it v.rbegin(); it ! v.rend();) { if (*it % 2 0) { auto tmp std::prev(it.base()); it std::reverse_iterator(tmp); v.erase(tmp); } else { it; } }说实话上面的逆向删除写法其实还是有点别扭最简单易懂的还是 remove_if erase。为什么 remove_if 更优雅因为 remove_if 先把要删的元素“移到末尾”然后统一由 erase 一次性删除整个过程迭代器都是安全的。7.2 list 的 size() 在 O(1) 和 O(n) 之间的区别在老的标准实现中list::size() 是 O(n) 的——它需要遍历整个链表数节点C11 之前标准允许这么做。很多老代码迁移到新标准库后发现 size() 变快了其实是好事但如果你在写跨平台、跨编译器的代码不能假设 size() 一定 O(1)。标准库实现基本都已经做到 O(1)但如果遇到很老的环境还是留心一下。这个坑已经边缘化但不知道的人第一次遇到会非常困惑。7.3 set 的迭代器不可写修改元素要 erase insertset 的迭代器解引用得到的是 const 引用你不能通过迭代器直接修改元素。原因很直白如果允许修改树的有序性可能被破坏。要修改 set 里的元素标准做法是 erase 旧值再 insert 新值。这看起来多了一次删除和插入成本是 O(log n)似乎不如直接改方便。但破坏平衡后的代价可是灾难性的——所有查找都会乱掉而且这种 bug 很难排查因为你不一定马上触发错误路径。std::setint s {1, 2, 5, 9}; // 想把 5 改成 6 s.erase(5); s.insert(6);7.4 自定义比较器写错导致 set 行为怪异比较器违反严格弱序的经典情况是多个字段参与比较时如果只比较第一个字段就返回会在第二个字段不同的对象上得出“两者都不小于对方”的判断导致 set 认为它们相等实际却丢失了数据。排查办法是构造一个不同字段组合的小数据集打印插入后的结果看看是否有元素被意外覆盖。写比较器时要在心里记住相等不等于对象完全相同它只代表“按定义的顺序来看两个对象不可区分”。7.5 deque 的神秘迭代器失效两端操作有时也中招标准对于 deque 两端插入时迭代器失效的规定比较微妙push_back 和 push_front 不使已持有的迭代器失效在常见实现中一致但使引用失效。这句话读起来绕实际含义是你保存了一个元素的引用然后向另一端 push 一个新元素——引用没问题元素地址不变但迭代器可能因为中控器重新分配而失效。实验代码在不同标准库下结果可能不一样所以写跨平台代码时不要把“deque 两端操作一定安全”当成铁律尽量在完成结构性变更后再获取迭代器。8. 从容器延伸到 map / unordered_map 的一点建议这次系列只覆盖了四个容器但实战中还有一个逃不开的问题是 map 和 unordered_map 的选择。map 的底层也是红黑树迭代有序unordered_map 是哈希表迭代无序但查找快。选型逻辑和 set 类似需要有序遍历选 map只需要键值查找且不关心顺序时unordered_map 通常更快。但哈希表有额外的性能隐患——哈希冲突、rehash、内存碎片这些都可能导致它在某些数据集上反而不如平衡树。所以“哈希一定比树快”是伪命题还是要按实际数据和操作频率测试。排序 vector 替代 set 的思路也可以用到 map 上把键值对放进 vector按键排序再二分查找静态数据场景下往往比 map 更快更省内存。这个方法很多人在性能敏感项目里用效果很好但也意味着代码可读性下降因为你要手动维护“有序且唯一”这个不变量。选型说到底是在性能、可维护性和开发成本之间做权衡没有唯一正确答案。我这几年写 C 下来最明显的感觉是STL 容器不是一个简单的“选一个用”的库而是一套关于数据结构选择的思维模型。想清楚每个容器在内存布局、操作复杂度、迭代器稳定性上的取舍再结合你的真实操作模式来选比背下一百条“某某场景用某某容器”的规则要可靠得多。如果看完这篇你只能带走一件事我希望是你理解了 vector 为什么在绝大多数情况下都是赢家以及什么时候它赢不了。