vector扩容真相
# 32.vector扩容真相
# 目录介绍
- 1. 案例引入
- 2. 架构概览
- 3. capacity 与 size 的本质差异
- 4. 扩容因子的数学推导
- 5. push_back 与 emplace_back 的真相
- 6. reserve 的最佳实践与反模式
- 7. 迭代器失效的精确规则
- 8. 扩容操作的汇编全景
- 9. 现代替代与优化策略
- 10. 综合案例串讲
# 1. 案例引入
# 1.1 高频交易系统的延迟抖动
某高频交易系统的行情接收模块，用 std::vector 存储实时订单簿。压测时发现 P99 延迟从 12 μs 突然跳到 680 μs，每隔约 1000 个订单发生一次：
// ====== 事故代码 V1：未知的扩容触发 ======
std::vector<Order> order_book; // 一开始没有 reserve
void on_order(const Order& order) {
order_book.push_back(order); // ← P99 延迟的元凶
update_bbo(order_book);
}
2
3
4
5
6
7
用 perf stat 诊断后，发现 on_order 的 60% CPU 时间消耗在 memcpy 上。查 order_book.capacity()——容量增长模式为 1→2→4→8→16→...→4096→...→65536，一共触发了 16 次扩容。每次扩容 = 分配新内存 + 拷贝所有已有元素 + 释放旧内存。
量化：第 16 次扩容（32768→65536）需要拷贝 32768 个 Order 对象（每个 ~128 字节）→ 4 MB 的 memcpy——这就是 P99 延迟脉冲的来源。
直觉修复——加一行 reserve：
order_book.reserve(100000); // 预分配——一次搞定
on_order 的 P99 立刻从 680 μs 降回 12 μs。但作者困惑：为什么 vector 不能自动预判我的需求量？1.5x/2x 的扩容因子到底是怎么算的？
# 1.2 迭代器在 emplace 后的神秘失效
同一个系统的策略引擎——在遍历订单簿时 emplace_back，迭代器突然指向非法内存：
// ====== 事故代码 V2：迭代器在扩容后失效 ======
std::vector<Order> order_book;
order_book.reserve(8); // capacity = 8, size = 0
for (int i = 0; i < 8; ++i) {
order_book.emplace_back(i); // size = 8, capacity = 8
}
auto it = order_book.begin(); // it 指向元素 0
order_book.emplace_back(99); // 第 9 个——触发扩容！capacity 变成 16
// → it 现在指向旧内存（已被释放）→ 悬垂迭代器
std::cout << it->price; // ← 未定义行为——可能输出垃圾、可能 SIGSEGV
2
3
4
5
6
7
8
9
10
11
12
13
关键洞察：reserve(8) 保证前 8 次插入不扩容。第 9 次扩容后，所有的迭代器、引用和指针全部失效——因为 vector 内部的三根指针（begin/end/capacity_end）全部被更新为新内存地址。这不是 emplace_back 的错——扩容 = 搬家 = 旧地址全部作废。
# 1.3 七个待解疑问
① vector 的 size 和 capacity 到底区别在哪? 三个指针分别是谁? → 第 3 章
② 扩容因子为什么是 1.5x 或 2x? 和 O(n²) / 内存复用有什么关系? → 第 4 章
③ emplace_back 和 push_back 到底差在哪? 什么时候等价、什么时候不同? → 第 5 章
④ reserve 为什么不能解决所有问题? 滥用 reserve 会有什么反效果? → 第 6 章
⑤ 哪些操作会使迭代器失效? 失效的精确规则是什么? → 第 7 章
⑥ 扩容在汇编层到底做了哪些事? 移动和拷贝的指令序列有什么区别? → 第 8 章
⑦ 什么时候不该用 vector? 有哪些现代替代方案? → 第 9 / 第 10 章
2
3
4
5
6
7
# 2. 架构概览
# 2.1 vector 的三段式内存模型
std::vector<T> 的内存本质上是由 三根指针 管理的一段连续堆内存：
┌─────────────────────────────────────────────────────┐
│ vector 的内存布局 │
│ │
│ [已构造元素区] [未构造预留区] [未分配区域] │
│ ◄── size() ──► ◄ capacity()-size() ► │
│ │
│ ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──────────────┐ │
│ │e0│e1│e2│e3│e4│e5│ │ │ │ │ │ 未分配内存 │ │
│ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──────────────┘ │
│ ▲ ▲ ▲ │
│ │ │ │ │
│ _M_start _M_finish _M_end_of_storage │
│ (begin) (end) (capacity end) │
└─────────────────────────────────────────────────────┘
2
3
4
5
6
7
8
9
10
11
12
13
14
三个指针的物理含义：
| 指针 | 别名 | 含义 | 改变时机 |
|---|---|---|---|
_M_start | begin() | 第一个元素的地址 | 仅在扩容/缩容时改变 |
_M_finish | end() | 最后一个元素的下一个地址 | push_back/pop_back/insert/erase |
_M_end_of_storage | — | 已分配内存的末尾 | 仅在扩容/缩容时改变 |
关键关系：
size() = _M_finish - _M_start（元素个数）capacity() = _M_end_of_storage - _M_start（最多能存多少）empty() = (_M_finish == _M_start)
# 2.2 为何这么切
疑惑：为什么 vector 必须有「capacity」这个概念？不能 size == capacity 吗？
论证：
- 扩容 = 重新分配整块内存 + 搬移所有元素——这是 O(N) 操作。如果在每次
push_back时都做一次（即 capacity == size），N次push_back的总开销是 O(N²)。预留 capacity 的本质是把 O(N²) 的扩容总开销摊还为 O(1) 的单次 push_back。 - capacity > size 的那部分空间是「未初始化的合法内存」——已经被
operator new分配、但尚未调用任何元素的构造函数。在这片空间上构造新元素是 O(1)，不需要重新分配。 - 反向验证：C 语言的动态数组必须手动
realloc——每次增长都要拷贝整个数组。C++ 的vector把这种「整块搬移」封装成了隐式的自动扩容——程序员只需push_back，编译器/标准库负责扩容策略。
结论：capacity 是 vector 将「O(N) 的重新分配」摊还为「O(1) 的单次 push_back」的核心机制。没有 capacity，vector 就是残废的；理解 capacity，就理解了 90% 的 vector 性能问题。
# 3. capacity 与 size 的本质差异
# 3.1 三个指针的物理含义
libstdc++ 的 vector 内部只有一个成员——_Vector_impl，它又只包含三根指针：
// libstdc++ 简化版 vector 内部结构
template <typename T, typename Alloc>
class vector {
struct _Vector_impl : public Alloc { // EBO 继承分配器
T* _M_start; // 已构造区域起点
T* _M_finish; // 已构造区域终点
T* _M_end_of_storage; // 已分配区域终点
};
_Vector_impl _M_impl; // vector 的唯一成员——3 个指针 = 24 字节
};
// sizeof(std::vector<int>) = 24（三根指针——64 位）
2
3
4
5
6
7
8
9
10
11
12
疑惑：为什么 _Vector_impl 继承 Alloc 而不是包含为成员？
论证：EBO（空基类优化）——std::allocator<T> 是无状态空类。通过继承，空分配器的 1 字节被压缩为 0。如果作为成员，至少占 1 字节。这是 C++ 标准库在微优化上的极致追求。
# 3.2 size 与 capacity 的不变性与改变条件
| 操作 | size 变化 | capacity 变化 | O(1)? |
|---|---|---|---|
push_back (有预留) | +1 | 不变 | ✅ |
push_back (无预留) | +1 | ×1.5 或 ×2 | ❌ O(N) |
pop_back | -1 | 不变 | ✅ |
clear() | →0 | 不变 | ✅ |
reserve(n) (n > capacity) | 不变 | →n | ❌ O(N) |
shrink_to_fit() | 不变 | →size | ❌ O(N) |
erase | -N | 不变 | ✅ (O(后面元素数)) |
核心不变量：size() <= capacity() 永远成立。capacity 只增不减（除非显式 shrink_to_fit）。
# 3.3 reserve、resize、shrink_to_fit 三部曲
std::vector<int> v(5, 42); // size=5, capacity=5, 每个元素=42
v.reserve(10); // size=5, capacity=10, 元素不变
v.resize(3); // size=3, capacity=10, 尾部 2 个元素被析构
v.resize(8, 99); // size=8, capacity=10, 新增 5 个 99
v.shrink_to_fit(); // ⚠️ 非强制——实现可以不缩减；如果缩减→size=8, capacity=8
2
3
4
5
6
reserve 的核心语义：保证 capacity >= n。如果已经 >= n → 什么都不做。 这使 reserve 可以安全地在任何时刻被调用。
# 3.4 内存布局的可视化
vector<int> v; v.reserve(4);
┌──┬──┬──┬──┬─────────────┐
│ │ │ │ │ 未分配区域 │ _M_start = _M_finish, _M_end_of_storage = +4*4
└──┴──┴──┴──┴─────────────┘
v.push_back(1); v.push_back(2);
┌──┬──┬──┬──┬─────────────┐
│1 │2 │ │ │ 未分配区域 │ _M_finish = +2*4
└──┴──┴──┴──┴─────────────┘
v.push_back(3); v.push_back(4);
┌──┬──┬──┬──┬─────────────┐
│1 │2 │3 │4 │ 未分配区域 │ _M_finish = _M_end_of_storage
└──┴──┴──┴──┴─────────────┘
v.push_back(5); // 触发扩容！capacity 4→8 (GCC ×2)
┌──┬──┬──┬──┬──┬──┬──┬──┬──────┐
│1 │2 │3 │4 │5 │ │ │ │ ... │ 旧内存被释放
└──┴──┴──┴──┴──┴──┴──┴──┴──────┘
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 4. 扩容因子的数学推导
# 4.1 1.5x vs 2x 的完整推演
疑惑：扩容因子既不是 1.5 也不是 2——不同编译器不同选择。到底哪个好？
论证——先算总拷贝代价：
假设 push_back N 次，扩容因子为 g > 1：
扩容次数 k = ⌈log_g(N)⌉
第 i 次扩容时的已有元素：g^(i-1)
第 i 次扩容的拷贝次数：g^(i-1)（移动/拷贝所有已有元素）
总拷贝次数 = Σ g^(i) (i=0..k-1)
≈ N × g / (g-1) [等比数列求和]
当 g = 2：总拷贝 ≈ 2N
当 g = 1.5：总拷贝 ≈ 3N
当 g = 1.1：总拷贝 ≈ 11N（扩容太多——虽然每次拷贝的少）
2
3
4
5
6
7
8
9
10
11
结论：从总拷贝次数来看，g=2 最优（拷贝最少）。但为什么 MSVC 选 1.5？
# 4.2 常数增量扩容的 O(n²) 灾难
如果每次扩容只加固定大小（如 +100）：
第 1 次 push_back：拷贝 0 个元素
第 101 次 push_back：拷贝 100 个元素
第 201 次 push_back：拷贝 200 个元素
...
第 10001 次 push_back：拷贝 10000 个元素
N 次 push_back 总拷贝 ≈ N² / (2*增量) → O(N²)
2
3
4
5
6
7
100000 次 push_back → ~50 亿次拷贝——完全不可接受。几何级扩容是必须的。
# 4.3 各编译器、各平台的决策表
| 实现 | 扩容因子 | 理由 |
|---|---|---|
| libstdc++ (GCC) | 2.0 | 最小化拷贝次数 |
| libc++ (Clang) | 2.0 | 同 GCC |
| MSVC | 1.5 | 内存复用——释放的空间可被后续分配复用 |
| Facebook folly (fbvector) | 1.5 | 同 MSVC 理由 |
为什么 MSVC/fbvector 选择 1.5：当扩容因子为 2 时，第 k 次扩容释放的空间（2^k 字节）比之前所有扩容累计释放的（2^k - 2 字节）还大——malloc 无法把它们粘在一起复用。当因子为 1.5 时，第 k 次扩容释放的空间（1.5^k）< 之前累计释放空间（1.5^k * 2），可以被分配器复用。
# 4.4 为什么 1.5 选择可以内存复用
扩容序列：1, 2, 4, 8, 16, 32, ...（因子=2）
第 5 次扩容（capacity: 16→32）：
释放的旧内存：16 个 T 的大小
之前累计释放的总和：1+2+4+8 = 15 个 T 的大小
16 > 15 → 新释放的内存块比之前所有碎片加起来还大 → 无法拼接复用
扩容序列：1, 1, 2, 3, 4, 6, 9, 13, 19, 28, ...（因子≈1.5，取整数）
第 10 次扩容（capacity: 28→42）：
释放的旧内存：28 个 T 的大小
之前累计释放的总和 ≈ 48 个 T 的大小
28 < 48 → 新释放的内存块比之前所有碎片小 → 分配器可能拼接复用
2
3
4
5
6
7
8
9
10
11
12
13
结论：g=2 最小化拷贝（更少扩容次数），g=1.5 最大化内存复用（减少碎片）。这是时间复杂度 vs 空间利用率的经典权衡。
与 deque 的扩容模型对比——为什么 deque 没有这个烦恼：
vector 扩容：
分配新内存块(capacity*2) → 搬移全部元素 → 释放旧块
问题：旧块和后续分配难以拼接（碎片）
deque 扩展：
申请新的 chunk（固定 512B）→ 把 chunk 指针放进 map
问题：旧 chunk 不动——不产生「已释放的大块」
但随机访问需要两级间址（map + chunk）
选择：
vector → 连续内存（缓存友好） + 扩容代价（O(N) 整块搬家）
deque → 不搬家（迭代器稳定） + 两级间址（缓存不友好）
2
3
4
5
6
7
8
9
10
11
12
# 4.5 扩容与异常安全的共生关系
第 27 篇讨论了 noexcept 移动对 vector 扩容的影响——这里补充完整论证：
疑惑：为什么 vector 扩容时必须保强异常安全？扩容中抛异常会怎样？
论证——扩容三阶段的异常传播：
阶段 ①：operator new——可能抛 bad_alloc
→ 旧内存完整 → 旧 vector 保持原状 ✅（强异常安全）
阶段 ②：搬移元素——移动构造可能抛异常
├─ 如果 noexcept → 全部搬完 ✅
└─ 如果不 noexcept：
├─ 部分搬完、某个中间元素抛异常
├─ vector 回滚：把已搬走的移回旧内存
└─ 释放新内存 → 旧 vector 保持原状 ✅
⚠️ 但！如果移回来也抛异常 → 强安全不可保 → basic guarantee
⇒ 这就是为什么 noexcept 移动构造对 vector 扩容如此重要：
没有它，vector 扩容可能在 ② 阶段回滚失败、丢失元素。
2
3
4
5
6
7
8
9
10
11
12
13
GCC 的 fallback 策略：如果 T 的移动构造不是 noexcept，GCC 在扩容时宁可拷贝也不移动——因为拷贝不会破坏原对象，回滚不需要「移回来」。强安全比性能更重要——这是库设计者的防御性选择。
# 5. push_back 与 emplace_back 的真相
# 5.1 emplace_back 的参数包展开链路
第 20 篇详解了可变参模板，这里把它应用到 emplace_back：
// libstdc++ 简化版 emplace_back
template <typename... Args>
T& emplace_back(Args&&... args) {
if (_M_finish == _M_end_of_storage) {
_M_realloc_grow(); // 扩容
}
// 在 _M_finish 地址上原地构造——没有临时对象！
::new (_M_finish) T(std::forward<Args>(args)...);
++_M_finish;
return *(_M_finish - 1);
}
2
3
4
5
6
7
8
9
10
11
关键：emplace_back 的参数通过完美转发直接传给 T 的构造函数——零中间临时对象。
# 5.2 移动 vs 拷贝 vs 原地构造的选择
std::vector<std::string> vec;
std::string s = "hello world";
vec.push_back(s); // ① 拷贝：s → 新元素
vec.push_back(std::move(s)); // ② 移动：s 被移走
vec.push_back("hello world"); // ③ 隐式构造临时 string + 移动
vec.emplace_back("hello world"); // ④ 原地构造——零临时对象
// ① 和 ② 的区别：push_back(const T&) vs push_back(T&&)
// ③ 和 ④ 的区别：是否需要先构造临时 string
2
3
4
5
6
7
8
9
10
汇编对比（GCC 13.2 -O2）：
; push_back("hello world") —— ③ 隐式构造 + 移动
call std::string::string(const char*) ; ① 构造临时 string
call std::string::string(string&&) ; ② 移动到 vector
call std::string::~string() ; ③ 析构临时
; emplace_back("hello world") —— ④ 原地构造
lea rdi, [_M_finish] ; 目标地址
call std::string::string(const char*) ; 直接在目标上构造！
; 省了一条移动 + 一条析构
2
3
4
5
6
7
8
9
# 5.3 三场景性能实测
100 万个 std::string("hello") 插入：
| 方式 | 构造次数 | 移动次数 | 总时间 | 原因 |
|---|---|---|---|---|
push_back(const T&) | 1 (在调用方) | 1 (拷贝到 vector) | 4.2 ms | — |
push_back(T&&) | 1 (在调用方) | 1 (移动到 vector) | 3.1 ms | 少一次深拷贝 |
push_back("literal") | 1 (临时) | 1 (移动到 vector) | 3.4 ms | 临时→移动 + 析构 |
emplace_back("literal") | 1 (原地) | 0 | 2.2 ms | 零临时对象、零移动 |
# 5.4 push_back(T&&) 与 emplace_back(T&&) 为什么等价
vec.push_back(std::move(s)); // 调 push_back(string&&)
vec.emplace_back(std::move(s)); // 转发 std::move(s) → string(string&&)
// 两者都调用 string 的移动构造——效果完全一致
2
3
4
emplace_back 的真正优势场景：当构造参数需要隐式转换时——直接传构造参数包，省去临时对象。
# 6. reserve 的最佳实践与反模式
# 6.1 提前 reserve 的收益量化
100 万个 int 的 push_back——有无 reserve 对比：
| reserve(1M) | 扩容次数 | 总拷贝次数 | push_back 总时间 |
|---|---|---|---|
| ❌ 无 | 20 (GCC, ×2) | ~2M | 4.2 ms |
| ✅ 有 | 0 | 0 | 1.8 ms |
# 6.2 误用 reserve 导致的四种问题
① reserve 不是 resize：
vec.reserve(100);
vec[50] = 42; // ❌ UB——size() 仍然是 0，vec[50] 未构造
2
② 无效 reserve 碎片：
std::vector<int> vec;
vec.reserve(1'000'000);
// ... 只用到了 100 个元素
// → 浪费了 900000 × sizeof(int) = 3.6 MB
2
3
4
③ reserve + 迭代失效：
vec.reserve(100);
auto it = vec.begin();
vec.reserve(200); // 重新分配→it 失效
2
3
④ 误解 capacity 的持久性：
vec2 = vec; // 拷贝赋值——capacity 可能不保留
# 6.3 reserve + push_back 的正确组合
std::vector<Order> orders;
orders.reserve(known_size); // 一次 reserve
for (auto& msg : messages) {
orders.emplace_back(msg); // 零扩容、零临时对象
}
2
3
4
5
# 7. 迭代器失效的精确规则
# 7.1 插入时的失效规则
std::vector<int> v = {1,2,3,4};
auto it = v.begin() + 2; // it → 3
// 场景 A：插入不扩容（capacity > size）
v.insert(v.begin(), 0); // capacity 不变，但所有元素后移
// it 仍指向原来的[2]位——现在是 2 了
// 所有指向插入点之后的迭代器、指针、引用 → 理论上应该失效（元素地址变了）
// 场景 B：插入触发扩容
v.push_back(5); // size==capacity → 扩容→全部搬家
// it → 旧内存（已释放）→ 悬垂
2
3
4
5
6
7
8
9
10
11
规则：push_back/emplace_back/insert 可能使所有迭代器失效（如果触发扩容）。即使不扩容，插入点之后的迭代器也失效（元素被后移）。
# 7.2 删除时的失效规则
auto it = v.begin() + 2;
v.erase(it); // 删除 v[2]——it 失效，且 it 之后的迭代器/引用全部失效
v.pop_back(); // 只失效 end()-1 的迭代器/引用
2
3
# 7.3 失效与「逻辑删除」模式的对比
// ❌ 常见错误：边遍历边改变
for (auto it = v.begin(); it != v.end(); ++it) {
if (should_remove(*it)) {
v.erase(it); // it 失效——++it 访问非法内存
}
}
// ✅ 正确——利用 erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); ) {
if (should_remove(*it)) {
it = v.erase(it); // erase 返回下一个有效元素的迭代器
} else {
++it;
}
}
// ✅ C++20 更简——erase_if
std::erase_if(v, should_remove);
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 7.4 下标索引为什么永远安全
v[100] = 42; // ✅ 和 v 的内存搬移无关——索引每次重新计算
// v[100] = *(v._M_start + 100)——_M_start 永远是最新的
2
迭代器失效的本质是「存了一个失效的裸地址」。下标索引是「存了一个相对偏移，每次都重新计算绝对地址」——天然免疫搬家。
# 8. 扩容操作的汇编全景
# 8.1 push_back 触发扩容的全指令序列
std::vector<Order> v;
for (int i = 0; i < 10; ++i) v.emplace_back(i);
2
第 5 次 push_back 触发扩容（capacity 4→8），GCC 13.2 -O2 简化汇编：
; push_back 触发的扩容核心路径：
; ① 检查是否需要扩容
mov rax, [_M_finish]
cmp rax, [_M_end_of_storage]
jne .L_no_realloc
; ② 计算新 capacity
; GCC: new_cap = max(old_cap * 2, old_cap + 1)
mov rdx, [_M_end_of_storage]
sub rdx, [_M_start] ; old_size
mov rax, rdx
shr rax, 2 ; old_size / 4 = old_capacity (int=4B)
lea rcx, [rax + rax*1] ; new_cap = old_cap * 2
; ③ 分配新内存
imul rdi, rcx, 4
call operator new
; ④ 移动/拷贝所有旧元素到新内存
; — 如果 Order 有 noexcept 移动构造 → 用移动（快）
; — 否则 → 用拷贝（慢但安全——强异常保证）
; ⑤ 析构旧内存上的元素 + 释放旧内存
call operator delete
; ⑥ 更新三根指针
mov [_M_start], rbx ; 新起点
mov [_M_finish], new_end
mov [_M_end_of_storage], new_cap_end
.L_no_realloc:
; 直接在 _M_finish 上原地构造
call Order::Order(int)
inc [_M_finish]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 8.2 移动 vs 拷贝的元素迁移开销
元素迁移时——如果 Order(Order&&) 是 noexcept，vector 走移动路径；否则走拷贝路径：
; noexcept 移动——只交换指针
mov rax, [rsi] ; 读源 ptr
mov [rdi], rax ; 写目标 ptr
mov QWORD [rsi], 0 ; 清空源 ptr
; 3 条 mov → ~1 ns per element
; 拷贝——深拷贝所有字段
call memcpy ; 一次拷贝整个元素块
; 大批量拷贝走 SIMD →
2
3
4
5
6
7
8
9
# 8.3 reserve 消除扩容后的汇编对比
v.reserve(10); // 有 reserve
for (int i = 0; i < 10; ++i) v.emplace_back(i);
2
; 扩容检查——cmp 在第一次后永远不等（因为 capacity=10, size 最多 10）
.Lloop:
mov rdi, [_M_finish]
mov esi, ebx
call Order::Order(int) ; 原地构造——零扩容
add QWORD [_M_finish], 24 ; sizeof(Order)=24
inc ebx
cmp ebx, 10
jne .Lloop
; 完全没有任何 operator new / memcpy / operator delete 的痕迹
2
3
4
5
6
7
8
9
10
# 9. 现代替代与优化策略
# 9.1 什么时候用 deque / list 代替
| 需求 | vector | deque | list |
|---|---|---|---|
| 尾部插入 | ✅ O(1) amortized | ✅ O(1) | ✅ O(1) |
| 头部插入 | ❌ O(N) | ✅ O(1) | ✅ O(1) |
| 随机访问 | ✅ O(1) | ✅ O(1) | ❌ O(N) |
| 迭代器稳定性 | ❌ 扩容失效 | ❌ 中段插入使迭代器失效 | ✅ 永不失效 |
| 内存连续性 | ✅ | ❌ 分段 | ❌ 分散节点 |
# 9.2 small_vector / static_vector 的嵌入式方案
// 如果前 16 个元素直接在对象内部——避免堆分配
// boost::container::small_vector<int, 16>
// 或 folly::small_vector<int, 16>
small_vector<int, 16> v;
v.push_back(1); // 前 16 个——零堆分配
v.push_back(17); // 第 17 个——自动切换到堆扩张
2
3
4
5
6
7
# 9.3 PMR allocator 的扩容优化
// 用 boost::container::pmr::monotonic_buffer_resource 避免多次 new/delete
char buffer[1024 * 1024];
pmr::monotonic_buffer_resource pool(buffer, sizeof(buffer));
pmr::vector<Order> orders(&pool);
orders.reserve(10000); // 在 pool 里直接分配——零系统调用
// 扩容也在 pool 里——不触发 operator new
2
3
4
5
6
7
# 10. 综合案例串讲
# 10.1 案例真相揭晓
| # | 疑问 | 答案 |
|---|---|---|
| ① | size vs capacity? | 第 3 章：三指针模型——_M_start/_M_finish/_M_end_of_storage |
| ② | 扩容因子 1.5 vs 2? | 第 4 章：g=2 总拷贝最优（2N）、g=1.5 内存复用更好（释放空间可拼接） |
| ③ | emplace vs push_back? | 第 5 章：emplace 原地构造——省一次临时+移动+析构；push_back(T&&) 和 emplace_back(T&&) 等价 |
| ④ | reserve 反效果? | 第 6 章：reserve 不是 resize、无效预留浪费内存、扩容仍可能失效迭代器 |
| ⑤ | 迭代器失效? | 第 7 章：扩容→全部失效；插入→插入点后全失效；删除→删除点后全失效 |
| ⑥ | 汇编扩容? | 第 8 章：检查→alloc→移动→delete→更新三指针 |
| ⑦ | 替代方案? | 第 9 章：deque(两端)、list(迭代器稳定)、small_vector(嵌入)、PMR(pool分配) |
案例①修复（延迟抖动）：加一行 reserve(100000)——P99 从 680μs 降到 12μs。
案例②修复（迭代器失效）：扩容后用下标索引代替保存迭代器；或用 deque（迭代器在两端插入时不失效）。
# 10.2 一次 push_back 的完整生涯
v.push_back(x);
═══════ 编译期 ═══════
① 重载决议：选择 push_back(const T&) 还是 push_back(T&&)
② 模板实例化：vector<T>::push_back 在当前 TU 被实例化
═══════ 运行期——无扩容路径 ═══════
③ cmp _M_finish, _M_end_of_storage → jne .Lno_realloc
④ placement new at _M_finish → 构造新元素
⑤ _M_finish++
═══════ 运行期——扩容路径 ═══════
③ cmp _M_finish, _M_end_of_storage → je .Lrealloc
④ 计算 new_cap = old_cap × 2
⑤ operator new(new_cap × sizeof(T))
⑥ 遍历旧元素 → noexcept 移动 或 拷贝
⑦ operator delete(旧内存)
⑧ 更新三指针
⑨ goto ③（回无扩容路径）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 10.3 设计哲学回扣
哲学 1：摊还分析——扩容的 O(1) 是数学的胜利
vector 的 push_back 是摊还 O(1)——单次可能是 O(N)（扩容），但 N 次总共 O(N)。这不是系统设计的侥幸——是几何级扩容的数学必然。好的数据结构设计把「偶尔的昂贵操作」摊到「频繁的廉价操作」上。 等比数列求和公式 Σg^i = (g^k - 1)/(g-1) ≈ N·g/(g-1) 是整个摊还分析的基础——g=2 时总拷贝 ~2N，g=1.5 时 ~3N。两者都是线性——这就是为什么即使某次 push_back 用了 680μs 拷贝 4MB，amortized 依然是 O(1)。
哲学 2：零开销抽象——三个指针管理一段连续内存，不多存一个 byte 的冗余
vector 的 sizeof = 24 字节（三根指针 × 8 = 24）——和任何自制的 T* begin, *end, *cap_end 完全一致。它不存 size_t size 和 size_t capacity 两个整数——因为 end - begin 就是 size，cap_end - begin 就是 capacity。标准库的微优化铁律：不存能算出来的东西。 这也解释为什么 EBO 继承分配器——继承 allocator<T> 把它压缩为 0 字节，包含为成员至少占 1 字节。
哲学 3：迭代器是地址的别名——搬家就是失效
vector 的迭代器本质上就是 T*。扩容就是搬家——旧地址被 operator delete 归还给系统，指向它的 T* 全部作废。这不是 vector 的 bug，是连续内存容器的物理必然。要迭代器稳定 → 用节点型容器（list/set）；要随机访问但怕失效 → 用下标索引代替迭代器。
哲学 4：reserve 是程序员向编译器传递「我知道未来」的唯一通道
编译器无法预知你要 push_back 多少次——但你知道。reserve 就是传递这条知识。不 reserve 的后果是接受摊还开销——可能可接受（N=100），可能灾难性（N=100000，延迟抖动）。性能调优的本质就是传递未表达出来的知识——reserve 是最简单的「知识传递」，也是最容易被忽略的。
哲学 5：emplace_back 把「先构造再搬进容器」替换成「在容器里直接构造」——这是零开销抽象的终极形态
一个 emplace_back("hello") 省了临时对象构造 + 移动 + 临时对象的析构——三条 call 变成一条。这不是「微小优化」——在 N=100000、T = std::string 时差值是 ~2ms。把三步变成一步，不是靠编译器优化——是靠更符合物理过程的接口设计。
# 10.4 速查表合集
扩容因子速查：
| 实现 | 因子 | 总拷贝次数(N次push) | 内存复用 |
|---|---|---|---|
| GCC/Clang | 2.0 | ≈ 2N | ❌ |
| MSVC | 1.5 | ≈ 3N | ✅ |
迭代器失效速查：
| 操作 | 是否扩容 | 失效范围 |
|---|---|---|
| push_back 不扩容 | ❌ | end() 以前所有有效 |
| push_back 扩容 | ✅ | 全部失效 |
| insert | 是/否 | 插入点及之后 |
| erase | — | 删除点及之后 |
| pop_back | — | 仅 end() 前一个 |
emplace_back vs push_back：
| 方式 | 临时对象 | 适用 |
|---|---|---|
push_back(const T&) | 1 (调用方) | 已有 const ref |
push_back(T&&) | 1 (调用方) | 已有可移动对象 |
emplace_back(args...) | 0 | 直接传构造参数 |
下一篇：vector 的连续内存扩容说清了。下一篇进入 33.deque 分段连续设计——deque 的 map+chunk 两级结构、为什么 deque 有 O(1) 随机访问却不是真正的连续内存、front/back O(1) 插入的妙处、为什么 stack/queue 默认用 deque 而不是 vector。
