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

(a) ==std::array<T, 30> — fixed size known at compile time, lives on the stack, zero overhead. (b) std::vector== — contiguous, $O(1)$ index v[i], amortised $O(1)$ push_back. (c) ==std::map<string,int>== — tree-based, so iteration is in sorted key order for free. (d) ==std::deque== — the only sequence container with amortised $O(1)$ at both ends.

Why not swap them? A vector for (d) pays $O(n)$ per push_front because every element must shift right one slot. An unordered_map for (c) would print in arbitrary bucket order — it has no ordering to give you.

• vector random access: ==$O(1)$== — one multiply-and-add on the base pointer.
• list random access: ==$O(n)$== — nodes are scattered, you must walk next pointers.
• set search: ==$O(\log n)$== — a balanced red-black tree halves the search space each level.
• unordered_set search (average): ==$O(1)$== — a hash jumps straight to the bucket.

Resizes trigger just before sizes $1,2,4,\dots ,512$ (the powers of two $\le 1000$). At a resize from capacity $m$ you copy the $m$ existing elements. Total copies: $T=1+2+4+\cdots +512={\sum }_{i=0}^9{2}^i=2^{10}-1=1023.$ Why this sum? A geometric series $1+2+\cdots +2^k=2^{k+1}-1$. Here $2^9=512\le 1000$, so $k=9$. $1023<2n=2000$, so copy work is $<2n$. Spread over $n$ pushes ⇒ $T/n\approx 1$, i.e. amortised ==$O(1)$== per push. See Amortised analysis.

• map: each insert $O(\log N)$ ⇒ $N\log N$ total; iteration already sorted, $O(N)$. Grand total ==$O(N\log N)$==.
• unordered_map: inserts $O(N)$ average, but to get sorted output you copy the $N$ keys and sort them: $O(N\log N)$. Grand total ==$O(N\log N)$== too.

Conclusion: same asymptotic class. The map wins on simplicity (order is free), while unordered_map might win on raw insert speed but then pays the sort. Neither is "always faster."

Binary search to find the slot is $O(\log n)$ — cheap. But inserting into the middle of a vector shifts every element after it right by one: up to $O(n)$ copies per insert (see the orange shifted block in the figure). Over $n$ inserts: $\text{total}={\sum }_{k=1}^{n}O(k)=O(n^2).$ The binary search does not save you — the shift dominates. Fix: a ==std::multiset== (tree-based). Each insert is $O(\log n)$ including placement, total $O(n\log n)$, and it stays sorted with duplicates allowed.

An unordered_map scatters keys into buckets via a hash function. If many keys collide into one bucket, that bucket becomes a linked chain of length up to $n$; a lookup must scan the whole chain — $O(n)$. This happens with a bad hash or an adversarial input set. A map is a red-black tree whose height is guaranteed $\le 2{\log }_2(n+1)$ by the balancing rules, so search is always $O(\log n)$ — there is no worst case to fear. The tradeoff: $O(\log n)$ average is slower than the hash's $O(1)$ average when the hash behaves.

Two phases:

1. Count with an ==unordered_map<string,int>== — freq[w]++ is $O(1)$ average, total $O(N)$.
2. Rank by moving the pairs into a vector<pair<string,int>> and sorting with a custom comparator: higher count first, alphabetical on ties. Sorting $D$ distinct words is $O(D\log D)$.

unordered_map<string,int> freq;
for (auto& w : words) freq[w]++;
vector<pair<string,int>> v(freq.begin(), freq.end());
sort(v.begin(), v.end(), [](auto& a, auto& b){
    if (a.second != b.second) return a.second > b.second; // count desc
    return a.first < b.first;                             // word asc
});
for (auto& [w,c] : v) cout << w << " " << c << "\n";

Why this split? Counting needs raw lookup speed (no order) → hash map. Ranking needs a custom order the hash map can't provide → dump to a vector and sort. Total ==$O(N+D\log D)$==, and since $D\le N$ this is $O(N\log N)$. Uses std::sort.

Use two multiset<int> halves: lo (the smaller half, whose largest is *lo.rbegin()) and hi (the larger half, whose smallest is *hi.begin()). Keep sizes balanced so lo has the same count as hi or exactly one more.

• Insert: put x into lo or hi by comparing to the current median, then rebalance by moving one boundary element across if sizes differ by 2. Each step is $O(\log n)$.
• Erase one copy: s.erase(s.find(x)) — note find gives an iterator so only one copy is removed; erase(x) would wipe all copies (that's the L5 trap below). $O(\log n)$.
• Median: if sizes equal, average *lo.rbegin() and *hi.begin(); else *lo.rbegin(). $O(1)$.

Why multiset not set? Duplicates must be storable — the same integer can appear many times. All ops are ==$O(\log n)$==.

Starting size = 4. (a) ms.erase(5) passes a value ⇒ removes every 5. Three fives gone. Size = ==$1$== (just the 7). (b) ms.erase(ms.find(5)) passes an iterator to one 5 ⇒ removes exactly one element. Size = ==$3$== (two 5s and a 7).

The rule: value-erase deletes all matches; iterator-erase deletes exactly one.

No — it is undefined behaviour. The vector was full (capacity 3, size 3), so push_back(4) allocates a new, larger block, copies 1,2,3,4 into it, and frees the old block. p still points at the freed old memory — it is a dangling pointer. Reading *p may print 1, garbage, or crash. Fix: re-fetch after any insertion that may reallocate, or reserve enough capacity up front so no reallocation occurs while you hold p. See Iterators in C++ — the same invalidation applies to iterators and references.

No single standard container gives both. unordered_map gives $O(1)$ lookup but has no order; map gives sorted iteration but $O(\log n)$ lookup. You must pick one primary structure:

• If lookups vastly outnumber ordered scans → keep an unordered_map, and when you occasionally need sorted output, copy keys to a vector and sort ($O(D\log D)$, done rarely).
• If ordered iteration is frequent → use a map and accept $O(\log n)$ lookups.

There is no free lunch: the parent note's ONE idea — every container is a chosen tradeoff — is exactly what forbids a container that is simultaneously unordered-fast and order-preserving.

I can name the right container for a given access pattern ::: L1 done I can amortise doubling and get $<2n$ copies for $n$ pushes ::: L2 done I can explain why sorted-vector insert is $O(n^2)$ and multiset fixes it ::: L3 done I can design a two-multiset median tracker at $O(\log n)$ ::: L4 done I know value-erase vs iterator-erase and pointer invalidation on reallocation ::: L5 done