vector 扩容与迭代器失效

面试回答

常见问法

• 为什么 std::vector 扩容会导致迭代器失效？
• 什么时候 vector 的迭代器不会失效？
• push_back、insert、erase 分别会让哪些迭代器失效？
• reserve 和 resize 有什么区别？
• 频繁插入时为什么很多场景不推荐 vector？

回答

vector 的底层是连续内存。这带来了两个核心收益：

1. 支持真正的随机访问，O(1) 下标访问；
2. 缓存局部性好，遍历性能通常很强。

但代价是：一旦容量不够，vector 不能像链表那样“随便接一块新内存”，而是通常要：

1. 申请一块更大的新连续内存；
2. 把旧元素搬过去（移动或拷贝）；
3. 释放旧内存。

这样一来，原来元素的地址整体变化，所以原来的迭代器、指针、引用都会失效。这就是为什么扩容会导致迭代器失效，本质原因不是“插入”本身，而是连续内存 + 重新分配（reallocation）。

要分情况说：

• 如果发生扩容：所有迭代器、指针、引用都失效，包括 end()

• 如果不发生扩容

  • push_back / emplace_back：已有元素的迭代器、引用通常仍有效，但 end() 会失效
  • insert / emplace 在中间插入：插入点及其后的迭代器、引用会失效
  • erase：被删位置及其后的迭代器、引用会失效

所以面试里最好不要只说“扩容会失效”，而要补一句： vector 的失效规则和“是否重新分配内存”“是否导致元素搬移”直接相关。

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;
    v.reserve(2);

    v.push_back(1);
    auto it = v.begin();   // 指向 1

    v.push_back(2);        // 容量足够，不扩容
    std::cout << *it << "\n";   // 仍然有效，输出 1

    v.push_back(3);        // 触发扩容，整体搬迁
    // std::cout << *it << "\n"; // 未定义行为：it 已失效
}

追问

• 为什么 vector 一定要用连续内存？
• 为什么扩容通常不是每次只加 1 个？
• reserve 能不能保证迭代器永远不失效？
• resize 和 reserve 的区别是什么？
• 为什么中间插入即使不扩容，也会导致部分迭代器失效？
• deque、list 在迭代器稳定性上和 vector 有什么不同？

---

原理展开

1. vector 为什么坚持连续内存

vector 的设计目标不是“插入删除最灵活”，而是“像动态数组一样高效”。

连续内存带来三件事：

① 真正的随机访问

v[i]

可以直接通过首地址加偏移计算，时间复杂度是 O(1)。

② 缓存友好

CPU 访问连续内存时更容易命中 cache，顺序遍历性能通常明显优于链式结构。

③ 能与 C 风格数组很好协作

例如：

v.data()

可以拿到连续缓冲区首地址，便于和底层接口、序列化、系统调用、数值计算库配合。

代价也很直接： 一旦空间不够，就不能“零碎扩展”，而必须重新找一块更大的连续空间。

---

2. 扩容时到底发生了什么

当 size() == capacity()，再执行 push_back / emplace_back / 某些 insert 时，常见流程是：

1. 分配更大的内存块；
2. 旧元素迁移到新内存；
3. 构造新插入元素；
4. 销毁旧内存中的元素并释放旧内存。

这会导致：

• 元素的新地址不再是旧地址
• 原来的迭代器、指针、引用都指向旧内存
• 因此全部失效

std::vector<std::string> v;
v.push_back("A");
v.push_back("B");

auto p = &v[0];       // 保存旧地址
v.push_back("C");     // 可能扩容

// p 可能已经悬空，不能再用

3. 为什么扩容策略通常按倍数增长

如果每次只多申请一个元素空间，那么连续 n 次 push_back 会频繁重新分配，总代价非常高。

因此实现通常采用“按倍数增长”的策略，比如 1.5 倍、2 倍等（具体倍数由实现决定，标准不强制）。 这样做的目的不是“绝对快”，而是保证尾插的均摊复杂度是 O(1)。

也就是说：

• 某一次扩容可能很贵；
• 但摊到很多次 push_back 上，平均代价可接受。

面试里可以说： vector::push_back 不是每次都 O(1)，而是均摊 O(1)。

---

4. 不扩容时，为什么中间插入仍会让迭代器失效

很多人只记得“扩容会失效”，但忽略了另一个点： 只要元素位置发生搬移，依赖原位置的迭代器也可能失效。

比如容量足够时：

std::vector<int> v{1, 2, 3, 4};
v.reserve(10);

auto it1 = v.begin();      // 指向 1
auto it2 = v.begin() + 2;  // 指向 3

v.insert(v.begin() + 1, 99);

插入后元素可能变成：

1, 99, 2, 3, 4

为了给 99 腾位置，原来从插入点开始的元素都要整体后移。 所以：

• 插入点之前的迭代器通常还有效
• 插入点及其后的迭代器、引用会失效
• end() 也会失效

这说明失效的根本判断依据有两个：

1. 有没有 reallocation
2. 有没有元素位置搬移

---

5. 常见操作的失效规则

这是面试最容易被追问的地方。

push_back / emplace_back

• 若发生扩容：全部失效
• 若不扩容：已有元素的迭代器/引用通常有效，但 end() 失效

insert / emplace

• 若发生扩容：全部失效
• 若不扩容：插入位置及其后的迭代器/引用失效；前面的通常有效；end() 失效

erase

• 被删位置及其后的迭代器/引用失效；前面的通常有效；end() 失效

clear

• 所有指向元素的迭代器、引用失效
• 容量通常不一定变成 0，capacity() 可能保持不变

reserve

• 如果申请的容量 大于当前 capacity，会触发重新分配，全部失效
• 如果申请值不大于当前 capacity()，通常不发生变化

resize

• 改的是 size
• 如果新大小超过当前容量，可能触发扩容，从而全部失效
• 如果缩小，只会销毁尾部元素，指向被删元素及其后的迭代器失效

shrink_to_fit

• 只是非强制请求
• 如果实现真的收缩了容量，可能重新分配，从而导致全部失效
• 不能把它当作“稳定且可预测的缩容手段”

---

6. reserve 和 resize 的区别，面试必须说清

这是高频追问。

reserve(n)

• 调整的是容量 capacity
• 不改变元素个数 size
• 不会创建新元素
• 目的是减少未来扩容次数

std::vector<int> v;
v.reserve(100);  // size 还是 0，但容量至少够放 100 个

resize(n)

• 调整的是当前元素个数 size
• 如果变大，会新增元素（默认构造或指定值）
• 如果变小，会销毁多余元素

std::vector<int> v;
v.resize(100);   // size 变成 100，真的有 100 个元素

面试一句话区分： reserve 管“预留空间”，resize 管“实际元素数量”。

---

7. 元素搬迁时是拷贝还是移动

这属于加分点。

扩容搬迁旧元素时，通常会优先使用移动构造，因为更高效； 但如果类型的移动构造不可用，或者某些实现出于异常安全考虑，也可能退回到拷贝。

所以工程上有两个启发：

• 给自定义类型提供高质量的移动语义，可以降低 vector 扩容成本
• 对重对象频繁扩容的场景，尽量提前 reserve

struct BigObject {
    BigObject() = default;
    BigObject(const BigObject&) { /* expensive copy */ }
    BigObject(BigObject&&) noexcept { /* cheap move */ }
};

如果对象移动很便宜，vector 扩容的代价就会小很多。

---

8. 工程实践里怎么选

适合用 vector 的场景

• 元素主要在尾部追加
• 读多写少
• 需要高效遍历、随机访问
• 数据规模可预估，能提前 reserve

不太适合的场景

• 经常在头部或中间插入/删除
• 长期持有很多迭代器、指针、引用，且容器会频繁修改
• 非常在意迭代器稳定性

常见优化建议

• 预估数量时优先 reserve
• 循环插入时避免反复触发扩容
• 需要稳定引用时，不要随便缓存 &v[i]
• 修改容器后，谨慎复用旧迭代器
• 如果业务是“频繁中间插入”，先问自己：真的该用 vector 吗？

---

对比总结

1. vector / deque / list 对比

工程上默认优先考虑 vector，不是因为它“功能最多”，而是因为它通常综合性能最好。 只有当插入删除模式、稳定性要求明显不适合时，才考虑 deque / list。

---

2. reserve / resize / shrink_to_fit 对比

---

3. 常见操作的迭代器失效规则

---

易错点

• 把“插入导致失效”说成唯一原因，忽略了本质其实是重新分配和元素搬移

• 只说“扩容会失效”，但没补充：

  • push_back 不扩容时，已有元素迭代器通常仍有效
  • insert 中间插入即使不扩容，也会让插入点及其后失效

• 忽略 end()：很多操作即使不扩容，end() 也常常会失效

• 误以为 reserve 能保证“永不失效” 它只能降低扩容概率，不能保证业务代码后续永不触发失效

• 把 reserve 和 resize 混用 前者是“留坑位”，后者是“真的创建元素”

• 误以为扩容一定是“翻倍” 实现通常按增长策略扩容，但标准不规定具体倍数

• 长期保存 &v[0]、v.data()、旧迭代器，然后在容器修改后继续用

• 忽略 vector<bool> 是特化版本，不完全等同于普通 vector<T>

---

记忆技巧

• 一句话总纲： vector 因为连续，所以扩容要搬家；一搬家，旧地址全失效。

• 两条判断线：

  1. 有没有 重新分配内存
  2. 有没有 导致元素位置搬移

• 三种典型规则：

  • 尾插不扩容：元素大多还稳，end() 不稳
  • 中间插入不扩容：插入点后面不稳
  • 只要扩容：全都不稳

• 口诀： “连续内存怕搬家，扩容一来全失效；不扩容也别大意，中后位置照样飘。”

---

面试速答版

vector 的底层是连续内存，所以它能高效随机访问、缓存友好。但也因为连续，一旦容量不够，扩容通常要重新申请更大的连续空间，把旧元素整体搬过去，再释放旧空间。这样原来元素地址全变了，所以旧的迭代器、指针、引用都会失效。

如果不扩容，要分操作看：push_back 一般不会让已有元素迭代器失效，但 end() 会失效；中间 insert 即使不扩容，也会让插入点及其后的迭代器失效，因为元素发生了搬移。工程上如果能预估数据量，应该先 reserve，减少扩容次数；如果频繁中间插入，就要重新评估是不是该用 vector。

---

面试加分版

vector 迭代器失效的根因，不能只回答“因为扩容”，更准确地说，是因为它采用连续内存。连续内存让它具备两个很强的优势：一是 O(1) 随机访问，二是缓存局部性好，所以顺序遍历通常非常快。这也是为什么工程里很多场景默认首选 vector。

但连续内存的代价是扩容不灵活。容量不足时，vector 往往需要重新申请一块更大的连续空间，把旧元素移动或拷贝过去，再释放旧空间。这样所有元素地址都会变化，所以之前保存的迭代器、指针、引用都会失效，包括 end()。这也是为什么 push_back 的复杂度是均摊 O(1)，因为实现通常按倍数增长容量，减少频繁重分配。

不过面试里更容易拉开差距的是：不是只有扩容才会失效。 如果容量足够，push_back 通常不会让已有元素迭代器失效，但 end() 会失效；如果是在中间位置 insert，即使不扩容，插入点以及后面的元素也会整体后移，所以这些位置对应的迭代器、引用一样会失效。erase 也是类似逻辑，被删位置及其后的迭代器会失效。

工程上我的选择原则是：如果主要是尾插、遍历、随机访问，就优先用 vector，并在已知规模时先 reserve；如果业务频繁中间插入删除，或者代码长期持有很多元素引用和迭代器，就要谨慎，可能更适合 deque 或 list。所以判断 vector 迭代器是否安全，核心不是死记规则，而是看两点：有没有重新分配内存，和有没有导致元素位置搬移。