企业官网建设流程全解析

前言

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的正确用法。代码以 C++17 为基准，所有关于「输出」的描述都只按标准语义推演，不声称在某个编译器上运行过。

一、size、capacity 与连续存储

vector内部通常用三个指针描述状态：begin指向缓冲区首元素，end指向最后一个元素之后，cap指向缓冲区末尾之后。size()是end - begin，capacity()是cap - begin。size()是「已构造元素个数」，capacity()是「不重新分配的前提下最多能容纳多少个元素」。

这两个值的关系永远是size() <= capacity()。对默认构造的空vector，capacity()可能是 0，也可能是某个实现预留的小值；标准只要求capacity() >= size()，不要求空容器容量为 0。

连续存储带来两个直接后果。好的一面是&v[0]可以作为指向连续数组的指针传给 C 接口（C++11 起，即使v[0]不存在，v.data()也是合法写法），缓存局部性也好。坏的一面是「扩容必须整体搬家」：新元素要放在末尾，而末尾之外的内存不属于这个vector，无法原地扩展，只能申请一块更大的缓冲区，把旧元素搬过去。

元素类型影响搬家方式。如果类型可移动且移动构造是noexcept，vector会移动元素；如果移动构造可能抛异常而类型又可拷贝，vector会选择拷贝，以保证「扩容失败时原容器不变」的强异常保证。这就是std::move_if_noexcept的用途，也是给自定义类型写移动构造函数时应当标noexcept的实际原因之一。

二、一次扩容的完整过程

容量耗尽时，push_back大致执行以下步骤：

1. 
   
2. 计算新的容量（具体策略由实现决定）；
3. 
   
4. 分配一块能容纳新容量的原始内存；
5. 
   
6. 把旧缓冲区中的元素逐个移动或拷贝构造到新缓冲区；
7. 
   
8. 在新缓冲区末尾构造新元素；
9. 
   
10. 销毁旧缓冲区中的元素；
11. 
    
12. 释放旧缓冲区；
13. 
    
14. 更新三个指针。
15. 
    

任何一步抛异常，标准要求容器保持有效状态。对push_back，如果新元素的构造抛出，容器不变；如果搬家过程中抛出，已经搬过去的元素要回滚，实现通常会销毁新缓冲区并保留旧缓冲区。这里的关键是元素的移动/拷贝构造是否可能抛出——可能抛出时，实现倾向于拷贝，因为拷贝失败可以放弃新缓冲区，旧数据仍在。

扩容的代价不只是复制元素，还包括一次分配和一次释放。分配器（allocator）的实现、内存碎片、元素大小都会影响这次操作的实际耗时，但标准不规定任何具体数字。能确定的是复杂度：一次扩容 O(n)，n 是当时的元素个数。

emplace_back与push_back在扩容行为上没有区别：都是尾部追加，都可能触发重新分配。区别只在元素的构造方式——emplace_back把参数直接转发给元素构造函数，省去一个临时对象；C++17 起emplace_back返回新元素的引用，push_back返回void。

三、增长因子与摊销复杂度

假设每次扩容把容量乘以因子 k（k > 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 的地方。规则可以按「是否发生重新分配」和「操作位置」两个维度记住：

「全部失效」包括迭代器、指针、引用、data()返回值。失效后继续使用是未定义行为，可能读到旧内存、也可能崩溃，不能假设「值还在」。

一个典型错误是在循环里保存end()：

// 适用于 C++17
#include <vector>

void wrong(std::vector<int>& 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()，是非强制请求，实现可以忽略；C++11 起提供。
• 
  

clear()只销毁元素，不释放缓冲区；要真正释放，可以用shrink_to_fit()，或者与一个空vector交换：std::vector<T>(v).swap(v)——注意这会拷贝，C++11 起更常见的写法是std::vector<T>().swap(v)，把v换成一个空容器，旧缓冲区随临时对象析构释放。

下面的程序不测时间，只记录每次容量变化，用来观察你所用实现的增长策略：

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
std::vector<int> 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」：

// 适用于 C++17
#include <cstddef>
#include <vector>

std::vector<int> build(std::size_t n) {
std::vector<int> v;
v.reserve(n); // 只分配缓冲区，size 仍为 0
for (std::size_t i = 0; i < n; ++i) {
v.push_back(static_cast<int>(i));
}
return v;
}

reserve之后size()仍是 0，不能直接下标访问；要访问必须先resize或push_back。另一个常见混淆是resize与reserve的顺序：先resize(n)再逐元素赋值，和先reserve(n)再push_back，最终size()都是 n，但前者对元素做了两次初始化（值初始化 + 赋值），后者只有一次构造，后者通常更合适。

常见坑点

1. 
   
2. ❌ 认为vector一定按 2 倍扩容，并据此写死容量计算。
3. 
   

✅ 增长因子由实现决定；只依赖摊销 O(1)，不依赖具体倍数。

1. 
   
2. ❌clear()之后以为内存已释放。
3. 
   

✅clear()只销毁元素；用shrink_to_fit或 swap 空容器释放。

1. 
   
2. ❌reserve(n)之后直接v[0] = 1;。
3. 
   

✅reserve不改变size()；先resize或push_back。

1. 
   
2. ❌ 扩容后继续使用之前保存的迭代器、指针或引用。
3. 
   

✅ 重新分配会使全部失效；重新获取。

1. 
   
2. ❌ 在循环外保存end()，循环内push_back。
3. 
   

✅ 每次重新取end()，或先预留足够容量。

1. 
   
2. ❌ 给自定义类型的移动构造不标noexcept，却期望扩容时移动。
3. 
   

✅ 移动可能抛异常且类型可拷贝时，vector会选择拷贝。

1. 
   
2. ❌ 认为shrink_to_fit()保证容量等于size()。
3. 
   

✅ 它是非强制请求，实现可以忽略。

1. 
   
2. ❌ 把std::vector<bool>当作普通vector取data()或元素地址。
3. 
   

✅ 它有专门的位压缩特化，元素是代理对象，不提供data()。

总结

理解vector的扩容，关键是区分「已构造元素」与「已分配空间」，并接受增长策略属于实现细节。写代码时只依赖标准保证的部分：摊销 O(1)、连续存储、重新分配导致全部失效；把reserve用在规模已知的地方，把迭代器失效当成硬约束，就能避开绝大多数与扩容相关的错误。