C++ std::vector Internals: Growth, Capacity, Reallocation and Iterator Invalidation

std::vector looks like an array that grows automatically, but a successful push_back can move every element and leave a saved iterator, pointer or reference dangling. The safe way to reason about it is to track size(), capacity() and the operation being performed, without memorising one library's growth multiplier.

C++ std::vector stores a contiguous sequence with spare capacity

size() counts live elements. capacity() says how many elements the current allocation can hold. Therefore, 0 <= size() <= capacity().

For ordinary std::vector<T> types other than the vector<bool> specialisation, elements occupy contiguous storage, so &v[i + 1] == &v[i] + 1 for valid adjacent indices. A data pointer, size and end-of-storage pointer form a useful conceptual model, not a required object layout.

For v = {10, 20, 30}, size = 3 and capacity = 4. Slots 0 to 2 are live; slot 3 is spare storage, not an element. Thus v[2] equals 30, but reading v[3] is invalid.

Beginner construction, access, sorting and general resizing belong to the earlier Vector in C++: Create, Update, Iterate and Sort with Runnable Examples. Allocation growth, relocation cost and saved-handle lifetime require a separate, operation-by-operation trace. Coding & DSA places both topics in wider coding preparation.

std::vector growth: guarantees and implementation choices

If an insertion makes the new size exceed the old capacity, the vector must obtain a larger allocation. C++ requires enough capacity for the new size but prescribes no multiplier such as 2x or 1.5x.

An implementation that doubles capacity could produce this illustrative trace while appending 10, 20, 30, 40, 50:

The fourth append fits because new size 4 equals old capacity 4. The fifth must reallocate because new size 5 exceeds old capacity 4. Capacity 8 is illustrative.

#include <iostream>
#include <initializer_list>
#include <vector>

int main() {
    std::vector<int> v;
    auto show = [&] {
        std::cout << "size=" << v.size()
                  << " capacity=" << v.capacity()
                  << " data=" << static_cast<const void*>(v.data()) << '\n';
    };

    show();
    for (int value : {10, 20, 30, 40, 50}) {
        v.push_back(value);
        show();
    }
}

Trust the printed capacities only for that build. Portably, compare required size with old capacity and determine whether reallocation occurred.

Amortised O(1) push_back spreads rare relocation costs

One push_back may cost O(n) because reallocation relocates existing elements by move or copy. Under geometric growth, reallocations become rarer, giving amortised O(1) per append across a sequence. For a fuller explanation of the difference between worst-case and aggregate cost, see our guide to time complexity and asymptotic notation.

For 16 appends under the same doubling policy, growth to capacities 2, 4, 8 and 16 relocates 1 + 2 + 4 + 8 = 15 old elements. Add 16 new-value constructions: 15 + 16 = 31 constructions or relocations. The average is 31 / 16 = 1.9375, below 2 per append.

This explains amortisation, not an exact library move count. Calling reserve(size() + 1) before every append can defeat geometric growth and cause repeated linear relocations.

std::vector reallocation: a dangling-reference trace

Start with v = {10, 20, 30, 40} at (4, 4). Save int& r = v[1], int* p = &v[1], auto it = v.begin() + 1 and auto old_end = v.end(). The first three identify 20 in allocation A.

After v.push_back(50), the vector is {10, 20, 30, 40, 50} at (5, 8), and data() changes from allocation A to B. Reallocation invalidates r, p, it and old_end. Do not inspect dangling handles. Reacquire &v[1] or v.begin() + 1.

Appending 40 to {10, 20, 30} at (3, 4) does not reallocate, so existing-element handles survive. The old end() does not, because the end moves from index 3 to 4.

std::vector iterator invalidation rules by operation

No reallocation does not mean no invalidation. Also consider the mutation position. The earlier C++ Iterators and Invalidation: Container Rules and Safe Erase Loops compares iterator categories and safe erasure across multiple container families. For std::vector, the decisive split is whether storage relocates and which positions a mutation shifts.

At (size, capacity) = (4, 8), inserting 25 at index 2 changes {10, 20, 30, 40} to {10, 20, 25, 30, 40} without reallocation. A handle to index 1 survives; handles to the original 30, original 40 and old end() do not.

Erasing index 1 from {10, 20, 30, 40, 50} gives {10, 30, 40, 50}. A handle to 10 survives; handles to the original 20, 30, 40 and 50 do not.

reserve, resize, clear and shrink_to_fit have different jobs

reserve(n) may increase capacity but creates no elements. resize(n) changes size, destroying or creating elements. clear() destroys all elements and sets size to zero without reducing capacity. shrink_to_fit() is a non-binding request. If it reallocates, handles invalidate.

For v = {10, 20, 30, 40, 50} at (5, 8), reserve(6) does nothing because 6 <= 8. reserve(12) reallocates, preserves size and values, and makes capacity at least 12. Then resize(7) produces {10, 20, 30, 40, 50, 0, 0} for vector<int> without reallocation. clear() leaves size 0 and retains capacity.

Index 1 may still exist as a position after reallocation, but insertion or erasure before it can change which element occupies that position.

std::vector traps in exams, interviews and production code

Typical prompts ask whether reallocation is forced, which handles survive, why amortised O(1) permits one O(n) append, or where one reserve(expected_count) helps.

Saving int* chosen = &v[1], appending until reallocation, then reading *chosen is undefined behaviour. Store a stable application identifier. If position is the intended identity and earlier elements stay ordered, store index 1 and reacquire v[1].

std::vector internals: the short version and next step

Revision card:

• size <= capacity.

• Spare capacity is not a live element.

• The growth factor is not standardised.

• Exceeding old capacity forces reallocation.

• Reallocation invalidates every element handle.

• A no-reallocation insert or erase can still invalidate handles at or after the mutation point.

Check three results from memory: five pushes end at (5, 8); 16 pushes relocate 15 old elements and total 31 constructions plus relocations; erasing index 1 from {10, 20, 30, 40, 50} gives {10, 30, 40, 50} and invalidates handles at or after index 1.

The C++ Programming course places vector behaviour inside a broader C++ sequence. If you only need this concept, run the program, watch data(), and practise the invalidation table without assuming a fixed multiplier.