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

5.2.20 · Coding › C++ Programming

Unifying idea: iterator range `[first, last)`

1. `sort` — ek range ko reorder karo

Worked example Descending sort karo

vector<int> v{3,1,4,1,5};
sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
// v = {5,4,3,1,1}

Ye step kyun? Lambda a > b true return karta hai jab a ko b se pehle aana chahiye; "bada pehle" ⇒ descending. Default < ascending deta.

2. `find` — pehla matching element locate karo

Common mistake Steel-man: "Main

if (it == nullptr) check karunga" Ye sahi lagta hai kyunki C mein tum NULL use karte the "not found" ke liye. Lekin find ek iterator return karta hai, pointer nahi — failure sentinel last hai, nullptr nahi. Fix: hamesha usi last se compare karo jo tune pass kiya tha:

auto it = find(v.begin(), v.end(), 7);
if (it != v.end()) { /* mila, *it use karo */ }

Worked example

find karo phir position use karo

vector<int> v{10,20,30};
auto it = find(v.begin(), v.end(), 20);
size_t idx = it - v.begin();   // idx == 1

Ye step kyun? Found iterator se begin() subtract karne par index milta hai (sirf random-access mein).

3. `transform` — ek range par function map karo

Worked example Har element ko in-place square karo

vector<int> v{1,2,3,4};
transform(v.begin(), v.end(), v.begin(),
          [](int x){ return x*x; });
// v = {1,4,9,16}

Ye step kyun? dest == v.begin() matlab "source ko overwrite karo." transform ke liye ye safe hai kyunki element i read aur write hota hai element i+1 se pehle.

4. `accumulate` — range ko ek value mein fold karo (`<numeric>`)

Common mistake Steel-man: "

accumulate(v.begin(), v.end(), 0) average deta hai / doubles ke liye kaam karta hai" Lagta hai sahi hai kyunki ye sab kuch sum karta hai. Lekin result type, init ka type hota hai. 0 (ek int) pass karo vector<double> par aur har partial sum int mein truncate ho jaata hai! Fix: 0.0 pass karo (ya bade sums ke liye 0LL):

double s = accumulate(v.begin(), v.end(), 0.0);

Worked example Sum ki jagah product

vector<int> v{1,2,3,4};
int p = accumulate(v.begin(), v.end(), 1,
                   [](int a, int b){ return a*b; });
// p == 24

Ye step kyun? Product ke liye identity element 1 hota hai, 0 nahi — init operation ka identity hona chahiye warna answer galat aayega.

5. `copy` — ek range duplicate karo

Common mistake Steel-man: "empty vector mein copy karo"

vector<int> dst;                // size 0!
copy(src.begin(), src.end(), dst.begin());  // UB — koi space nahi

Sahi lagta hai (humne kaha tha dest dst.begin() hai). Lekin copy assign karta hai, grow nahi karta. Fix: copy(src.begin(), src.end(), back_inserter(dst)); (ek inserter iterator push_back call karta hai).

6 & 7. `all_of` / `any_of` — range par quantifiers

Worked example

vector<int> v{2,4,6};
bool allEven = all_of(v.begin(), v.end(), [](int x){ return x%2==0; }); // true
bool anyNeg  = any_of(v.begin(), v.end(), [](int x){ return x<0; });    // false

Ye step kyun? Predicate per element bool return karta hai; all_of AND-fold karta hai, any_of OR-fold karta hai.

Figure — STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of

Recall Feynman: 12-saal ke bacche ko explain karo

Socho ek row mein toy boxes hain. Robot ko ye kehne ki jagah "box 1 se box 5 tak ja aur kuch karo," tum use ek task card dete ho:

sort = "inhe chhote se bade mein line karo."
find = "pehle red box ki taraf point karo; agar koi nahi hai, end ke aage point karo."
transform = "har box ko paint karo aur painted copy ek nayi shelf par rakho."
accumulate = "boxes par likhe saare numbers add karo, ek number se shuru karo jo main tujhe dunga."
copy = "yahan ek duplicate row banao (dhyan raho shelf kaafi badi ho!)."
all_of = "KYA SAARE boxes red hain?" any_of = "KYA KOI box red hai?" Tum sirf goal batao; robot chalna sambhal leta hai. Galti ke liye kam jagah, padhne mein aasaan.

Flashcards

Lagbhag saare STL algorithms kaun sa range convention use karte hain?

Half-open range [first, last) — first included, last (one past end) excluded.

Jab value nahi milti toh find kya return karta hai?

Wahi last iterator jo tumne pass kiya tha (NOT nullptr).

accumulate ka init desired result type se kyun match karna chahiye?

Accumulator type init ka type hota hai; 0 (int) doubles par har partial sum truncate kar deta hai. 0.0 use karo.

accumulate ke zariye product ke liye identity init kya hai?

1 (sum ke liye 0 hota hai).

Tum std::list ko std::sort kyun nahi kar sakte?

sort ko random-access iterators chahiye; list mein sirf bidirectional hain — list.sort() use karo.

std::sort ka worst-case time kya hai?

O (n lo g n)

— introsort iska guarantee karta hai (quicksort + heapsort fallback).

all_of empty range par kya return karta hai, aur kyun?

true — vacuous truth:

\forall x \in \emptyset

hold karta hai (koi counterexample nahi).

any_of empty range par kya return karta hai?

false — koi element exist hi nahi karta predicate satisfy karne ke liye.

Empty/auto-growing vector mein safely copy kaise karte hain?

Destination iterator ke roop mein back_inserter(dst) use karo.

transform kya return karta hai?

Destination mein last written element se ek aage ka iterator.

sort ke liye ek lambda tab true return karta hai jab…?

…uska pehla argument doosre se PEHLE aana chahiye (ek strict-weak-ordering "less-than").

Vector mein find result it ka index kaise nikaalte hain?

it - v.begin() (sirf random-access iterators mein).

Connections

Iterators and ranges — woh abstraction jis par har algorithm ride karta hai.
Lambda expressions — predicates/comparators kaise pass kiye jaate hain.
Function objects (functors) — op/pred ke liye lambdas ka alternative.
Time complexity Big-O — $O (n lo g n)$ aur $O (n)$ costs ko justify karta hai.
std::vector — sabse common container jis par ye run karte hain.
Ranges library (C++20) — modern, composable successor.