C++ Iterator Invalidation Rules and Stable Handles

The question

Your book keeps a std::vector of orders and an index from order id to Order*. After a burst of new orders, a cancel corrupts memory. Why?

What happened

std::vector<Order> orders_;
std::unordered_map<OrderId, Order*> by_id_;

void add(const Order& o) {
    orders_.push_back(o);
    by_id_[o.id] = &orders_.back();       // pointer into the vector's buffer
}

When push_back finds the vector full it allocates a bigger buffer, moves the orders into it and frees the old one. Every pointer stored in by_id_ still points into the freed buffer. The next cancel looks up an order, writes through the stale pointer, and corrupts whatever now lives there.

What push_back does at full capacity, one step at a time.

Step 1 / 3

A vector holds four quotes at capacity 4. Some code keeps p = &v[0].
Step 2 / 3

push_back needs a fifth slot. The vector allocates a buffer twice the size and moves the four quotes into it.
Step 3 / 3

The old buffer is freed. The vector uses the new one, but p still holds the old address: reading through it is undefined behaviour.

This is iterator invalidation. Containers promise that pointers, references and iterators to their elements stay valid only under certain operations. Knowing those rules, and designing around them, is a standard interview topic.

The rules that matter

Container	Insert	Erase	Notes
`vector`	invalidates everything if it reallocates; otherwise everything at or after the insertion point	everything at or after the erased element	`reserve` prevents reallocation up to the capacity
`deque`	insert at either end: iterators invalidated, references to elements remain valid; in the middle: all	at either end: only the erased element; in the middle: all	elements never move when you push at the ends
`list`, `forward_list`	nothing	only the erased element	node-based; addresses are stable
`map`, `set`	nothing	only the erased element	node-based
`unordered_map`	iterators if a rehash happens; references and pointers to elements stay valid	only the erased element	`reserve` prevents rehash up to the reserved count

Two subtleties catch people. A std::deque keeps references valid on push at the ends while invalidating iterators, because the iterator holds a pointer into its map of blocks, which may reallocate. A std::unordered_map in the standard library is node-based, so a rehash moves nodes between buckets without moving the elements: pointers to the values survive, iterators do not. Open-addressing hash maps such as Abseil's flat_hash_map move elements on rehash, so pointers into them do not survive.

Erasing while iterating

The other classic bug:

for (auto it = orders.begin(); it != orders.end(); ++it)
    if (it->expired()) orders.erase(it);        // it is invalid after erase; ++it is undefined

erase returns the iterator to the next element; use it, or use std::erase_if (C++20) which does the whole loop correctly for every standard container:

std::erase_if(orders, [](const Order& o) { return o.expired(); });

Stable handles

Trading systems need to refer to orders for a long time: an acknowledgement, a fill, a cancel can arrive milliseconds after the order was created. Pointers into growing containers are unsafe, and node-based containers are slow to walk. The usual answer is a pool with handles:

Orders live in a preallocated array of slots that never reallocates.
A handle is a slot index plus a generation number.
Freeing a slot increments its generation and puts it on a free list.
Looking up a handle checks that the slot's generation still matches; a stale handle is rejected rather than reading whatever order now occupies the slot.

A pool with generation counters. A handle is an index plus the generation it was issued with; reusing a slot bumps its generation, so stale handles are detected instead of silently reading another order.

struct Handle { std::uint32_t index, gen; };

Order* OrderPool::get(Handle h) {
    Slot& s = slots_[h.index];
    return s.gen == h.gen && s.live ? &s.order : nullptr;
}

The exchange gives you its own ids for orders; mapping those to handles in a hash map that stores handles, not pointers, keeps the book safe across growth and reuse.

Check yourself

Question 1 of 3

You hold int* p = &v[0]; and call v.push_back(x) where v.size() < v.capacity(). Is p still valid?

Question 2 of 3

Which pointer stays valid after inserting many elements into a std::unordered_map that rehashes?

Question 3 of 3

What does a generation counter in a handle protect against?

In the interview

Say your own answer out loud first, then open the one we would give.

When does push_back invalidate iterators?

When the vector reallocates, which happens when size reaches capacity: every iterator, pointer and reference to its elements is invalidated. Without reallocation only the end iterator changes. Reserving capacity up front avoids the reallocation and makes the rule predictable.

How do you erase elements from a container while iterating over it?

Use the iterator returned by erase as the next position, or better, std::erase_if in C++20, which handles every standard container. The common bug is calling ++ on an iterator that erase has just invalidated.

How would you refer to orders that may be cancelled or reused?

With handles into a preallocated pool: an index and a generation number. Lookups check the generation, so a stale handle is rejected instead of pointing at a different order. Exchange ids map to handles, not raw pointers.