size、capacity,和那个 2

1 · 三个数,一句话

顺序是:growth factor 是政策 → capacity 是政策产生的结果 → size 是你自己的数据。 capacity >= size 任何时刻都成立。

2 · 动手玩:每按一次 push 会发生什么

下面这个演示就是你那个 C++ 程序的可视化版。蓝格子 = size(真实存在的元素), 虚线框内的灰格子 = capacity 里空着的部分(买了但没用的地)。 扩容发生时,被橙色高亮的那些格子就是 moved —— 它们要被逐个搬到新内存去。

3 · moved 到底在数什么

扩容不是「把原地那块地变大」—— 做不到,旁边可能早被别人占了。真实动作是三步:

① 在别处申请一块更大的内存
② 把老地方【已有的每一个元素】逐个搬过去   ← moved 数的就是这一步
③ 销毁老元素、把老内存还给系统

所以 moved 永远等于那一刻的 size。 cap 512→1024 那次搬了 512 个;1000 次 push 全程累计 1023 次。

4 · 均摊 O(1):把它算出来

「均摊」(amortized)不是「每次都是 O(1)」,而是: 把偶发的昂贵操作分摊到大量便宜操作上之后,平均单次的成本。 对 push_back 来说:

推导

扩容只发生在容量为 1、2、4、8… 的时刻,每次搬运的元素个数正好等于当时的容量。 所以整个过程的总搬运次数是一个几何级数:

总搬运 = 1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) − 1

因为扩容到的最大容量不会超过 2N,有 2^k ≤ N,于是

总搬运 = 2·2^k − 1 ≤ 2N − 1 < 2N

平均每次 push_back 的搬运成本 < 2N / N = 2 = O(1)   ∎

那个常数其实在 1 和 2 之间摆动

上面证明了它 < 2,但具体是多少取决于 N 落在两个 2 的幂之间的哪个位置:

看第 2、3 行:N 从 513 变成 1024,总搬运一个都没多(都是 1023), 但分母翻了一倍,比值就从 1.994 掉到 0.999。这解释了为什么比值会来回摆 —— 搬运总量只在扩容那一刻跳一次,而 N 是连续在长。

5 · 为什么是 2 —— 标准没规定过

先把两个东西分开,这一条本身就是面试题:

语言标准   C++17      ← -std=c++17 控制的是这个
标准库实现 libc++     ← 增长因子 2 是【这里】定的

把 -std=c++17 换成 -std=c++20,因子还是 2。 换一个标准库才会变:

标准只规定了一件事,但那一件事很有力

标准要求 push_back 是 amortized O(1)。这句话逼出了「必须按倍数长」:

总搬运次数 ≈ n / (g - 1)

g = 2    → 约 n 次      （你实测 1023,n = 1000）
g = 1.5  → 约 2n 次
g = 1    → 分母是 0,公式塌掉 → 真实答案 n(n-1)/2 = O(n²)

只要 g 是大于 1 的常数,总量就是 O(n)。所以「乘法」有数学硬理由, 「乘 2」没有 —— 2、1.5、1.1 都满足 O(1)。

那 2 和 1.5 差在哪

g 大 → 扩容少、拷贝少 → 但空着的内存多（g=2 最坏浪费 50%）
g 小 → 空着的内存少   → 但拷贝多（g=1.5 总搬运是 2n,不是 n）

上面演示里的「浪费」那一行会实时告诉你这件事:刚扩完容那一刻, g=2 有一半的地是空的,g=1.5 只空三分之一。

6 · 今晚实测到的数

Verify ① — capacity_growth.cpp

Verify ② — reserve_bench.cpp(10⁷ 次 push_back)

只快 1.78× 是正确答案,不是实验失败。 int 的搬运就是 memcpy, 非常便宜,所以 reserve 主要省掉的是反复向系统申请/释放内存那一半。 换成一个「拷贝会自己再分配内存」的类型,差距会大得多 —— 那正是 Week 2 周六 Buffer 类要演示的事。能解释这个 1.78 比记住它值钱。

7 · reserve:已知上限就先把地买够

核心理解一句话:如果事先知道最多会放多少个元素,就先 reserve, 这样 size 永远撞不到 capacity,扩容一次都不会发生 —— 既省掉反复向系统申请内存,也省掉搬运已有元素。

这是对的。下面四条是实测出来的细节,每一条都能被追问到:

① reserve(n) 给的是精确值,不会向上取整到 2 的幂

reserve(1000)  →  size = 0,  capacity = 1000

是 1000,不是 1024。reserve 之后 capacity 完全由你说了算, 几何增长那套规矩这时候不参与。

② reserve 只能变大,不能变小

capacity 已经是 1000,再 reserve(10)  →  capacity 仍然是 1000

它的语义是「至少要这么大」,不是「设成这么大」。 想把多余的地还回去得用 shrink_to_fit(), 而且标准只把它当作一个请求 —— 实现可以完全不理你。

③ 估小了不是灾难:从你设的那个数接着 ×2

reserve(10),然后 push 40 个  →  capacity: 10 → 20 → 40

不是退回 1、2、4、8 重来。几何增长从你给的起点继续走, 所以估小了只是「少省了一部分」,不会更糟。

④ 第三个好处:指针和迭代器不会失效

这一条不是性能,是正确性,也是你上面那段理解里唯一没提到的:

reserve 够   →  &v[0] 前后一致                     指针依然有效
不 reserve   →  0x...1a0  变成  0x...350            指针悬空 → UB

只要不发生扩容,指向元素的指针 / 引用 / 迭代器就一直有效。 在「一边往 vector 里加东西、一边握着某个元素的指针」的代码里,这是硬需求, 跟快慢无关。(周三的热身会专门用 ASan 把这个 bug 抓出来看。)

8 · push_back vs emplace_back

push_back — 重点是「一个」「成品」

• 参数位只有一个。v.push_back(1, 2) 直接编译报错: no matching member function。
• 你给的东西不是 T 时,编译器会试着隐式转换出一个 T —— 那是一个临时对象,不是免费的。
• explicit 禁止的正是这次隐式转换。加了它,你就必须把构造写在调用点上。

emplace_back — 重点是「构造」,与 explicit 无关

• 参数任意个 —— 它们就是构造函数的实参,被原样转发进容器内部。
• 内部执行的是 ::new (ptr) T(args...),即直接初始化 (direct-initialization)。
• 所以 explicit 与否都调得到 —— 因为这里根本没有「转换」,只有「构造」。explicit 管的是转换。

四个场景的实测调用次数

所以「emplace_back 更快」作为一般说法是假的。 准确说法:它只在「能避免临时对象」时更省。

explicit 为什么拦得住一个、拦不住另一个

vector<Person>          emplace_back(30)         能编过 → 无害(只是防手滑的转换)
vector<regex>           emplace_back(nullptr)    能编过 → 静默 UB
vector<unique_ptr<int>> emplace_back(new int(5)) 能编过 → 抛异常就泄漏

push_back takes an already-constructed object and copies or moves it in. emplace_back forwards the constructor arguments and builds the element in place, so it avoids a temporary when you're building from raw arguments. If you pass an object that already exists, the two are identical. And emplace_back uses direct-initialization, so it can reach explicit constructors that push_back would reject — slightly faster in one case, but you lose a compile-time check.

9 · 区分:四组容易混的东西

v.reserve(100);
v[0] = 1;        // ← 越界写入,UB

10 · 面试怎么答

被问 "What happens when you push_back into a vector that is at capacity?", 60 秒内给完这些,然后闭嘴等追问:

It allocates a larger buffer, moves the existing elements over, destroys the old ones and frees the old block. The growth is geometric — I measured a factor of 2 on libc++. That's what makes push_back amortized O(1): a single push can be O(n), but reallocation only happens about log n times, so the total work over n pushes stays O(n) — I measured 1023 element moves for 1000 pushes, about one move per element. All iterators, pointers and references into the old buffer are invalidated.

被问 "Why 2?" —— 不要直接答 2。正确的形状是:

The standard doesn't specify it — it only requires amortized O(1), which forces geometric growth. The factor itself is a library choice: libc++ and libstdc++ use 2, MSVC uses 1.5. I measured 2 on my machine. It's a trade-off — a larger factor means fewer copies but up to 50% wasted memory, and there's an argument that a factor below the golden ratio lets the allocator reuse freed blocks, which 2 never can.

这个答案同时证明三件事:你知道标准管什么不管什么、你跑过、 你知道这是权衡不是定理。