前言std::vector是使用频率最高的标准容器它保证元素连续存储、随机访问 O(1)、尾部插入摊销 O(1)。这三个特性里最容易被误解的是「摊销」二字push_back并不是每次都快而是在容量耗尽时触发一次重新分配把全部元素搬到新缓冲区再释放旧缓冲区。单次扩容是 O(n)但按几何级数增长长期平均下来每次插入是 O(1)。常见误解有五个。第一以为扩容因子一定是 2——标准完全不规定增长策略2 倍、1.5 倍都是实现选择。第二以为reserve之后就不会再扩容——只保证到指定容量为止超出仍然会扩。第三以为clear()会释放内存——它只销毁元素capacity()不变。第四以为shrink_to_fit()一定能把容量降到size()——它是非强制请求实现可以忽略。第五以为扩容后原来的迭代器、指针、引用还能用——只要发生重新分配全部失效。本文从size/capacity的语义讲起拆解一次扩容的完整步骤解释增长因子与摊销复杂度的关系再给出迭代器失效规则和reserve/resize/shrink_to_fit的正确用法。代码以 C17 为基准所有关于「输出」的描述都只按标准语义推演不声称在某个编译器上运行过。一、size、capacity 与连续存储vector内部通常用三个指针描述状态begin指向缓冲区首元素end指向最后一个元素之后cap指向缓冲区末尾之后。size()是end - begincapacity()是cap - begin。size()是「已构造元素个数」capacity()是「不重新分配的前提下最多能容纳多少个元素」。这两个值的关系永远是size() capacity()。对默认构造的空vectorcapacity()可能是 0也可能是某个实现预留的小值标准只要求capacity() size()不要求空容器容量为 0。连续存储带来两个直接后果。好的一面是v[0]可以作为指向连续数组的指针传给 C 接口C11 起即使v[0]不存在v.data()也是合法写法缓存局部性也好。坏的一面是「扩容必须整体搬家」新元素要放在末尾而末尾之外的内存不属于这个vector无法原地扩展只能申请一块更大的缓冲区把旧元素搬过去。元素类型影响搬家方式。如果类型可移动且移动构造是noexceptvector会移动元素如果移动构造可能抛异常而类型又可拷贝vector会选择拷贝以保证「扩容失败时原容器不变」的强异常保证。这就是std::move_if_noexcept的用途也是给自定义类型写移动构造函数时应当标noexcept的实际原因之一。二、一次扩容的完整过程容量耗尽时push_back大致执行以下步骤计算新的容量具体策略由实现决定分配一块能容纳新容量的原始内存把旧缓冲区中的元素逐个移动或拷贝构造到新缓冲区在新缓冲区末尾构造新元素销毁旧缓冲区中的元素释放旧缓冲区更新三个指针。任何一步抛异常标准要求容器保持有效状态。对push_back如果新元素的构造抛出容器不变如果搬家过程中抛出已经搬过去的元素要回滚实现通常会销毁新缓冲区并保留旧缓冲区。这里的关键是元素的移动/拷贝构造是否可能抛出——可能抛出时实现倾向于拷贝因为拷贝失败可以放弃新缓冲区旧数据仍在。扩容的代价不只是复制元素还包括一次分配和一次释放。分配器allocator的实现、内存碎片、元素大小都会影响这次操作的实际耗时但标准不规定任何具体数字。能确定的是复杂度一次扩容 O(n)n 是当时的元素个数。emplace_back与push_back在扩容行为上没有区别都是尾部追加都可能触发重新分配。区别只在元素的构造方式——emplace_back把参数直接转发给元素构造函数省去一个临时对象C17 起emplace_back返回新元素的引用push_back返回void。三、增长因子与摊销复杂度假设每次扩容把容量乘以因子 kk 1从容量 1 开始第 m 次扩容后容量约为 k 的 m 次方。搬家的总次数是 1 k k² … 这是一个等比级数总和与最终容量成正比而不是与「插入次数 × 每次搬家」成正比。因此把 n 次push_back的总代价摊到每次平均是 O(1)。如果每次只增加固定数量例如每次加 1总搬家次数就是 1 2 … n O(n²)摊销到每次是 O(n)push_back就退化成线性操作。这就是「必须按比例增长」的原因。标准不规定 k 的值。常见的实现选择是libstdc 通常按 2 倍增长MSVC 的vector通常按 1.5 倍增长。这只是实现策略不是标准保证也不能据此推断某次push_back之后的capacity()一定等于多少。不同版本、不同平台可能不同。k 的选择有权衡k 越大扩容次数越少、搬家总代价越低但浪费的内存越多最坏情况下容量接近元素数的 k 倍k 越小内存利用率越高但扩容更频繁。1.5 倍的一个额外好处是多次扩容释放的旧块之和不容易刚好超过新块大小对复用内存的分配器更友好——这是实现层面的考虑不是标准要求。还要注意reserve(n)请求的是「至少 n」实现可以给得更多capacity()返回实际值。不要写v.reserve(100); assert(v.capacity() 100);这样的断言。四、迭代器、指针与引用的失效规则这是vector最容易出 bug 的地方。规则可以按「是否发生重新分配」和「操作位置」两个维度记住操作是否可能重新分配失效范围push_back/emplace_back是若扩容则全部失效否则仅end()失效reserve(n)n capacity()时若扩容则全部失效resize(n)n capacity()时若扩容则全部失效否则仅尾后位置insert是插入点及之后的元素扩容则全部erase否删除点及之后的元素clear()否所有元素capacity()不变shrink_to_fit()可能若发生则全部失效swap否迭代器仍指向原元素但属于另一个容器「全部失效」包括迭代器、指针、引用、data()返回值。失效后继续使用是未定义行为可能读到旧内存、也可能崩溃不能假设「值还在」。一个典型错误是在循环里保存end()// 适用于 C17#include vectorvoid wrong(std::vectorint v) {auto end v.end();for (int i 0; i 10; i) {v.push_back(i); // 可能扩容end 失效}// 此后使用 end 是未定义行为}正确做法是每次重新取v.end()或者先reserve到足够容量再取。即便reserve过只要后续插入超过预留容量仍然会失效——reserve不是永久承诺。erase不会重新分配但被删除位置之后的元素会前移因此从删除点开始的迭代器、指针、引用都失效。常见的「边遍历边删除」写法必须用it v.erase(it)接收返回值erase返回被删除元素之后的迭代器。五、reserve、resize、shrink_to_fit 与观察扩容三个容量相关函数语义不同reserve(n)请求容量至少为 n不构造元素size()不变。n 小于当前容量时通常不产生效果。resize(n)把size()改为 n。变大时对新增元素做值初始化对int是 0对类类型调用默认构造可能触发扩容变小时销毁尾部元素容量不变。shrink_to_fit()请求把容量降到size()是非强制请求实现可以忽略C11 起提供。clear()只销毁元素不释放缓冲区要真正释放可以用shrink_to_fit()或者与一个空vector交换std::vectorT(v).swap(v)——注意这会拷贝C11 起更常见的写法是std::vectorT().swap(v)把v换成一个空容器旧缓冲区随临时对象析构释放。下面的程序不测时间只记录每次容量变化用来观察你所用实现的增长策略// 适用于 C17#include cstddef#include iostream#include vectorint main() {std::vectorint v;std::size_t last v.capacity();std::cout initial capacity: last \n;for (int i 0; i 100; i) {v.push_back(i);if (v.capacity() ! last) {last v.capacity();std::cout size v.size() capacity last \n;}}return 0;}按标准语义在持续插入的过程中capacity()只增不减除非shrink_to_fit、交换或赋值每次变化都对应一次重新分配具体在哪些size上变化、每次变成多少由实现决定。这类程序适合在自己机器上确认实现策略不要把某次观察到的序列当成标准结论。预留容量的正确用法是「已知大致规模时一次性 reserve」// 适用于 C17#include cstddef#include vectorstd::vectorint build(std::size_t n) {std::vectorint v;v.reserve(n); // 只分配缓冲区size 仍为 0for (std::size_t i 0; i n; i) {v.push_back(static_castint(i));}return v;}reserve之后size()仍是 0不能直接下标访问要访问必须先resize或push_back。另一个常见混淆是resize与reserve的顺序先resize(n)再逐元素赋值和先reserve(n)再push_back最终size()都是 n但前者对元素做了两次初始化值初始化 赋值后者只有一次构造后者通常更合适。常见坑点❌ 认为vector一定按 2 倍扩容并据此写死容量计算。✅ 增长因子由实现决定只依赖摊销 O(1)不依赖具体倍数。❌clear()之后以为内存已释放。✅clear()只销毁元素用shrink_to_fit或 swap 空容器释放。❌reserve(n)之后直接v[0] 1;。✅reserve不改变size()先resize或push_back。❌ 扩容后继续使用之前保存的迭代器、指针或引用。✅ 重新分配会使全部失效重新获取。❌ 在循环外保存end()循环内push_back。✅ 每次重新取end()或先预留足够容量。❌ 给自定义类型的移动构造不标noexcept却期望扩容时移动。✅ 移动可能抛异常且类型可拷贝时vector会选择拷贝。❌ 认为shrink_to_fit()保证容量等于size()。✅ 它是非强制请求实现可以忽略。❌ 把std::vectorbool当作普通vector取data()或元素地址。✅ 它有专门的位压缩特化元素是代理对象不提供data()。总结主题结论存储连续缓冲区三个指针描述 size/capacity扩容分配新块、搬迁元素、销毁并释放旧块增长因子实现定义libstdc 常见 2 倍MSVC 常见 1.5 倍复杂度单次扩容 O(n)push_back摊销 O(1)搬迁方式移动构造noexcept时移动否则可能拷贝失效重新分配则全部失效否则按操作位置局部失效reserve只改容量不改 size不保证精确等于 n释放clear不释放shrink_to_fit非强制理解vector的扩容关键是区分「已构造元素」与「已分配空间」并接受增长策略属于实现细节。写代码时只依赖标准保证的部分摊销 O(1)、连续存储、重新分配导致全部失效把reserve用在规模已知的地方把迭代器失效当成硬约束就能避开绝大多数与扩容相关的错误。 
长河君 · 2026/10/22 8:04:40 · 阅读 1.2k 详解C++ STL中vector扩容机制
前言std::vector是使用频率最高的标准容器它保证元素连续存储、随机访问 O(1)、尾部插入摊销 O(1)。这三个特性里最容易被误解的是「摊销」二字push_back并不是每次都快而是在容量耗尽时触发一次重新分配把全部元素搬到新缓冲区再释放旧缓冲区。单次扩容是 O(n)但按几何级数增长长期平均下来每次插入是 O(1)。常见误解有五个。第一以为扩容因子一定是 2——标准完全不规定增长策略2 倍、1.5 倍都是实现选择。第二以为reserve之后就不会再扩容——只保证到指定容量为止超出仍然会扩。第三以为clear()会释放内存——它只销毁元素capacity()不变。第四以为shrink_to_fit()一定能把容量降到size()——它是非强制请求实现可以忽略。第五以为扩容后原来的迭代器、指针、引用还能用——只要发生重新分配全部失效。本文从size/capacity的语义讲起拆解一次扩容的完整步骤解释增长因子与摊销复杂度的关系再给出迭代器失效规则和reserve/resize/shrink_to_fit的正确用法。代码以 C17 为基准所有关于「输出」的描述都只按标准语义推演不声称在某个编译器上运行过。一、size、capacity 与连续存储vector内部通常用三个指针描述状态begin指向缓冲区首元素end指向最后一个元素之后cap指向缓冲区末尾之后。size()是end - begincapacity()是cap - begin。size()是「已构造元素个数」capacity()是「不重新分配的前提下最多能容纳多少个元素」。这两个值的关系永远是size() capacity()。对默认构造的空vectorcapacity()可能是 0也可能是某个实现预留的小值标准只要求capacity() size()不要求空容器容量为 0。连续存储带来两个直接后果。好的一面是v[0]可以作为指向连续数组的指针传给 C 接口C11 起即使v[0]不存在v.data()也是合法写法缓存局部性也好。坏的一面是「扩容必须整体搬家」新元素要放在末尾而末尾之外的内存不属于这个vector无法原地扩展只能申请一块更大的缓冲区把旧元素搬过去。元素类型影响搬家方式。如果类型可移动且移动构造是noexceptvector会移动元素如果移动构造可能抛异常而类型又可拷贝vector会选择拷贝以保证「扩容失败时原容器不变」的强异常保证。这就是std::move_if_noexcept的用途也是给自定义类型写移动构造函数时应当标noexcept的实际原因之一。二、一次扩容的完整过程容量耗尽时push_back大致执行以下步骤计算新的容量具体策略由实现决定分配一块能容纳新容量的原始内存把旧缓冲区中的元素逐个移动或拷贝构造到新缓冲区在新缓冲区末尾构造新元素销毁旧缓冲区中的元素释放旧缓冲区更新三个指针。任何一步抛异常标准要求容器保持有效状态。对push_back如果新元素的构造抛出容器不变如果搬家过程中抛出已经搬过去的元素要回滚实现通常会销毁新缓冲区并保留旧缓冲区。这里的关键是元素的移动/拷贝构造是否可能抛出——可能抛出时实现倾向于拷贝因为拷贝失败可以放弃新缓冲区旧数据仍在。扩容的代价不只是复制元素还包括一次分配和一次释放。分配器allocator的实现、内存碎片、元素大小都会影响这次操作的实际耗时但标准不规定任何具体数字。能确定的是复杂度一次扩容 O(n)n 是当时的元素个数。emplace_back与push_back在扩容行为上没有区别都是尾部追加都可能触发重新分配。区别只在元素的构造方式——emplace_back把参数直接转发给元素构造函数省去一个临时对象C17 起emplace_back返回新元素的引用push_back返回void。三、增长因子与摊销复杂度假设每次扩容把容量乘以因子 kk 1从容量 1 开始第 m 次扩容后容量约为 k 的 m 次方。搬家的总次数是 1 k k² … 这是一个等比级数总和与最终容量成正比而不是与「插入次数 × 每次搬家」成正比。因此把 n 次push_back的总代价摊到每次平均是 O(1)。如果每次只增加固定数量例如每次加 1总搬家次数就是 1 2 … n O(n²)摊销到每次是 O(n)push_back就退化成线性操作。这就是「必须按比例增长」的原因。标准不规定 k 的值。常见的实现选择是libstdc 通常按 2 倍增长MSVC 的vector通常按 1.5 倍增长。这只是实现策略不是标准保证也不能据此推断某次push_back之后的capacity()一定等于多少。不同版本、不同平台可能不同。k 的选择有权衡k 越大扩容次数越少、搬家总代价越低但浪费的内存越多最坏情况下容量接近元素数的 k 倍k 越小内存利用率越高但扩容更频繁。1.5 倍的一个额外好处是多次扩容释放的旧块之和不容易刚好超过新块大小对复用内存的分配器更友好——这是实现层面的考虑不是标准要求。还要注意reserve(n)请求的是「至少 n」实现可以给得更多capacity()返回实际值。不要写v.reserve(100); assert(v.capacity() 100);这样的断言。四、迭代器、指针与引用的失效规则这是vector最容易出 bug 的地方。规则可以按「是否发生重新分配」和「操作位置」两个维度记住操作是否可能重新分配失效范围push_back/emplace_back是若扩容则全部失效否则仅end()失效reserve(n)n capacity()时若扩容则全部失效resize(n)n capacity()时若扩容则全部失效否则仅尾后位置insert是插入点及之后的元素扩容则全部erase否删除点及之后的元素clear()否所有元素capacity()不变shrink_to_fit()可能若发生则全部失效swap否迭代器仍指向原元素但属于另一个容器「全部失效」包括迭代器、指针、引用、data()返回值。失效后继续使用是未定义行为可能读到旧内存、也可能崩溃不能假设「值还在」。一个典型错误是在循环里保存end()// 适用于 C17#include vectorvoid wrong(std::vectorint v) {auto end v.end();for (int i 0; i 10; i) {v.push_back(i); // 可能扩容end 失效}// 此后使用 end 是未定义行为}正确做法是每次重新取v.end()或者先reserve到足够容量再取。即便reserve过只要后续插入超过预留容量仍然会失效——reserve不是永久承诺。erase不会重新分配但被删除位置之后的元素会前移因此从删除点开始的迭代器、指针、引用都失效。常见的「边遍历边删除」写法必须用it v.erase(it)接收返回值erase返回被删除元素之后的迭代器。五、reserve、resize、shrink_to_fit 与观察扩容三个容量相关函数语义不同reserve(n)请求容量至少为 n不构造元素size()不变。n 小于当前容量时通常不产生效果。resize(n)把size()改为 n。变大时对新增元素做值初始化对int是 0对类类型调用默认构造可能触发扩容变小时销毁尾部元素容量不变。shrink_to_fit()请求把容量降到size()是非强制请求实现可以忽略C11 起提供。clear()只销毁元素不释放缓冲区要真正释放可以用shrink_to_fit()或者与一个空vector交换std::vectorT(v).swap(v)——注意这会拷贝C11 起更常见的写法是std::vectorT().swap(v)把v换成一个空容器旧缓冲区随临时对象析构释放。下面的程序不测时间只记录每次容量变化用来观察你所用实现的增长策略// 适用于 C17#include cstddef#include iostream#include vectorint main() {std::vectorint v;std::size_t last v.capacity();std::cout initial capacity: last \n;for (int i 0; i 100; i) {v.push_back(i);if (v.capacity() ! last) {last v.capacity();std::cout size v.size() capacity last \n;}}return 0;}按标准语义在持续插入的过程中capacity()只增不减除非shrink_to_fit、交换或赋值每次变化都对应一次重新分配具体在哪些size上变化、每次变成多少由实现决定。这类程序适合在自己机器上确认实现策略不要把某次观察到的序列当成标准结论。预留容量的正确用法是「已知大致规模时一次性 reserve」// 适用于 C17#include cstddef#include vectorstd::vectorint build(std::size_t n) {std::vectorint v;v.reserve(n); // 只分配缓冲区size 仍为 0for (std::size_t i 0; i n; i) {v.push_back(static_castint(i));}return v;}reserve之后size()仍是 0不能直接下标访问要访问必须先resize或push_back。另一个常见混淆是resize与reserve的顺序先resize(n)再逐元素赋值和先reserve(n)再push_back最终size()都是 n但前者对元素做了两次初始化值初始化 赋值后者只有一次构造后者通常更合适。常见坑点❌ 认为vector一定按 2 倍扩容并据此写死容量计算。✅ 增长因子由实现决定只依赖摊销 O(1)不依赖具体倍数。❌clear()之后以为内存已释放。✅clear()只销毁元素用shrink_to_fit或 swap 空容器释放。❌reserve(n)之后直接v[0] 1;。✅reserve不改变size()先resize或push_back。❌ 扩容后继续使用之前保存的迭代器、指针或引用。✅ 重新分配会使全部失效重新获取。❌ 在循环外保存end()循环内push_back。✅ 每次重新取end()或先预留足够容量。❌ 给自定义类型的移动构造不标noexcept却期望扩容时移动。✅ 移动可能抛异常且类型可拷贝时vector会选择拷贝。❌ 认为shrink_to_fit()保证容量等于size()。✅ 它是非强制请求实现可以忽略。❌ 把std::vectorbool当作普通vector取data()或元素地址。✅ 它有专门的位压缩特化元素是代理对象不提供data()。总结主题结论存储连续缓冲区三个指针描述 size/capacity扩容分配新块、搬迁元素、销毁并释放旧块增长因子实现定义libstdc 常见 2 倍MSVC 常见 1.5 倍复杂度单次扩容 O(n)push_back摊销 O(1)搬迁方式移动构造noexcept时移动否则可能拷贝失效重新分配则全部失效否则按操作位置局部失效reserve只改容量不改 size不保证精确等于 n释放clear不释放shrink_to_fit非强制理解vector的扩容关键是区分「已构造元素」与「已分配空间」并接受增长策略属于实现细节。写代码时只依赖标准保证的部分摊销 O(1)、连续存储、重新分配导致全部失效把reserve用在规模已知的地方把迭代器失效当成硬约束就能避开绝大多数与扩容相关的错误。