size, capacity, and that factor of 2

1 · Three numbers, one sentence

The order runs: growth factor is policy → capacity is the consequence of that policy → size is your own data. capacity >= size holds at every instant.

2 · Play with it: what happens on each push

The demo below is a visualisation of that C++ program. Blue cells = size (elements that really exist), grey cells inside the dashed box = the unused part of capacity (land bought but not built on). When a reallocation happens, the cells highlighted in orange are exactly what moved counts — each one has to be relocated to the new memory.

3 · What moved is actually counting

Reallocation is not “growing the existing block in place” — that is impossible, the memory next door may already belong to someone else. What really happens is three steps:

1. allocate a larger block somewhere else
2. relocate [every element that already exists] one by one   <- this is what moved counts
3. destroy the old elements and return the old block to the system

So moved always equals the size at that moment. The cap 512→1024 step relocated 512 elements; across 1000 pushes the running total is 1023.

4 · Amortized O(1): deriving it

“Amortized” does not mean “every call is O(1)”. It means: the average cost per call once the occasional expensive operation is spread across the many cheap ones. For push_back:

The derivation

Reallocation only happens at capacities 1, 2, 4, 8… and the number of elements relocated each time is exactly the capacity at that moment. So the total number of relocations over the whole process is a geometric series:

total moves = 1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) - 1

since the largest capacity reached never exceeds 2N, we have 2^k <= N, hence

total moves = 2 * 2^k - 1 <= 2N - 1 < 2N

average relocation cost per push_back < 2N / N = 2 = O(1)   QED

That constant actually oscillates between 1 and 2

The proof above bounds it below 2, but the exact value depends on where N falls between two powers of two:

Look at rows 2 and 3: going from N=513 to N=1024 adds not a single relocation (both are 1023), but the denominator doubles, so the ratio drops from 1.994 to 0.999. That is why the ratio swings back and forth — total relocations jump only at the moment of a reallocation, while N grows continuously.

5 · Why 2 — the standard never said so

First separate two things; this distinction is itself an interview question:

language standard      C++17    <- this is what -std=c++17 controls
standard library impl  libc++   <- the growth factor of 2 is decided [here]

Swap -std=c++17 for -std=c++20 and the factor is still 2. Only swapping the standard library changes it:

The standard specifies exactly one thing, but it is a powerful one

The standard requires push_back to be amortized O(1). That single sentence forces growth to be multiplicative:

total moves ~= n / (g - 1)

g = 2    -> about n moves     (you measured 1023 for n = 1000)
g = 1.5  -> about 2n moves
g = 1    -> denominator is 0, the formula collapses
            -> the real answer is n(n-1)/2 = O(n^2)

As long as g is a constant greater than 1, the total is O(n). So “multiply” has a hard mathematical reason behind it; “multiply by 2” does not — 2, 1.5 and 1.1 all satisfy O(1).

So what separates 2 from 1.5

larger g -> fewer reallocations, fewer copies -> but more idle memory (g=2 wastes up to 50%)
smaller g -> less idle memory                 -> but more copying (g=1.5 totals 2n moves, not n)

The “wasted” readout in the demo above tells you this live: right after a reallocation, g=2 leaves half the land empty, while g=1.5 leaves only a third.

6 · The numbers measured tonight

Verify ① — capacity_growth.cpp

Verify ② — reserve_bench.cpp (10⁷ push_backs)

Only 1.78× is the right answer, not a failed experiment. Relocating an int is just a memcpy and therefore very cheap, so what reserve mainly saves is the other half: the repeated allocate/free round trips to the system. Use a type whose copy allocates memory of its own and the gap gets far larger — which is exactly what the Buffer class on Saturday of Week 2 is there to demonstrate. Being able to explain that 1.78 is worth more than remembering it.

7 · reserve: if you know the upper bound, buy the land up front

The core idea in one sentence: if you know in advance how many elements you will store at most, call reserve first, so that size never runs into capacity and not a single reallocation happens — which saves both the repeated trips to the allocator and the relocation of existing elements.

That is correct. The four details below were all measured, and every one of them is a plausible follow-up:

① reserve(n) gives you exactly n, not the next power of two

reserve(1000)  ->  size = 0,  capacity = 1000

1000, not 1024. After a reserve, capacity is entirely yours to dictate; the geometric growth rules do not participate at that point.

② reserve can only grow, never shrink

capacity is already 1000, then reserve(10)  ->  capacity is still 1000

Its meaning is “at least this big”, not “set it to this”. Returning the surplus requires shrink_to_fit(), and even then the standard treats it as merely a request — an implementation is free to ignore you.

③ Guessing low is not a disaster: it continues ×2 from the number you set

reserve(10), then push 40 elements  ->  capacity: 10 -> 20 -> 40

It does not fall back to 1, 2, 4, 8 and start over. Geometric growth continues from the starting point you gave, so guessing low merely means “you saved less”, never something worse.

④ The third benefit: pointers and iterators stay valid

This one is not about performance, it is about correctness, and it is the only part missing from the summary above:

reserved enough  ->  &v[0] is unchanged throughout     pointer still valid
not reserved     ->  0x...1a0 becomes 0x...350         dangling pointer -> UB

As long as no reallocation occurs, pointers, references and iterators to elements stay valid. In code that pushes into a vector while holding a pointer to one of its elements, this is a hard requirement that has nothing to do with speed. (Wednesday's warm-up will use ASan to catch exactly this bug in the act.)

8 · push_back vs emplace_back

push_back — the key words are “one” and “finished”

• Exactly one parameter slot. v.push_back(1, 2) fails to compile outright: no matching member function.
• When what you hand it is not a T, the compiler tries to implicitly convert one into existence — that is a temporary object, and it is not free.
• explicit forbids precisely that implicit conversion. Add it and you are forced to write the construction at the call site.

emplace_back — the key word is “construct”, and explicit is irrelevant

• Any number of parameters — they are the constructor's arguments, forwarded verbatim into the container.
• Internally it performs ::new (ptr) T(args...), i.e. direct-initialization.
• Which is why it reaches the constructor either way — because there is no “conversion” here at all, only “construction”. explicit governs conversions.

Measured call counts across four scenarios

So “emplace_back is faster” is false as a general statement. The accurate version: it only saves anything when it can avoid a temporary.

Why explicit stops one and not the other

vector<Person>          emplace_back(30)         compiles -> harmless (guard against a slip)
vector<regex>           emplace_back(nullptr)    compiles -> silent UB
vector<unique_ptr<int>> emplace_back(new int(5)) compiles -> leaks if it throws

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 · Telling apart: four pairs that get confused

v.reserve(100);
v[0] = 1;        // <- out-of-bounds write, UB

10 · How to answer it in an interview

Asked “What happens when you push_back into a vector that is at capacity?”, deliver all of this inside 60 seconds, then stop talking and wait for the follow-up:

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.

Asked “Why 2?” — do not just answer “2”. The right shape is:

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.

That answer proves three things at once: you know what the standard does and does not govern, you ran it yourself, and you know this is a trade-off, not a theorem.