vector Growth, capacity and reserve

Part I · Module 19 · Chapter 19.3 · vector Growth, capacity and reserve

1. Two Numbers, Not One

A std::vector tracks two counts, and the whole chapter follows from keeping them apart.

size() is the number of elements that exist. Those are real, constructed objects; you may read them, write them, and iterate over them.

capacity() is how many elements the currently allocated block could hold. The difference between capacity and size is allocated memory holding nothing — raw storage, no objects in it.

The invariant is size() <= capacity(). When they are equal the vector is full, and the next insertion cannot write into the existing block because there is nowhere in it to write. That is the moment this chapter is about.

What happens then is fixed: the vector asks the allocator for a bigger block, moves or copies every existing element into it, destroys the originals, frees the old block, and then appends the new element. §3 counts every part of that.

A third member, max_size(), reports the largest size the implementation could ever support. It is a large number and it is not useful; ignore it.

2. The Capacity Sequence

The standard does not specify how much a vector grows by. It requires only that push_back be amortised O(1), which — as §5 shows — forces growth by a constant factor rather than a constant amount, but leaves the factor to the implementation. So the factor is a measurement, not a fact to be recited.

std::vector<int> v;
std::size_t last = v.capacity();
std::printf("%zu", last);
for (int i = 0; i < 1000; ++i) {
    v.push_back(i);
    if (v.capacity() != last) { last = v.capacity(); std::printf(" -> %zu", last); }
}

0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> 512 -> 1024

Twelve distinct capacities on the way to a thousand elements, each exactly twice the previous. This implementation — libc++, the library that ships with Apple clang — uses a growth factor of 2. An empty vector has capacity 0 and has made no allocation, which is worth knowing: a default-constructed std::vector is free.

Other implementations differ. Microsoft's STL uses 1.5, and the argument for a factor below 2 is that freed blocks can be reused by later allocations, whereas doubling always asks for more than the sum of everything freed so far. Both satisfy the standard. If your reasoning depends on the number, measure it on your implementation rather than quoting this chapter's.

The reason the factor matters at all is §5.

3. Counting the Element Moves

The capacity sequence tells you how many reallocations happen. It does not tell you what they cost, and for that the element type has to report on itself:

struct Tracked {
    int v = 0;
    static std::size_t ctor, copy, move, dtor;
    Tracked() { ctor++; }
    explicit Tracked(int x) : v(x) { ctor++; }
    Tracked(const Tracked& o) : v(o.v) { copy++; }
    Tracked(Tracked&& o) noexcept : v(o.v) { move++; }
    ~Tracked() { dtor++; }
};

A thousand emplace_back calls, with and without reserve:

1000 emplace_back, no reserve   ctor=1000 copy=0 move=1023 dtor=2023
1000 emplace_back, reserved     ctor=1000 copy=0 move=0    dtor=1000

1,023 moves to build a 1,000-element vector. The number is not arbitrary: it is 1 + 2 + 4 + 8 + … + 512, the sum of the capacities that were abandoned, because every reallocation moves every element already present. The final doubling alone moved 512 elements. And dtor=2023 is 1000 + 1023: every moved-from original had to be destroyed.

With reserve(1000) in front, the figures are move=0 and dtor=1000. No element is ever relocated, because the block it was constructed in is the block it stays in.

copy=0 in both rows is the second thing in that output, and it is Chapter 13.8 §7's noexcept mechanism doing its job. Tracked's move constructor is marked noexcept, so the library is willing to move the existing elements during reallocation. Had it not been, the library would have had to copy them — because if a move threw half-way through, the elements already moved out of the old block could not be put back, and push_back's strong exception guarantee would be broken. A single reallocation confirms the choice:

at the reallocation: moves +4, copies +0  (4 existing elements)

For an int this is a distinction without a cost. For a type that owns a heap buffer it is the difference between relocating a pointer and duplicating the buffer, which is why marking your move operations noexcept is not a micro-optimisation when the type is going into a vector.

4. Counting the Allocations and the Bytes

n=100    grown:  8 allocs /   1020 bytes    reserved: 1 alloc /   400 bytes
n=1000   grown: 11 allocs /   8188 bytes    reserved: 1 alloc /  4000 bytes
n=10000  grown: 15 allocs / 131068 bytes    reserved: 1 alloc / 40000 bytes

Three observations, and the third is the one people miss.

The allocation count grows logarithmically. Eight, eleven, fifteen for a hundredfold increase in elements — because the count is the number of doublings, which is log2(n). This is the amortisation working, and it is why the unreserved path is not catastrophic. It is wasteful, not quadratic.

The bytes requested are roughly twice the payload. At n=10,000 the vector asked for 131,068 bytes to store 40,000 bytes of ints. The total is the sum of every block it ever allocated: 4 + 8 + 16 + … + 65,536 bytes. With a growth factor of 2, the sum of all previous blocks is one byte short of the final block, so the total requested is very close to twice the final capacity — and the final capacity is itself up to twice the size. At n=10,000 the final capacity is 16,384, which is 65,536 bytes for 40,000 bytes of data: 39% of the final block is waste that shrink_to_fit would have to be called to recover.

reserve makes it exactly one allocation of exactly the right size. Not approximately; reserve(n) on a fresh vector allocates capacity exactly n, so the 40,000 bytes at n=10,000 is the payload with nothing over.

The ratio worth carrying away: 15 allocations and 3.3× the bytes, against 1 allocation and 1.0×. One line of code.

5. Why the Factor Has to Be a Factor

This is the part of the amortisation argument that makes the design inevitable rather than arbitrary, and it is a common interview question.

Suppose a vector grew by a constant amount — say 64 elements each time. Reaching n elements takes n/64 reallocations, and the kth one moves 64k elements, so the total element moves are 64 * (1 + 2 + … + n/64), which is O(n²). Building a million-element vector by appending would move on the order of 10¹² elements. Growth by a constant amount makes push_back O(n) amortised, not O(1).

Now suppose it grows by a constant factor f. Reaching n takes log_f(n) reallocations, and the element moves form a geometric series summing to n * f/(f-1) — a constant multiple of n, independent of how many reallocations happened. Total work O(n), so O(1) per push.

The measurement confirms the arithmetic: for f = 2 the predicted total is n * 2/(2-1) minus the final, which for n = 1000 with capacities ending at 1024 gives the 1,023 moves observed. The series is the reason the number came out just above n rather than proportional to n².

That is what amortised buys and it is why Chapter 19.1 §8's caveat matters: the average is genuinely O(1), and the individual call that happens to trigger the final doubling moved 512 elements.

6. reserve Is Not resize

These two are confused constantly and the consequence is undefined behaviour, so the distinction deserves its own measurement.

std::vector<int> a; a.reserve(5);
std::vector<int> b; b.resize(5);

reserve(5): size=0 capacity=5  (no elements exist; a[0] would be UB)
resize(5):  size=5 capacity=5  b[0]=0 (five value-initialised ints)

reserve(n) allocates storage and creates nothing. size() stays 0. The vector is still empty. a[0] is undefined behaviour, and because the memory is allocated it will usually return 0 rather than crashing — a wrong program that tests clean.

resize(n) creates elements. size() becomes 5 and five value-initialised ints exist, which for int means five zeros.

So the two are used in different places. reserve goes in front of a loop that will push_back, and the loop is unchanged. resize is for when you want the elements to exist so you can assign to them by index:

std::vector<int> v;
v.reserve(n);                       // capacity only
for (int i = 0; i < n; ++i) v.push_back(f(i));     // push_back, not v[i]

std::vector<int> w;
w.resize(n);                        // elements exist
for (int i = 0; i < n; ++i) w[i] = f(i);           // indexing is now legal

The mistake is reserve(n) followed by v[i] = ..., which compiles, runs, writes into raw storage, and leaves size() at 0 so every later loop over the vector iterates zero times. There is no diagnostic. A sanitizer build will usually catch it as a container-overflow.

7. A Vector Never Shrinks By Itself

The growth is automatic. The shrinking is not, at all, and this is the asymmetry that surprises people last.

after resize(10000):   size=10000 capacity=10000
after clear():         size=    0 capacity=10000  (memory still held)
after shrink_to_fit(): size=    0 capacity=    0
resize(10000)->resize(10): capacity=10000 (resize down frees nothing)

clear() destroys all the elements and leaves size() at 0. It releases no memory — capacity stays at 10,000, which is 40,000 bytes still held. resize(10) from 10,000 likewise destroys 9,990 elements and keeps the block. erase is the same.

This is deliberate and usually right: a vector that is cleared and refilled in a loop should not return its block to the allocator only to ask for it again. But it means a std::vector member of a long-lived object holds its high-water mark forever, which is a real source of memory that looks like a leak and is not one.

shrink_to_fit() is the request to release it, and it is a request: the standard permits an implementation to ignore it. Here it took capacity to 0. Note that shrinking is itself a reallocation, so it invalidates everything — Chapter 19.1 §6's rule covers shrink_to_fit for exactly this reason.

The idiom for guaranteeing the memory is gone is to swap with an empty vector, which works because the two objects exchange their blocks and the temporary takes the old one to its destructor:

std::vector<int>().swap(v);        // v now has capacity 0, guaranteed

8. Where Growth Invalidates

Chapter 19.1 §6 measured this and stated the rule; it is restated here because this is the chapter where the mechanism is visible.

Any operation that can change capacity invalidates every iterator, pointer and reference into the vector: push_back, emplace_back, insert, emplace, resize, reserve, shrink_to_fit. "Can" is the operative word — push_back with spare capacity invalidates nothing, which is why the rule cannot be checked from the type and has to be assumed.

Insertion or erasure in the middle additionally invalidates everything from the modification point onward even when capacity does not change, because the tail shifts.

The defence is the one from Chapter 19.1 §13: hold an index, not a pointer, across any modification. An index is not an address, so reallocation cannot invalidate it.

9. Appending Efficiently

Three members append, and the differences are small but real.

push_back(x) copies or moves x into place. push_back(std::move(x)) moves it. emplace_back(args...) constructs the element in place from the arguments, with no temporary at all — the perfect-forwarding mechanism Chapter 18.9 §6 measured.

For an int these are identical. For a type whose construction is expensive, emplace_back saves one construction and one destruction:

v.push_back(Widget(7, "seven"));   // construct a temporary, move it in, destroy it
v.emplace_back(7, "seven");        // construct it in place

Since C++17, emplace_back returns a reference to the new element, which is occasionally convenient.

The one case where push_back is preferable is clarity: emplace_back takes constructor arguments, so v.emplace_back(10) on a std::vector<std::vector<int>> creates a ten-element inner vector, not an element with the value 10. When the argument list is ambiguous to a reader, the explicit push_back of a named object is better code.

10. The Numbers Table

11. What to Actually Do

• Call reserve(n) whenever the final count or a tight upper bound is known. Measured: 15 allocations → 1, and 1,023 element moves → 0.
• Do not reserve a guess. A wrong large reserve is worse than the doublings.
• Never index into reserved-but-not-resized storage. Use push_back after reserve, operator[] after resize.
• Mark your types' move constructors noexcept if they will go in a vector, so reallocation moves rather than copies.
• Prefer emplace_back for expensive element types, unless the argument list reads ambiguously.
• Remember clear() frees nothing. Use shrink_to_fit() or the swap idiom when the memory must go back.
• Hold an index, not a pointer or iterator, across any modification.
• Measure your implementation's growth factor rather than quoting 2; libc++ uses 2 and MSVC uses 1.5.

12. Mistakes Worth Making Once

reserve then v[i] = x. Compiles, runs, writes into raw storage, leaves size() at 0. Every later loop iterates zero times and the program silently produces nothing.

reserve when you meant resize. The same bug seen from the other side.

Assuming clear() releases memory. Measured: capacity stayed at 10,000. A long-lived vector holds its high-water mark.

Holding &v[0] across a push_back. Chapter 19.1 §6 measured the relocation. The read usually still returns the old value, so the bug ships.

Reserving inside the loop. reserve in a loop body that also pushes can make growth quadratic if the argument is computed from the current size. Reserve once, before.

Expecting push_back to be O(1) every time. It is amortised. The call that triggers the final doubling moved 512 elements.

Not marking a move constructor noexcept and then wondering why a vector of your type is slow. The library is copying because it cannot risk a throwing move.

Trusting shrink_to_fit absolutely. It is a request; the standard allows it to do nothing.

13. Interview Relevance

The frozen curriculum marks this chapter High, and the growth question is one of the most common in the whole container area.

"What happens when a std::vector runs out of capacity?" Allocate a larger block, move or copy every existing element, destroy the originals, free the old block, append. All iterators, pointers and references are invalidated.

"By how much does it grow?" Implementation-defined; libc++ doubles, MSVC uses 1.5. The strong answer continues: it must be a constant factor rather than a constant amount, and then gives §5's O(n²)-versus-O(n) argument. That argument is what the question is really testing.

"What does reserve do?" Allocates capacity without creating elements, so size() is unchanged. The follow-up is always the difference from resize, and the sharp version of the answer is that indexing after reserve is undefined behaviour.

"Why does clear() not free memory?" So that a cleared-and-refilled vector does not churn the allocator. shrink_to_fit or the swap-with-empty idiom releases it.

"Why should a move constructor be noexcept?" Because vector reallocation can only use moves if they cannot throw — otherwise the strong exception guarantee on push_back would be unachievable — so a throwing move downgrades every reallocation to copies.

"How many element moves to build an n-element vector by pushing?" About n, not n log n and not n², because the abandoned capacities form a geometric series. The measured figure of 1,023 for n = 1,000 is a good thing to be able to quote.

14. What You Should Be Able to Say Now

• The difference between size() and capacity(), and that the gap is raw storage with no objects in it.
• The exact capacity sequence this implementation produced and that the factor is 2 by measurement.
• That building a 1,000-element vector by pushing performed 1,023 element moves, and why that number is a geometric series.
• Why growth must be by a factor: constant-amount growth is O(n²) total.
• That 10,000 unreserved pushes cost 15 allocations and 131,068 bytes against 1 and 40,000.
• That reserve creates no elements and resize does, and that indexing after reserve is undefined behaviour.
• That clear() frees nothing and shrink_to_fit is a request.
• Why noexcept on a move constructor changes what reallocation does.

15. Exercises

Exercise 1 — your factor. Print the capacity sequence to 10,000 on your implementation and state the factor. If it is not 2, recompute §5's series for your factor.

Exercise 2 — the move count. Reproduce Tracked and confirm 1,023 for n = 1,000. Then predict and verify the count for n = 5,000 before running it.

Exercise 3 — the noexcept experiment. Remove noexcept from Tracked's move constructor and re-run. Report the new copy and move counts, and explain the library's choice.

Exercise 4 — the waste. For n from 1 to 100,000, compute the ratio of final capacity to size. Find the worst case and explain which n produces it.

Exercise 5 — the quadratic container. Write a container that grows by a constant 64 elements and time building 200,000 elements in it against a std::vector. Plot both; confirm the shapes are O(n²) and O(n).

Exercise 6 — the silent bug. Write the reserve-then-index bug, run it, and show that the program prints nothing from a later loop. Then run it under a sanitizer and report the diagnostic.

Exercise 7 — releasing memory. Fill a vector with a million elements, clear() it, and print capacity. Then release the memory three ways — shrink_to_fit, swap-with-empty, and scope exit — and verify each.

Exercise 8 — reserve the wrong amount. Time and measure peak memory for building a 12-element vector with reserve(1'000'000) against no reserve at all, and state which is worse and why.

16. Summary

• size() is elements that exist; capacity() is room in the block. The gap is raw storage.
• Measured capacity sequence: 0 1 2 4 8 … 1024 — this implementation's growth factor is 2.
• Measured: 1,023 element moves to build a 1,000-element vector by pushing, because each reallocation moves everything already present and the abandoned capacities form a geometric series.
• Measured: copy=0 — the library moved rather than copied because the move constructor was noexcept.
• Measured: n=10,000 unreserved costs 15 allocations and 131,068 bytes for 40,000 bytes of data; reserved costs 1 and 40,000.
• Growth must be by a factor, not an amount — otherwise push_back is O(n) amortised and building is O(n²).
• Measured: reserve(5) leaves size() at 0; indexing then is undefined behaviour. resize(5) creates five elements.
• Measured: clear() leaves capacity at 10,000. A vector never shrinks by itself; shrink_to_fit is a request.
• Any capacity change invalidates everything — so hold an index.

That completes the contiguous containers. Chapter 19.4 turns to the two that give up contiguity for something else: std::deque, which keeps random access and buys cheap insertion at both ends by storing its elements in a sequence of blocks, and std::list, which gives up random access entirely in exchange for O(1) insertion at a position you already hold. Both are chosen far more often than their guarantees justify, and the chapter measures why — including the figure that makes the strongest case against reaching for std::list: what one int in a list actually costs.