vector — internals, push_back amortization

Scenario

You store a pointer to the first element of your `std::vector`. You then call `push_back()` a few times. When you try to read your pointer, the program crashes with a segmentation fault.

If you never deleted the vector, why did the pointer to its data become invalid?

Mental model

`std::vector` is a dynamic array. When it runs out of space, it doesn't just expand—it buys a bigger house, copies all the furniture over, and burns down the old house.

`std::vector` is the default sequence container in C++. It manages a contiguous block of memory on the heap. When that memory fills up, the vector must reallocate a larger block (usually double the size) and move all existing elements. This reallocation makes `push_back` an 'amortized O(1)' operation.

Explanation

Under the hood, a `std::vector` maintains three pointers: `begin` (start of data), `end` (end of active data), and `capacity` (end of allocated memory). The **size** is the number of active elements, while the **capacity** is the total number of elements it can hold before it must allocate more memory.

**Amortized O(1) Growth:**

When you call `push_back()` and `size == capacity`, the vector is full. It cannot just grow in place, because the adjacent memory might be owned by something else. Instead, it:

1. Allocates a completely new, larger array (usually 2x the current capacity).

2. Moves/copies all elements to the new array.

3. Deletes the old array.

While this reallocation is O(N), it happens so rarely that the *average* time per `push_back` remains O(1). This is called 'amortized' O(1).

**The Reallocation Trap:**

Because reallocation deletes the old array, **any pointers or references** pointing to elements inside the vector immediately become invalid (dangling). To prevent unnecessary reallocations and invalidation, always use `vec.reserve(N)` if you know roughly how many elements you will insert.

**Real-world Engineering:** If you must store references to elements but expect the vector to grow, **store integer indices** instead of pointers. Indices remain valid regardless of reallocation. A classic bug in game development is storing pointers to game entities inside a vector; when a new entity spawns and triggers a reallocation, all existing pointers danglingly crash the game. Use indices, or `reserve()` the max capacity upfront.

Code examples

Reallocation and Invalidation

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3};
    
    // Get a reference to the first element
    int& firstElement = vec[0];
    
    // Force a reallocation by exceeding capacity
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    
    // BUG: firstElement is now a dangling reference!
    // The original array was deleted during reallocation.
    // std::cout << firstElement; // Undefined Behavior
    
    return 0;
}

The moment `push_back` triggers a capacity increase, the vector moves all its data to a new heap location. The reference `firstElement` is left pointing to freed memory.

Using reserve() for performance

#include <vector>

int main() {
    std::vector<int> vec;
    
    // Pre-allocate space for 1,000 elements.
    // Size is still 0, but Capacity is 1000.
    vec.reserve(1000);
    
    // These 1,000 push_backs are guaranteed to be true O(1).
    // Zero reallocations will occur.
    for (int i = 0; i < 1000; ++i) {
        vec.push_back(i);
    }
    
    return 0;
}

`reserve(N)` allocates memory ahead of time without changing the logical size of the vector. This prevents both performance hiccups and iterator/reference invalidation.

Key points

• Contiguous memory is king: `std::vector` is the fastest container because it is cache-friendly. It should be your default choice.
• Beware reallocation: Growth means moving data. Reallocation invalidates all pointers, references, and iterators to the vector's elements.

Common mistakes

• Confusing reserve() with resize(): `reserve(N)` only changes capacity (allocates memory). `resize(N)` changes both capacity AND size, actually instantiating `N` default objects (e.g., zeros). If you `resize(10)` and then `push_back(5)`, the `5` will be inserted at index 10, not index 0.

Recall questions

• What is the difference between a vector's `size` and its `capacity`?
• Why is `push_back` considered amortized O(1) rather than strict O(1)?
• What does `std::vector::reserve(N)` do?

Questions & answers

A candidate reads 1 million integers from a file into a `std::vector` using a `while` loop and `push_back()`. The profiler shows the code spends 30% of its time allocating memory. How do you optimize this?

If the file size or the number of elements is known beforehand, call `vec.reserve(1000000)` before the loop. This ensures exactly one memory allocation occurs, completely eliminating the reallocation overhead.

Approach: Recognize the performance impact of repeated vector reallocations.

Is it safe to store pointers to elements of a `std::vector` inside another data structure?

Generally, no. If the vector ever grows beyond its capacity, it will reallocate, invalidating every single stored pointer. If you must do this, either `reserve()` enough space so it never grows, or store indices (which remain valid) instead of pointers.

Approach: Identify reference invalidation risks with dynamic arrays.

Continue learning

Previous: Stack vs heap — new/delete & memory layout

Next: Iterator invalidation — when containers reshuffle under you

Next: deque, list & array

Return to C++ Roadmap