std::vector — Four Mechanisms Behind Every push_back()

You have called push_back() a thousand times. But do you know how many times your vector actually reallocated memory to make that happen?

Not a thousand. Not even close.

About ten.

Behind that simple interface, four mechanisms are working together — each one invisible during normal use, each one shaping your performance in ways that push_back() will never tell you about.

Exponential growth and amortized O(1)

When a vector runs out of capacity, it does not grow by one element. It allocates a new block that is some multiple of the current capacity, copies (or moves) everything over, and frees the old block.

With a growth factor of 2, the capacity progression looks like this:

8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024

A thousand push_back() calls trigger roughly ten reallocations. Each one copies everything — but because the block grows exponentially, the total number of element copies across all reallocations is bounded. For a growth factor of 2, inserting n elements produces at most ~2n total copies. The average cost per insert stays O(1).

The word for this is amortized. And it is one of the most elegant tradeoffs in the entire standard library.

You can see it directly:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    size_t old_cap = 0;
    for (int i = 0; i < 1000; ++i) {
        v.push_back(i);
        if (v.capacity() != old_cap) {
            std::cout << "size=" << v.size()
                      << "  capacity=" << v.capacity() << '\n';
            old_cap = v.capacity();
        }
    }
}

Run this on Compiler Explorer with different compilers and you will see the growth factor in action — libstdc++ and libc++ double, MSVC uses 1.5.

If you know the final size upfront, reserve() eliminates reallocations entirely:

std::vector<int> v;
v.reserve(1000);       // one allocation, zero reallocations
for (int i = 0; i < 1000; ++i)
    v.push_back(i);    // capacity never changes

Total copies with reserve(): exactly 1000. Without it: roughly 2000. The difference is measurable in tight loops with heavy objects.

The growth factor problem

But why do most implementations double? It seems like the obvious choice — and for decades it was the default. Then Andrei Alexandrescu pointed out a subtle problem.

When a vector doubles, the new allocation is always larger than the sum of all previous allocations combined:

Freed so far:  8
Next request: 16   → 16 > 8, must use fresh memory

Freed so far:  8 + 16 = 24
Next request: 32   → 32 > 24, must use fresh memory

Freed so far:  8 + 16 + 32 = 56
Next request: 64   → 64 > 56, must use fresh memory

Freed so far:  8 + 16 + 32 + 64 = 120
Next request: 128  → 128 > 120, must use fresh memory

The pattern never converges. The allocator is sitting on a growing pile of freed blocks that are never quite big enough to reuse. Every single growth goes to fresh address space.

With a factor of ~1.5 — closer to the golden ratio — something different happens. After a few rounds, the sum of freed blocks exceeds the next request:

Freed so far:  8
Next request: 12   → 12 > 8, fresh memory

Freed so far:  8 + 12 = 20
Next request: 18   → 18 < 20, can reuse!

The allocator can start reclaiming previously freed memory instead of always reaching forward. It is a small change in the multiplier. It is a fundamental change in the allocation pattern.

The tradeoff is real: a factor of 2 means fewer reallocations (you reach the target capacity faster) but worse memory reuse. A factor of 1.5 means more reallocations but friendlier allocation patterns. Neither is universally better — it depends on your workload.

Contiguity and cache performance

The growth strategy determines how often you reallocate. But the other half of the story is where the data ends up.

A vector stores its elements in one contiguous block of memory. Not scattered across the heap. Not linked by pointers. One flat array.

This matters enormously for performance, and the reason is hardware. When the CPU fetches one element from memory, it does not fetch just that element — it loads an entire cache line (typically 64 bytes). If the next element you access is sitting right next to the first one in memory, it is already in cache. The hardware prefetcher sees a sequential access pattern and starts loading ahead of you before you even ask.

This is why iterating a vector<int> can be 10–50x faster than walking a list<int> — even though both are O(n) on paper:

// Contiguous: elements are adjacent in memory.
// The prefetcher loads ahead. Cache hit after cache hit.
std::vector<int> vec(1'000'000, 42);
int sum = 0;
for (auto x : vec) sum += x;

// Linked: each node is a separate heap allocation.
// Every step is a pointer chase to a random address.
// The prefetcher cannot help you.
std::list<int> lst(1'000'000, 42);
int sum = 0;
for (auto x : lst) sum += x;

Big-O tells you the shape of the curve. Cache behavior tells you where on the curve you actually live.

This also explains why std::deque — which stores elements in fixed-size blocks rather than one contiguous array — is measurably slower than vector for sequential iteration, despite having the same O(n) complexity. The blocks are contiguous internally, but the jumps between blocks break the prefetch stride.

Move semantics during reallocation

Before C++11, every reallocation meant copying every element to the new block. A vector of a thousand std::string objects meant a thousand deep copies — allocating fresh character buffers, copying bytes, deallocating the old ones. For heavy objects this was expensive.

Move semantics changed this. Now reallocation can transfer ownership instead of duplicating data. A moved std::string is just a pointer swap — the new object takes the internal buffer, the old object is left in a valid but empty state. No allocation, no byte copying, no cleanup:

// What a copy does (simplified):
//   1. Allocate new buffer
//   2. Copy all characters
//   3. Deallocate old buffer when source is destroyed

// What a move does (simplified):
//   1. Steal the pointer from the source
//   2. Set source to empty
//   Done.

For vectors of lightweight types like int, this barely matters — there is nothing to “move” that is cheaper than copying. But for vectors of strings, containers, or any type that owns heap memory, move semantics during reallocation is a dramatic improvement.

The silent trap: noexcept

Here is the part that surprises people.

The vector will not move your objects during reallocation unless the move constructor is marked noexcept.

Why? Because std::vector guarantees strong exception safety. If a move throws halfway through reallocation, some elements live in the old block, some in the new one, and both are in a corrupted state. There is no way to roll back a half-finished sequence of moves — the source objects have already been gutted.

A copy can be rolled back — just destroy the partial copies and the originals are still intact.

So if your move constructor might throw, the vector quietly falls back to copying. Every single reallocation. You have move semantics defined, but you are paying the full copy cost, and nothing in your code will tell you:

struct Widget {
    std::string name;
    std::vector<int> data;

    // This move constructor is NOT noexcept.
    // std::vector will fall back to copying during reallocation.
    Widget(Widget&& other)
        : name(std::move(other.name))
        , data(std::move(other.data)) {}
};

struct BetterWidget {
    std::string name;
    std::vector<int> data;

    // One word. Massive performance difference. Completely silent.
    BetterWidget(BetterWidget&& other) noexcept
        : name(std::move(other.name))
        , data(std::move(other.data)) {}
};

You can verify this with std::move_if_noexcept — the same mechanism the vector uses internally:

#include <type_traits>
#include <iostream>

int main() {
    std::cout << std::boolalpha;
    std::cout << "Widget movable:       "
              << std::is_nothrow_move_constructible_v<Widget> << '\n';
    std::cout << "BetterWidget movable: "
              << std::is_nothrow_move_constructible_v<BetterWidget> << '\n';
}

One prints false, the other true. The vector checks this at compile time and chooses its reallocation strategy accordingly.

The simplest fix: if you define a move constructor, mark it noexcept. If you let the compiler generate one (by not declaring any special member functions), it will be noexcept automatically — provided all members have noexcept moves themselves.

The full picture

Your vector grows exponentially — with a ratio that shapes whether freed memory can ever be reused. It stores everything contiguously so the hardware prefetcher can do its job. It moves elements during reallocation — unless it cannot prove the move is safe, in which case it silently falls back to copying.

Four mechanisms. Each one invisible behind push_back(). All four shaping your performance.

Go look at a class you store in a vector. Does its move constructor have noexcept? If not, add it and run a benchmark before and after. Then print your implementation’s growth factor with the snippet above — and ask yourself whether those freed blocks are ever coming back.