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

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

Yahan kuch bhi assume nahi kiya gaya ki aapne pehle C++ dekha hai. Hum "memory mein box kya hota hai" ke level se shuru karte hain aur ek-ek rung chadhte hue us vocabulary tak pahunchte hain jo parent topic freely use karta hai.

1. Ek memory cell, aur "contiguous" ka matlab

Kisi bhi container se pehle, memory hoti hai. Computer memory ko ek infinitely lamba street of identical houses samjho. Har house ek byte hai — sabse chota addressable unit — aur uska ek address hai, uska house number.

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

Yahan ek subtlety hai jo metaphor ko nahi chhupani chahiye: ek data value kai bytes occupy kar sakti hai. Ek chota integer 4 bytes mein fit ho sakta hai, bada 8 mein. Toh ek value hamesha ek house nahi hoti — woh paas-paas houses ka ek block ho sakti hai. Ek element kitne bytes occupy karta hai, usse hum size kehte hain, likha jaata hai $s$ .

YEH TOPIC KO KYUN CHAHIYE: parent note kehta hai ki vector " $O (1)$ random access deta hai kyunki index math address deta hai." Yeh meaningless hai jab tak aap yeh nahi dekh sakte ki kyun. Upar ke teen symbols ke saath, element $i$ shuru hota hai:

$address (i) = B + i \times s .$

Words mein padho: base $B$ se shuru karo, phir $i$ poore elements skip karo, har ek $s$ bytes wide. Yeh ek multiply ( $i \times s$ ) aur ek add hai — ek fixed amount of work chahe $i$ kitna bhi bada ho. Yahi hai "kisi bhi element par seedha jump karo" ka matlab, aur yeh sirf tabhi kaam karta hai jab elements ek row mein hon.

2. " $O (\cdot)$ " asal mein kya kehta hai — Big-O zero se

Parent note $O (1)$ , $O (n)$ , $O (lo g n)$ se bhara hua hai. Yeh numbers nahi hain. Yeh ek sawaal ka jawaab dete hain: "jaise data ki maatra badhti hai, kaam kaise badhta hai?"

Figure ko teen growth shapes ki tarah padho, sabse slow upar:

$O (1)$ — flat. $n$ badhne par kaam bilkul nahi badhta. Section 1 se "element $i$ par jump karo" $O (1)$ hai: ek multiply-add chahe $n$ 10 ho ya 10 million.
$O (lo g n)$ — bahut dheere badhna. $n$ double karne par sirf constant amount of work badhti hai. Yahi tree containers (set, map) dete hain — Section 6 dekho.
$O (n)$ — seedhi line. Data double, kaam double. "Har element mein se walk karo ek value dhoondh ke" $O (n)$ hai.

Recall

$B + i \times s$ ek $O (1)$ operation kyun hai? Kyunki yeh hamesha same kaam hai — ek multiply, ek add (har ek primitive $O (1)$ costing) — regardless of kitne elements hain. Count $n$ formula mein kabhi appear nahi hota. ::: $n$ se independent primitives ki ek fixed number $O (1)$ ki definition hai.

3. "Amortised" — ek run mein average

Parent claim karta hai ki push_back amortised $O (1)$ hai. Woh word "amortised" bahut kaam kar raha hai.

YEH TOPIC KO KYUN CHAHIYE: "amortised" ke bina, aap resize ke dauran occasional $O (n)$ copy dekhke galat conclusion nikalte ki push_back slow hai. Poora proof Amortised analysis mein hai; parent note wahan $< 3 n$ total derive karta hai.

4. Pointers aur nodes — linked world

Section 1 ne hume contiguous world diya. STL ka doosra aadha — list, aur tree containers ki internals — linked world mein rehta hai, aur uska atom pointer hai.

Figure dekho. Nodes memory mein scattered hain — node A 1000 par, node B 5000 par, node C 2000 par — lekin red next arrows unhe ek order mein seeti hain. Yeh Section 1 ke saath key contrast hai:

Contiguous array: neighbours memory mein neighbours hain ⇒ index $i$ par instantly jump karo, lekin beech mein insert karne par har baad wale house ko physically shift karna padta hai.
Linked nodes: neighbours jahan bhi hon; unhe sirf pointers follow karke milte hain ⇒ index par jump nahi, lekin insert karna sirf do arrows rewrite karna hai ( $O (1)$ ).

Recall Figure mein B aur C ke beech ek node insert karne ke liye kya badlega?

Sirf chaar arrows: naaye node ke prev/next, plus B ka next aur C ka prev. Koi doosra node nahi hilta. ::: Isliye linked-list insertion (given the position) $O (1)$ hai — pure pointer surgery, koi shifting nahi.

5. Keys, values, aur "sorted order"

Parent containers ko sequence (insertion se ordered) aur associative (value se organised) mein baantta hai. Yeh padhne ke liye, aapko teen words chahiye.

6. Trees aur hash tables — key ke hisaab se organise karne ke do tarike

Do engines associative containers ko power karte hain. Aapko har ek ki mental picture chahiye.

Figure mein 40 dhundhte hue red path trace karo: 50 se shuru karo (40 < 50 → left jao), 30 tak pahuncho (40 > 30 → right jao), 40 tak pahuncho ✓. Saat nodes mein se teen comparisons. Har level jo bacha hai usse half karta hai — wohi halving jo binary search ko $O (lo g n)$ banati hai.

7. Iterators — universal "position marker"

Aakhirkar, woh word jo har worked example use karta hai: iterator.

Parent ka list example — L.insert(it, x) $O (1)$ hai — sirf tabhi kaam karta hai kyunki it already position hold karta hai. Iterator ko us spot tak laana khud $O (n)$ cost kar sakta hai. Yahi distinction (position hold karna vs. usse find karna) cheat-sheet ke aadhe "gotchas" explain karta hai. Deep dive: Iterators in C++, aur jo functions unhe consume karte hain: STL algorithms.

Foundations topic ko kaise feed karte hain

Equipment checklist

Byte kya hota hai, aur uska element se kya relation hai?

Byte memory ki sabse choti addressable cell hai (ek house); ek element kai neighbouring bytes occupy kar sakta hai — unke

s

Element

i

ka starting address do, har symbol define karo

address (i) = B + i \times s

, jahan

B

base address hai (element 0 ki byte) aur

s

element size hai bytes mein.

Kaunsa standing assumption

B + i \times s

O (1)

step kehne deta hai?

Unit-cost assumption: har primitive (add, multiply, dereference, key comparison, hash)

O (1)

cost karta hai.

Kya std::deque ek contiguous block hai?

Nahi — yeh fixed-size chunks ka ek segmented array hai; random access phir bhi

O (1)

hai lekin memory ek unbroken block nahi hai.

O (n)

ka matlab ek sentence mein kya hai?

Kaam elements ki sankhya ke saath ek seedhi line mein badhta hai — data double, kaam double.

"Amortised

O (1)

" kya allow karta hai jo plain

O (1)

nahi karta?

Rare expensive operations, jab tak operations ki lambi run mein average constant ho.

Pointer kya hai, aur usse dereference karne ki kya cost hai?

Ek value jo doosri value ka address rakhti hai; usse follow karna (dereference) ek primitive hai jo

O (1)

cost karta hai.

Ek linked list

O (1)

mein insert kyun kar sakta hai lekin vector nahi?

List sirf kuch pointer arrows rewrite karta hai; vector ko har baad wale element ko physically shift karna padta hai.

Binary search tree mein, ek node ke relative chote keys kahaan rehti hain?

Uske left mein; bade keys right mein — jo search ko har step mein candidates half karne deta hai.

Hash table sorted order kyun nahi deta?

Hash function deliberately keys ko buckets mein scatter karta hai, jo koi bhi ordering destroy kar deta hai.

Iterator kya hota hai?

Ek movable position marker (ek "unguli") jo ek element ki taraf point karta hai, jo agle par step kar sakta hai.