Question bank — STL containers — vector, list, deque, array, set, multiset, map, multimap, unordered_map, unordered_set

multiset<int> ms{50,50,20}; ms.erase(50);
``` — how many elements remain? ::: One (the `20`) — value-`erase` removes **every** copy of `50`, deleting both. To drop a single `50` you must pass an iterator: `ms.erase(ms.find(50))`.
 
```cpp
vector<int> v{1,2,3}; int* p=&v[0]; v.push_back(4); *p=9;
``` — what's wrong? ::: The `push_back` may reallocate, moving the array; `p` then dangles and `*p=9` is undefined behaviour. Re-fetch pointers/iterators after any insert, or `reserve()` first.
 
```cpp
map<string,int> m; if (m["missing"] == 0) { /*...*/ }
``` — subtle bug? ::: `m["missing"]` **inserts** a default `0` for a key that wasn't there, silently growing the map. Use `m.find("missing") == m.end()` or `m.count("missing")` to test presence without inserting.
 
```cpp
for (auto it=s.begin(); it!=s.end(); ++it) if (*it<0) s.erase(it);
``` — why does this break? ::: `erase(it)` invalidates `it`, so the following `++it` is undefined. Fix with the returned iterator: `it = s.erase(it);` (and only `++it` when you don't erase).
 
```cpp
set<int> s; auto it=s.insert(5).first; *it = 6;
``` — legal? ::: No — a `set` element **is** its key; mutating it through the iterator would break the tree's ordering, so `set` iterators are effectively `const`. Erase and re-insert instead.
 
```cpp
unordered_map<int,int> u{{1,10}}; u.reserve(1000); auto* p=&u[1]; u[2]=20; /* use *p */
``` — safe? ::: Reserving ahead means the second insert won't rehash, so `p` (pointer to a *mapped value*) stays valid. Note: rehash invalidates *iterators* but **not** references/pointers to elements — a subtlety unique to unordered containers.
 
---
 
## Why questions
 
Why is `list::insert` $O(1)$ but `vector::insert` in the middle $O(n)$? ::: `list` just relinks two `prev`/`next` pointers, touching nothing else. `vector` is contiguous, so a middle insert must shift every later element up by one slot to make room.
 
Why do we *ever* pick `map` over `unordered_map` given $O(1)$ vs $O(\log n)$? ::: Because `map` gives sorted iteration and range queries (`lower_bound`, `upper_bound`) for free, and has a hard $O(\log n)$ worst case, whereas `unordered_map` offers none of that and degrades to $O(n)$ on bad [[Hash functions and collisions|collisions]].
 
Why is `vector`'s amortised cost $O(1)$ even though single pushes can cost $O(n)$? ::: Doubling makes reallocations rare; the total copy work over $n$ pushes is a geometric sum $1+2+4+\dots < 2n$, so spreading it out gives $<3n/n = O(1)$ per push (see [[Amortised analysis]]).
 
Why does `deque` give $O(1)$ `push_front` when `vector` gives $O(n)$? ::: `deque` keeps a *block map* and can prepend a new chunk (or fill an existing front chunk) without moving old data. `vector` has only one block, so front-insert must shift all elements right.
 
Why is a balanced tree's height $\approx \log_2 n$ and why does that matter? ::: Level $i$ holds up to $2^i$ nodes, so $n$ nodes need height $h \ge \log_2(n+1)-1$; each search descends one level per comparison, giving $O(\log n)$ (see [[Big-O notation]]).
 
Why can `unordered_map` still hit $O(n)$ despite "$O(1)$ average"? ::: If many keys hash to the same bucket (a bad hash or an adversarial input), that bucket's chain becomes a linear list and a lookup walks all of it — the average collapses to the worst case.
 
Why does `array` beat `list` for a simple sum-all loop even with equal $O(n)$? ::: `array` is contiguous, so the CPU prefetches neighbours into cache; `list` nodes are scattered, causing a [[Cache locality|cache miss]] per node — same Big-O, wildly different constant.
 
---
 
## Edge cases
 
What does `*ms.begin()` return on an empty `multiset`? ::: Undefined behaviour — `begin()==end()` when empty, and dereferencing `end()` is illegal. Always guard with `if (!ms.empty())` first.
 
Erasing `s.erase(value)` on a `set` when `value` is absent — crash? ::: No — value-`erase` returns the *count removed* (`0` here) and does nothing. It's `erase(iterator)` that requires a valid iterator and is unsafe on `end()`.
 
Can you `push_back` on a `std::array`? ::: No — `array` is ==fixed-size==, so it has no `push_back`, `insert`, or `resize`; its `N` is baked in at compile time.
 
What is `v.size()` vs `v.capacity()` after `vector<int> v; v.reserve(100);`? ::: `size()` is `0` (no elements yet) but `capacity()` is at least `100` — `reserve` allocates room without constructing elements, so future pushes won't reallocate up to that point.
 
Inserting into a `map` — are existing iterators invalidated? ::: No — tree-based associative containers keep every node in place on insert, so all iterators/references stay valid (only `erase` invalidates the one erased element). This is the opposite of `vector`.
 
Rehashing an `unordered_set` — what survives? ::: Element **pointers and references survive**, but **iterators are invalidated** because the bucket structure is rebuilt. Reserve up front if you must hold iterators across inserts.
 
What order does `map<int,int>{{3,0},{1,0},{2,0}}` iterate in? ::: `1, 2, 3` — keys, not insertion order; the tree sorts on the key the moment each pair is inserted.
 
---
 
> [!recall]- One-line summary of the traps
> Guarantees ::: `map`/`set` = sorted + $O(\log n)$ worst case; `unordered_*` = $O(1)$ average, no order, $O(n)$ worst.
> Iterator survival ::: `vector` insert may invalidate all; `map`/`set` insert invalidates none; unordered rehash kills iterators but not references.
> `erase(value)` ::: removes **all** matches on multiset/multimap (and 0-or-more on set/map); pass an iterator to remove exactly one.