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

(a) ==std::array<T, 30> — fixed size compile time pe pata hai, stack pe rehta hai, zero overhead. (b) std::vector== — contiguous, $O(1)$ index v[i], amortised $O(1)$ push_back. (c) ==std::map<string,int>== — tree-based, toh iteration sorted key order mein free mein hoti hai. (d) ==std::deque== — yeh akela sequence container hai jisme dono ends pe amortised $O(1)$ milta hai.

Inhe swap kyun nahi karna? (d) ke liye vector pe $O(n)$ per push_front lagta hai kyunki har element ko ek slot right shift karna padta hai. (c) ke liye unordered_map arbitrary bucket order mein print karega — iske paas koi ordering nahi hai.

• vector random access: ==$O(1)$== — base pointer pe ek multiply-and-add.
• list random access: ==$O(n)$== — nodes bikre hue hain, tumhe next pointers walk karne padte hain.
• set search: ==$O(\log n)$== — ek balanced red-black tree har level pe search space half kar deta hai.
• unordered_set search (average): ==$O(1)$== — ek hash seedha bucket pe jump karta hai.

Resizes sizes $1,2,4,\dots ,512$ (woh powers of two $\le 1000$) se theek pehle trigger hote hain. Capacity $m$ se resize pe tum $m$ existing elements copy karte ho. Total copies: $T=1+2+4+\cdots +512={\sum }_{i=0}^9{2}^i=2^{10}-1=1023.$ Yeh sum kyun? Geometric series $1+2+\cdots +2^k=2^{k+1}-1$. Yahaan $2^9=512\le 1000$, toh $k=9$. $1023<2n=2000$, toh copy work $<2n$ hai. $n$ pushes mein spread karo ⇒ $T/n\approx 1$, yaani amortised ==$O(1)$== per push. Dekho Amortised analysis.

• map: har insert $O(\log N)$ ⇒ $N\log N$ total; iteration already sorted, $O(N)$. Grand total ==$O(N\log N)$==.
• unordered_map: inserts $O(N)$ average, lekin sorted output ke liye $N$ keys copy karo aur sort karo: $O(N\log N)$. Grand total ==$O(N\log N)$== bhi.

Conclusion: same asymptotic class. map simplicity mein jeetra hai (order free hai), jabki unordered_map raw insert speed mein jeet sakta hai lekin phir sort ka daam chukana padta hai. Koi bhi "hamesha faster" nahi hai.

Slot dhundne ke liye binary search $O(\log n)$ hai — sasta. Lekin vector ke middle mein insert karne se uske baad wala har element ek slot right shift hota hai: har insert pe $O(n)$ copies tak (figure mein orange shifted block dekho). $n$ inserts ke baad: $\text{total}={\sum }_{k=1}^{n}O(k)=O(n^2).$ Binary search tumhe save nahi karta — shift dominate karta hai. Fix: ek ==std::multiset== (tree-based). Har insert $O(\log n)$ hai placement samet, total $O(n\log n)$, aur yeh duplicates ke saath sorted rehta hai.

Ek unordered_map keys ko ek hash function ke zariye buckets mein scatter karta hai. Agar bahut saari keys ek bucket mein collide ho jayein, woh bucket length $n$ tak ki linked chain ban jaati hai; ek lookup ko poori chain scan karni padti hai — $O(n)$. Yeh bure hash ya adversarial input set ke saath hota hai. Ek map ek red-black tree hai jiska height guaranteed $\le 2{\log }_2(n+1)$ hai balancing rules ki wajah se, toh search hamesha $O(\log n)$ hai — koi worst case darne wala nahi. Tradeoff: $O(\log n)$ average hash ke $O(1)$ average se slower hai jab hash theek behave kare.

Do phases:

1. Count ek ==unordered_map<string,int>== se — freq[w]++ average $O(1)$ hai, total $O(N)$.
2. Rank karo pairs ko ek vector<pair<string,int>> mein move karke aur custom comparator se sort karke: pehle higher count, ties pe alphabetical. $D$ distinct words sort karna $O(D\log D)$ hai.

unordered_map<string,int> freq;
for (auto& w : words) freq[w]++;
vector<pair<string,int>> v(freq.begin(), freq.end());
sort(v.begin(), v.end(), [](auto& a, auto& b){
    if (a.second != b.second) return a.second > b.second; // count desc
    return a.first < b.first;                             // word asc
});
for (auto& [w,c] : v) cout << w << " " << c << "\n";

Yeh split kyun? Counting ko raw lookup speed chahiye (koi order nahi) → hash map. Ranking ko ek custom order chahiye jo hash map provide nahi kar sakta → vector mein dump karo aur sort karo. Total ==$O(N+D\log D)$==, aur kyunki $D\le N$ hai toh yeh $O(N\log N)$ hai. std::sort use karta hai.

Do multiset<int> halves use karo: lo (chhota half, jiska sabse bada *lo.rbegin() hai) aur hi (bada half, jiska sabse chhota *hi.begin() hai). Sizes balanced rakho taaki lo mein hi ke barabar ya exactly ek zyada count ho.

• Insert: x ko lo ya hi mein daalo current median se compare karke, phir rebalance karo ek boundary element ko doosri taraf move karke agar sizes 2 se differ karein. Har step $O(\log n)$ hai.
• Erase one copy: s.erase(s.find(x)) — note karo ki find ek iterator deta hai toh sirf ek copy remove hoti hai; erase(x) saari copies wipe kar deta (yahi L5 trap neeche hai). $O(\log n)$.
• Median: agar sizes equal hain, *lo.rbegin() aur *hi.begin() ka average; warna *lo.rbegin(). $O(1)$.

multiset kyun, set nahi? Duplicates store hone chahiye — same integer kai baar aa sakta hai. Saare ops ==$O(\log n)$== hain.

Starting size = 4. (a) ms.erase(5) ek value pass karta hai ⇒ har 5 remove ho jaata hai. Teen panchon gone. Size = ==$1$== (sirf 7). (b) ms.erase(ms.find(5)) ek 5 ke iterator ko pass karta hai ⇒ exactly ek element remove hota hai. Size = ==$3$== (do 5 aur ek 7).

Rule: value-erase saare matches delete karta hai; iterator-erase sirf ek delete karta hai.

Nahi — yeh undefined behaviour hai. Vector full tha (capacity 3, size 3), toh push_back(4) ek naya, bada block allocate karta hai, 1,2,3,4 usmein copy karta hai, aur purana block free kar deta hai. p abhi bhi freed purani memory ki taraf point karta hai — yeh ek dangling pointer hai. *p padhne se 1, garbage, ya crash ho sakta hai. Fix: kisi bhi insertion ke baad re-fetch karo jo reallocate kar sakta ho, ya pehle se itna reserve karo ki jab tak p hold karo koi reallocation na ho. Dekho Iterators in C++ — same invalidation iterators aur references pe bhi apply hoti hai.

Koi single standard container dono nahi deta. unordered_map $O(1)$ lookup deta hai lekin koi order nahi; map sorted iteration deta hai lekin $O(\log n)$ lookup. Tumhe ek primary structure choose karni hogi:

• Agar lookups ordered scans se kahin zyada hain → unordered_map rakho, aur jab kabhi sorted output chahiye, keys ko vector mein copy karo aur sort karo ($O(D\log D)$, rarely hota hai).
• Agar ordered iteration frequent hai → map use karo aur $O(\log n)$ lookups accept karo.

Koi free lunch nahi hai: parent note ka EK idea — har container ek chosen tradeoff hai — yahi forbid karta hai ek container jo simultaneously unordered-fast aur order-preserving ho.

Main ek given access pattern ke liye sahi container naam kar sakta hoon ::: L1 done Main doubling amortise kar sakta hoon aur $n$ pushes ke liye $<2n$ copies nikaal sakta hoon ::: L2 done Main explain kar sakta hoon ki sorted-vector insert $O(n^2)$ kyun hai aur multiset kyun fix karta hai ::: L3 done Main $O(\log n)$ pe two-multiset median tracker design kar sakta hoon ::: L4 done Main value-erase vs iterator-erase aur reallocation pe pointer invalidation jaanta hoon ::: L5 done