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

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

Scenario matrix

Kisi bhi code se pehle, yahan case classes ki poori list hai jinmein container problems aati hain. Neeche har worked example us cell ke saath tagged hai jise woh cover karta hai, aur milke woh poori table cover karte hain.

#	Case class	Kya tricky hai	Winning container	Example
A	Index se random access, read-heavy	$O (1)$ `v[i]` chahiye	`vector` / `array`	Ex 1
B	Middle mein insert/erase, baar baar	shifting cost	`list`	Ex 2
C	Dono ends par insert (front + back)	vector par front push $O (n)$ hai	`deque`	Ex 3
D	Unique keys, fast lookup, order zaruri nahi	hashing	`unordered_set/map`	Ex 4
E	Keys sorted rehni chahiye / range queries	tree ordering	`map` / `set`	Ex 5
F	Duplicate keys survive karne chahiye	set dupes drop kar deta hai	`multiset` / `multimap`	Ex 6
G	Degenerate / zero input (empty, size 0, single element)	UB traps	koi bhi — dhyan chahiye	Ex 7
H	Limiting behaviour — capacity growth, worst-case collision	amortised vs worst	`vector` / `unordered_map`	Ex 8
I	Real-world word problem — ek paragraph se pick karo	needs → costs mein translate karna	mixed	Ex 9
J	Exam twist — iterator invalidation / erase-during-loop	silent dangling bug	vector/map	Ex 10

Recall Padhne se pehle quick self-test

"Front aur back inserts, dono cheap" ke liye kaun sa container? ::: deque Kaun se containers unique keys rakhte hain aur duplicates silently drop kar dete hain? ::: set aur map dono unique keys enforce karte hain (duplicates rakhne ke liye multiset/multimap use karo) multiset par erase(value) kitne remove karta hai? ::: saare matching copies

Cell A — Random access, read-heavy

Worked example Ex 1 — Ek bade number list ke har 3rd element ka sum

$1 0^{6}$ integers hain aur tumhe baar baar index $k$ par element padhna hai. Kaun sa container, aur $m$ arbitrary indices padhne ki total cost kya hai?

Forecast: container guess karo aur yeh bhi ki ek read $O (1)$ hai ya $O (n)$ — aage padhne se pehle.

vector<int> choose karo. Yeh step kyun? Contiguous memory ka matlab hai ki element $k$ ka address base + k*sizeof(int) hai — ek multiply aur ek add, koi walking nahi. Yeh $O (1)$ per read hai.
Indices $0, 3, 6, \dots$ padho. Har v[k] independent $O (1)$ hai.
$m$ reads ke liye total $= m \cdot O (1) = O (m)$ .

vector<int> v(1000000);
long long s = 0;
for (size_t k = 0; k < v.size(); k += 3) s += v[k];

Verify: agar hum list use karte, to har v[k] ke liye $k$ nodes walk karne padte, isliye indices $0, 3, \dots, 3 (m - 1)$ padhne ki cost $0 + 3 + 6 + \dots = 3 \cdot \frac{m ( m - 1 )}{2} = O (m^{2})$ hoti. $m = 1000$ ke liye woh $\approx 1, 498, 500$ node-hops hote vector ke $1000$ ke mukable. Vector design se jeet jaata hai.

Cell B — Middle mein baar baar insert/erase

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

Worked example Ex 2 — Ek playlist maintain karo jahaan songs mid-list mein constantly insert hote hain

Tumhare paas insertion spot ka iterator pehle se hai aur tum wahaan $n$ inserts karte ho. vector vs list compare karo.

Forecast: har container mein har insert ke liye kitne element-moves honge?

vector middle-insert. Yeh step kyun? Position $p$ par gap kholne ke liye, $p$ ke baad ke har element ko ek right shift karna padta hai — $n$ tak moves. Figure ki top row dekho: pink block sab kuch slide kar deta hai.
list middle-insert. Yeh step kyun? Ek doubly-linked node bas 4 pointers relink karta hai (naye node ke prev/next, aur do neighbours). Figure ki bottom row: kuch aur nahi hilta. Yeh $O (1)$ hai.
$n$ baar karo. vector $= O (n)$ har baar $\Rightarrow O (n^{2})$ total; list $= O (1)$ har baar $\Rightarrow O (n)$ total (iterator given ho to).

list<string> playlist;
auto it = playlist.begin();      // already at the spot
playlist.insert(it, "newSong"); // O(1) pointer surgery

Verify: $n = 10, 000$ middle inserts ke liye, vector $\sim \frac{n ^{2}}{2} = 5 \times 1 0^{7}$ moves karta hai; list $\sim 4 n = 40, 000$ pointer writes karta hai. Ratio $\approx 1250 \times$ — $O (n^{2})$ vs $O (n)$ prediction se match karta hai.

Cell C — Dono ends par insert

Worked example Ex 3 — Sliding window / double-ended queue of tasks

Tum naye tasks back par push karte ho aur finished ones ko front se pop karte ho, laakhon baar.

Forecast: vector yahan trap kyun hai?

vector reject karo. Yeh step kyun? vector mein koi cheap front operation nahi hai — insert(begin(), x) saare $n$ elements ko right shift kar deta hai, $O (n)$ . Har task ke liye yeh karna $O (n^{2})$ hai.
deque choose karo. Yeh step kyun? Ek deque fixed-size chunks ka ek map hai (figure dekho). Front par barhna pehle wale se pehle ek chunk add karta hai, back par barhna baad mein ek chunk add karta hai — dono amortised $O (1)$ , aur chunks ke across index math abhi bhi $O (1)$ random access deta hai.
Operate karo.

deque<int> q;
q.push_back(x);   // amortised O(1)
q.push_front(y);  // amortised O(1)
int a = q.front(); q.pop_front();  // O(1)

Verify: $n$ tasks ko front+back ops ke saath process karne ki cost deque par $O (n)$ hai vs vector-with-front-inserts par $O (n^{2})$ . $n = 100, 000$ ke liye: deque $\sim 2 \times 1 0^{5}$ ops, vector $\sim 5 \times 1 0^{9}$ — deque hi ek viable choice hai.

Cell D — Fast lookup, order zaruri nahi

Worked example Ex 4 — "Kya maine yeh ID pehle dekha hai?" ek stream mein

$N$ user IDs ka stream; har ke liye average $O (1)$ mein pehle dekha? jawab do.

Forecast: hash ya tree? Kyun?

unordered_set<long> choose karo. Yeh step kyun? Tumhe sirf membership chahiye, kabhi sorted order nahi. Ek hash function IDs ko buckets mein scatter karta hai, average $O (1)$ find/insert deta hai. Ek tree (Red-black trees) per query $O (lo g n)$ cost karega — yahan faaltu slow.
Query karo phir insert karo.

unordered_set<long> seen;
for (long id : stream) {
    if (seen.count(id)) reportDuplicate(id);
    seen.insert(id);          // O(1) average
}

Worst case jaano. Yeh step kyun? $O (1)$ sirf ek average hai, aur yeh ek acche hash function ko assume karta hai jo keys evenly spread kare. Agar bahut saare IDs ek hi bucket mein collide ho jaayein — bura hash, ya koi adversary jo colliding keys choose kare — bucket ek lambi chain ban jaati hai aur har lookup $O (n)$ ho jaata hai (dekho Hash functions and collisions). Isliye $N$ queries average mein $O (N)$ hain par worst case mein $O (N^{2})$ . Ek set guaranteed $O (lo g n)$ deta hai chahe kuch bhi ho.

Verify: total average cost $= N \cdot O (1) = O (N)$ . Ek set $O (N lo g N)$ hota. $N = 1024$ ke liye, $lo g_{2} N = 10$ , isliye tree average mein $\sim 10 \times$ zyada comparisons karta hai — hashing tab jeets hai jab order nahi chahiye aur hash accha ho; jab hash par trust nahi kar sakte, tree ki worst-case guarantee prefer karo.

Cell E — Sorted keys / range queries

Worked example Ex 5 — Leaderboard: names sorted, plus "kisne 40 aur 60 ke beech score kiya?"

Alphabetical iteration aur range queries dono chahiye.

Forecast: unordered_map yeh kyun fail karta hai?

map<string,int> choose karo (ya set). Yeh step kyun? Tree-based ⇒ keys sorted rehti hain, isliye iteration alphabetical hai free mein, aur lower_bound/upper_bound $O (lo g n)$ range queries dete hain. unordered_map mein koi order nahi aur koi lower_bound bhi nahi.
Bounds ke saath range query.

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

Verify: iteration order apple, banana, cherry hai — strictly sorted, BST invariant se guaranteed. Har key ke liye search $O (lo g 3)$ hai. Ek unordered_map unpredictable bucket order mein print karta, requirement fail karta.

Cell F — Duplicates survive karne chahiye

Worked example Ex 6 — Har score rakho, repeats allow karo, ek baar mein sabse chhota pop karo

$50, 50, 20$ insert karo; sabse chhota lo; exactly ek sabse chhota remove karo.

Forecast: erase(20) vs erase(begin()) kya karta hai? Step 3 se pehle guess karo.

multiset<int> choose karo. Yeh step kyun? Ek set dono 50s ko ek mein collapse kar deta. multiset duplicates rakhta hai, sorted rehta hai, isliye begin() hamesha $O (1)$ mein minimum hai.
Minimum padho *scores.begin() se.
EK sabse chhota remove karo erase(iterator) se — erase(value) se nahi.

multiset<int> scores;
scores.insert(50); scores.insert(50); scores.insert(20);
int smallest = *scores.begin();     // 20
scores.erase(scores.begin());       // removes ONE 20 -> {50,50}
// scores.erase(50) would delete BOTH 50s

Verify: insert(50),insert(50),insert(20) ke baad size $= 3$ , begin() $= 20$ . erase(begin()) ke baad size $= 2$ aur contents {50,50}. Agar hum phir erase(50) call karein to size $0$ ho jaata hai (dono remove) — confirming karta hai ki value-erase saare matches kill karta hai.

Cell G — Degenerate / zero input

Worked example Ex 7 — Empty aur single-element traps

Possibly-empty containers par front(), back(), begin() call karne se pehle kya check karna zaroori hai?

Forecast: ek empty vector par v.front() kya return karta hai? (Trick: woh $0$ nahi hai.)

Empty vector front() Undefined Behaviour hai. Yeh step kyun? front() *begin() return karta hai, par empty container par begin() == end() hota hai, isliye tum ek non-element dereference kar rahe ho. Hamesha !v.empty() se guard karo.
Empty map [] insert karta hai. Yeh step kyun? Missing key par m[k] default-construct aur insert karta hai — isliye ek read silently map ko badha sakta hai. Sirf check karna ho to m.find(k) ya m.count(k) use karo.
Single element: begin() aur --end() ek hi element ko point karte hain; use erase karne par container empty ho jaata hai aur koi bhi held iterator dangling ho jaata hai.

vector<int> v;                  // size 0
// int x = v.front();           // UB — do NOT
if (!v.empty()) use(v.front()); // safe
 
map<string,int> m;
if (m.count("x")) use(m["x"]);  // avoids accidental insert

Verify: default-constructed vector ke liye v.size()==0 aur v.empty()==true — guard exactly wahi hai jo UB rokta hai. Empty map par, m.count("x")==0, isliye branch skip ho jaata hai aur koi phantom key nahi banti; agar humne m["x"] likhaa hota, to m.size() $1$ tak jump kar jaata.

Cell H — Limiting behaviour (capacity growth & worst case)

Worked example Ex 8 — Ek million push_backs ke liye kitne reallocations?

Empty se shuru karo, capacity har baar fill hone par double hoti hai. $1 0^{6}$ elements push karo. Kitne resizes honge, aur total copy work kitna?

Forecast: "resizes ki sankhya" aur "total copies" $n$ ke multiples mein guess karo.

Resizes sizes $1, 2, 4, \dots, 2^{k}$ par hote hain (figure mein staircase dekho — har riser ek resize hai, flat tread saste pushes hain). $n = 1 0^{6}$ ke liye, $n$ se chhota ya barabar sabse bada power of two $2^{19} = 524288$ hai, isliye $k = 19$ ⇒ 20 resizes ( $2^{0}$ se $2^{19}$ tak).
Total copy work $= \sum_{i = 0}^{19} 2^{i} = 2^{20} - 1 = 1, 048, 575 < 2 n$ . Yeh step kyun? Geometric series $1 + 2 + \dots + 2^{k} = 2^{k + 1} - 1$ ; dekho Amortised analysis.
Amortised per push $= O (1)$ . Yeh step kyun? $n$ pushes mein do costs add hoti hain: (a) saste pushes — $n$ mein se har element apne slot mein exactly ek baar likha jaata hai, cost $n$ ; (b) resizes se copy work, jise humne abhi $< 2 n$ bound kiya. Isliye total work $< 2 n + n = 3 n$ hai, aur $n$ pushes se divide karne par $< 3 = O (1)$ average per push milta hai. Contiguous block un copies ko cache-friendly bhi rakhta hai.

vector<int> v;
v.reserve(1000000);   // ONE allocation, ZERO resizes — best practice
for (int i = 0; i < 1000000; i++) v.push_back(i);

Common mistake "Har implementation capacity double karta hai."

Kyun sahi lagta hai: doubling model wahi hai jo textbooks (aur yeh example) amortised bound derive karne ke liye use karte hain cleanly. Reality: C++ standard sirf amortised $O (1)$ push_back guarantee karta hai — growth factor mandate nahi karta. libstdc++ (GCC) double karta hai ( $2 \times$ ), par MSVC roughly $1.5 \times$ se barhta hai. Analysis kyun abhi bhi hold karta hai: kisi bhi fixed growth factor $g > 1$ ke liye, resizes sizes $1, g, g^{2}, \dots$ par hote hain aur copy work geometric sum $\frac{g}{g - 1} n$ hai, abhi bhi total $O (n)$ ⇒ abhi bhi $O (1)$ amortised. Chhota $g$ (jaise $1.5$ ) zyada resizes karta hai par kam memory waste karta hai — yeh space/time tradeoff hai, complexity change nahi. Fix: exact factor par nahi, amortised guarantee par rely karo; neeche exact resize count $2 \times$ assume karta hai.

Verify: $2 \times$ model ke liye, reserve ke bina copies $= 2^{20} - 1 = 1, 048, 575$ hain, jo $< 2 \times 1 0^{6}$ hai; $n = 1 0^{6}$ saste writes add karne par $< 3 \times 1 0^{6}$ total milta hai. General factor $g$ ke liye, total copies $= \frac{g}{g - 1} n$ : $g = 2$ par woh $2 n$ hai, $g = 1.5$ par $3 n$ — dono $O (n)$ . Worst-case contrast: ek adversarial hash har key ko ek bucket mein force kar sakta hai, unordered_map find ko $O (n)$ bana deta hai — woh limiting case jo average $O (1)$ chhupaata hai.

Cell I — Real-world word problem

Worked example Ex 9 — Word-frequency report, alphabetically print kiya gaya

$N$ words padho, har ek count karo, phir counts alphabetical order mein print karo. Container paragraph ki needs se pick karo.

Forecast: ek container ya do? Counting ke liye hash, printing ke liye tree?

Needs list: (a) har word per fast count-up → hash favour karta hai; (b) sorted output → tree favour karta hai. Yeh step kyun? Har sentence clause ko ek cost requirement mein translate karna hi poori skill hai.
Sabse simple correct choice: map<string,int>. Yeh step kyun? Ek structure dono satisfy karta hai — $O (lo g n)$ counting aur free sorted iteration. $D$ distinct words ke liye total $O (N lo g D)$ .
Faster alternative: unordered_map se $O (N)$ mein count karo, phir keys ko ek vector mein copy karo aur $O (D lo g D)$ mein sort karo. Yeh step kyun? Jab $N ≫ D$ (thode distinct words ke bahut saare repeats) ho, to $O (N)$ hash counting map ke $O (N lo g D)$ ko beat karta hai, aur hum sorting cost sirf ek baar $D$ distinct keys par pay karte hain, har insert par nahi (dekho STL algorithms).

map<string,int> freq;
for (auto& w : words) freq[w]++;     // counts, stays sorted
for (auto& [w,c] : freq) cout << w << " " << c << "\n";  // alphabetical

Verify: {"pear","apple","apple"} ke liye, freq mein apple->2, pear->1 hai, apple 2 phir pear 1 print hota hai. Counts ka sum $= 3 = N$ — har word account mein hai.

Cell J — Exam twist: iterator invalidation

Worked example Ex 10 — Loop ke beech mein container se saare even numbers erase karo

Naively range-for ke andar erase karna silently iteration corrupt karta hai. vector aur map ke liye fix karo.

Forecast: kya tootta hai agar tum ek hi loop turn mein erase(it) likhte ho aur phir ++it karte ho?

Trap. Yeh step kyun? vector par erase(it) it ko invalidate kar deta hai (aur uske baad ki sab cheez, kyunki elements shift hote hain). Uske baad old it use karna ya ++ karna UB hai.
Fix — erase ki return value use karo. Yeh step kyun? erase removed element ke baad wale element ka ek valid iterator return karta hai, isliye tum dead iterator touch karne ki bajaye sahi se aage badhte ho.

vector<int> v = {1,2,3,4,5,6};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);   // erase returns next valid it
    else ++it;
}
// v == {1,3,5}

map ke liye, ek node erase karna baaki nodes ko invalidate nahi karta (tree ke remaining links theek rehte hain) — par erased iterator khud mar jaata hai. Yeh step kyun? Isliye tumhe abhi bhi dead iterator ko ++ nahi karna chahiye; erase ki return value capture karo (C++11 aur baad mein) ya classic post-increment idiom m.erase(it++) use karo:

map<int,int> m = {{1,1},{2,2},{3,3},{4,4}};
for (auto it = m.begin(); it != m.end(); ) {
    if (it->first % 2 == 0) it = m.erase(it);  // returns next valid it
    else ++it;
}
// keys left: {1,3}

Verify: vector result {1,3,5} hai (size $3$ , sum $9$ ); map mein baaki keys {1,3} hain (size $2$ ). Dono "remove evens" spec se match karte hain. Har container ke liye full invalidation rules ke liye Iterators in C++ dekho.

Recall Final scenario check

Front + back cheap → ::: deque Free sorted iteration → ::: map / set erase(it) return karta hai → ::: next element ka ek valid iterator Empty-vector front() → ::: undefined behaviour — !empty() se guard karo