STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of: Visual walkthrough

5.2.20 · D2 · Coding › C++ Programming › STL algorithms — sort, find, transform, accumulate, copy, al

Prerequisites jinpe hum rely kar rahe hain (koi word naya lage toh kholna): Iterators and ranges, Lambda expressions, Function objects (functors), std::vector. Yeh STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of ka child hai.

Step 1 — Boxes ki row aur do pointers

KYA. Hum raw material se shuru karte hain: ek std::vector<int> jisme numbers $2, 5, 3$ hain. Abhi kuch nahi hai — na koi formula, na koi loop, sirf data ek row mein.

KYU. Koi bhi algorithm run karne se pehle hame agree karna hoga ki data kahan se start hota hai aur kahan khatam hota hai. STL iska jawab do iterators se deta hai — inhe boxes ko point karne wali ungliyon ki tarah socho.

==first== pehle element (box $0$ ) ko point karta hai.
==last== last box ke baad ek box aage point karta hai — last box ke baad ki khaali jagah.

first se lekar last tak (lekin last ko include nahi karte) boxes ka chunk $[first, last)$ likha jaata hai — left par square bracket matlab "included", right par round bracket matlab "excluded".

PICTURE. Red finger last hai; notice karo ki yeh $3$ ke aage point kar raha hai, $3$ par nahi.

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

Step 2 — Extra ingredient jo koi expect nahi karta: `init`

KYA. Hum ek teesri cheez add karte hain jo vector mein nahi hai: ek starting value jise ==init== kehte hain. Yahan hum $init = 0$ choose karte hain.

KYU. Ek fold ko running total shuru karne ke liye kahin se toh shuru karna hoga. Socho ek cash register: pehla item scan hone se pehle, display par koi number pehle se show ho raha hota hai. Woh pre-set number hi init hai. Agar hum + operation choose karein, toh hum chahenge ki register $0$ se start kare (adding $0$ kuch nahi badalta). Sahi init choose karna hi poora game hai — galat chose karein toh har jawab uss amount se off ho jaata hai.

PICTURE. Row ke neeche red box init hai — yeh vector ke bahar rehta hai lekin calculation ke andar hota hai.

Step 3 — Woh ek operation jo saara kaam karta hai: `op`

KYA. Hum ek binary operation ==op(a, b)== introduce karte hain — ek rule jo do numbers khaata hai aur ek return karta hai. Plain summation ke liye, op sirf addition hai: op(a, b) = a + b.

KYU. Ek do-argument rule kyun, na ki ek-argument wala? Kyunki folding mein hamesha abhi tak jo hai (a = running total) aur next box (b = next element) combine hote hain. Yeh fundamentally do-input act hai: purana total + naya value → naya total. C++ mein tum op ko ek lambda ya functor ke roop mein supply karte ho.

PICTURE. op red machine hai: do arrows andar (left = running total, right = next box), ek arrow bahar (new total).

Step 4 — Recurrence: ek box fold in kiya

KYA. Hum pehla real box lete hain, $e_{0} = 2$ , aur machine mein feed karte hain: $op (acc_{0}, e_{0}) = 0 + 2 = 2$ . Ise naya running total $acc_{1}$ ke roop mein store karo.

KYU. Yeh poore algorithm ka atom hai — crank ka ek single turn. Baad ki har cheez yahi exact move hai, repeat hoti hui. Ise ek aisi rule ki tarah likhna jo $acc_{k}$ ko $acc_{k + 1}$ mein badal de, hamare liye kisi bhi length ke vector ko ek line mein describe karne deta hai.

PICTURE. Red arrow dikhata hai ki purana total ( $0$ ) aur box ( $2$ ) machine mein enter kar rahe hain aur naya total ( $2$ ) bahar aa raha hai. first ek box right khisar gaya hai.

Step 5 — Crank ko end tak ghumaana

KYA. Hum Step 4 ko baaki har box ke liye repeat karte hain:

$acc_{1} = 0 + 2 = 2, acc_{2} = 2 + 5 = 7, acc_{3} = 7 + 3 = 10.$

Jab chalti hui first finger last tak pahunchti hai, hum ruk jaate hain. Final total $acc_{3} = 10$ wahi hai jo accumulate return karta hai.

KYU. Hum exactly last par ruke hain — ise kabhi touch nahi karte — kyunki last khaali jagah point karta hai (Step 1). Isliye half-open convention itna clean hai: loop condition sirf while (first != last) hai, aur yeh empty vector ke liye bhi kaam karta hai (loop body kabhi run nahi hota).

PICTURE. Staircase: har red step running total ko next box ki value se uthata hai, $10$ par khatam hota hai.

Worked example Woh code jo IS picture hai

vector<int> v{2, 5, 3};
int total = accumulate(v.begin(), v.end(), 0);   // == 10

v.begin() first hai, v.end() last hai, 0 init hai, aur invisible default op + hai.

Step 6 — `op` badlo, meaning badlo (product)

KYA. Machine swap karo. op(a, b) = a * b lo aur — crucially — init ko $1$ kar do:

$acc_{1} = 1 \cdot 2 = 2, acc_{2} = 2 \cdot 5 = 10, acc_{3} = 10 \cdot 3 = 30.$

KYU. Fold ki shape Step 5 jaisi hi hai — same staircase, same recurrence — sirf machine aur start value alag hai. $0$ se nahi, $1$ se kyun start karte hain? Kyunki start value operation ki identity honi chahiye: woh number jo apne partner ko unchanged chhod de. + ke liye woh $0$ hai; * ke liye woh $1$ hai. Product ko $0$ se start karo aur har answer $0$ ho jaata hai — yeh ek classic bug hai.

PICTURE. Step 5 jaisa wahi staircase skeleton lekin red multiplying machine aur init = 1 box; total multiplicatively $30$ tak jaata hai.

Common mistake Galat identity element

int p = accumulate(v.begin(), v.end(), 0,          // WRONG: 0 is + 's identity
                   [](int a, int b){ return a*b; });
// p == 0, because 0 * anything == 0

Fix: 1 pass karo — multiplication ki identity:

int p = accumulate(v.begin(), v.end(), 1,
                   [](int a, int b){ return a*b; });  // p == 30

Step 7 — Degenerate cases jinpar kabhi trip nahi karna chahiye

KYA. Do edge inputs decide karte hain ki tumhara mental model sach mein sahi hai ya nahi.

Empty range (first == last, jaise vector<int> v;): crank kabhi nahi ghoomta. Recurrence kuch naya produce nahi karta, toh result sirf init hota hai.
Type trap: running total ka type init ka type hota hai, elements ka type nahi. Ek vector<double> ko init = 0 (ek int) ke saath fold karo aur har partial total cut hokar whole number ban jaata hai.

KYU. Yahi exactly woh corners hain jahaan "usually works" code toot jaata hai. Empty case seedha half-open rule (Step 1) se nikalti hai: zero boxes ⇒ zero turns ⇒ answer start value hi hai. Type case Step 2 se nikalta hai: acc janam liya init ke barabar, toh woh apni poori life mein init ka type inherit karta hai.

PICTURE. Left: fingers touch kar rahi hain (empty), red result box = init. Right: real values $1.5, 2.5$ lekin ek int register $1.5 \to 1$ truncate kar raha hai, phir $1 + 2.5 \to 3$ sahi $4.0$ ki jagah.

Common mistake Truncation trap (sabse common real bug)

vector<double> v{1.5, 2.5};
auto bad  = accumulate(v.begin(), v.end(), 0);    // int acc: 0+1=1, 1+2=3  → 3  ✗
auto good = accumulate(v.begin(), v.end(), 0.0);  // double acc            → 4.0 ✓

Do characters .0 accumulator ka type badal dete hain aur har partial sum ko bacha lete hain.

Ek-picture summary

Upar ki saari cheezein — do fingers, bahari init, do-input machine, staircase, identity element, empty case — ek single diagram mein compress ki gayi hain. Red pipeline hi accumulate hai.

Recall Feynman retelling — kisi dost ko batao

Socho numbered boxes ki ek row aur do ungliyan: ek pehle box par, ek last box ke ek spot aage khaali jagah par point karti hui. Ek taraf tum ek chhota scratch pad pakde ho jisme ek starting number likha hai — wahi init hai. Ab tumhare paas ek machine hai jisme do slots hain: scratch pad ka number left slot mein daalo aur next box ka number right slot mein daalo; woh ek naya number wapas deti hai, jise tum scratch pad par pehle wale number ke upar likh dete ho. Apni ungli ek box right slide karo aur phir wahi karo. Jab teri ungli khaali spot par pahunche, ruko aur scratch pad padhlo — wahi answer hai. Machine ko "add" banao aur pad $0$ se shuroo karo: tumhe sum milega. "Multiply" choose karo aur $1$ se shuroo karo: tumhe product milega. Agar boxes decimals hain, toh pakka karo ki scratch pad khud bhi decimal ho (0.0), warna machine tumhara total round down karte rahegi. Aur agar koi box hi nahi hai, toh tum crank kabhi ghoomate nahi, isliye answer wahi hoga jo tumne pad par shuru mein likha tha. Yahi accumulate ka poora secret hai — aur har doosra STL algorithm same walk hai bas ek alag machine lagi hui.

Recall Quick self-test

accumulate empty range par kya return karta hai? ::: Exactly init — crank kabhi nahi ghoomta. vector<double> sum ke liye init 0.0 (na ki 0) kyun hona chahiye? ::: Accumulator ka type init ke type ke barabar hota hai; int init har partial sum truncate karta hai. Product fold ke liye sahi init kya hai? ::: 1, multiplication ka identity element (0 sab kuch zero kar deta). Running total op ke kis side jaata hai? ::: Left: op(acc, element) — yeh left fold hai.

Flashcards

accumulate ka result empty range par?

init unchanged (koi iteration run nahi hoti).

Accumulator ka type kis se determine hota hai?

init ke type se — mismatch truncation cause karta hai.

vector<double> sum karne ke liye sahi init?

0.0, 0 nahi.

Product fold ke liye sahi init?

1 (multiplication ki identity).