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

5.2.19 · Coding › C++ Programming

YE containers kyun exist karte hain (big picture)

Speed kya decide karta hai? Memory layout:

Contiguous array (vector, array, deque-ish): index math $O (1)$ random access deta hai, lekin beech mein insert karne pe sab kuch shift hota hai ( $O (n)$ ).
Linked nodes (list): har node agle ki taraf point karta hai, toh splicing $O (1)$ hai, lekin tum seedha index $k$ pe jump nahi kar sakte — tumhe walk karna padega ( $O (n)$ ).
Balanced binary search tree (set/map): keys ko sorted rakhta hai, toh search/insert/erase $O (lo g n)$ hain aur tum sorted order mein iterate kar sakte ho.
Hash table (unordered_*): ek hash function keys ko buckets mein scatter karta hai, average $O (1)$ search/insert deta hai — lekin koi order nahi, aur collisions pe worst case $O (n)$ ho sakta hai.

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 (lo g n)$	—	—	$O (lo g n)$	sorted
`unordered_*`	—	$O (1)$ avg	—	—	$O (1)$ avg	no

Worked examples

Worked example 1. "Words ki frequency count" ke liye choose karna

Chahiye: har word ko → count map karo, fast lookups, order matter nahi karta.

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

Yeh step kyun? freq[w] missing hone pe value ko 0 pe default-construct karta hai, phir ++. Hash table $O (1)$ average deta hai — $N$ words ke liye total $O (N)$ . map kaam karta lekin ek $lo g$ factor add karta aur humein sorted output nahi chahiye.

Worked example 2. "Beech mein ek million baar insert karna"

list<int> L;
auto it = L.begin();
// ... it ko jagah pe advance karo, phir:
L.insert(it, x);   // O(1) — bas pointers relink hote hain

Yeh step kyun? vector ke saath, har middle insert $n$ elements tak shift karta hai ( $O (n)$ ). list ke saath, iterator diya ho toh yeh pure pointer surgery hai — $O (1)$ . (Lekin iterator tak pahunchna $O (n)$ cost kar sakta hai, toh yeh tab hi faida karta hai jab tumhare paas already position ho.)

Worked example 3. "Scores ka sorted set rakho, duplicates allow ho, sabse chhota milna chahiye"

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)

Yeh step kyun? multiset elements ko hamesha sorted rakhta hai, toh begin() minimum hai. Hum set ki jagah multiset use karte hain kyunki duplicate 50s rakhne hain. erase(iterator) ek single element remove karta hai; erase(value) sari copies remove kar deta.

Worked example 4. Map ko sorted key order mein iterate karna

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

Yeh step kyun? map tree-based hai ⇒ iteration keys ko sorted order mein yield karta hai free mein. unordered_map arbitrary bucket order mein print karta.

Common mistakes (Steel-manned)

Recall Feynman: 12-saal ke bacche ko explain karo

Socho apne toys rakhne ke alag-alag tarike. Vector/array ek lambi shelf hai — tum seedha toy #7 instantly grab kar sakte ho, lekin beech mein naya toy squeeze karne ke liye sabko slide karna padega. List toys ki ek chain hai jahan woh ek doosre ka haath pakde khade hain — do haathon ke beech naya dost instantly splice ho sakta hai, lekin 7th toy dhundhne ke liye chain mein count karte chalte rehna padega. Deque ek shelf hai jo dono ends pe khuli hai, toh front ya back mein asaani se add kar sakte ho. Set/map ek librarian ki tarah hai jo toys ko hamesha alphabetical order mein rakhti hai — koi bhi toy dhundhna jaldi hota hai kyunki use pata hai cheezein kahan jaati hain. Unordered_map labeled bins ki ek wall hai — tum compute karte ho kaunse bin mein toy jaayega aur seedha toss karte ho (super fast), lekin toys kisi neat order mein nahi aate.

Flashcards

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

std::vector

Vector ka push_back amortised O(1) kyun hai resize hone ke baavajood?

Resizing capacity double karta hai, toh O(n) copies rarely hoti hain; n pushes mein total copy work < 2n hota hai, average O(1) nikalta hai.

set aur multiset mein key difference kya hai?

set unique keys store karta hai; multiset duplicate keys allow karta hai (dono sorted rehte hain).

set/map ke peeche kaunsa underlying data structure hai?

Ek self-balancing binary search tree (red-black tree), jo O(log n) operations aur sorted iteration deta hai.

unordered_map/unordered_set ke peeche kya hai?

Ek hash table — average O(1), koi ordering nahi, worst case O(n).

map ko unordered_map ke upar kab prefer karna chahiye?

Jab sorted iteration chahiye, range queries (lower_bound/upper_bound) chahiye, ya guaranteed log worst case chahiye.

vector vs list mein beech mein insert karne ki complexity (iterator ke saath)?

vector O(n) (elements shift hote hain); list O(1) (pointers relink hote hain).

Kaunsa container O(1) push_front aur push_back ke saath O(1) random access bhi deta hai?

std::deque.

Multiset se exactly EK element value se kaise erase karein?

ms.erase(ms.find(value)) — value directly pass karna (ms.erase(value)) SAARI matches erase kar deta hai.

Vector iterators/pointers ko kya invalidate karta hai?

Ek reallocation (jaise capacity se zyada push_back) array ko move karta hai; reserve() isse avoid karta hai.

std::array aur std::vector mein difference?

array fixed compile-time size ka hota hai, stack pe, resize nahi hota; vector dynamic hai, heap-allocated hai, grow karta hai.

Balanced BST O(log n) search kyun deta hai?

Iski height ~log2(n) hoti hai, aur search har level pe zyada se zyada ek node visit karta hai, har step pe search space half karta jaata hai.

Connections

Big-O notation — in tradeoffs ki language.
Amortised analysis — vector ke O(1) push_back ko justify karta hai.
Hash functions and collisions — kyun unordered_* average O(1) hota hai.
Red-black trees / Binary search trees — set/map ka engine.
Iterators in C++ — invalidation rules har container ke liye alag hain.
Cache locality — kyun contiguous vector aksar practice mein list se better perform karta hai.
STL algorithms (sort, find, lower_bound) — in containers pe operate karte hain.

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

YE containers kyun exist karte hain (big picture)

Sequence containers

Associative containers

Complexities ka cheat-sheet