std::vector 扩容机制详解（libc++ 源码导读）

基于 macOS / Xcode 自带 libc++ 源码：
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/v1/

目录

1. 为什么需要扩容
2. 内存模型：三个指针
3. 触发条件：快路径与慢路径
4. 扩容第一步：__recommend 决定新容量
5. 扩容第二步：在新内存上构造
6. 扩容第三步：__swap_out_circular_buffer 搬迁并交换
7. 扩容第四步：旧块自动释放（RAII）
8. 搬迁路径的三种特化：memcpy / move / copy
9. 强异常安全保证
10. __allocate_at_least：实际容量可能大于 2 倍
11. 各标准库的扩容策略对比
12. 为什么 2 倍是均摊 O(1)
13. 1.5 倍的来历与取舍
14. 实验验证
15. 工程实践建议

---

1. 为什么需要扩容

std::vector 承诺：

• 元素连续存储；
• operator[]、at() 是 O(1)；
• push_back 均摊 O(1)；
• 任意位置 insert/erase 是 O(n)。

连续存储 + O(1) 随机访问，意味着底层只能是一块固定大小的连续内存。但元素数量是动态的，标准库无法预知未来要多少空间，所以只能：

先用一块较大的内存，用完时申请一块更大的、把旧数据搬过去、释放旧内存。

这个"申请更大的 + 搬迁"就是扩容（reallocation）。它的存在是 vector 高性能的基础，也是所有指针/迭代器失效问题的根源。

---

2. 内存模型：三个指针

libc++ 的 vector 内部只有三个指针（位于 __vector/vector.h 的 __vector_base）：

相关计算：

• size() = __end_ - __begin_
• capacity() = __cap_ - __begin_
• 区间 [__begin_, __end_) 里是活的、已构造的对象；
• 区间 [__end_, __cap_) 里只是裸内存，不是对象。

这点非常重要：正因为后一段不是对象，标准库才能用 __construct / __destroy 直接在那块内存上就地构造新元素，push_back 平时才不需要做任何搬运。

由于 [end, cap) 里的内存不是对象，扩容不能用 realloc —— realloc 不懂 C++ 的构造/析构语义（例如 std::string 的 SSO 缓冲区是对象内部指针，整体 memmove 会破坏它，除非类型是 trivially relocatable）。

---

3. 触发条件：快路径与慢路径

emplace_back 本体（__vector/vector.h:1144）：

pointer __end = this->__end_;
if (__end < this->__cap_) {              // 快路径：还有空间
  __emplace_back_assume_capacity(std::forward<_Args>(__args)...);
  ++__end;
} else {
  __end = __emplace_back_slow_path(std::forward<_Args>(__args)...);  // 慢路径：扩容
}
this->__end_ = __end;

push_back 只是 emplace_back 的一层转发（vector.h:455-457）。

结论：只有当 size() == capacity() 时才真正扩容。 平时的 push_back 只是"在未初始化内存上构造一个对象 + end 指针自增"，不搬运任何已有元素。这正是看源码时"到处找不到扩容代码"的原因：扩容逻辑分散在 __recommend 和 __split_buffer 里，而且只在容量耗尽时才被调用。

---

4. 扩容第一步：__recommend 决定新容量

__vector/vector.h:898-908：

//  Precondition:  __new_size > capacity()
template <class _Tp, class _Allocator>
size_type vector<_Tp, _Allocator>::__recommend(size_type __new_size) const {
  const size_type __ms = max_size();
  if (__new_size > __ms)
    this->__throw_length_error();
  const size_type __cap = capacity();
  if (__cap >= __ms / 2)
    return __ms;
  return std::max<size_type>(2 * __cap, __new_size);
}

关键点

• 参数语义：__new_size 是"至少需要多大"，不是"增长多少"。
  • push_back 传 size() + 1；
  • insert 一次插入 n 个传 size() + n，所以一次插入一大段时一次扩容到位，不会反复扩容。
• 公式：新容量 = max(2 * 当前容量, 需要的大小)。
  • 连续单元素 push_back 时：1 → 2 → 4 → 8 → 16 → …，严格 2 倍；
  • 一次插入很多时：直接取需求值（若它更大）。
• 溢出保护：if (__cap >= __ms / 2) return __ms;
  • 若 cap 已超过 max_size()/2，2 * cap 会整数溢出回绕成很小的值，导致分配过小、后续越界写。这类整数溢出是容器实现里真实存在过的安全漏洞。
• max_size() 的取值：通常是 PTRDIFF_MAX / sizeof(T)，而不是 SIZE_MAX / sizeof(T)。因为标准要求两个元素指针之差能用 ptrdiff_t 表示。

谁调用 __recommend

接口	位置	传入参数
__append(n)	vector.h:957	size() + n
__append(n, x)	vector.h:972	size() + n
resize / assign(count)	vector.h:1074, 1090	新尺寸
__emplace_back_slow_path	vector.h:1128	size() + 1
insert（各重载）	vector.h:1210, 1229, 1250, 1278, 1349	size() + n

注意 reserve 不走 __recommend（vector.h:1096-1103），它直接用你给的值：

void vector::reserve(size_type __n) {
  if (__n > capacity()) {
    if (__n > max_size()) this->__throw_length_error();
    __split_buffer<value_type, allocator_type&> __v(__n, size(), this->__alloc_);
    __swap_out_circular_buffer(__v);
  }
}

同理 shrink_to_fit 也直接给 size()。

---

5. 扩容第二步：在新内存上构造

__emplace_back_slow_path（vector.h:1124-1134）：

template <class... _Args>
pointer vector::__emplace_back_slow_path(_Args&&... __args) {
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), this->__alloc_);
  __alloc_traits::construct(this->__alloc_, std::__to_address(__v.__end_),
                            std::forward<_Args>(__args)...);
  __v.__end_++;
  __swap_out_circular_buffer(__v);
  return this->__end_;
}

__split_buffer 构造函数签名为 __split_buffer(cap, start, alloc)：

• cap：申请多少个元素的空间；
• start：begin_ 和 end_ 初始时放在块内的偏移，即前端预留多少槽位。

这里传 start = size()，意味着旧元素会被搬进新块的后半部分，前面留下 size() 个空槽。为什么这么设计？见下一节。

新元素先于旧元素构造，放在 __v.__end_ 处（此时它恰好位于块尾），这样后面搬迁旧元素时不会覆盖它。

---

6. 扩容第三步：__swap_out_circular_buffer 搬迁并交换

__vector/vector.h:837-854：

// __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v
// and swaps the buffers of *this and __v. It is assumed that __v provides space for exactly
// (__end_ - __begin_) objects in the front. This function has a strong exception guarantee.
void vector::__swap_out_circular_buffer(__split_buffer& __v) {
  __annotate_delete();                                   // ASan 注解
  auto __new_begin = __v.__begin_ - (__end_ - __begin_); // 旧元素要搬到的起点
  std::__uninitialized_allocator_relocate(
      this->__alloc_, std::__to_address(__begin_), std::__to_address(__end_),
      std::__to_address(__new_begin));
  __v.__begin_ = __new_begin;
  __end_       = __begin_;   // 旧块里的对象已被 relocate "销毁"
  std::swap(this->__begin_, __v.__begin_);
  std::swap(this->__end_,   __v.__end_);
  std::swap(this->__cap_,   __v.__cap_);
  __v.__first_ = __v.__begin_;
  __annotate_new(size());
}

函数名里的 “circular” 是什么意思

新块里，旧元素被放在后部，前面留出的 size() 个槽位是给新元素（insert 场景）或空着（push_back 场景）的。看起来像是把旧数据"绕一圈"放进新块，所以叫 circular buffer。

对 insert 的一次深层理解：insert(pos, x) 走的是带 __p 参数的重载版本（vector.h:862），它把 [begin, pos) 搬到新块前部、[pos, end) 搬到新块后部，中间留一个洞给新元素——一次搬迁就能完成任意位置插入，无需二次搬移。这就是 start = size() 设计的价值。

relocate 与 move_if_noexcept

搬迁不是简单的 std::copy、也不是普通的 std::move，而是调用 __uninitialized_allocator_relocate，内部使用 move_if_noexcept：

construct(__alloc, __result, std::move_if_noexcept(*__iter));

• 元素的移动构造是 noexcept → 移动；
• 移动构造可能抛异常、但拷贝构造可用 → 拷贝；
• 两者都不行 → 移动（标准要求 move-only 类型也必须能工作，此时异常安全退化为基本保证）。

---

7. 扩容第四步：旧块自动释放（RAII）

__split_buffer 的析构（__split_buffer:338-343）：

~__split_buffer() {
  clear();
  if (__first_)
    __alloc_traits::deallocate(__alloc_, __first_, capacity());
}

swap 之后：

• this 拿到了新块的 begin_/end_/cap_；
• 局部对象 __v 持有旧块的所有权；
• 函数返回时 __v 析构，旧内存自动归还给分配器。

这就是 RAII 支撑异常安全的标准手法：扩容过程中任何一步抛异常，__v 都会释放已分配的新内存，原 vector 完全不受影响。

---

8. 搬迁路径的三种特化：memcpy / move / copy

__memory/uninitialized_algorithms.h:612-641：

template <class _Alloc, class _ContiguousIterator>
void __uninitialized_allocator_relocate(
    _Alloc& __alloc, _ContiguousIterator __first, _ContiguousIterator __last,
    _ContiguousIterator __result) {
  if (__libcpp_is_constant_evaluated() ||
      !__libcpp_is_trivially_relocatable<_ValueType>::value ||
      !__allocator_has_trivial_move_construct_v<_Alloc, _ValueType> ||
      !__allocator_has_trivial_destroy_v<_Alloc, _ValueType>) {
    // 通用路径：逐元素 move_if_noexcept + 析构
    auto __iter = __first;
    while (__iter != __last) {
      construct(__alloc, __result, std::move_if_noexcept(*__iter));
      ++__iter; ++__result;
    }
    std::__allocator_destroy(__alloc, __first, __last);
  } else {
    // 特化路径：trivially relocatable，直接 memcpy！
    __builtin_memcpy(std::__to_address(__result), std::__to_address(__first),
                     sizeof(_ValueType) * (__last - __first));
  }
}

这是整块知识里性能差距最大的地方：

三类类型在扩容时的实际行为

元素类型	扩容时的处理	复杂度
int、double、char*、POD 结构体	memcpy，不调用任何构造函数	最快
std::pair<int,int>、std::array<T,N>（若成员平凡）	memcpy	最快
std::string	逐元素移动（SSO 的小字符串有自引用，不能 memcpy）	每元素一次移动
std::unique_ptr<T>	逐元素移动（移动后置空）	每元素一次指针搬移
std::shared_ptr<T>	逐元素移动 + 原子引用计数加减	最慢之一
自定义类型，移动构造未标 noexcept 但可拷贝	逐元素拷贝	慢，且无预期

engineering takeaway：给自定义类型的移动构造加 noexcept，是让 vector 不下意识退化成拷贝的最简单手段。（实验 3 中有实测对比。）

命名空间中的 trivially_relocatable

注意 libc++ 内部判断的是内部概念 __libcpp_is_trivially_relocatable，它比"trivially copyable"更强，但比"trivially copyable"更弱：例如一个具有非平凡默认构造函数但所有拷贝/移动/析构都平凡的类型，也可能被判定为 relocatable。这个内部概念是为了将来标准化 P1144 std::relocatable 做的铺垫。

---

9. 强异常安全保证

__swap_out_circular_buffer 在 move_if_noexcept 的前提下能提供强异常安全（strong exception guarantee）：扩容失败时，vector 保持扩容前的状态。

完整时序：

下面是分阶段抛异常的结果：

抛异常位置	结果
allocate_at_least 失败（OOM）	原 vector 不变，抛 bad_alloc
新元素构造失败	原 vector 不变，新块释放
relocate 中途中止（任何异常）	新块中已拷贝/已移动的元素被逆序析构，原 vector 不变

注意：从 C++11 起，标准只要求 push_back 在"元素 move 构造不抛异常，或者类型可拷贝"时提供强保证；否则只保证基本保证（容器有效，但内容可能已改变）。

---

10. __allocate_at_least：实际容量可能大于 2 倍

__memory/allocate_at_least.h:25：

[[nodiscard]] constexpr auto __allocate_at_least(_Alloc& __alloc, size_t __n) {
  return std::allocator_traits<_Alloc>::allocate_at_least(__alloc, __n);
}

C++23 起 allocator_traits::allocate_at_least 允许分配器返回至少 n 个（可能更多）。典型场景：某些分配器（slab / 页对齐的）在满足 n 的同时会顺带给出额外空间。

因此在自定义分配器的环境下：

• __recommend 给出的只是下限请求；
• capacity() 实测可能大于 2 * old_cap。

而在标准 std::allocator 下，allocate_at_least 会退化为 {__alloc.allocate(__n), __n}，也就是恰好 n 个——这就是为什么你用 std::allocator 观察到的容量是严格的 2 的幂。

---

11. 各标准库的扩容策略对比

实现	公式	实际增长倍数	备注
libc++（Clang / Apple）	max(2 * cap, need)	严格 2 倍	本机实现
libstdc++（GCC）	size() + max(size(), n)	接近 2 倍，通常略小于 2	bits/stl_vector.h 的 _M_check_len
MSVC（VS2017+）	old + old/2，下限 old + max(old, n)	约 1.5 倍	_Calculate_growth
folly::fbvector	max(1.5 * cap, need)	1.5 倍	主动选择，为了内存复用

---

12. 为什么 2 倍是均摊 O(1)

把 n 次 push_back 的真实开销加起来（按 2 倍策略、模拟初始容量为 1）：

• 第 1 次扩容（1 → 2）：搬 1 个元素
• 第 2 次扩容（2 → 4）：搬 2 个元素
• 第 3 次扩容（4 → 8）：搬 4 个元素
• …
• 最后一次扩容：搬 n/2 个元素

总搬迁量 = 1 + 2 + 4 + … + n/2 < n。

所以 n 次 push_back 总计 O(n)，均摊到每次是 O(1)。

前提是增长因子 > 1（任何常数倍都满足）。增长因子为 2 和 1.5 都满足，代价不同而已：

• 因子 r，扩容总次数 = log_r(n)；
• 总搬迁量 = n * (1 + 1/r + 1/r² + …) = n * r/(r-1)。

增长因子 r	扩容次数（n=10⁹）	总搬迁量系数
1.5	≈ 51	3.0
2.0	≈ 30	2.0
1.618（φ）	≈ 43	2.618

从这个角度看，2 倍反而更省搬迁总量。1.5 倍的优势不在摊销成本，而在内存复用（见下节）。

---

13. 1.5 倍的来历与取舍

2 倍增长的内存碎片问题

经典场景（以 jemalloc 之类的小对象分配器为例）：

更一般地：

• 增长因子 r ≥ 2：下一次所需 r·c ≥ 2c，而释放的旧块只有 c，即使相邻全空也拼不出来（除非能和其他空闲块合并）；
• 增长因子 1 < r < 2：下一次所需 r·c < 2c，有机会由"旧块 c + 相邻空闲块"拼接出，地址可以原地长大。

1.5 倍是经验值：既满足 r < 2，又让容量翻倍成本不太高。

结论

• 1.5 倍不是任何主流标准库的严格实现值。MSVC 的 old + old/2 在下限 old + max(old, n) 作用下，小数据时更接近 2 倍。
• 中文资料里的"1.5 倍"多数指的是 MSVC 的 _Calculate_growth，也有从 folly::fbvector 的"内存复用"设计引用而来。
• 1.618（黄金比例 φ）常见于某些文章，主流实现都没有使用。

---

14. 实验验证

程序用 Clang / libc++ 编译（macOS 默认）：

实验 1：capacity 跳变与地址漂移

step   size     capacity   oldptr           newptr
1      1        1          首次分配        0x105001c10
2      2        2           扩容          0x105001c20
3      3        4           扩容          0x105001c10
5      5        8           扩容          0x105001c20
9      9        16          扩容          0x105001aa0
...
513    513      1024        扩容          0x9cac04000
1025   1025     2048        扩容          0x1050030a0

观察要点：

1. 容量严格 1, 2, 4, 8, 16, … 翻倍（与 __recommend 的 2 * cap 一致）；
2. 地址会周期性复用（如第 1 次和 3 次都落在 0x105001c10），说明分配器会回收旧块；但并不是每次都原地长大。

实验 2：__recommend 公式的直接验证

• push_back 单元素：0→1→2→4→8→16（2 倍）；
• insert 一次插 100 个（size=4）：4 → 104，一次到位（max(2*4, 4+100) = 104）；
• reserve(300)：100 → 300，不乘 2；
• resize(120)：100 → 200（max(200, 120) = 200）。

实验 3：relocate 路径选择

is_trivially_copyable<int> = true
TrivialCounter(noexcept move) moved=63    copied=0     (逐元素 noexcept move)
NonTrivialCounter(含 string) moved=63    copied=0      (逐元素 move)
ThrowingMoveCounter(move 非 noexcept) moved=0     copied=63     (退化为拷贝)

观察要点：

1. 移动构造标 noexcept → relocate 用 move；
2. 移动构造未标 noexcept 且可拷贝 → relocate 退化为 copy（63 次拷贝，0 次移动）；
3. int 这类平凡类型因为"没有构造函数可计数"，计数器为 0——它们走的是 memcpy 特化，压根没调用构造函数。可以用 -fsanitize=address 在 -O0 下验证 std::vector<int> 扩容过程无 ASan 报错。

实验 4：指针/迭代器失效

扩容前 data()=0x105001c10  p=0x105001c10  size=4 cap=4
扩容后 data()=0x105001c20  p=0x105001c10  (p 已悬空)

p 指向的旧块已经被释放（或将被释放），继续解引用是 use-after-free。

实验 5：reserve 的价值

无 reserve    扩容次数=21   最终容量=1048576
有 reserve    扩容次数=1    最终容量=1000000

100 万次 push_back，无 reserve 时扩容 21 次、搬迁约 100 万个元素；
有 reserve 时扩容 1 次、不搬迁。

如果事先知道元素数量，reserve 是性价比最高的优化。

---

15. 工程实践建议

1. 能 reserve 就 reserve：已知数量时（如 fread 读文件、遍历数组一次构建），能省掉所有扩容和搬迁。
2. 给移动构造加 noexcept：否则扩容时会退化成拷贝，且可能失去强异常安全保证。
3. 少在性能敏感路径用 vector<shared_ptr>：每次扩容都有原子引用计数的开销。可考虑 vector<unique_ptr> 或 vector<T> 直接存值。
4. 注意扩容带来的失效：push_back 可能使所有迭代器/指针/引用失效。循环中 push_back 时不要缓存 &v[i]。
5. shrink_to_fit 不保证释放：它是非绑定请求（non-binding），由实现决定。
6. resize 与 reserve 的区别：resize 改变 size()（构造/析构元素），reserve 只改变 capacity()（不构造元素）。
7. 不要用 capacity() 推断 size()：扩容公式是实现定义的，跨平台/跨编译器结果不同。
8. 理解"摊销"的本质：频繁 push_back 是 O(1) 均摊，但单次扩容的延迟尖峰是 O(n)。实时系统中如果有延迟要求，要提前 reserve。