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

multiset<int> ms{50,50,20}; ms.erase(50);
``` — kitne elements bachte hain? ::: Ek (`20`) — value-`erase` `50` ki **har** copy hata deta hai, dono delete ho jaate hain. Sirf ek `50` drop karne ke liye iterator pass karna hoga: `ms.erase(ms.find(50))`.
 
```cpp
vector<int> v{1,2,3}; int* p=&v[0]; v.push_back(4); *p=9;
``` — kya galat hai? ::: `push_back` reallocate kar sakta hai, array ko move karke; `p` phir dangle karta hai aur `*p=9` undefined behaviour hai. Kisi bhi insert ke baad pointers/iterators dobara fetch karo, ya pehle `reserve()` karo.
 
```cpp
map<string,int> m; if (m["missing"] == 0) { /*...*/ }
``` — subtle bug? ::: `m["missing"]` us key ke liye jo wahan thi hi nahi, ek default `0` **insert** kar deta hai, silently map badha deta hai. Presence test karne ke liye bina insert kiye `m.find("missing") == m.end()` ya `m.count("missing")` use karo.
 
```cpp
for (auto it=s.begin(); it!=s.end(); ++it) if (*it<0) s.erase(it);
``` — yeh kyun break hota hai? ::: `erase(it)` `it` ko invalidate kar deta hai, isliye baad mein `++it` undefined hai. Returned iterator se fix karo: `it = s.erase(it);` (aur `++it` tabhi karo jab erase na karo).
 
```cpp
set<int> s; auto it=s.insert(5).first; *it = 6;
``` — legal hai? ::: Nahi — `set` ka element **hi** uski key hai; iterator ke through ise mutate karna tree ki ordering tod dega, isliye `set` iterators effectively `const` hote hain. Erase karke dobara insert karo.
 
```cpp
unordered_map<int,int> u{{1,10}}; u.reserve(1000); auto* p=&u[1]; u[2]=20; /* use *p */
``` — safe hai? ::: Pehle se reserve karne se doosra insert rehash nahi karega, isliye `p` (*mapped value* ka pointer) valid rehta hai. Note: rehash *iterators* ko invalidate karta hai lekin elements ke **references/pointers** ko nahi — yeh unordered containers ki ek unique subtlety hai.
 
---
 
## Why questions
 
`list::insert` $O(1)$ kyun hai lekin `vector::insert` middle mein $O(n)$? ::: `list` sirf do `prev`/`next` pointers relink karta hai, kuch aur touch nahi karta. `vector` contiguous hai, isliye middle insert mein har baad wale element ko ek slot upar shift karna padta hai jagah banane ke liye.
 
Hum `map` ko `unordered_map` ke upar kabhi kyun choose karte hain jabki $O(1)$ vs $O(\log n)$ hai? ::: Kyunki `map` sorted iteration aur range queries (`lower_bound`, `upper_bound`) free mein deta hai, aur hard $O(\log n)$ worst case hai, jabki `unordered_map` mein yeh sab nahi aur bure [[Hash functions and collisions|collisions]] par $O(n)$ tak degrade ho jaata hai.
 
`vector` ka amortised cost $O(1)$ kyun hai jabki single pushes $O(n)$ cost kar sakte hain? ::: Doubling reallocations ko rare banati hai; $n$ pushes mein total copy work ek geometric sum $1+2+4+\dots < 2n$ hai, isliye faila ke $<3n/n = O(1)$ per push aata hai (dekho [[Amortised analysis]]).
 
`deque` $O(1)$ `push_front` kyun deta hai jabki `vector` $O(n)$ deta hai? ::: `deque` ek *block map* rakhta hai aur purana data move kiye bina ek naya chunk prepend kar sakta hai (ya existing front chunk fill kar sakta hai). `vector` mein sirf ek block hai, isliye front-insert mein saare elements right shift karne padte hain.
 
Balanced tree ki height $\approx \log_2 n$ kyun hoti hai aur yeh kyun matter karta hai? ::: Level $i$ mein most $2^i$ nodes hote hain, isliye $n$ nodes ke liye height $h \ge \log_2(n+1)-1$ chahiye; har search ek level per comparison utarta hai, giving $O(\log n)$ (dekho [[Big-O notation]]).
 
`unordered_map` "$O(1)$ average" hone ke bawajood phir bhi $O(n)$ kyun hit kar sakta hai? ::: Agar bahut saari keys same bucket mein hash ho jaayein (bura hash ya adversarial input), toh us bucket ki chain ek linear list ban jaati hai aur lookup sab walk karta hai — average worst case mein collapse ho jaata hai.
 
Simple sum-all loop ke liye `array` `list` se kyun better hai chahe dono $O(n)$ ho? ::: `array` contiguous hai, isliye CPU neighbours ko cache mein prefetch karta hai; `list` nodes scattered hote hain, har node par ek [[Cache locality|cache miss]] hoti hai — same Big-O, wildly different constant.
 
---
 
## Edge cases
 
Empty `multiset` par `*ms.begin()` kya return karta hai? ::: Undefined behaviour — empty hone par `begin()==end()` hota hai, aur `end()` ko dereference karna illegal hai. Pehle hamesha `if (!ms.empty())` se guard karo.
 
`set` par `s.erase(value)` jab `value` absent ho — crash? ::: Nahi — value-`erase` *count removed* return karta hai (yahan `0`) aur kuch nahi karta. `erase(iterator)` ko valid iterator chahiye aur `end()` par unsafe hai.
 
Kya `std::array` par `push_back` kar sakte hain? ::: Nahi — `array` ==fixed-size== hai, isliye usmein `push_back`, `insert`, ya `resize` nahi hai; uska `N` compile time par baked in hota hai.
 
`vector<int> v; v.reserve(100);` ke baad `v.size()` vs `v.capacity()` kya hoga? ::: `size()` `0` hai (abhi koi elements nahi) lekin `capacity()` kam se kam `100` hai — `reserve` elements construct kiye bina room allocate karta hai, isliye future pushes us point tak reallocate nahi karenge.
 
`map` mein insert karne par — kya existing iterators invalidate ho jaate hain? ::: Nahi — tree-based associative containers insert par har node ko jagah par rakhte hain, isliye saare iterators/references valid rehte hain (sirf `erase` erased element ko invalidate karta hai). Yeh `vector` ke bilkul opposite hai.
 
`unordered_set` rehash karne par — kya bachta hai? ::: Element **pointers aur references survive** karte hain, lekin **iterators invalidate** ho jaate hain kyunki bucket structure rebuild hoti hai. Agar inserts ke across iterators hold karne hain toh pehle se reserve karo.
 
`map<int,int>{{3,0},{1,0},{2,0}}` kis order mein iterate hoga? ::: `1, 2, 3` — insertion order nahi, keys; tree har pair insert hote waqt key par sort karta hai.
 
---
 
> [!recall]- Traps ka one-line summary
> Guarantees ::: `map`/`set` = sorted + $O(\log n)$ worst case; `unordered_*` = $O(1)$ average, no order, $O(n)$ worst.
> Iterator survival ::: `vector` insert sab invalidate kar sakta hai; `map`/`set` insert kuch invalidate nahi karta; unordered rehash iterators kill karta hai lekin references nahi.
> `erase(value)` ::: multiset/multimap par **saare** matches remove karta hai (aur set/map par 0-or-more); exactly ek remove karne ke liye iterator pass karo.