Container Complexity & Iterator Invalidation

STL Containers showed you what each container is for. In interviews and in real code reviews you will be asked two deeper questions: how expensive is this operation? and is this iterator, pointer or reference still valid after I changed the container? Getting the first wrong makes programs slow; getting the second wrong causes undefined behaviour.

This lesson gives you the complexity guarantees the C++ standard makes, explains vector growth, lists the invalidation rules you need to remember, and shows the safe ways to erase while looping.

Big-O in one minute

Big-O notation describes how the work grows as the number of items n grows. It ignores constant factors and only describes the trend:

Amortised O(1) means "usually constant, occasionally expensive, but constant on average over many operations". vector::push_back is the classic example.

What each operation costs

These are the guarantees the standard library gives (n is the container size):

Two warnings about this table. First, the hash containers are O(1) on average; with a poor hash function, or many keys landing in the same bucket, a lookup can scan many items. Second, Big-O ignores memory layout. A vector stores items side by side, which the CPU cache loves, so a linear scan of a small vector is often faster than a map or list lookup. For a few hundred items, measure before choosing a "faster" container (see Performance & Profiling).

Vector growth, capacity and reserve

A vector has a size (items stored) and a capacity (items it has room for). When push_back finds the vector full, it allocates a bigger block, moves every item across, and frees the old block. The new capacity is a multiple of the old one, which is what makes push_back amortised O(1). The exact growth factor is up to the library.

#include <cstddef>
#include <print>
#include <vector>

int count_reallocations(bool reserve_first) {
    std::vector<int> tickets;
    if (reserve_first) {
        tickets.reserve(1000);
    }
    int moves = 0;
    std::size_t last_capacity = tickets.capacity();
    for (int i = 0; i < 1000; ++i) {
        tickets.push_back(i);
        if (tickets.capacity() != last_capacity) {
            ++moves;
            last_capacity = tickets.capacity();
        }
    }
    return moves;
}

int main() {
    std::println("Without reserve: {} reallocations", count_reallocations(false));
    std::println("With reserve:    {} reallocations", count_reallocations(true));
}

Without reserve: 11 reallocations
With reserve:    0 reallocations

The first line is what GCC's library prints, because it doubles the capacity each time (1, 2, 4, ... 1024). Microsoft's library grows by about one and a half times and reports more reallocations. The second line is the same everywhere: after reserve(1000), the standard guarantees no reallocation until the size exceeds the capacity. When you know roughly how many items are coming, call reserve first. shrink_to_fit() asks the vector to release unused capacity, but the library may ignore the request.

Iterator invalidation rules

An iterator, pointer or reference into a container becomes invalid when the element it refers to moves or disappears. Using it afterwards is undefined behaviour. The rules to remember:

The node-based containers (list, map, set) are the most forgiving because each element lives in its own memory block and never moves. A vector is the least forgiving. This is the bug from Undefined Behaviour & Sanitizers: a pointer to runs[0] was kept while push_back reallocated.

The same trap appears in a range-for loop:

std::vector<int> queue = {1, 2, 3};
for (int x : queue) {
    if (x == 2) {
        queue.push_back(99);     // undefined behaviour: the loop's hidden iterators may now dangle
    }
}

Fix it by collecting the new items in a second vector and appending them after the loop, or by looping with an index and reading queue.size() once before the loop.

Erasing safely while looping

erase returns an iterator to the element after the erased one. Use that iterator instead of incrementing the old, now invalid one:

#include <map>
#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<int> waiting = {101, 102, 103, 104, 105, 106};
    for (auto it = waiting.begin(); it != waiting.end();) {
        if (*it % 2 == 0) {
            it = waiting.erase(it);     // continue from the element after the erased one
        } else {
            ++it;
        }
    }
    std::println("{} {} {}", waiting[0], waiting[1], waiting[2]);

    std::map<std::string, int> seats = {
        {"Shatabdi", 0}, {"Rajdhani", 12}, {"Duronto", 0}, {"Garib Rath", 40}};
    auto removed = std::erase_if(seats, [](const auto& entry) { return entry.second == 0; });
    std::println("Removed {} full trains", removed);
    for (const auto& [train, free_seats] : seats) {
        std::println("{}: {}", train, free_seats);
    }
}

101 103 105
Removed 2 full trains
Garib Rath: 40
Rajdhani: 12

The C++20 function std::erase_if does the whole job in one call for every standard container and returns how many items it removed. Prefer it to hand-written loops; for vectors it is also faster, because it moves each remaining item only once instead of shifting the tail after every single erase (which makes the hand-written loop O(n²) in the worst case).

Map lookups that change the map

map[key] is convenient, but if the key is missing it inserts a default value. Reading with [] silently grows the map:

#include <map>
#include <print>
#include <string>

int main() {
    std::map<std::string, int> marks = {{"Priya", 88}};
    if (marks["Rohan"] > 50) {            // Rohan did not exist: now added with 0
        std::println("Rohan passed");
    }
    std::println("Students: {}", marks.size());

    if (auto it = marks.find("Isha"); it != marks.end()) {   // lookup without inserting
        std::println("Isha: {}", it->second);
    }
    marks.insert_or_assign("Priya", 91);  // update or add, clearly
    std::println("Priya: {}, students: {}", marks.at("Priya"), marks.size());
}

Students: 2
Priya: 91, students: 2

Use find or contains to check, at to read (it throws std::out_of_range if the key is missing), insert_or_assign to set, and try_emplace to add only if the key is new. operator[] also cannot be used on a const map, which is another hint that it is meant for writing.

Common mistakes

• Keeping pointers or iterators into a vector across push_back or insert. Store indexes, or call reserve first if you truly need stable addresses (or use a node-based container).
• ++it after erase(it). The old iterator is invalid; use the return value of erase or std::erase_if.
• Using map[key] to check whether a key exists. It inserts the key. Use contains or find.
• Choosing list for speed. Its O(1) insert needs an iterator you already have, and its scattered memory makes traversal slow.
• Assuming hash containers are always O(1). Bad hashes or many collisions make them linear.

Key points

• Vector: O(1) index access and amortised O(1) push_back, but O(n) insert or erase anywhere except the end.
• map and set are O(log n) and sorted; unordered_ containers are O(1) on average and unsorted.
• reserve prevents reallocations; growth factors differ between libraries.
• Vector reallocation invalidates all iterators, pointers and references; node-based containers only invalidate erased elements.
• Erase with it = c.erase(it) or C++20 std::erase_if; read maps with find, contains or at, not [].

#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> orders = {"Samosa", "Kachori", "Samosa", "Lassi", "Samosa"};
    auto removed = std::erase_if(orders, [](const std::string& o) { return o == "Samosa"; });
    std::println("Removed {}", removed);
    for (const auto& o : orders) {
        std::println("{}", o);
    }
}

Removed 3
Kachori
Lassi