深入理解 C++ vector 扩容机制：一次 push_back 背后发生了什么？

在 C++ 中，std::vector是最常用的顺序容器之一。它既支持像数组一样通过下标快速访问元素，又可以随着元素增加自动扩大容量。

这种“自动增长”很容易让人产生一个直觉：当空间不够时，vector只要在原来的内存后面再申请一些空间即可。但实际情况并没有这么简单。

考虑下面这段代码：

std::vector<int>values;for(inti=0;i<1000;++i){values.push_back(i);}

循环中的某些push_back()只需要构造一个新元素，而另一些push_back()却可能申请内存、搬迁全部已有元素，再释放旧内存。两者的执行成本可能相差很大。

由此可以引出几个问题：

• vector为什么需要扩容，而不能在原内存后面继续增长？
• 一次扩容过程中究竟发生了什么？
• 单次扩容需要移动所有元素，为什么push_back()的均摊复杂度仍然是O(1)？
• 怎样避免不必要的扩容开销？

本文将围绕这些问题，逐步理解vector的容量管理、扩容过程、复杂度以及实际使用中需要注意的细节。

先说结论：vector使用连续内存保存元素。当现有容量不足时，它通常需要申请一块更大的连续内存，并把已有元素移动或复制过去。几何增长策略减少了重新分配的次数，使连续尾部插入具有均摊O(1)的复杂度。扩容会使原有指针、引用和迭代器失效；如果能够预估元素数量，提前调用reserve()通常可以避免多次扩容。

一、vector 为什么需要扩容？

1.1 size 和 capacity 是两个不同的概念

理解扩容之前，首先要区分vector的两个状态：

• size()表示当前已经构造的元素数量；
• capacity()表示在不重新分配内存的前提下，当前存储空间最多可以容纳多少个元素。

两者始终满足：

size() <= capacity()

假设一个vector<int>的size为 3，capacity为 5，它的逻辑布局可以表示为：

图 1：size为 3、capacity为 5 时的逻辑布局

图中的后两个位置已经属于vector获得的存储空间，但那里还没有构造int对象。因此，capacity()大于size()并不代表容器中存在额外元素。

当size() < capacity()时，尾部仍有预留空间。此时调用push_back()，通常只需要在end()所指位置构造新元素，然后增加size，不需要重新申请整块内存。

当size() == capacity()时，当前存储空间已经用完。继续插入元素就需要扩大容量。

1.2 连续内存既是优势，也是限制

vector的元素必须连续存放。这一特性带来了很多优势：

• 可以通过values[i]在常数时间内定位元素；
• 可以使用data()获得指向连续存储区域的指针；
• 相邻元素通常具有较好的缓存局部性；
• 可以方便地与需要连续数组的 C 接口配合。

但连续存储也限制了它的增长方式。

假设vector当前占用地址区间后面的内存已经属于其他对象，分配器无法保证可以原地扩大这段区域。为了继续保持所有元素连续，vector只能在其他位置寻找一块更大的完整空间，然后搬迁已有元素。

所以，扩容并不是简单地“在末尾接上一段内存”，而更接近于“搬到一个更大的房间”。

1.3 哪些操作可能触发扩容

最常见的触发场景是容量已满时调用push_back()或emplace_back()，但它们并不是唯一的情况。以下操作都可能导致重新分配：

• push_back()或emplace_back()后元素数量超过当前容量；
• insert()插入元素后所需容量超过当前容量；
• resize(n)中的n大于当前容量；
• reserve(n)中的n大于当前容量。

与之相对，pop_back()、缩小尺寸的resize()和clear()通常不会主动缩小容量。这样做是为了保留已经申请的空间，方便后续再次插入元素。

二、一次扩容背后发生了什么？

2.1 申请新空间并搬迁元素

当尾部空间不足时，一次典型的扩容可以抽象为以下过程：

1. 根据当前容量和本次操作需要的元素数量，计算新容量；
2. 申请一块能够容纳新容量的连续存储空间；
3. 在新空间中移动或复制已有元素，并构造新加入的元素；
4. 销毁旧空间中的元素；
5. 释放旧存储空间；
6. 更新vector内部记录的地址、大小和容量。

具体实现为了满足异常安全等要求，构造已有元素和新元素的先后顺序可能有所不同，但整体效果可以用下面这张图理解：

图 2：vector扩容时的内存搬迁过程

如果原来有n个元素，那么仅搬迁已有元素就可能需要O(n)的时间。因此，触发扩容的那一次push_back()并不是严格的常数时间操作。

此外，在新旧内存短暂共存的阶段，程序的瞬时内存占用可能明显高于扩容完成后的容量。这也是存放大量对象的vector在扩容时可能产生内存峰值的原因。

2.2 已有元素是移动还是复制

C++11 引入移动语义之后，扩容不一定需要昂贵地复制每一个对象。对于持有堆内存、文件句柄等资源的类型，移动构造通常只需要转移资源所有权。

例如，一个简化的资源类型可以同时提供复制和移动构造：

classResource{public:Resource(constResource&other);// 复制资源Resource(Resource&&other)noexcept;// 转移资源};

2.3 扩容为什么会导致指针、引用和迭代器失效

扩容完成后，元素已经位于一块新的内存中。即使某个元素的值完全没有变化，它的地址也通常发生了变化。

下面的代码存在风险：

std::vector<int>values;values.reserve(3);values.push_back(10);values.push_back(20);values.push_back(30);int*first=&values[0];autoit=values.begin();values.push_back(40);// 当前容量不足，触发扩容std::cout<<*first;// 未定义行为：first 已经悬空std::cout<<*it;// 未定义行为：it 已经失效

只要操作引发了重新分配，所有指向原有元素的指针、引用和迭代器都会失效，旧的data()返回值也不能继续使用。

如果尾部插入没有引发重新分配，已有元素的指针和引用仍然有效，但原来的end()迭代器会失效。对于insert()、erase()等在中间位置移动元素的操作，失效规则还会进一步取决于操作位置。

所以，不能只看代码中是否调用了push_back()，还需要判断它是否可能触发扩容。拿不准时，最安全的做法是完成可能改变容器的操作后，重新获取指针、引用或迭代器。

三、vector 为什么采用几何增长？

3.1 C++ 标准没有规定固定扩容倍数

关于vector扩容，经常能看到“每次扩大为原来的两倍”或者“每次增长 1.5 倍”的说法。这些说法可以描述某些标准库在某些情况下的实现，但不是 C++ 标准作出的保证。

C++ 标准主要规定容器的行为和复杂度要求，并没有要求vector必须使用某一个固定增长因子。不同标准库、不同版本，甚至不同插入方式，都可能得到不同的容量变化结果。

因此，下面这样的代码不应该依赖某个精确容量：

values.push_back(42);// 不要假设扩容后一定满足：// values.capacity() == old_capacity * 2

虽然具体倍率属于实现细节，但常见实现通常不会每次只增加一个位置，而会让容量按照某个比例增长。这种策略称为几何增长。

3.2 为什么不能每次只增加一个位置

假设每次空间不足时，容量都只增加 1。连续插入n个元素时，需要搬迁的元素数量大致为：

0 + 1 + 2 + 3 + ... + (n - 1)

这个和约为n² / 2，因此整体搬迁成本是O(n²)。当元素数量增加时，频繁分配和搬迁会迅速成为性能瓶颈。

如果容量按照两倍增长，容量变化可以简化为：

1 → 2 → 4 → 8 → 16 → ...

扩容到可容纳n个元素的过程中，累计搬迁数量大致为：

1 + 2 + 4 + 8 + ... < 2n

虽然某一次扩容仍然需要移动O(n)个元素，但完成n次尾部插入的累计搬迁次数仍然是O(n)。把总成本分摊到每一次插入上，每次插入的平均成本就是常数级别。

这就是push_back()具有均摊O(1)复杂度的原因。这里的“均摊”并不表示每一次调用都一样快，而是表示一长串操作的平均成本为常数级。

图 3：几何增长将扩容集中在少数几个时刻

3.3 扩容倍数是在时间与空间之间取舍

容量增长得更快，通常意味着：

• 扩容次数更少；
• 元素被反复搬迁的次数更少；
• 但暂时没有使用的预留空间可能更多；
• 扩容时申请的新块更大，瞬时内存压力也可能更明显。

容量增长得更慢，则意味着：

• 未使用空间相对更少；
• 但扩容发生得更频繁；
• 内存分配和元素搬迁的成本可能更高。

因此，不同实现选择约 1.5 倍、2 倍或其他增长方式，本质上都是在分配次数、搬迁成本、内存利用率以及分配器复用之间做工程权衡。

从使用者角度看，重要的不是记住某个平台当前采用的倍率，而是理解两点：

1. capacity()通常会留出尚未使用的空间；
2. 不能把具体增长倍率当成可移植的程序逻辑。

四、如何正确使用 vector，减少扩容代价？

4.1 已知元素数量时使用 reserve

如果能够提前估计元素数量，可以使用reserve()一次性预留足够的容量：

std::vector<int>values;values.reserve(1000);for(inti=0;i<1000;++i){values.push_back(i);}

reserve(1000)的含义是让capacity()至少达到 1000。它不会创建 1000 个int，因此调用后通常仍然满足：

values.size()==0;values.capacity()>=1000;

后续插入不超过预留容量时，vector不需要再次重新分配。这可以减少：

• 内存分配与释放次数；
• 已有元素的移动或复制次数；
• 扩容造成的瞬时内存峰值；
• 插入过程中偶发的延迟抖动；
• 指针、引用和迭代器因重新分配而失效的机会。

但reserve()也不是越大越好。明显高估容量会让vector长时间持有大量未使用空间。通常应根据已知数量或合理上界进行预留，而不是随意申请一个极大的容量。

4.2 不要在循环中逐次 reserve

下面这种写法看起来是在主动管理容量，实际上可能让性能更差：

std::vector<int>values;for(inti=0;i<1000;++i){values.reserve(values.size()+1);values.push_back(i);}

每次reserve()都要求容量至少增加到刚好容纳下一个元素，这可能迫使容器频繁重新分配，等于人为破坏了vector自己的几何增长策略。

正确思路通常是：

• 能估计总量时，一次性reserve()；
• 无法估计时，让vector使用自身的增长策略；
• 只有掌握明确的分批增长信息时，才按较大的阶段调整容量。

4.3 区分 reserve、resize、clear 和 shrink_to_fit

这几个接口都与元素数量或存储空间有关，但语义完全不同：

reserve()与resize()最容易混淆：

std::vector<int>a;a.reserve(100);// size 仍然是 0，不能直接访问 a[0]std::vector<int>b;b.resize(100);// size 是 100，已经存在 100 个 int 元素

下面的代码虽然可能没有立即崩溃，但仍然是未定义行为：

std::vector<int>values;values.reserve(100);values[0]=42;// 错误：容量存在，但第 0 个元素尚未构造

如果希望创建 100 个元素，应使用resize(100)或其他插入方式，而不是只调用reserve(100)。

另外，clear()只销毁元素，通常不会把容量降到零；shrink_to_fit()可以请求减少多余容量，但这是一个非强制性请求，实现不保证一定执行。即使执行，它也可能重新分配内存并使所有指针、引用和迭代器失效。