文档目录

一、物理内存：绝对连续

vector 是 C++ 唯一保证元素在堆内存中绝对连续排列的容器（与 std::array 一样，但 array 在栈上）。

vector<int> v = {10, 20, 30, 40};

堆内存 (Heap):
+──────+──────+──────+──────+──────────────────+
|  10  |  20  |  30  |  40  |  预留空间         |
+──────+──────+──────+──────+──────────────────+
  ^      ^      ^      ^                       ^
  |      |      |      |                       |
v[0]   v[1]   v[2]   v[3]                   v.capacity() - 1

栈上 (Stack) — vector 对象本身 (24 字节，64位):
+────────────────────────────────────────────────────+
| _M_start (ptr)  | _M_finish (ptr) | _M_end_of_storage (ptr) |
| 指向堆首         | 指向堆尾(size)   | 指向容量尾(capacity)    |
+────────────────────────────────────────────────────+

关键结论：

  • v.data() 返回的指针可以做指针运算：*(v.data() + 2) 就是 v[2]。
  • 因为连续，CPU 预取器（Prefetcher）在遍历时会自动把相邻元素加载到缓存行，所以 vector 的遍历速度是 list 的 10-50 倍。

二、扩容因子：为什么是 1.5 倍或 2 倍？

当 size() == capacity() 时，push_back 触发扩容：

v.push_back(50); // capacity() 不够了 → 分配新内存 → 搬移所有元素 → 释放旧内存

扩容流程：

旧内存: [10][20][30][40]         容量=4
       ↓ push_back(50)
1. 分配新内存: [ ][ ][ ][ ][ ][ ][ ][ ]  容量=8 (2倍)
2. 搬移:      [10][20][30][40][50][ ][ ][ ]
3. 释放旧内存

为什么是 2 倍（GCC）或 1.5 倍（MSVC）？

扩容因子 均摊复杂度 内存浪费 内存复用可能性
2x (GCC) $O(1)$ 均摊 最多浪费 50% 低：新内存总是两倍大，旧内存碎片很难被复用
1.5x (MSVC) $O(1)$ 均摊 最多浪费 33% 高：1.5 倍增长满足"之前释放的总和 > 下次分配大小"，有机会复用旧内存

面试经典题：“为什么 vector 扩容不固定加 N 个元素？”

  • 如果每次固定 +N：连续 M 次插入的时间复杂度是 $O(M \times N)$ → 每次都是 $O(N)$。
  • 如果是倍数增长：M 次插入的均摊复杂度是 $O(1)$（每次扩容的元素数量是指数增长的，拷贝次数是 1+2+4+…+M/2 ≈ M）。

三、size() vs capacity()，reserve() vs resize()

vector<int> v;
v.reserve(100);   // 只扩大 capacity，不构造元素，不改变 size
v.resize(100);    // 扩大 capacity 并构造 100 个默认元素，size=100
v.push_back(1);   // reserve后：size=101，不触发扩容
                 // resize后：size=101，触发扩容（因为 size==capacity==100）

硬件代价对比：

reserve(10000):       一次 malloc(40KB)，不构造元素   → 约 0.1μs
resize(10000):        一次 malloc + 10000次默认构造   → 约 10μs (100倍！)
默认 push_back 10000次: 多次 malloc + 多次拷贝搬移    → 约 50μs (最慢)

最佳实践：如果你预先知道元素数量，永远先 reserve。这是零成本优化。

四、迭代器失效（Iterator Invalidation）—— 面试必考

操作 迭代器失效情况
push_back / emplace_back 如果触发扩容 → 所有迭代器失效；如果不触发 → end() 迭代器失效
insert / erase 插入/删除位置之后的所有迭代器失效
pop_back 被删除元素和 end() 的迭代器失效
reserve 如果新容量 > 旧容量 → 所有迭代器失效
resize 如果新容量 > 旧容量 → 所有迭代器失效

底层原因：扩容时 _M_start 指针变了，指向一块新的堆内存——所有基于旧地址的迭代器都变成了悬垂指针。

// ❌ 错误代码
vector<int> v = {1, 2, 3, 4};
int* ptr = &v[2];        // 指向第三个元素
v.push_back(5);          // 可能触发扩容 → ptr 变成悬垂指针！
*ptr = 42;               // 💥 Use-After-Free！

// ✅ 正确做法
v.reserve(8);            // 提前预留空间
int* ptr = &v[2];
v.push_back(5);          // 不触发扩容，ptr 依然有效