STL容器底层内存模型：从vector扩容到deque分段连续

先问个问题：你写过这样的代码吗？往STL的vector里push_back几十万次，程序却吞吞吐吐——问题很可能不在算法，而在底层容器的内存模型。或者你在某个循环里保存了一个指向list元素的指针，回头在别处插了几个元素，发现vector的迭代器早就失效了，而list的还好好指着一块地址。这些现象背后，对应的是不同容器在内存里截然不同的摆放方式。

这篇是《STL底层容器与内存模型总结》的第一篇。我打算直接把自己常用的几个容器，从内存的角度完整过一遍：vector、list、deque，以及stack和queue这两个容器适配器。适合谁看？做C++后端想优化性能的人、准备C++面试的人、以及写了很久STL但对底层细节一直模模糊糊的人。看完你会发现很多“常识”其实还可以再往深挖一层。

1. 两种底层存储形态：连续空间与节点链接

1.1 容器分类的底层逻辑

STL标准容器按使用习惯分序列式和关联式，但按内存模型分，可以粗暴分成两类：连续存储和节点链接。连续存储的代表是array、vector、deque的缓冲区；节点链接的代表是list、forward_list、set、map等基于树的容器。这一刻分类方式决定了访问速度、插入代价、缓存效率、迭代器失效规则等一系列行为。

我见过不少同事把容器分类背得滚瓜烂熟，include、储备、默认构造函数都清楚，但一到性能问题就抓瞎。原因很简单：他们背的是“接口层”，不是“物理层”。以vector为例，它是一个连续内存的动态数组，元素之间紧挨着，一个元素占sizeof(T)字节，第i个元素地址就是首地址加上i乘以元素大小。这种布局意味着随机访问只要一次指针算数就能完成，时间复杂度是真正的O(1)。

而list是另一个极端。它的每个元素是一个独立的节点，每个节点里存着数据本身，外加指向前后节点的两个指针。第i个元素在哪里？不知道，你必须从头节点顺着指针一个一个跳过去。这就是为什么list的随机访问是O(n)，而且这个n不只是“慢一点”的问题——每次跳转都可能是一次缓存未命中，实际开销比理论分析更难看。

关联式容器（红黑树、哈希表）这次不展开，留到后面的篇目。先把序列式容器的内存模型讲透，因为你日常写的代码里90%都在跟它们打交道。

1.2 为什么说迭代器失效是内存重排的镜子

我在教新人C++的时候总爱问一个问题：“vector和list，谁的迭代器更容易失效？”十个人里有八个会回答list，因为“链表结构复杂，插入节点容易把指针搞乱”。事实恰恰相反：list的插入几乎不会让已有迭代器失效，vector一扩容全失效。

这个反直觉的背后正是内存模型。vector扩容意味着整片内存搬家，所有元素地址都变了，迭代器保存的是旧地址，自然全废。list插入节点只是改几个指针，已有节点的地址一个都没动，迭代器依然指向原来的元素，当然不会失效。所以迭代器失效规则不是需要死记硬背的八股文，而是“元素物理地址有没有变”的自然结果。

理解这一点有个小技巧：把迭代器理解成“带类型的指针”就够了。指针保存的是地址，迭代器本质也是地址信息。容器元素一旦移动，地址失效；地址不变，指针就还有效。从这个角度反推所有容器的失效规则，基本十拿九稳。

2. vector的连续内存与扩容机制：越搬越贵的真相

2.1 start/finish/end_of_storage三指针揭秘

vector的底层实现中，一般只有三个指针成员，没有别的元数据。以libstdc++为例，它的核心结构长这样：

cpp复制template <typename T>
class vector {
    T* start;            // 已用空间的起始
    T* finish;           // 已用空间的末尾（最后一个元素的下一个位置）
    T* end_of_storage;   // 已分配空间的末尾
};

size()的实现是finish减去start，capacity()的实现是end_of_storage减去start，这两个值之间就是预留空间。很多初学者以为vector对象里存了size和capacity两个整数，其实不是，它存的是三个指针，size和capacity都是算出来的。中间那段预留空间只有原始内存，没有构造任何对象，这点很关键——capacity比size大不代表里面有空对象等着你用，它只是一片“允许构造对象但还没构造”的荒地。

2.2 push_back到底经历了什么

当我们调用push_back时，有两种情况。如果finish还没碰到end_of_storage，也就是容量够用，那么直接在finish指向的位置构造新元素，然后finish后移一位，全程不需要搬动任何已有元素。第二种情况是容量满了，这时就要走扩容流程：

1. 分配一块更大的新内存。
2. 把旧元素全部搬到新内存。
3. 销毁旧内存里的所有元素。
4. 释放旧内存。
5. 更新start、finish、end_of_storage三个指针，在新内存末尾构造新元素。

这个流程里最耗时的就是第2步。C++11之前是纯拷贝，每个元素都执行一次拷贝构造函数；C++11之后如果类型支持移动构造且移动构造被标记为noexcept，就改成移动，把大对象的深拷贝变成指针搬运，快很多。

这里有个经常被忽略的坑：如果你的自定义类型有移动构造，但构造函数里可能抛异常，没有写noexcept，标准库为了异常安全会强制走拷贝构造。我之前优化一个项目，自定义结构体里有一个4KB的缓冲区，写了移动构造函数但忘了加noexcept，结果vector扩容时每次都是几百微秒的深拷贝，加上noexcept后直接降到几微秒。这件事让我记住了：移动构造不写noexcept等于没写。

2.3 扩容倍数：2倍与1.5倍之争

C++标准对扩容倍数没有任何硬性规定，只要求“capacity必须以可增长的方式变化”，所以不同编译器实现各有偏向。GCC的libstdc++和Clang的libc++都是2倍扩容，MSVC的STL是1.5倍。

为什么会有1.5倍和2倍的区别？2倍扩容的数学性质更好：顺序插入n个元素，累计搬移次数是1 + 2 + 4 + ... + n/2 + n ≈ 2n，均摊到每次push_back上就是O(1)，常数因子小。1.5倍扩容的搬移次数会多一些（等比求和系数更大），均摊依然是O(1)。但1.5倍有一个隐藏优势：内存分配器往往会缓存释放的块，新块大小小于旧块的话，有机会直接复用旧块或相邻块，减少外部内存碎片。

实战中这个差异根本感知不到。真正要记住的是：不管2倍还是1.5倍，频繁扩容都会带来大量拷贝开销和短暂的内存峰值。如果你提前知道大概会存多少元素，直接reserve预分配，把扩容次数砍到最少。

2.4 reserve和resize：一字之差，天壤之别

面试里我几乎每次都会问reserve和resize，能讲清楚的人不多。简单说：

• reserve(n)只改capacity，分配原始内存，不构造任何元素，size不变。
• resize(n)改的是size，如果n大于当前size，会在末尾追加对象并构造，比如int会用0填充，自定义类型会掉默认构造函数；如果n小于当前size，会销毁多余对象。

看代码更直观：

cpp复制std::vector<int> v;
v.reserve(100);     // size = 0,  capacity = 100
v.resize(10);       // size = 10, capacity >= 100, 元素被初始化为0

reserve之后可以放心用push_back，不会触发扩容；resize之后可以直接用下标访问那些位置，因为它们已经构造好了。很多人把reserve当成resize的加强版用，结果下标越界崩溃，查半天查不出来。

2.5 vector的迭代器失效规则：三条铁律

vector的失效规则其实就三条，都是从内存模型推出来的：

• 扩容导致所有迭代器、引用、指针全部失效，因为整个内存搬家了。
• 在中间插入元素导致插入位置之后的所有迭代器、引用、指针全部失效，因为后面的元素整体后移了一位。
• 删除中间元素，被删除位置之后的所有迭代器、引用、指针全部失效，因为后面的元素前移了。

这三条规则下面还藏着一个不常被注意到的点：如果只push_back一个元素且没触发扩容，之前所有元素的迭代器依然有效，因为它们的地址没移动过。但是end()迭代器会变，它指向的已经是新位置了，所以永远不要长期保存end()。

3. list的节点式内存：O(1)插入背后的隐藏成本

3.1 每存一个元素，多负担两个指针

list的底层是双向循环链表，每个节点是一个独立的内存块。节点结构简化后长这样：

cpp复制template <typename T>
struct list_node {
    list_node* prev;   // 指向前一个节点
    list_node* next;   // 指向后一个节点
    T data;            // 实际数据
};

这意味着你往list里存一个int（4字节），实际每节点至少占16字节（两个指针加数据，还要考虑对齐）。如果存的是64字节的大结构体，节点开销还好说；如果存的是小对象，内存浪费率直接翻倍。而且每个节点都单独从分配器申请内存，插入100万个元素就是100万次小内存分配，这个成本在复杂度分析里根本看不出来。

list还有一个容易忽略的设计：它有一个不存放数据的空节点作为哨兵，end()就指向这个哨兵。这个设计的妙处在于，所有常规情况都不需要特殊处理，比如在尾部插入就是在哨兵节点前面插入，头部插入就是在哨兵节点后面插入，统一走同一条路径。

3.2 中间插入O(1)的真正含义

list在指定位置插入新节点，理论上只需要改四个指针：

cpp复制node->prev = pos->prev;
node->next = pos;
pos->prev->next = node;
pos->prev = node;

不需要搬动任何已有元素，所以是O(1)。但你要注意，这个O(1)是“已经找到插入位置”的O(1)。如果让你在第1000个节点后面插入，你得先从头部遍历1000次才能拿到那个位置，定位本身是O(n)。

很多人在代码里这样写：

cpp复制std::list<int> lst;
auto it = lst.begin();
std::advance(it, 1000);   // 这一步已经O(n)了
lst.insert(it, 42);        // 这一步才是O(1)

所以“list插入快”一定要限定在“迭代器已经拿到手”的场景。如果你每次都通过值或索引去找位置再插入，list可能比vector还慢，因为它多了一次线性遍历。

3.3 list被高估的真相：缓存局部性

复杂度理论不骗人，但现实世界有缓存。vector的元素在内存里连续排列，遍历时CPU会一次性把一整块内存搬进缓存行，顺序读完全程都在缓存里跑。list的节点分散在堆的各处，遍历时每次跳到一个新地址，大概率缓存未命中，必须从主存重新加载数据——这个过程比缓存访问慢一个数量级。

我用10万个小整数做遍历求和，vector通常不到1毫秒，list稳定在3到5毫秒，有时更慢。这只是整数而已，如果元素是复杂对象，list的缓存劣势会更明显。所以我的经验是：单纯遍历和随机访问为主的场景，尽量不要用list；list只在“插入删除极其频繁、元素本身很大、不需要随机访问”的组合下才真正划算。

4. deque的分段连续：中控器、迭代器和双端神话

4.1 为什么有了vector和list还要deque

vector尾部插入快但头部插入是O(n)，list两端插入都快但随机访问是O(n)。deque的设计目标就是折中：既要像vector一样支持随机访问，又要像list一样支持两端快速插入。

它怎么做到的呢？deque把内存切成若干段连续缓冲区，每段buffer内部是连续的，但buffer与buffer之间不连续。整个容器由一张“地图”把这些分散的缓冲区串起来。你可以把它想象成一列火车：每节车厢是一段连续的存储块，车厢之间不直接相连，但列车长手里有一张表，记录每节车厢所在的位置。

4.2 map中控器到底怎么工作

deque的中控器（map）本质是一个指针数组，每个指针指向一段缓冲区。缓冲区的大小不是随便定的，标准库普遍采用“约512字节”的策略：

cpp复制// 简化逻辑：元素小于512字节时，每个缓冲区能放 512 / sizeof(T) 个元素
// 元素大于等于512字节时，每个缓冲区只放1个元素
inline size_t deque_buf_size(size_t n) {
    return n < 512 ? size_t(512 / n) : size_t(1);
}

也就是说，一个deque（sizeof(int)=4）的缓冲区可以放128个int，一个deque的缓冲区可以放64个double，而deque可能每个buffer只放1个大对象。这种设计让缓冲区总大小稳定在512字节左右，不会因为元素大小导致内存碎片过多。

当中控器满了，deque会重新分配一块更大的指针数组，把旧的节点指针搬过去，然后继续用。注意这个时候只搬了指针数组，元素本身没动，所以元素的引用和指针不会失效——但迭代器会失效，因为迭代器内部保存着“中控器节点”的信息。

4.3 deque迭代器为什么有四个指针

deque的迭代器是它最大的亮点，也是最难看懂的部分。它不只是指向单个元素，还要知道元素属于哪个缓冲区、缓冲区在哪里。所以它至少保存四个指针：

cpp复制struct deque_iterator {
    T* cur;          // 指向当前元素
    T* first;        // 当前缓冲区的头部
    T* last;         // 当前缓冲区的尾部
    T** node;        // 指向中控器中该缓冲区指针的位置
};

当迭代器不断自增，走到当前缓冲区末尾（cur == last）时，必须先通过node拿到下一段缓冲区的地址，更新first和last，再把cur指向新缓冲区的first。这个过程在C++里是封装好的，operator++内部自动处理。

cpp复制deque_iterator& operator++() {
    ++cur;
    if (cur == last) {           // 当前缓冲区走完了
        ++node;                  // 跳到中控器下一个槽位
        first = *node;           // 新缓冲区的头
        last = first + buf_size; // 新缓冲区的尾
        cur = first;
    }
    return *this;
}

这个设计让deque的随机访问变成了两次间接跳转：先通过中控器找到缓冲区，再在缓冲区里计算偏移。所以deque的operator[]不是严格意义上的O(1)，而是一次指针跳转加一次偏移，性能通常比vector慢那么一线，但数量级一样。

4.4 双端操作与失效规则细节

deque在两端操作时，为什么是O(1)？push_back时，如果当前尾缓冲区还有空位，直接原地构造，改一下finish迭代器的cur指针就行；如果尾缓冲区满了，就新申请一个缓冲区，挂到中控器末尾，再把cur指向新缓冲区。整个过程不动已有元素，所以双端插入很快。

但它的迭代器失效规则和vector不同，很多人会在这里踩坑：

• 两端插入（push_back/push_front）后，所有迭代器都会失效，但元素的引用和指针不受影响，因为元素地址没动。
• 中间插入会导致所有迭代器、引用、指针全部失效，因为中间插元素时，deque要移动元素来腾位置。
• 两端删除（pop_back/pop_front），只有被删除迭代器/引用失效，其余不受影响。

所以你不应该长期保存deque的迭代器，但如果存的是引用或指针，两端插入后依然能安全使用。

5. stack和queue：适配器的内存真相

5.1 适配器没有自己的数据

stack、queue、priority_queue在STL里的正式名称叫“容器适配器”（container adapter）。它们不是新的底层结构，而是把已有容器包装一层，限制接口。stack只允许从顶部操作，queue只允许从队尾入、队头出。

默认情况下，stack和queue都用deque做底层容器：

cpp复制template <typename T, typename Container = deque<T>>
class stack;

template <typename T, typename Container = deque<T>>
class queue;

为什么默认是deque？因为stack需要尾插尾删，vector和deque都满足；queue需要尾插头删，vector没有pop_front这种接口（如果你强行用vector的erase(begin())，那是O(n)级别的灾难），deque原生支持双端操作，所以是更合理的默认值。

5.2 切换底层容器的实际影响

适配器的模板参数允许你替换底层容器，但要注意接口约束。

stack可以用vector做底层，很多时候比默认的deque更高效，因为vector的尾部操作更快，且内存更紧凑。queue则不能用vector，因为vector没有高效的pop_front能力；用list倒是可以，但你在一个频繁front()和pop_front()的场景里用list，就会掉进上面说的缓存陷阱。

priority_queue比较特殊，它默认用vector做底层。深度上它需要堆算法，std::make_heap、push_heap、pop_heap这些操作都需要随机访问来维护堆结构，list的双向迭代器根本喂不饱这些算法。从这一点反推，容器底层的选择其实早就被算法需求定死了。

6. 从内存模型反推容器选型：我不背面试八股

6.1 复杂度、失效、缓存三张速查表

容器选型不能只看某个操作的单次复杂度，要把“定位成本”“搬移成本”“缓存成本”三个维度叠在一起看。这里把我常用的速查信息整理成表格。

6.2 我的三个选择经验

第一，默认vector，别想太多。C++标准库里大量组件都以vector为默认底层，比如priority_queue、flat_map类似的辅助结构。除非你有明确理由，否则vector在绝大多数场景都是最优解，尤其是数据量可控、以读写为主的场合。

第二，需要双端操作才用deque。典型场景是生产者消费者队列、滑动窗口、双端缓冲。deque的两端O(1)和引用的稳定性，在这类场景里是真正的利器。但它没有reserve接口，无法预分配大容量，内存也是分段管理的，如果你确定只需要尾插，vector加上reserve会更好。

第三，list留给“元素大、引用稳定、中间增删频繁”的组合。比如一个GUI管理着一大批不透明的对象，插入删除都在中间发生，而且外部代码持有元素的引用，这时list的引用稳定性和中间插入O(1)才能真正发挥价值。如果元素很小或容器遍历频繁，list大概率会让你失望。

6.3 一个容易被忽略的优化技巧

vector频繁扩容的坑，通过reserve就能避开，但很多人连reserve都不知道。我写服务端代码时有一个习惯：凡是能预估元素数量的容器，第一时间调用reserve；预估不了，也要给一个合理上限，比如从配置读到的批量大小。

cpp复制std::vector<int> ids;
ids.reserve(expected_count);   // 一次预分配，拒绝频繁搬家
for (int id : input) {
    ids.push_back(id);
}

有时候reserve带来的性能收益比换一个容器更明显。原因很简单：扩容是“分配新内存+搬全部旧元素”，搬的次数随扩容次数指数级增长，你把扩容次数压到0，这整块开销就消失了。

另外关于deque和list，有一个反向的提醒：不要迷信“list插入O(1)”这句话，它省略了迭代器定位成本；也不要迷信“list元素稳定”这句话，它在迭代器失效场景下确实好，但缓存性能确实差。复杂度是数学，性能是物理，两者要放一起看。

系列总结（1）到这里，vector、list、deque和两个适配器基本抠完了。下一篇我准备把关联式容器拆开，红黑树和哈希表的内存模型其实是另一种思路：用节点关系维护有序性，用桶数组换取哈希检索。先把序列式容器的“连续vs分散”想透，后面理解树和哈希的节点管理时，你会发现很多规律是相通的。

最后补一句我的体会：STL容器的底层实现，本质上都是在“连续”和“分散”两端之间找平衡。vector在连续一端做到了极致，list在分散一端做到了极致，deque站在中间取了最大公约数。搞清楚您手头的数据操作模式是哪一种，选择自然就出来了。