Question bank — STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of

auto it = find(v.begin(), v.end(), 7);
if (it == nullptr) { /* not found */ }
``` ::: `find` ek **iterator** return karta hai, kabhi pointer nahi, isliye "nahi mila" sentinel `v.end()` hai, `nullptr` nahi. Fix: `if (it == v.end())`.
 
```cpp
vector<int> dst;
copy(src.begin(), src.end(), dst.begin());
``` ::: `dst` ka size 0 hai, isliye `dst.begin() == dst.end()` — assign karne ke liye koi slot nahi hai (undefined behaviour). Fix: `copy(src.begin(), src.end(), back_inserter(dst));`.
 
```cpp
double avg = accumulate(v.begin(), v.end(), 0) / v.size();
``` ::: Do bugs hain: `init = 0` ek `double` sum ko `int` mein truncate karta hai, aur `v.size()` unsigned hai isliye division integer division hai. Fix: `accumulate(..., 0.0) / v.size()` (ya cast karo).
 
```cpp
auto end2 = find(v.begin(), v.end(), x);
size_t idx = end2 - w.begin();
``` ::: Iterator range `v` se aaya lekin **alag** container `w` ke `begin()` se subtract kiya gaya. Index arithmetic sirf *usi* container ke andar meaningful hoti hai. Fix: `v.begin()` subtract karo.
 
```cpp
sort(v.begin(), v.end(), [](int a, int b){ return a >= b; });
``` ::: `>=` equal elements ke liye `true` return karta hai, strict weak ordering violate karta hai (`cmp(a,a)` `false` hona chahiye). Fix: descending order ke liye `>` use karo.
 
```cpp
transform(a.begin(), a.end(), b.begin(), out.begin(), plus<>{});
// a has 5 elements, b has 3
``` ::: Binary `transform` `a` ke saath lockstep mein `b` se padhta hai lekin `a.end()` tak hi rukta hai; `b` chhota hone se yeh `b` ke end ke baad chala jaata hai — undefined behaviour. Dono input ranges pehli jitni lambi honi chahiye.
 
```cpp
list<int> L{3,1,2};
sort(L.begin(), L.end());
``` ::: `std::sort` ko random-access iterators chahiye; list sirf bidirectional iterators deti hai, isliye yeh compile nahi hoga. Fix: `L.sort();` (member function).
 
---
 
## Why questions
 
Range half-open `[first, last)` kyun hai naa ki `[first, last]`? ::: Taaki size exactly `last - first` ho (koi `+1` nahi), empty range naturally `first == last` ho, aur "nahi mila" hamesha valid sentinel `last` return kar sake. Dekho [[Iterators and ranges]].
 
`transform` "ek past the last written" element return kyun karta hai naa ki kuch nahi? ::: Taaki aap **chain** kar sako: woh iterator exactly wahan hai jahan se next algorithm likhna shuru kare, poori library ko `[first, last)` philosophy ke saath consistent rakhte hue.
 
`accumulate` ka `init` operation ka *identity* kyun hona chahiye? ::: Fold `init` se shuru hota hai aur `op` har element par apply karta hai. `+` ke liye identity `0` hai; `*` ke liye `1` hai. Galat `init` (jaise product ke liye `0`) poore result ko `0` kar deta hai.
 
Hum kyun kehte hain STL algorithms "declarative" hain? ::: Aap state karte ho **kya** chahiye (`sort`, `find`, `all_of`) naa ki hand-write karte ho **kaise** loop chalao. Isse off-by-one bugs khatam hote hain aur intent ek nazar mein readable hoti hai — parent ka core "big picture" idea yahi hai.
 
`sort` $O(n\log n)$ worst case guarantee kyun de sakta hai jab akela quicksort nahi de sakta? ::: `std::sort` **introsort** hai: yeh quicksort se shuru hota hai lekin buri recursion depth detect karta hai aur heapsort par switch karta hai, jo $O(n\log n)$ worst case hai. Dekho [[Time complexity Big-O]].
 
`sort` ko plain function pointer ki jagah *functor* pass karna kabhi kabhi better kyun hota hai? ::: Function object ka `operator()` compiler dwara **inline** kiya ja sakta hai (iska type compile time par known hota hai), jabki function pointer often indirect call force karta hai. Dekho [[Function objects (functors)]].
 
Hand-written loop with flag ki jagah `all_of(...)` prefer kyun karein? ::: Yeh intent name karta hai ("kya sab even hain?"), automatically short-circuit karta hai, aur classic bug nahi aa sakta jaise `break` bhoolna ya flag galat initialize karna.
 
---
 
## Edge cases
 
Size 0 ya 1 ki range par `sort` — kya hota hai? ::: Kuch reorder nahi karna; yeh ek valid no-op hai. Algorithms is tarah likhe hain ki degenerate ranges "just work" karein `[first, last)` convention ki wajah se.
 
Empty range par `accumulate` — kya wapas aata hai? ::: Exactly `init`, bina kisi badlav ke. Fold `op` zero baar apply karta hai, isliye starting value hi jawab hai.
 
Empty range par `find` — kya return karta hai? ::: `last` (jo yahan `first` ke barabar hai), yaani "nahi mila", general sentinel rule ke saath consistent.
 
`copy` jab source aur destination **same** range ho — safe hai? ::: Identical iterators ke saath khud par copy karna harmless hai, lekin **overlapping** ranges jahan `dest` `[first, last)` ke andar aur `first` se aage ho, undefined hai — `copy_backward` ya `std::move` semantics carefully use karo.
 
`all_of` jab range mein exactly ek failing element sabse aage ho — cost? ::: Effectively $O(1)$: yeh pehle element par short-circuit karta hai aur turant `false` return karta hai baaki scan kiye bina.
 
`transform` jab `dest` source range ke beech mein point kare — safe hai? ::: Generally nahi. In-place sirf tabhi safe guarantee hai jab `dest == first` ho (element read phir write karo aage badhne se pehle). Overlapping offset abhi-tak-na-padhe inputs ko clobber kar sakta hai — undefined behaviour.
 
`any_of` ek range par jahan predicate kisi element ke liye match se pehle throw kare — kya hota hai? ::: Exception `any_of` se bahar propagate ho jaata hai turant; koi "swallow and continue" nahi hai. Predicates in quantifiers ke liye total (na throw karne wale) hone chahiye.
 
C++20 ranges versions (`std::ranges::sort(v)`) — kaunsi boundary annoyance door karte hain? ::: Aap `v.begin(), v.end()` ki jagah directly container pass karte ho, mismatched-iterator bugs khatam hote hain (jaise `v.begin()` ko `w.end()` ke saath mix karna). Dekho [[Ranges library (C++20)]].
 
---
 
> [!recall]- One-line survival rules
> Range `[first, last)` hai — last excluded ::: Size hai `last - first`, empty hai `first == last`, "nahi mila" hai `last`.
> `find` fail hota hai with ::: `last`, kabhi `nullptr` nahi.
> `accumulate` result type hai ::: `init` ka type — doubles ke liye `0.0` use karo.
> Empty vector mein `copy` ke liye chahiye ::: `back_inserter(dst)`.
> `all_of` empty par hai ::: `true` (vacuous); `any_of` empty par hai `false`.
> `sort` ko chahiye ::: random-access iterators (`std::list` par nahi).