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

WHY these containers exist (the big picture)

WHAT decides speed? The memory layout:

Contiguous array (vector, array, deque-ish): index math gives $O(1)$ random access, but inserting in the middle shifts everything ( $O(n)$ ).
Linked nodes (list): each node points to the next, so splicing is $O(1)$ , but you can't jump to index $k$ — you must walk ( $O(n)$ ).
Balanced binary search tree (set/map): keeps keys sorted, so search/insert/erase are $O(\log n)$ and you can iterate in sorted order.
Hash table (unordered_*): a hash function scatters keys into buckets, giving average $O(1)$ search/insert — but no order, and worst case $O(n)$ on collisions.

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

Container	Random access	Insert/erase middle	Insert front	Insert back	Search by value	Ordered?
`array`	$O(1)$	— (fixed)	—	—	$O(n)$	insertion
`vector`	$O(1)$	$O(n)$	$O(n)$	amort. $O(1)$	$O(n)$	insertion
`deque`	$O(1)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$	insertion
`list`	$O(n)$	$O(1)$ *	$O(1)$	$O(1)$	$O(n)$	insertion
`set`/`map`	—	$O(\log n)$	—	—	$O(\log n)$	sorted
`unordered_*`	—	$O(1)$ avg	—	—	$O(1)$ avg	no

Worked examples

Worked example 1. Choosing for "frequency count of words"

Need: map each word → count, fast lookups, order doesn't matter.

unordered_map<string,int> freq;
for (auto& w : words) freq[w]++;   // O(1) average per word

Why this step? freq[w] default-constructs the value to 0 if missing, then ++. Hash table gives $O(1)$ average — total $O(N)$ for $N$ words. A map would work but adds a $\log$ factor and we don't need sorted output.

Worked example 2. "Insert in the middle a million times"

list<int> L;
auto it = L.begin();
// ... advance it to the spot, then:
L.insert(it, x);   // O(1) — just relinks pointers

Why this step? With a vector, each middle insert shifts up to $n$ elements ( $O(n)$ ). With list, given the iterator, it's pure pointer surgery — $O(1)$ . (But getting to the iterator can cost $O(n)$ , so this wins only when you already hold the position.)

Worked example 3. "Keep a sorted set of scores, allow duplicates, get the smallest"

multiset<int> scores;
scores.insert(50); scores.insert(50); scores.insert(20);
int smallest = *scores.begin();      // 20, O(1) after sort kept by tree
scores.erase(scores.begin());        // remove ONE smallest, O(log n)

Why this step? multiset keeps elements sorted at all times, so begin() is the minimum. We use multiset not set because duplicate 50s must be kept. erase(iterator) removes a single element; erase(value) would remove all copies.

Worked example 4. Iterating a map in sorted key order

map<string,int> m = {{"banana",3},{"apple",5}};
for (auto& [k,v] : m) cout << k << " " << v << "\n";
// prints apple 5, then banana 3  (alphabetical)

Why this step? map is tree-based ⇒ iteration yields keys in sorted order for free. unordered_map would print in arbitrary bucket order.

Common mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine ways to keep your toys. A vector/array is a long shelf — you can grab toy #7 instantly, but to squeeze a new toy in the middle you must slide everyone over. A list is toys holding hands in a chain — you can splice a new friend between two hands instantly, but to find the 7th toy you must walk the chain counting. A deque is a shelf open at both ends, so you can add at the front or back easily. A set/map is a librarian who always keeps toys in alphabetical order — finding any toy is quick because she knows where things go. An unordered_map is a wall of labelled bins — you compute which bin a toy belongs to and toss it straight in (super fast), but the toys end up in no neat order.

Flashcards

Which container gives O(1) random access AND amortised O(1) push_back?

std::vector

Why is vector's push_back amortised O(1) despite resizing?

Resizing doubles capacity, so the O(n) copies happen rarely; total copy work over n pushes is < 2n, averaging O(1).

What is the key difference between set and multiset?

set stores unique keys; multiset allows duplicate keys (both kept sorted).

What underlying data structure backs set/map?

A self-balancing binary search tree (red-black tree), giving O(log n) operations and sorted iteration.

What backs unordered_map/unordered_set?

A hash table — average O(1), no ordering, worst case O(n).

When should you prefer map over unordered_map?

When you need sorted iteration, range queries (lower_bound/upper_bound), or guaranteed log worst case.

Complexity of inserting in the middle of a vector vs a list (with iterator)?

vector O(n) (shifts elements); list O(1) (relinks pointers).

What container allows O(1) push_front and push_back plus O(1) random access?

std::deque.

How do you erase exactly ONE element from a multiset by value?

ms.erase(ms.find(value)) — passing the value directly (ms.erase(value)) erases ALL matches.

What invalidates vector iterators/pointers?

A reallocation (e.g. push_back beyond capacity) moves the array; reserve() avoids it.

Difference between std::array and std::vector?

array is fixed compile-time size, on stack, no resize; vector is dynamic, heap-allocated, grows.

Why does a balanced BST give O(log n) search?

Its height is ~log2(n), and search visits at most one node per level, halving the search space each step.

Connections

Big-O notation — the language of these tradeoffs.
Amortised analysis — justifies vector's O(1) push_back.
Hash functions and collisions — why unordered_* averages O(1).
Red-black trees / Binary search trees — engine behind set/map.
Iterators in C++ — invalidation rules differ per container.
Cache locality — why contiguous vector often beats list in practice.
STL algorithms (sort, find, lower_bound) — operate on these containers.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, STL containers ka pura funda ek hi baat par tika hai: har container ek tradeoff hai. Koi bhi structure sab kuch fast nahi kar sakta. Agar tumhe index se turant element chahiye (jaise v[7]), toh vector ya array lo — yeh contiguous memory mein rehte hain, isliye jump O(1) hota hai. Lekin beech mein insert karoge toh saare elements shift karne padenge, that's O(n). Iska ulta list hai — yeh nodes ki chain hai jahan har node next/prev pointer rakhta hai, toh beech mein insert karna O(1) (bas pointer jodo), par 7th element dhoondhne ke liye poori chain walk karni padegi.

deque ek mast cheez hai — front aur back dono taraf se O(1) mein add kar sakte ho, aur index access bhi milta hai. Jab queue/sliding window banana ho toh yeh kaam aata hai. array fixed size ka hota hai, compile time pe size pata hota hai, stack pe rehta hai — zero overhead.

Ab associative wale: set aur map andar se balanced binary search tree (red-black tree) hote hain, isliye sab kuch sorted rehta hai aur operations O(log n) lagte hain. Iska bonus yeh ki iterate karoge toh sorted order milega free mein. multiset/multimap mein duplicate keys allowed hain. unordered_map aur unordered_set hash table hain — average O(1), bohot fast, par order kuch nahi milta aur worst case O(n) ho sakta hai agar collisions zyada ho.

Practical rule yaad rakho: by default vector use karo (cache friendly, fastest in real life). Sorted chahiye ya range query (lower_bound) chahiye toh map. Sirf fast lookup chahiye aur order ki parwah nahi toh unordered_map. Aur ek bada trap: multiset.erase(value) saare matching elements uda deta hai — sirf ek hatana

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

WHY these containers exist (the big picture)

The sequence containers

The associative containers

Cheat-sheet of complexities

Worked examples

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — C++ Programming

Connections