深入STL容器内部：vector为何扩容、deque为何更快、map为何用红黑树

先说件让我印象很深的事。前几年我接手过一个消息分发服务压测时发现内存涨得飞快一度怀疑是业务逻辑有泄漏。后来用工具排查根因居然是几个std::vector在循环里push_back没有reserve频繁扩容带来的拷贝和内存碎片把整台机器的表现拖垮了。从那以后我一直觉得写 C 如果只看容器 API 的表面不往内部实现里看一眼性能问题早晚会在线上给你上一课。这篇我打算围绕 STL 容器内部实现把 vector、deque、list、map/unordered_map 的内存布局、节点结构、扩容策略和迭代器行为拆开讲一遍。适合两类人看一类是刚把 C 语法基础过完、对容器还停留在“会用”阶段的读者另一类是已经开始做服务端或客户端性能优化、想搞清楚“为什么用这个容器就是更慢”的从业者。我会尽量把原理和实操串在一起讲有些地方会直接对照我本地 GCC 12 的实现说因为标准库实现和你读到的讲解文章之间差距有时候还挺大的。1. 复杂度约定STL容器的“合同”决定了长什么样很多人学容器的时候是先背接口再背复杂度但很少有人反过来想一个问题标准里那些复杂度要求其实是容器的“设计合同”。容器内部结构不是随喜好定的它是被这份合同逼成这样的。拿最典型的几个来说vector要求尾插尾删摊还 O(1)、随机访问 O(1)。这个要求基本上就锁定了一个答案——必须用连续内存动态数组因为只有连续内存才能做到一次指针偏移完成随机访问。如果你用链表去实现 vector随机访问要沿着链走直接违约。list的逻辑正好反过来它要求任意位置插入删除都是真 O(1)并且只提供双向迭代器不要求随机访问所以它才被设计成双向循环链表。你要是用连续数组做 list中间插入一次要搬一半元素也违约。map和set的合同是查找、插入、删除都不超过 O(log n)。线性结构做不到哈希表平均能做到 O(1) 但不满足“最坏情况 log n”的强要求于是标准库普遍选平衡二叉搜索树。红黑树是平衡树里的一种后面我会专门讲为什么是它而不是 AVL。unordered_map签的是另一份合同平均 O(1) 的查找插入不要求有序于是哈希表登场。deque这份合同最特别它要求两端插入删除都是 O(1)还要求随机访问 O(1)。单独一个连续数组满足不了头插 O(1)单独一个链表满足不了随机访问 O(1)于是它只能走一条折中路——分段连续用一个中控结构把多段连续内存串起来。这个设计我后面会展开。理解这份“合同”还有一个隐藏价值迭代器类型本身也是合同的一部分。随机访问迭代器可以被sort、binary_search这类算法调用双向迭代器只能用reverse、next/prev这种。为什么有些泛型代码用map编译不过std::sort因为map的迭代器是双向迭代器不支持跳跃式访问。你一旦理解了“容器的内部结构决定迭代器能力迭代器能力决定算法适配性”这条链路很多编译报错就不需要猜了。所以我建议你把每个容器的复杂度表当成一张“骨架图”来背然后想一想如果我是标准库作者给我这些复杂度约束我会用什么结构想完之后再去看实现你会发现自己和设计者的思路其实是能对上的。对不上也没关系对不上的地方往往就是这篇文章后面要讲的“折中与权衡”。2. vector连续存储是效率的起点也是痛的根源vector表面上是“动态数组”三个指针搞定_M_start指向首元素、_M_finish指向最后一个有效元素之后、_M_end_of_storage指向已分配内存的末尾。用size()是_M_finish - _M_start用capacity()是_M_end_of_storage - _M_start。这个模型简单到让人以为没有秘密但它最大的痛点恰好就出在“扩容”这两个字上。2.1 扩容倍数之争2倍到底哪里不对当size() capacity()再push_back时vector必须申请一块更大的内存把旧元素拷过去再释放旧内存。问题是新内存到底开多大才合适我本地 GCC 12 的libstdc走的是老牌策略新容量大约是旧容量的 2 倍准确点说是max(2 * old_capacity, old_capacity new_elements)这类规则。而 MSVC 的std::vector常见做法是 1.5 倍增长。为什么会有这种差异2 倍增长的好处是扩容次数少、摊还成本低。从 1 个元素开到 n 个元素每次扩容都按 2 倍翻扩容次数是 log2(n) 级别总元素拷贝次数大约 124...n/2约等于 n 次。也就是说每个元素平均只被拷贝一次这个摊还成本是可以接受的。但 2 倍增长有个现实问题它浪费空间。一块内存用完扩容后旧内存释放和原本相邻的可合并内存如果不满足新块大小就白白浪费了如果用 1.5 倍或 1.6 倍这类增长率新块更大可能被旧块合并出来的空间接住内存分配的复用率更高。所以在现代实现里偏向内存复用和缓存友好的库会选 1.5 倍偏向减少扩容次数的库会选 2 倍。这个不是对错问题是取舍问题。你在做高性能低延迟服务时如果vector里放的是大对象扩容拷贝的代价远大于多占一块内存的代价这时候手动reserve比纠结实现用几倍更重要。2.2 push_back 的摊还分析为什么它是摊还 O(1)很多教程只说“push_back是摊还 O(1)”但不说为什么“摊还”。我把账算给你看。假设初始容量 1第 1 次push_back不扩容第 2 次扩容到 2拷 1 个元素第 3 次扩容到 4拷 2 个第 5 次扩容到 8拷 4 个以此类推。到第 n 次插入时扩容发生大约 log2(n) 次每次拷贝的元素数量翻倍总拷贝次数约等于 n。均摊到 n 次插入上每次插入额外成本约等于常数所以叫“摊还 O(1)”。如果每次扩容只固定增加 K 个槽位比如每次加 100那总拷贝次数是 100 200 300 ...摊下来每次插入都要移动 O(n) 个元素复杂度直接退化成 O(n)。这就是为什么你永远不会看到vector用固定步长扩容——它在数学上就不成立。我提一个常见误解reserve和resize总是有人搞混。reserve(n)只保证capacity n不改变size也就是不构造任何元素resize(n)会把size改成 n新增的元素会被默认构造或拷贝构造。优化时知道接下来要插入 100 万个元素就调reserve(1000000)元素还会一个一个放进去但不会再发生中途扩容拷贝。如果调成resize(1000000)等于先构造了 100 万个默认元素后面再赋值白白多一轮初始化成本。2.3 insert 和 erase 的真实代价元素搬运与迭代器失效vector的insert在中间插入时要把插入点后面的所有元素往后移一格。erase反过来把删除点后面的元素往前移一格。移动本身是 O(n)而且一旦插入导致重新分配所有迭代器、指针、引用全部失效即使没有重新分配插入点之后的所有迭代器也会失效。erase之后从删除点开始到end()的所有迭代器同样失效。这个失效规则不是写来吓人的它对应的是内存里的真实变动迭代器本质上是指针的封装元素搬走了旧地址上的值已经挪到新地址你再通过旧迭代器访问轻则读到搬完后的脏数据重则访问到已经释放的内存。所以我写代码时有一条习惯如果一段逻辑里要对vector做多次中间插入删除要么先通过下标确定好位置然后合并成一次批量操作要么干脆考虑用list替换。注意我说的是“考虑”不是“一定”因为list的单次插入 O(1) 背后有别的代价这个在后面专门讲链表的章节里展开。关于vector元素本身还有一个值得注意的优化点移动语义。vector重新分配时如果元素的移动构造函数是noexcept的它就能复用已分配的内存做高效移动如果没有移动构造或者移动构造可能抛异常标准库往往退回拷贝构造。这就是为什么你的自定义类型里移动构造函数一定要记得标noexcept。不标的话即使你的类里有std::unique_ptr这种天然支持移动的成员编译器也可能因为异常安全考虑选择老老实实走一遍深拷贝性能直接掉一个量级。3. deque中控器、缓冲区和双端迭代的折中方案deque大概是 STL 里最被低估的容器。它看起来像是能随时在头尾操作的vector但你要是真把它当vector用会发现一些别扭的特性和坑。3.1 分段连续一张中控器的指针网络deque的核心思想是不要求一整块连续内存而是让多个固定大小的连续缓冲区buffer手拉手形成逻辑上的连续序列。每个缓冲区里存若干元素缓冲区之间用一个“中控器”串起来。中控器在libstdc里本质上是一个map里面存的是指向各个缓冲区的指针注意这个 map 不是红黑树那个 map它就是一个动态指针数组。缓冲区默认大小一般是 512 字节除以元素大小之后得到的个数比如元素是int一个缓冲区可以放 512/4128 个如果元素很大比如 1000 字节的结构体一个缓冲区可能就放 1 个。这么做是为了控制缓冲区内存粒度避免小元素浪费太多也避免大元素导致缓冲区内部碎片严重。你在deque头部push_front时如果当前最前面的缓冲区满了它不会去搬动后面所有元素而是向中控器里当前 slot 的左侧申请一个新缓冲区把新元素放进去。尾部push_back同理。这就是为什么两端插入都是 O(1)。中间insert就没有这个待遇了它需要把插入点之后的元素向最近的一端搬运平均移动半个序列的元素复杂度 O(n)。3.2 迭代器如何在缓冲区之间跳转deque的迭代器是理解这个容器内部的关键。以libstdc的实现来看迭代器通常包含四个成员cur指向当前元素、first和last指向当前缓冲区首尾、node指向中控器中当前缓冲区的槽位。当operator把cur移动到last时说明当前缓冲区走完了于是迭代器跳转node加一从新槽位里取出下一个缓冲区的首地址再把first、last、cur全部更新到新缓冲区里。这个过程看起来只多了一次指针寻址和判断但和vector那种“直接 addr1”相比每次遍历要多做不少分支。所以deque的随机访问虽然标称 O(1)常数却远大于vector。循环遍历deque也比vector慢因为它要不断在缓冲区边界处做跳转无法像连续内存那样纯靠步长寻址。3.3 为什么 deque 没有 capacity 和 reserve很多人第一次发现deque没有reserve()时会愣一下。原因是deque根本不需要“整块内存预留”。它不存在整体搬迁的问题中控器的槽位不够了只需要把这个指针数组搬到一个更大的指针数组里元素本身不移动。所以从元素角度看永远不需要像vector那样为了预留空间提前申请一整块内存。没有reserve不代表没有成本。中控器本身扩容时所有迭代器会失效因为迭代器里存的node指向旧中控器的位置中控器一搬旧地址就作废了。什么时候中控器会扩容就是你在头尾两侧不断插入直到当前中控器的所有槽位都被缓冲区占满时。这在普通业务里不常触发但如果你用deque做一个持续百万级元素的双端队列是可能发生的。我的建议是如果明确只需要尾部操作用vector如果首尾都要频繁操作再考虑deque。不要把deque当成“能头插的 vector”去用。4. list与forward_list哨兵节点、splice与容易被低估的开销链表大概是所有 STL 容器里“看着简单实际最有迷惑性”的一类。很多人觉得链表插入快、删除快仿佛是个万能优化招但真到工程里一测往往比连续内存容器慢一截。4.1 哨兵节点空链表不是空指针std::list的经典实现是双向循环链表并且有一个专门的哨兵节点。这个哨兵节点不属于任何元素它的next指向第一个元素prev指向最后一个元素自己作为end()的位置。空链表时哨兵的next和prev都指向它自己所以空链表也能正常运行begin()、end()和迭代器自增自减。为什么需要哨兵因为链表实现最烦的就是处理“空表”和“首尾节点被删除”这些边界情况。不用哨兵的话每次插入删除都要判断“当前是不是第一个节点”更新头指针用了哨兵所有节点的插入删除都是同样一套指针操作不需要特殊分支代码简洁很多运行效率也稳定。begin()就是哨兵-nextend()就是哨兵自己的地址所以end()的迭代器本质上就是一个指向栈上哨兵的指针。4.2 splice 为什么是 O(1)std::list的splice可以把一个列表的一段节点原封不动地转移到另一个列表时间复杂度是 O(1)。很多人不解不是在链上移动一批节点吗怎么不用遍历因为splice做的是“剪贴”而不是“复制”。它只需要改三对指针被剪段的头节点前驱和后继、目标位置的节点前驱和后继。比如把listA的[it1, it2)剪下来接到listB的pos前面本质上就是把这段链表从原来的前后节点之间“解扣”再穿到目标位置的节点之间。节点内部的数据和指针本身都不用动所以整个操作和这段链有多长完全无关必须是 O(1)。这也解释了为什么list和vector的适用场景完全不同如果你需要频繁把一个大型结构体的子序列移动位置list::splice是几乎唯一能在常数时间内完成这个操作的容器。4.3 链表的隐藏成本节点分配与缓存不友好链表插入删除的 O(1) 有一个前提就是节点所在内存已经存在。但现实里你每次插入一个新元素往往都要通过分配器新建一个节点。在libstdc里链表节点包含前驱指针、后继指针和数据本身它们在同一个块里并不是“一个节点里再放一个指针指向数据”。这个设计减少了分配次数但每个节点的内存开销还是不小。我实测过一个简单示例64 位 Linux 下listint里每个节点通常要占 24 字节左右因为两个指针 16 字节加上int4 字节再按 8 字节对齐补到 24。而vectorint里每个元素只要 4 字节额外开销几乎为零。如果你存一百万个intvector只占约 4MBlist要占约 24MB是前者的六倍。你要是存的是一个很小的自定义结构体差距会更夸张。这还没算缓存命中率。vector遍历时内存是连续的CPU 预取器和缓存能把一整片数据搬进高速缓存访问效率极高list的节点散落在堆上跳着访问每次都可能缓存未命中等内存的延迟比算数据的延迟高一个量级。所以实际工程里除非你需要“任意位置 O(1) 插入删除”并且真的高频这么干否则链表的综合表现常常不如vector。很多高性能系统里宁可维护一个逻辑上的“空闲槽位数组”模拟链表也不用真正的std::list。5. map/set与unordered_map/set红黑树与哈希表台前幕后关联容器是 STL 容器里结构最复杂的一批而且它有一个特有趣的对比map用平衡树平均和最坏都是 O(log n)unordered_map用哈希表平均 O(1)最坏可能 O(n)。两者各有各的“内部公式”。5.1 红黑树为什么不选 AVLC 标准只要求std::map是有序关联容器且操作复杂度 O(log n)没有强制说必须用红黑树。但事实上主流标准库实现全选了红黑树原因在于红黑树在“平衡代价”和“查找效率”之间取了一个平衡点。红黑树的高度约束是“最长路径不超过最短路径的两倍”直观上说它不像 AVL 那样死磕左右子树高度差不超过 1而是允许一定程度的“不完全平衡”。这带来一个好处插入和删除后的重平衡代价极其有限。红黑树插入后最多需要两次旋转加变色删除后最多三次旋转加变色整体是 O(1) 级别的调整成本AVL 的插入删除则可能需要沿着路径一路旋转上去O(log n) 次旋转并不罕见。map是种读多写也多的容器插入删除和查找都频繁所以总成本不能只看查找速度。红黑树用轻微牺牲树高的方式换来了插入删除时更少的旋转开销。工程上这个权衡非常划算。另外红黑树的实现相对简单稳定节点插入删除时能保证迭代器不失效这也是它被厂商选中的一个现实原因。5.2 end() 迭代器与迭代器加减背后的“树走法”红黑树容器的迭代器并不维护额外链表它靠的是树结构里的父节点指针。以libstdc来说_Rb_tree_node_base里通常有parent、left、right、color四个成员再加上数据整个节点在 64 位下常常在 40 字节上下。你看着map查找是 O(log n)但一个节点的体积是int的好几倍所以mapint,int存几十万条记录时内存会明显涨上去。end()的实现也很有意思它返回的是header节点header不存储数据颜色被标记为红色目的是为了在实现里区分“这是 header 而不是普通节点”。header的parent指向根节点left指向树中最左节点right指向树中最右节点。这样begin()就是header.leftend()就是header。迭代器operator则是标准二叉搜索树后继算法如果当前节点有右子树那后继是右子树的最左节点否则向上回溯找到第一个“自己是左孩子”的祖先那个祖先就是后继。这个过程平均 O(log n)但每个节点只被访问常数次所以整树遍历总体是 O(n)。红黑树节点在插入删除时内存地址不会变只是指针关系在调换因此map的插入删除不会让已有迭代器失效。这一点在需要长期持有引用或迭代器的场景里非常宝贵也是unordered_map不能完全替代它的一个原因。5.3 unordered_map 的桶、rehash 与冲突退化unordered_map的内部是“桶数组 冲突链表”。每个元素先通过哈希函数得到一个size_t哈希值再对桶数量取模得到所在桶然后插入到这个桶的链表中。正常情况下每个桶里只有一两个元素访问就是“算哈希、定位桶、找链表”平均 O(1)。max_load_factor默认是 1.0意思是桶数最多承载和桶数一样多的元素超过这个比例容器会触发 rehash把桶数量翻倍左右然后把所有元素重新挂到新桶上。rehash会让迭代器失效因为元素挂桶的位置变了但引用不失效因为元素对象本身没有被搬走。如果你能预估数据量提前reserve(n)可以减少 rehash 次数这和vector::reserve是同一个道理。哈希表最怕的是哈希冲突。如果自定义类型的hash实现得差比如所有对象都返回同一个哈希值那么所有元素都进同一个桶查找直接退化成线性扫链表复杂度 O(n)和“哈希表快”彻底没关系了。我给自定义类型写哈希时通常会参考标准库已有的哈希组合方式比如hash_combine用多个成员哈希值混合而不是简单地把两个整数相加。一个常见的坏例子是把两个成员做 XOR 或者加和对称类型很容易全撞一起。另外还要知道unordered_map的迭代器遍历不是有序的它是按桶从头到尾走的和插入顺序也没关系。所以需要“按 key 顺序输出”时老实回去用map不要硬拿unordered_map排序那个成本比直接建map高得多。6. 实测与调优几个值得记下来的容器经验前面几章讲的是原理这一章我到实践中去验证这些原理顺便分享一些在代码里真正起作用的小经验。6.1 reserve 不是可有可无的花哨装饰我做过一个很粗糙的测试向vectorint里插入 100 万个随机数一种直接push_back一种先reserve。情况是后者不仅耗时明显低峰值内存也干净很多。原因在于前者每扩容一次就要分配新块、拷贝、释放旧块这个过程的额外开销不只是 CPU还有内存碎片的累积。有人可能会说vector扩容是 2 倍100 万元素也就 20 次扩容能有几次拷贝问题就在这 20 次扩容中最后一次要从 50 万左右拷到 100 万级别单次拷贝就是几十万个元素。如果元素是int倒还好要是元素是一个 100 字节的结构体这一下就是几十 MB 的内存搬运放大效应非常可观。明确知道规模的地方先reserve不确定规模但想省事的也至少想想会不会出现超大扩容场景。6.2 判断 key 是否存在别用 operator[]一个非常经典的坑std::mapstd::string, int m; if (m[not_exist] 0) { // 想判断存不存在 }这段代码执行完not_exist这个 key 已经被插入map里了value 是 0。原因就是operator[]等价于“先查找找不到就插入默认元素再返回引用”。它的设计本意是方便写m[key]这种更新逻辑不是用来做存在性查询的。判断存在性是find()或者contains()C20 之后if (m.find(key) ! m.end()) { /* 存在 */ }这个坑不仅让map的元素数量莫名增加还会导致后续遍历、序列化逻辑全都跟着变味排查起来很隐蔽。6.3 节点型容器的内存碎片问题list、map、unordered_map这类容器每个元素都是一次独立的内存分配长期频繁插入删除会产生大量小块内存分配器往往不能完美复用它们碎片越攒越多。一个运行几天的服务如果它内部频繁读写一个mapstring, vectorint你会发现内存占用可能在缓慢爬升甚至像是泄漏。这时候先别急着怀疑指针泄漏试试用长时间压测观察内存是否回落如果内存曲线整体上升就在代码里加一些统计看看是不是节点容器的分配次数异常高。缓解手段有几种一是减少容器本身的插入删除频率能批量处理就批量处理二是使用自定义分配器比如从内存池里一次性申请一批节点再按需分配避免反复找堆管理器要内存三是真的需要频繁从中间插入删除时评估改用手写的分层结构或第三方容器库。自定义分配器在绝大多数业务代码里不是必需品但它确实是解决节点容器碎片问题的终极手段。6.4 vector 与 shrink_to_fit 的两个现实之坑vectorbool是 C 里一个著名的特殊容器。它明明叫vector但不满足“连续存放bool”的语义实现把每 1 个字节压缩成 8 个 bool 的位operator[]返回的是一个代理对象不是真bool。所以你要是写auto b vec[0]会得到代理类型的引用使用起来限制很多甚至在不同实现行为还略有差异。实际做位集时我一般直接用std::bitset或者干脆用std::vectoruint8_t自己控制绕过vectorbool的坑。另一个坑是shrink_to_fit()。标准只说“请求”减少容量到适配 size并不强制。在 GCC 里vector的shrink_to_fit通常能生效但某些实现和场景下它可能忽略请求。如果你确实需要立刻释放多余内存又不在意拷贝成本最老派可靠的办法是和临时对象交换std::vectorT(v).swap(v);这样会构造一个容量刚好等于 size 的临时vector再和v交换底层缓冲区v的多余容量随之释放到临时对象里继而随临时对象析构。这个技巧在老的代码里很常见。结尾再说点私货这几章拆下来我自己最大的体会是不要被容器表面的“复杂度表”骗了。复杂度表说的是渐近行为但它不告诉你常数有多大、内存占多少、缓存命中率高不高。vector尾插是 O(1) 摊还unordered_map查找是平均 O(1)这些都没错但它们之间的真实性能差距能到五六倍甚至更多原因全藏在内部实现里。我平时排查线上性能问题时开场三句话往往是你这个容器会不会经常扩容节点是一次一个分配的还是一次一批的你到底需要的是有序性还是哈希速度把这三个问题问完一半的容器选型问题都解决了。剩下的就是像我一样找个周末把vector、deque、list的头文件打开一页一页翻过去。标准库源码虽然初看晦涩但你每看明白一个_M_finish、一个_Rb_tree_node_base你对这些容器的掌控感就会加深一点下次写出性能问题的概率就会少一点。这也是我想分享这篇文章的真正原因。