What the Standard Containers Guarantee

Part I · Module 19 · Chapter 19.1 · What the Standard Containers Guarantee

1. A Container Is a Storage Strategy

The standard library's containers are usually introduced as a list of class templates with overlapping interfaces, and that framing is the reason so many engineers reach for std::vector by habit and std::list by rumour. A more useful framing is that there are only a few genuinely different ways to store a sequence of objects in memory, each of them a trade, and the containers are those strategies wearing a conventional interface.

There are three strategies for sequences. You can put the elements in one contiguous block, which makes reaching the nth element arithmetic and makes growing the block expensive. You can put them in several medium-sized blocks and keep an index of the blocks, which keeps access nearly as cheap, makes growth at either end cheap, and gives up the single pointer that C interfaces want. Or you can give every element its own allocation and link them together, which makes inserting anywhere cheap once you are already there, and makes finding there a walk.

There are two more for keyed lookup. You can keep the keys in sorted order in a balanced tree, which gives you logarithmic lookup and ordered traversal and range queries. Or you can scatter them into buckets by a hash of the key, which gives you constant-time lookup on average and no ordering at all.

Everything in this module is one of those five strategies. std::vector and std::array are the contiguous one, std::deque the blocked one, std::list and std::forward_list the linked one, std::map and std::set the tree, std::unordered_map and std::unordered_set the hash. The container names are conventions; the strategies are the content. Once you can name the strategy, the member functions stop needing to be memorised, because they follow from it: the blocked container has push_front and the contiguous one does not, and that is not an arbitrary API decision.

2. The Four Questions

A container's documentation is long. The part you need in order to choose one is short, and it is the answer to four questions.

How do I reach an element? By index in constant time, by walking from one end, or by key. This is the first filter and it eliminates most of the candidates immediately. If the access pattern is "the 40,000th element, right now," a linked list is out before any measurement.

What does each operation cost as the container grows? Not "how many nanoseconds" — the complexity, the shape of the growth. Chapter 19.8 will show at length that this question's answer is a poor predictor of actual speed, which is exactly why it has to be asked separately from the measurement rather than instead of it.

Which iterators does a modification invalidate? An iterator is a position. Modifying a container can make a position meaningless, and the standard says precisely which modifications do that to which containers. This is a correctness question, not a performance one.

Does an element keep its address? If you take a pointer or a reference to an element and then modify the container, is that pointer still usable? This sounds like the previous question and is not, and §7 measures a container where the two answers differ.

The last two are the ones that cause bugs. The first two cause slowness, which is visible in a profiler; the last two cause undefined behaviour, which is visible in production.

3. Element Access

The access question has three answers across the standard containers, and the vocabulary is worth being precise about because the standard's own terms describe it.

A random-access container lets you reach any element in constant time from its index. std::vector, std::array and std::deque all provide operator[] and an iterator you can add an integer to. For the contiguous two, the arithmetic is the obvious base + n * sizeof(T); for std::deque it is a two-step lookup through the block index, which is still constant time but, as Chapter 19.4 measures, not the same speed.

A bidirectional container lets you step forwards and backwards one element at a time. std::list, std::map and std::set are bidirectional. There is no operator[] on any of them, and this is not an oversight: there is no way to reach the nth element of a linked structure except by taking n steps, so offering the syntax would hide a linear cost behind a constant-looking expression. std::forward_list is weaker still — forward-only — which is why it has no size() either.

Keyed access is map, set and their unordered counterparts, where the question is not "which position" but "which key," and the answer comes back as an iterator or an exception or a default-inserted element depending on which function you called. Chapter 19.5 §3 measures the one of those three behaviours that surprises people.

The important consequence: contiguity is a stronger promise than random access. std::deque offers random access but not contiguity, so it has no data() member, and it cannot be handed to a C function expecting a pointer and a length. Chapter 19.2 §4 measures that interop for the containers that do offer it.

4. Complexity Is a Promise About Shape

The complexity guarantees in the standard are statements about how cost grows with the number of elements, and they are guarantees — a conforming implementation that made std::map::find linear would be non-conforming, not merely slow.

What they are not is a statement about speed. Two operations both documented O(1) can differ by a factor of fifty, and two operations documented O(1) and O(log n) can rank the other way round at every size you will ever use. Chapter 19.8 §6 measures exactly that: a lookup documented O(log n) in a sorted std::vector beat the same lookup in a std::map, which is also O(log n), because the constant hidden inside the notation is where the memory system lives.

So the right use of a complexity table is as a filter and not as a ranking. It tells you which operations will degrade as the data grows, which is the thing you cannot fix later with tuning. An O(n) lookup inside a loop is a design error that gets worse with success; an O(1) lookup that is forty nanoseconds instead of four is a tuning question. Read the table to find the first kind.

One term in the table needs unpacking before §8, because it is the most misread word in the container documentation: amortised.

5. Iterator Invalidation, Measured

An iterator denotes a position in a container. Some modifications destroy positions. The standard specifies which, and the specification is worth knowing from measurement rather than from a table, so here is the measurement.

The program takes a container, records the address of every element, appends one element, and compares. Any element whose address changed has been moved, which means every iterator, pointer and reference that referred to it is now dangling.

template <typename C>
static void addrProbe(const char* name, C& c)
{
    std::vector<const void*> before;
    for (const auto& e : c) before.push_back(&e);

    c.insert(c.end(), *c.begin());          // append one element

    std::vector<const void*> after;
    for (const auto& e : c) after.push_back(&e);

    std::size_t moved = 0;
    for (std::size_t i = 0; i < before.size(); ++i)
        if (before[i] != after[i]) moved++;

    std::printf("%-14s %2zu of %2zu existing elements CHANGED ADDRESS\n",
                name, moved, before.size());
}

Four containers, each holding {1,2,3,4}:

vector(full)    4 of  4 existing elements CHANGED ADDRESS
vector(spare)   0 of  4 existing elements CHANGED ADDRESS
deque           0 of  4 existing elements CHANGED ADDRESS
list            0 of  4 existing elements CHANGED ADDRESS

Two things in that output matter. The first is that the full std::vector moved every element — not the new one, all four of the existing ones — because appending past capacity allocates a new block and relocates the contents. The second is that the same container type moved nothing when it had spare capacity. std::vector's invalidation is conditional on a run-time property, which is why it cannot be reasoned about from the type alone and why §6's rule is stated the way it is.

6. The Vector Case in Detail

Because std::vector is the default container and this is its one sharp edge, it earns its own measurement.

std::vector<int> v{10,20,30,40};
v.shrink_to_fit();                      // make size == capacity
std::printf("capacity before=%zu size=%zu\n", v.capacity(), v.size());
const void* dBefore = v.data();
v.push_back(50);
std::printf("capacity after =%zu  data() %s\n",
            v.capacity(), v.data() == dBefore ? "same" : "MOVED");

capacity before=4 size=4  (full: the next push MUST reallocate)
capacity after =8  data() MOVED  v[0] still 10

The rule that follows is simple to state and easy to violate: any operation that can change a std::vector's capacity invalidates everything — all iterators, all pointers, all references. push_back, emplace_back, insert, resize, reserve and shrink_to_fit are all in that set. An insertion or erasure in the middle additionally invalidates everything from the modification point onward, even when no reallocation happens, because the tail elements shift.

The reason this bites harder than other invalidation rules is that the broken program usually works. The old memory has just been freed, not scribbled on, so a read through the stale pointer often returns the old value. It is undefined behaviour that behaves itself in testing, which is the worst kind. Chapter 13.4 §3's point that nothing objects to this class of error applies without modification; the difference here is that the dangling is caused by an operation that looks like a pure addition.

The habit that avoids it: do not hold a pointer or iterator into a std::vector across a modification of that vector. Hold an index instead. An index survives reallocation because it is not an address.

7. References and Iterators Are Two Different Promises

Here is the distinction that §2 flagged, and it is the single most useful thing in this chapter.

For the node-based containers, every element lives in its own allocation. Inserting another element allocates another node and relinks some pointers; it does not touch the existing nodes. So an element's address is stable for the element's whole lifetime:

std::map<int,int> m; m[0] = 0;
const void* p = &m.at(0);
for (int i = 1; i < 1000; ++i) m[i] = i;
// is &m.at(0) still p?

map:           &m.at(0) UNCHANGED after 999 more inserts

That is std::map's promise and std::list's and std::set's: insertion invalidates nothing at all, and erasure invalidates only iterators and references to the erased element.

Now the interesting one. std::unordered_map is also node-based, but it keeps an array of buckets pointing into those nodes, and when the load factor gets too high it allocates a bigger bucket array and redistributes — a rehash. The nodes themselves are not moved:

unordered_map: &u.at(0) UNCHANGED   buckets 2 -> 1597 (rehashed)

The bucket count went from 2 to 1597, which is unambiguous evidence that a rehash occurred, and the element's address did not change. So std::unordered_map keeps references and pointers valid across a rehash while invalidating iterators. The standard says exactly this, and the reason is visible in the measurement: an iterator into an unordered container has to know its bucket in order to advance to the next element, and rehashing changes which bucket an element is in. The address is fine; the position is meaningless.

Code written as though the two promises were one thing is wrong in both directions. Holding an iterator across an insert into an unordered_map is a bug the measurement above would not catch. Refusing to hold a pointer because "insertion invalidates things" gives up a guarantee you were entitled to.

8. Amortised Constant Is Not Constant

std::vector::push_back is documented as amortised O(1), and the word carries real content.

Any individual push_back is either cheap — write one element, bump the size — or expensive: allocate a bigger block, move every existing element, free the old block. The expensive case is O(n). The claim is about the average over a sequence: because the capacity grows by a constant factor, the expensive case happens rarely enough that n pushes cost O(n) in total, so each one costs O(1) on average.

Chapter 19.3 measures the whole mechanism — the exact capacity sequence, the number of reallocations, and the fact that a thousand appends performed 1,023 element moves on the way. For this chapter the point is narrower and it is about what amortisation does not promise. It does not promise that any particular push_back is fast. A real-time path with a deadline cannot rely on an amortised bound, because the one call in a thousand that reallocates will blow the deadline even though the average is fine. The fix is reserve, which converts the amortised guarantee into an actual one by making the expensive case happen zero times; Chapter 19.3 §4 measures the difference as 15 allocations down to 1.

The same word appears on std::deque's push_front and push_back for the same reason, and std::unordered_map::insert is amortised O(1) because of rehashing — the operation that §7 just measured.

9. What a Container Requires of Its Elements

A container is a class template, and Chapter 18.4 §3 established that each instantiation is a separate, unrelated type generated from the template. Chapter 18.2 §3 established the other half: a template requires of its argument only the operations its body actually uses, and those requirements are documented rather than enforced.

Both facts apply directly here, and together they explain the shape of the diagnostics you get when an element type is unsuitable. std::vector<T> needs T to be destructible to do almost anything, copyable or movable to grow, and default-constructible only for the operations that create elements from nothing — resize(n) and the sizing constructor. std::map<K,V> needs K to be comparable with < by default. std::unordered_map<K,V> needs K to be hashable and equality-comparable.

When one of those is missing, the failure appears deep inside a library header, with your line mentioned in a "in instantiation of" note — the exact diagnostic shape Chapter 18.6 §5 measured. Chapter 19.5 §4 shows a clean example: a map whose value type has no default constructor compiles fine until the first operator[], and then reports no matching constructor for initialization of 'NoDefault' from inside pair.h.

The practical reading: a container's element requirements are part of its interface, they are checked at the point where you use the operation rather than where you declare the container, and the error will not name the container.

10. The Guarantee Table

This is the table the module is built on. Every entry is the standard's guarantee, and the ones marked measured appear in this chapter's or a later chapter's output.

The two bold columns are the ones worth memorising, because they are the correctness half of §2 and the only place in the table where two adjacent cells disagree. vector invalidates both together; unordered_map invalidates one and not the other.

11. Erasure Is a Separate Row

Insertion gets most of the attention and erasure has its own rules, which are simpler but still worth stating because one of them is the basis of a common bug.

For the node-based containers — list, map, set, and the unordered pair — erasing an element invalidates iterators and references to that element only. Everything else is untouched. The measurement in Chapter 19.5 §6 shows an iterator to key 5 still usable after erase(4).

For vector and deque, erasing invalidates everything at or after the erasure point, because the tail shifts down to close the gap.

The bug this creates is the erase-in-a-loop:

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == target) v.erase(it);        // 'it' is now invalid; ++it is UB

Every container's erase returns an iterator to the element after the erased one, which is what makes the correct form possible:

for (auto it = v.begin(); it != v.end(); )
    if (*it == target) it = v.erase(it);   // adopt the returned iterator
    else               ++it;

Module 20 covers the better answer for the contiguous containers — std::erase_if, or the remove-erase idiom it replaced — which does the whole job in one pass instead of one shift per removal.

12. Exception Safety Is Also a Guarantee

The containers make promises about what is true if an operation throws, and they are worth knowing because they are the reason some container code is written the way it is.

push_back on a std::vector is strongly exception-safe when the element type's move constructor is noexcept: either the element is appended or the vector is unchanged. The qualifier is doing real work. If reallocation has to move existing elements and a move throws part-way, the vector cannot restore the original block, so it cannot offer the strong guarantee — which is why the library uses copies instead of moves when the move is not noexcept, trading speed for safety. Chapter 13.8 §7's point about marking move operations noexcept is exactly this mechanism, and Chapter 19.3 §3 measures the library choosing moves when the guarantee is available.

std::map::insert is strongly exception-safe without qualification: the node is allocated and constructed before anything is relinked, so a throw leaves the tree as it was.

The general shape is that single-element insertions are strongly safe and multi-element ones usually are not, which is why a loop of push_back is not interchangeable with one insert of a range when exceptions are in play.

13. What to Actually Do

• Choose from the access pattern first. Which operations have to be fast, and how is the data traversed? That eliminates most candidates before any other consideration.
• Default to std::vector. Chapter 19.2 argues this at length with measurements. Deviate when a specific guarantee in §10's table requires it, and be able to name the column.
• Read the invalidation paragraph, not just the complexity table. Separately for iterators and for references.
• Inside a vector, hold an index rather than a pointer or iterator across any modification.
• Inside a node-based container, a pointer to an element is genuinely stable — use it rather than working around a restriction that does not apply.
• In an unordered container, trust pointers and distrust iterators across insertion.
• Use reserve when the final size is known, which turns an amortised bound into a real one.
• Adopt the iterator that erase returns rather than incrementing the one you just invalidated.

14. Mistakes Worth Making Once

Holding a pointer across push_back. The program works in testing because the freed block still holds the old bytes — §6 measured v[0] reading 10 after relocation. Make this once with a sanitizer on and you will never make it again.

Assuming operator[] exists because the container is "a sequence." std::list has no operator[], and the reason is a feature: the syntax would hide a linear walk.

Treating iterator invalidation and reference invalidation as one rule. §7's measurement is the counterexample, and it goes wrong in both directions.

Reading "amortised O(1)" as "O(1)". Fine for throughput, wrong for a deadline.

Choosing std::list because the complexity table says insertion is O(1). True per operation and almost always irrelevant, because you have to find the position first. Chapter 19.4 §6 and Chapter 19.8 §8 measure both halves of that.

Trusting std::deque to be contiguous because it has operator[]. Random access and contiguity are different promises; deque has one and not the other, and there is no data() member to catch the mistake.

15. Interview Relevance

The frozen curriculum marks this chapter High, and the questions are predictable because they test whether you have read the guarantees or absorbed the folklore.

"When are std::vector iterators invalidated?" The complete answer names the condition — any capacity change, so push_back, insert, resize, reserve, shrink_to_fit — and adds that a middle insertion or erasure invalidates from that point on even without reallocation.

"Does inserting into a std::map invalidate iterators?" No, and the follow-up is why: every element is its own node, so insertion relinks rather than relocates.

"What about unordered_map?" This is the discriminating question. Iterators yes, on rehash; references and pointers no, ever. Being able to say that cleanly, and to explain that an iterator needs its bucket while an address does not, is a strong signal.

"What does amortised mean?" That the average over a sequence is constant while an individual operation may be linear, and that reserve removes the linear case.

"How do you choose a container?" The four questions in §2, in order, with the complexity table used as a filter and the invalidation rules as a constraint. Chapter 19.7 builds this into a decision path.

16. What You Should Be Able to Say Now

• That there are five storage strategies in the standard library and every container is one of them.
• The four questions, and which two of them are correctness rather than performance.
• That a std::vector's invalidation depends on a run-time property, so the type alone cannot tell you.
• That node-based containers keep element addresses stable for the element's lifetime.
• That unordered_map invalidates iterators on rehash and never invalidates references, with the bucket explanation for why.
• What amortised promises and what it does not.
• That complexity filters rather than ranks, and that Chapter 19.8 will measure an O(log n) container beating another O(log n) container.

17. Exercises

Exercise 1 — the probe. Reproduce §5's addrProbe and run it on std::deque with 2,000 elements rather than 4. Explain the result using Chapter 19.4 §4's block structure.

Exercise 2 — the conditional rule. Write a program that calls push_back ten times on a std::vector and prints, before each call, whether that call will invalidate iterators. Use only size() and capacity().

Exercise 3 — the two promises. Build an unordered_map, hold both a pointer and an iterator to one element, insert enough to force a rehash, and show by measurement that the pointer is still correct. Explain why printing through the iterator would not be a valid test.

Exercise 4 — erase in a loop. Write the broken loop from §11, run it under a sanitizer, and then fix it with the returned iterator.

Exercise 5 — the table from memory. Reconstruct §10's two invalidation columns for all eight containers, then check them against the output of your own probe.

Exercise 6 — amortised. Time 100,000 individual push_back calls and print the ten slowest. Relate the pattern to the capacity sequence Chapter 19.3 §1 measures.

Exercise 7 — requirements. Put a type with no operator< into a std::map and read the diagnostic. Identify which library header reports it and which line of yours is named.

18. Summary

• A container is a storage strategy, and there are five of them in the standard library.
• Four questions decide a choice: element access, complexity, iterator invalidation, reference stability.
• Two of the four are correctness questions whose failures are invisible — undefined behaviour that usually works.
• Measured: one push_back on a full std::vector moved 4 of 4 existing elements; the same type with spare capacity moved 0 of 4. Invalidation is a run-time property.
• Measured: std::map kept an element's address across 999 further insertions.
• Measured: std::unordered_map kept an element's address while its bucket count went 2 → 1597 — references survive a rehash, iterators do not.
• Complexity filters, it does not rank; Chapter 19.8 measures the reversal.
• Amortised O(1) is a promise about the average, and reserve converts it into a real bound.
• Erasure invalidates only the erased element in node-based containers, and everything after it in the contiguous ones — so adopt the iterator erase returns.

The rest of the module applies this chapter's four questions to each strategy in turn and measures what the guarantees cost. Chapter 19.2 starts with the contiguous pair, std::array and std::vector, and makes the case that std::vector is the right default for a sequence — not by assertion, but by measuring what the alternatives give up. Chapter 19.3 then takes std::vector's one sharp edge, the capacity change that §6 measured here, and follows it all the way down: the exact growth sequence, how many times your elements get moved, and what reserve removes.