STL Containers — choose by guarantees, not by name
Picking a container is one of the first technical decisions in any data structure and one of the most common topics on a C++ interview. Easy to get wrong: std::list looks attractive for "frequent middle insertions" until profiling shows it 3× slower than std::vector on real data because of a cache miss per node. std::unordered_map looks like the obvious "fast lookup" until its hash function degrades on adversarial keys.
In C++ an "STL container" is not just a data structure — it is a bundle of four things: a storage model (array, tree, hash), an iterator interface, an invalidation policy, and an allocator template parameter. All standard algorithms (std::sort, std::find, ranges) work through the iterator interface without knowing the underlying container. Allocators let you change where the memory comes from without changing the algorithm.
The right container choice is the choice of guarantees: what complexity, what ordering, what iterator stability, what memory model do you want. The full map lives in the layers below.
Topic map
- Sequence containers and adapters —
vector,deque,list,forward_list,array;stack/queue/priority_queueadapters; growth strategy and cache locality. - Ordered associative containers —
map,set,multimap,multiseton a red-black tree; range queries,lower_bound, custom comparators. - Unordered associative containers —
unordered_map/set; hash table, load factor, rehash, hash quality, hash collision attack. - Iterators and invalidation — iterator categories, range-based for, invalidation rules after
insert/erase/push_back. - Allocators and std::pmr —
std::allocator, custom allocators as part of the type, polymorphic memory resources from C++17, monotonic buffer.
Complexity at a glance
| Container | Find | End insert | Mid insert | Random access |
|---|---|---|---|---|
vector | O(n) | O(1) amortized | O(n) | O(1) |
deque | O(n) | O(1) | O(n) | O(1) |
list | O(n) | O(1) | O(1) after find | — |
map | O(log n) | O(log n) | O(log n) | — |
unordered_map | O(1) avg | O(1) avg | O(1) avg | — |
set | O(log n) | O(log n) | O(log n) | — |
Common traps
| Mistake | Consequence |
|---|---|
Holding a reference/pointer to a vector element across push_back | Reallocation → UB, reference points at freed memory |
operator[] on std::map to check for a key | Silently inserts a default-valued element |
Picking std::list because mid-insert is O(1) | On small/medium data it loses to vector due to cache misses |
unordered_map without a good hash on external keys | Hash collision attack — degrades to O(n) |
| Combining hashes with symmetric XOR | hash(a) ^ hash(b) == hash(b) ^ hash(a) — extra collisions |
Treating std::vector<int> and std::vector<int, MyAlloc> as one type | They are different template instantiations |
Indexing vector with [i] and no bounds check | UB on overflow; use .at(i) for the checked version |
Assuming adapter pop() returns a value | It does not — by design, for exception safety; use top() + pop() |
Using an iterator after unordered_map rehash | Invalidated; re-query needed |
Custom comparator using <= instead of < | Breaks strict weak ordering → UB in the RB-tree |
Interview relevance
Containers appear on almost every C++ interview, from junior to staff. Reason: container choice exposes your understanding of complexity, the memory model, and trade-offs — the things that separate a confident engineer from someone who "knows the syntax".
Typical checks:
- How
vectorandlistdiffer in actual speed, not just Big-O. vectorgrowth strategy and whatpush_backinvalidates.mapvsunordered_map— which guarantees, when to pick which.- What load factor is and when rehash happens.
- Iterator categories and invalidation rules.
- Why
operator[]onmapis dangerous and how to avoid it. - What
std::pmris and why it exists. - How to build an LRU cache on top of standard containers (
list+unordered_map).
Common wrong answer: "I pick list because mid-insert is O(1)." That opens the discussion of amortized complexity vs hardware reality, where cache misses often dominate the count of comparisons.