How a Vector Grows: Size, Capacity and Reallocation

Start with the problem

A vector can grow whenever you call push_back. But its elements form one contiguous block of memory, and a block cannot always be stretched, because the memory right after it may belong to something else. So what does the vector do when the block is full? And if the answer involves copying everything to a bigger block, how can appending a million items be fast?

The answers explain a quantity that arrays never had: a vector's capacity.

How the idea works

Size and capacity. The size of a vector is the number of elements it holds. Its capacity is the number of elements the current buffer can hold before it must be replaced. The elements at indexes from 0 up to but not including the size are real. The slots after them are raw, unused memory. The first two cells of the trace show both numbers, and you can read them with size() and capacity().

What push_back does. There are two cases:

1. If the size is below the capacity, there is room. The new element is constructed in the next free slot, and the size increases by one. Nothing else happens (step 5).
2. If the size equals the capacity, the vector allocates a bigger buffer, moves the existing elements into it, constructs the new element, frees the old buffer, and updates its pointers (steps 2, 3, 4 and 6).

The growth policy. The new capacity is a multiple of the old one, not a fixed amount more. libstdc++ and libc++ double it, and MSVC multiplies it by 1.5. The trace shows libstdc++'s sequence: 0, 1, 2, 4 and 8. A strategy where the capacity grows by a constant factor is called geometric growth.

Amortized constant time. A single append sometimes costs a lot, but the average over many appends is low. With doubling, the elements moved across all reallocations add up to 1 + 2 + 4 + ... which is less than the final size. So n appends move fewer than 2n elements in total, and the average cost per append is constant. This is called amortized constant time. Appending a million integers reallocates about 20 times and moves about a million elements. Growing by one slot each time would instead move about 500 billion elements, which is minutes of work.

Controlling capacity. The call reserve(n) allocates room for at least n elements up front, without creating any. It leaves the size unchanged. The call resize(n) changes the size, adding zero-valued elements or dropping some. The call shrink_to_fit() asks the vector to release unused capacity. The call clear() removes all elements but keeps the buffer.

Invalidation. When a vector reallocates, every pointer, reference and iterator into its elements becomes invalid. They still hold the old addresses, which now point into freed memory (step 7).

std::vector<int> v = {1, 2, 3};
int& first = v[0];
v.push_back(4);        // may reallocate
first = 99;            // dangling if it did

Even without reallocation, push_back invalidates the end iterator, and insert and erase invalidate everything from the changed position onward. The standard documents these rules exactly, so that you can rely on them.

Why it is correct

Keeping the elements contiguous is what gives the vector its fast indexing and cache behavior, and contiguity forces the rule: a full block can only be replaced by a larger one. Moving to a new block is therefore not a flaw of the design but the price of its main benefit.

Geometric growth is correct in the sense that it keeps that price low. Each element moved in a reallocation can be paid for by the appends since the previous one, because the buffer has doubled and at least half of its slots have been filled since then. Invalidation is the unavoidable consequence: the old block is freed, so any address into it is stale. And the guarantee that reserving a capacity prevents reallocation until the size exceeds it lets careful code use references safely.

What it costs

A reallocating append. It costs time proportional to the size: allocate, move every element, free. At a million integers, which is 4 MB, that is around half a millisecond or more. A normal append costs a couple of nanoseconds.

Memory. The buffer may be nearly twice as large as the data, and at the moment of reallocation the old and the new buffers exist together, so the peak can be around three times the size of the data. For a very large vector that can raise std::bad_alloc.

Reserve pays off. When you know the final size, reserve removes every reallocation, and filling a large vector is often noticeably faster. When you do not know it, the default growth is fine.

Shrinking. shrink_to_fit is a request and costs a reallocation, so use it rarely.

Pitfalls and variations

References across an append. The classic bug is holding a reference, pointer or iterator into a vector while appending to it. A loop such as for (auto& x : v) { v.push_back(x); } is undefined behavior for this reason. Hold indexes instead, because an index stays valid across a reallocation.

Reserve is not resize. After v.reserve(10) the size is still 0, and v[5] = 1 is undefined behavior. To get ten usable elements, construct the vector with v(10) or call v.resize(10).

Relying on the factor. The growth factor is up to the implementation, so portable code does not depend on specific capacities.

Clear does not free. clear() keeps the capacity. To give the memory back, call shrink_to_fit() afterwards or swap with an empty vector.

Insertion at the front. Every insertion at the start shifts all the elements, so repeated front insertions take quadratic time. The Core level introduces std::deque for that.

Variations. The call emplace_back constructs the element in place and avoids a temporary. std::string uses the same size and capacity scheme. Custom allocators, in the Advanced level, change where the buffers come from.

Where it is used

Any code that builds a collection step by step relies on this: reading the lines of a file, collecting results, parsing. Performance-sensitive code calls reserve when the count is known. The same amortized argument underlies the dynamic arrays of other languages, such as Java's ArrayList, Python's list, Rust's Vec and Go's slices, as well as string builders and the rehashing of hash tables.

The next lesson, "Strings: C-Strings and std::string", looks at the most common array of all, an array of characters, and at the two ways C++ represents text.