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

5.2.19 · D2 · Coding › C++ Programming › STL containers — vector, list, deque, array, set, multiset,

Hum parent note ki central formula earn karne wale hain: $T = \sum_{i = 0}^{⌊ l o g_{2} n ⌋} 2^{i} = 2^{⌊ l o g_{2} n ⌋ + 1} - 1 < 2 n$ ek picture at a time. Agar in symbols mein se koi abhi scary lag raha hai — good. Step 8 tak woh obvious feel hone lagenge.

Step 1 — Memory mein ek vector actually hota kya hai

KYA HAI. Ek std::vector teen numbers ka wrapper hai: memory ke ek block ki taraf ek pointer, ek size (kitne slots use ho rahe hain), aur ek capacity (block kitne slots hold kar sakta hai fill hone se pehle).

KYUN. Jab tak tum yeh nahi dekh sakte ki "full" ka matlab kya hai, tab tak tum kisi cheez ko grow karne ki cost ke baare mein reason nahi kar sakte. Poora $O (1)$ argument size aur capacity ke beech ke gap par hinge karta hai.

PICTURE. Neeche, grey slots reserved but empty hain (capacity abhi use nahi hui); cyan slots occupied hain (size). Notice karo: push_back sirf agli grey slot mein likhta hai aur size ko ek se bump karta hai. Yeh ek single write hai — $O (1)$ — jab tak koi grey slot maujood hai.

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

Step 2 — Sasta case aur mehnga case

KYA HAI. Jab tum push_back call karte ho, exactly do cheezein ho sakti hain:

Sasta ( $s < c$ ): ek free slot mein likho, $s + = 1$ . Constant kaam.
Mehnga ( $s = c$ ): jagah nahi — ek bada block allocate karo, saare $s$ purane elements copy karo, purana block free karo, phir likho. Yeh copy $O (s)$ kaam hai.

KYUN. Agar har push mehnga hota, toh vector ek bekar container hota. Magic yeh hai ki mehnga case rare hai. Yeh measure karne ke liye ki "kitna rare", pehle hume yeh fix karna hoga ki naya block kitna bada hoga.

PICTURE. Left: ek push jo free slot mein land kar raha hai (ek arrow, ek write). Right: ek full block jo reallocation force kar raha hai — har existing element ek naye, bade ghar mein carry ho raha hai.

Step 3 — Growth rule: doubling kyun?

KYA HAI. Full hone par, vector $c_{new} = 2 c$ capacity ka block allocate karta hai (typical libstdc++/MSVC choice). Woh double karta hai.

Doubling kyun aur "+1 har baar" kyun nahi? Yeh key design decision hai, toh isko justify karte hain, assume nahi. Maan lo hum iske bajaye har baar fixed +1 se badhte. Toh har single push ek "full" push hota, saare $s$ elements copy karta: $1 + 2 + 3 + \dots + n \approx n^{2} /2$ total copies — quadratic! Doubling ki wajah se full-events exponentially rarer ho jaate hain jaise vector grow karta hai, aur yahi $O (n^{2})$ ko $O (n)$ mein turn karta hai.

PICTURE. Do timelines of "reallocation kab fire hoti hai?" The +1 strategy constantly fire karti hai; doubling strategy $1, 2, 4, 8, 16, \dots$ par fire karti hai — gaps har baar double hote hain.

Step 4 — Har expensive event list karo

KYA HAI. Empty vector se start karo aur $n$ elements push karo. Reallocations (copies) exactly tab hoti hain jab size $1, 2, 4, 8, \dots, 2^{k}$ hit kare, jahan $2^{k}$ sabse bada power of two hai jo $\leq n$ ho.

KYUN. Total cost add up karne ke liye, pehle hume har expensive moment aur uski cost enumerate karni hogi. Capacity $m$ par ek reallocation exactly $m$ elements copy karti hai (pura existing block carry karta hai).

PICTURE. Pushes $1 \dots n$ ki ek number line. Amber spikes reallocations mark karti hain; har spike apni copy cost ke saath labelled hai ( $1, 2, 4, 8, \dots$ ). Spikes ke beech sab kuch cheap $O (1)$ pushes ka flat run hai.

Step 5 — Copy work sum karo (geometric series)

KYA HAI. Saari reallocations mein total copy work: $T = i = 0 1 + i = 1 2 + i = 2 4 + \dots + i = k 2^{k} = \sum_{i = 0}^{k} 2^{i} .$

Yeh tool kyun — geometric sum? Har term pehle wale se double hai (constant ratio $2$ ). Ek sum jahan har term ek fixed number se multiply hoti hai ek geometric series hai, aur uski ek famously clean closed form hoti hai. Hum isko exactly isliye use karte hain kyunki "har reallocation pichle se double copy karti hai" ek doubling pattern hai — geometric series exactly isi shape ko collapse karne ke liye bani thi.

PICTURE. Classic proof-without-words: $1, 2, 4, 8, \dots, 2^{k}$ heights ke bars stack karo. Poora stack agले bar $2^{k + 1}$ se ek short hai. Woh single missing unit hi closed form ka poora content hai.

Step 6 — Ise $2 n$ se bound karo

KYA HAI. Abstract $2^{k + 1} - 1$ ko $n$ ke terms mein kuch se replace karo: $T = 2^{k + 1} - 1 < 2^{k + 1} = 2 \cdot 2^{k} \leq 2 n .$

KYUN. Humne $k$ define kiya tha taaki $2^{k} \leq n$ ho (Step 4). Dono sides ko 2 se multiply karo: $2^{k + 1} \leq 2 n$ . Aur $- 1$ drop karne se left side aur badi ho jaati hai, toh strict inequality hold karti hai. Yeh "sum over reallocations" ko ek plain bound mein convert karta hai jo reader feel kar sake: saari copying milake $n$ se do guna se kam hai.

PICTURE. Do bars side by side: total copy work $T$ , aur ceiling $2 n$ . $T$ kabhi ceiling ko touch nahi karta, chahe $n$ kitna bhi bada ho.

Step 7 — Divide karo: amortised cost

KYA HAI. Amortised analysis poochta hai: "total cost ko saare $n$ operations mein evenly spread karo, toh har ek ko average par kya cost aati hai?" $amortised cost per push = \frac{total work}{n} = \frac{< 3 n}{n} < 3 = O (1) .$

Divide kyun? Amortised ka matlab yeh nahi ki "har push sasta hai" — ek push (reallocation) sach mein $O (n)$ ka hota hai. Iska matlab yeh hai ki poore sequence mein bill split constant hai. Total ko count se divide karna exactly wahi split hai.

PICTURE. True per-push cost ki ek jagged red line (mostly height 1 par, powers of two par tall spikes ke saath) aur height $\approx 3$ par ek flat amber line — average. Spikes flat line ke upar jaati hain lekin calm valleys average ko neeche kheench laati hain.

Step 8 — Degenerate aur edge cases

KYA AUR KYUN. Ek derivation tab tak finish nahi hoti jab tak har corner cover na ho.

$n = 0$ (empty): koi pushes nahi, koi reallocations nahi, $T = 0$ . Formula deta hai $\sum_{i = 0}^{⌊ l o g_{2} 0 ⌋}$ jo ek empty/undefined sum hai — hum ise simply $0$ treat karte hain. Koi contradiction nahi: zero kaam zero pushes ke liye.
$n = 1$ (single push): $k = 0$ , ek reallocation $2^{0} = 1$ element copy karti hai... actually ek fresh empty vector mein pehla push allocate karta hai lekin copy kuch nahi karta (copy karne ke liye kuch hai hi nahi). Toh real implementations bound se bhi better karti hain — bound ek upper limit hai, kabhi violate nahi hoti.
Pehle reserve(n): agar tum vector ko uski final size pehle se bata do, toh woh ek baar allocate karta hai aur har push cheap branch mein hoti hai — zero reallocations. Yahi fix hai jo parent note ki mistake box point out karti hai.
Growth factor $\neq = 2$ (e.g. kuch libraries mein $1.5 \times$ ): ratio $r > 1$ phir bhi geometric series deta hai $\sum r^{i} = \frac{r ^{k + 1} - 1}{r - 1}$ , phir bhi $O (n)$ total, phir bhi $O (1)$ amortised. Koi bhi constant factor $> 1$ kaam karta hai — sirf "+1 growth" (ratio effectively $1$ ) isko wapas $O (n^{2})$ mein todta hai.

PICTURE. Char mini-panels: empty, single push, pre-reserved (flat, koi spikes nahi), aur $1.5 \times$ growth (spikes paas paas lekin phir bhi exponentially sparse).

Ek-picture summary

Upar sab kuch compress: per-push cost curve (powers of two par spikes), running total $2 n$ se bounded ek line par chadh raha hai, aur flat amortised average — sab ek blueprint par.

Recall Feynman retelling — jaise kisi dost ko explain karo

Vector ek box hai jisme spare room hai. Koi cheez add karna usually free hai — tum use spare slot mein drop kar dete ho. Lekin jab box full ho jaata hai, tum ek double size ka box khareedne aur sab kuch carry karne par majboor ho. Woh carrying slow hai. Trick yeh hai: kyunki tum double karte ho har baar, box utna half frequently bharta hai jitna pichli baar grow kiya tha — slow moves rarer aur rarer hote jaate hain. Agar tum saari carrying jo tumne kabhi ki sab add karo, toh woh tumhari stored cheezein ki sankhya se do guna se kam hai. Woh bill har "add" mein split karo, aur har add average par ek tiny constant cost karta hai. Iska matlab yahi hai "amortised $O (1)$ ": rare expensive moves, cheap ones ki bheed ke dwara pay ki gayi. Aur agar size pehle se pata tha, toh reserve karo — phir tumhe kuch carry hi nahi karna padega.

Recall Quick self-test

"+1" se har baar grow karne par $O (n^{2})$ total kyun hota hai? ::: Har push ek "full" push hota jo saare $s$ elements copy karta, toh total $= 1 + 2 + \dots + n \approx n^{2} /2$ . $⌊ lo g_{2} 100 ⌋$ kya hai aur yahan iska kya matlab hai? ::: $6$ — 100 elements tak pahunchne se pehle aakhri reallocation ne $2^{6} = 64$ items copy kiye. Ek single push_back worst case kya complexity hai? ::: $O (n)$ — jab woh reallocation trigger karta hai aur poora array copy karta hai. $1 + 2 + 4 + \dots + 2^{k}$ ki closed form? ::: $2^{k + 1} - 1$ . Jab size pata ho toh saari reallocations kaise avoid karo? ::: Pehle reserve(n) call karo.

Prerequisites revisited: Amortised analysis, Big-O notation, aur Cache locality se memory-layout intuition — yeh sab is result ko feed karte hain. Parent par wapas: STL containers overview.