Code inserts into a std::unordered_map while holding an iterator to one element and a pointer to another; which survives a rehash, and why?
answer
- nodes stay where they are
- bucket array is replaced
- references survive, iterators do not
- the no-rehash window
basics
~20 sThe pointer survives and the iterator may not. A rehash invalidates every iterator and reorders elements, but each element lives in its own node that is relinked rather than moved, so pointers and references stay valid until that element is erased.
solid answer
~50 sThe standard states it directly: rehashing invalidates iterators, changes the ordering between elements and changes which buckets they are in, but **does not invalidate pointers or references to elements**. Inserts and emplaces never affect references, and may invalidate all iterators whenever they trigger a rehash; they leave iterators alone only while `(N + n) <= z * B` holds. `erase` invalidates only iterators and references to the erased elements. So in a session cache, storing `Session*` or `Session&` across inserts is safe; storing an iterator is not, and neither is inserting while a range-for walks the same map, where elements can be skipped or visited twice. The fixes are to collect insertions and apply them after the loop, to `reserve` so the no-rehash window covers them, or to keep keys or pointers instead of iterators.
code
cpp · 19 lines#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> sessions{{1, "alpha"}};
std::string* p = &sessions.at(1); // pointer to the mapped value
auto it = sessions.find(1); // iterator to the same element
std::size_t b = sessions.bucket_count();
for (int i = 2; i < 1000; ++i) sessions.emplace(i, "s");
std::cout << "rehashed: " << (sessions.bucket_count() != b) << '\n';
// the iterator 'it' is now invalid and must not be used;
// the pointer still refers to the same node
std::cout << "pointer still valid: " << (p == &sessions.at(1)) << ' ' << *p << '\n';
it = sessions.find(1); // re-find after possible rehash
std::cout << it->second << '\n';
}go deeper
Know that inserting into a std::unordered_map can invalidate its iterators, so you do not keep iterators across inserts.
State the exact rule: rehash invalidates iterators and order, never pointers or references, and erase affects only erased elements.
Diagnose skipped or repeated elements from insert-while-iterating, and fix them by deferring inserts, reserving, or holding pointers or keys.
Treat reference stability as an explicit dependency when choosing a hash map type, since a faster replacement may silently drop it.
## What the standard guarantees The unordered containers have their own invalidation rules, which differ from both `std::vector` and `std::map`: | Operation | Iterators | Pointers and references to elements | |---|---|---| | `insert`, `emplace`, `operator[]` that inserts, `try_emplace` | **all may be invalidated** if a rehash happens; none otherwise | **never invalidated** | | `rehash`, `reserve` | **all may be invalidated** (a rehash invalidates every iterator) | never invalidated | | `erase` | only those to erased elements | only those to erased elements | | `extract` | only those to the extracted element | remain valid, but using them while a node handle owns the element is undefined | | `clear` | all | all | The standard spells out the rehash case in one sentence: rehashing *invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements*. ## Why: node-based storage Both libstdc++ and libc++ build `std::unordered_map` as a **bucket array** of pointers plus one heap-allocated **node** per element, linked into singly linked lists. A rehash allocates a new bucket array and relinks the existing nodes into it. Nodes are never copied or moved, which is why addresses of elements stay put. An iterator, however, encodes a position in the traversal order: which node comes next depends on the bucket layout, and after a rehash that layout is different, so the standard declares the iterator invalid even if it would still happen to point at the same node. The reference guarantee is a requirement the standard places on every implementation, not an accident of one library; it is one of the reasons the standard containers are node-based. ## The no-rehash window Inserts and emplaces do not invalidate iterators if `(N + n) <= z * B`, where: - `N` is the number of elements before the insert, - `n` is the number of elements inserted, - `B` is `bucket_count()`, - `z` is `max_load_factor()`. Calling `reserve(N + n)` before the inserts makes that inequality hold, so code that must keep iterators across a known number of insertions can pre-size the table and stay within the guarantee. ## Loops that break 1. **Inserting while iterating the same map.** A range-for over the cache that inserts derived sessions can trigger a rehash mid-loop. The loop's iterator is then invalid: continuing is undefined behaviour, and in practice elements are skipped or visited twice because the order changed. 2. **Caching iterators in long-lived objects.** A request handler that stores `cache.find(key)` in a member and uses it after other requests inserted is using a possibly invalid iterator. 3. **Erasing in a loop the wrong way.** `cache.erase(it); ++it;` increments an iterator to an erased element. Use `it = cache.erase(it);`, or the C++20 `std::erase_if(cache, pred)`. Erasure never rehashes, so other iterators remain valid. ## Patterns for the session cache - **Hold pointers or references** to `Session` objects when you need stable handles across inserts; they stay valid until that session is erased. - **Hold keys** when the session may be erased by someone else, and look it up again; a key cannot dangle. - **Collect, then apply**: gather new entries in a vector during iteration and insert them after the loop. - **Reserve** before a batch of inserts if iterators must survive it. - **Do not rely on order** after any insert; a rehash reshuffles iteration order. ## Catching misuse Using an invalidated iterator is undefined behaviour, and in a release build it often "works" until the table grows at the wrong moment. Two tools make it visible earlier: - **libstdc++ debug mode** (`-D_GLIBCXX_DEBUG`) wraps the unordered containers in checked versions that invalidate every outstanding safe iterator when the bucket count changes, so a stale iterator is reported at its next use instead of silently walking the wrong chain. - **Code review rules**: no iterator into a hash map stored in a member or kept across a call that might insert; pointers or keys instead. AddressSanitizer is not a reliable detector here: after a rehash the old iterator usually still points into a live node, so there is no freed memory to flag. ## Contrast with other containers `std::map` never invalidates iterators on insert. `std::vector` invalidates references *and* iterators when it reallocates. An open-addressing hash map from a third-party library typically moves elements on rehash and so invalidates references too; code ported between them must be re-audited for exactly this.
- Why does the standard keep references stable across rehash but not iterators, if both point at the same node?A reference names an element, and the element's node never moves. An iterator also encodes a position in the traversal: incrementing it depends on which bucket comes next and what that bucket holds. After a rehash, that traversal structure is different, so the standard does not promise that an old iterator can still be incremented or compared meaningfully.
- How do you erase expired sessions from a std::unordered_map while iterating it?Use the iterator returned by `erase`: `for (auto it = m.begin(); it != m.end();) { if (expired(it->second)) it = m.erase(it); else ++it; }`. Or, in C++20, call `std::erase_if(m, pred)`. Erasure never rehashes, and it invalidates only iterators and references to the erased elements.
- A rehash moves elements, so pointers to them dangle
- Inserting never invalidates unordered_map iterators, like std::map
- Inserting while iterating is fine as long as the key is new
- erase on an unordered_map can trigger a rehash
- After a rehash, iteration order stays the same