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

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

---

Scenario matrix

Kuch bhi solve karne se pehle, chalte hain har case class map karte hain jo yeh 7 algorithms hit kar sakte hain. Har row ek "corner" hai behaviour ka; last column us worked example ka naam deta hai jo uspe land karta hai.

#	Algorithm	Case class (tricky corner)	Covered by
A	sort	custom comparator, stability & ties	Ex 1
B	sort	degenerate: empty / single-element range	Ex 1 (part b)
C	find	value present vs absent (the last sentinel)	Ex 2
D	transform	in-place alias (dest == first)	Ex 3
E	transform	two-range binary op	Ex 3 (part b)
F	accumulate	type trap: int init over double data	Ex 4
G	accumulate	non-+ fold; identity element matters	Ex 5
H	copy	no room → back_inserter fix	Ex 6
I	all_of / any_of	empty range vacuous truth / falsity	Ex 7
J	all_of / any_of	short-circuit stops early	Ex 7 (part b)
K	Real-world word problem	kai algorithms combine karo	Ex 8
L	Exam twist	return value precisely padhna	Ex 9

Nau examples, barah cells. Chalte hain.

---

Ex 1 — sort with ties, aur degenerate ranges (cells A, B)

Forecast: descending result guess karo, aur guess karo ki (b) crash karta hai ya nahi.

Part (a) — steps.

1. Comparator likho [](int a, int b){ return a > b; }. Yeh step kyun? sort cmp(a,b) call karta hai aur a ko b se pehle rakhta hai jab woh true return karta hai. "a > b true hai jab a bada ho" ⇒ bade elements pehle aate hain ⇒ descending. Default < ascending deta hai.
2. sort(v.begin(), v.end(), cmp) apply karo. Yeh step kyun? std::vector ke random-access iterators introsort ko $O(n\log n)$ kaam karne dete hain (dekho Time complexity Big-O).
3. Dono 1 tied hain. std::sort guaranteed stable nahi hai, isliye unka relative order unspecified hai — lekin kyunki dono 1 hain, hum bata nahi sakte, aur matter bhi nahi karta. Yeh step kyun? Ties ek real corner hain: agar tumhe equals mein original order preserve karna ho, toh stable_sort use karo.

Result: v = {9, 6, 5, 4, 3, 2, 1, 1}.

Part (b) — degenerate steps.

1. Empty range: first == last, toh "smart loop" zero iterations chalata hai. Koi crash nahi, vector {} rehta hai.
2. Single element: compare karne ke liye kuch nahi, loop body kabhi swap nahi karta. {7} rehta hai. Yeh step kyun? Half-open range [first, last) dono ko natural base cases banata hai — kabhi special if ki zaroorat nahi.

---

Ex 2 — find: present aur absent (cell C)

Forecast: dono cases mein kaun sa iterator wapas aata hai, aur kya index?

Steps.

1. auto it1 = find(v.begin(), v.end(), 30); Yeh step kyun? find ek linear $O(n)$ scan hai jo pehle match ka iterator return karta hai.
2. Kyunki 30 present hai, it1 != v.end(). Index = it1 - v.begin() = 2. Yeh step kyun? begin() ko found iterator se subtract karna position deta hai — yeh sirf random-access iterators ke liye valid hai.
3. auto it2 = find(v.begin(), v.end(), 99); Yeh step kyun? Ab failure path test karo — scenario matrix ka poora point yahi hai ki yeh path exist karta hai.
4. 99 absent hai ⇒ it2 == v.end(). Isse dereference mat karo, aur nullptr se compare mat karo. Yeh step kyun? Sentinel wohi last hai jo tumne pass kiya — yeh hamesha exist karta hai, empty vectors ke liye bhi.

---

Ex 3 — transform: in-place, phir two-range (cells D, E)

Forecast: kya source overwrite karna baad ke elements corrupt karega?

Part (a) — steps.

1. transform(v.begin(), v.end(), v.begin(), [](int x){ return x*x*x; }); Yeh step kyun? 3rd argument dest hai. dest == first set karna matlab hai "results source pe wapas likho."
2. Kya yeh safe hai? transform element i padhta hai, compute karta hai, element i likhta hai — i+1 ko touch karne se pehle. Koi element overwrite hone ke baad nahi padha jata. Yeh step kyun? Aliasing tabhi dangerous hoti hai jab koi write kisi cheez ko clobber kare jo baad ki read ko chahiye; yahan ek hi slot ka read aur write pair hain, isliye safe hai.

Result: v = {1, 8, 27, 64}.

Part (b) — two-range steps.

1. Room ke saath destination banao: vector<int> net(3); Yeh step kyun? Baad ke copy mistakes ki tarah nahi, hum pre-size karte hain toh net.begin() pe likhna legal hai.
2. transform(p.begin(), p.end(), d.begin(), net.begin(), [](int a, int b){ return a - b; }); Yeh step kyun? Binary form dono ranges ko lockstep mein chalta hai, g(p[i], d[i]) call karta hai. 2nd range ko sirf ek first (d.begin()) chahiye — uski length pehli range se ≥ assume ki jati hai.

Result: net = {90, 175, 270}.

---

Ex 4 — accumulate: int-vs-double type trap (cell F)

Forecast: dono sums guess karo — unme se ek jaanboojhkar galat hai.

Steps.

1. accumulate(v.begin(), v.end(), 0) — accumulator type init ka type hai, yahan int. Yeh step kyun? Parent note ka rule: result type = init type. Yahi poora trap hai.
2. Fold trace karo int mein truncation ke saath har + pe: ${\text{acc}}_0=0$; $0+1.5=1.5\to$ truncated to $1$; $1+2.5=3.5\to 3$; $3+3.0=6.0\to 6$. Yeh step kyun? Har partial sum int mein store hota hai, isliye fractional parts har step pe gayab hote hain, sirf end mein nahi.
3. (a) ka result = 6. Ab (b): accumulate(v.begin(), v.end(), 0.0) double accuracy rakhta hai. Yeh step kyun? 0.0 pass karna accumulator ko double banata hai; sahi sum bachta hai.
4. Sahi sum $=1.5+2.5+3.0=7.0$.

---

Ex 5 — accumulate non-sum fold ki tarah: identity matters (cell G)

Forecast: (a) guess karo, phir (b) mein disaster predict karo.

Steps.

1. accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a*b; }); Yeh step kyun? Multiplication ke liye identity element (wo value jo kuch nahi badlati) 1 hai, kyunki $1\times x=x$. Isliye init 1 hona chahiye.
2. Fold: $1\to 1\cdot 2=2\to 2\cdot 3=6\to 6\cdot 4=24$. Answer 24.
3. (b) init = 0 ke saath: $0\to 0\cdot 2=0\to 0\to 0$. Answer 0 — hamesha zero! Yeh step kyun? 0 multiplication ka absorbing element hai, identity nahi. Galat init chuno aur answer meaningless hai.
4. (c) accumulate(w.begin(), w.end(), string(""), [](string a, string b){ return a + b; }); Yeh step kyun? String concatenation ka identity empty string "" hai. Left-fold: "" + "a" + "b" + "c" = "abc".

Recall Identity rule

Har fold ko init = operation ki identity chahiye: +→0, *→1, &&→true, ||→false, string +→"". Warna tum result shift ya corrupt karte ho.

---

Ex 6 — copy with no room, aur back_inserter fix (cell H)

Forecast: (a) mein kya galat hota hai?

Steps.

1. (a) vector<int> dst; copy(src.begin(), src.end(), dst.begin()); Yeh step kyun? Yeh sahi lagta hai — hum dest ko dst.begin() pe point karte hain. Lekin dst ka size 0 hai, toh dst.begin() == dst.end(). Assign karne ke liye koi slot nahi hai.
2. Result: undefined behaviour (end ke baad likhna). Yeh crash ho sakta hai, silently memory corrupt kar sakta hai. Yeh dst ko grow nahi karta. Yeh step kyun? copy assign karta hai; yeh kabhi push_back call nahi karta. Yahi corner hai jo matrix demand karta hai.
3. (b) copy(src.begin(), src.end(), back_inserter(dst)); Yeh step kyun? back_inserter(dst) ek output iterator hai jiska "assign" actually dst.push_back(...) call karta hai, toh dst har element ko hold karne ke liye grow karta hai.

Result: dst = {5, 6, 7}.

---

Ex 7 — all_of / any_of: empty range aur short-circuit (cells I, J)

Forecast: (a) mein dono booleans guess karo aage padhne se pehle.

Part (a) — steps.

1. all_of on {}: "har element even hai" ka koi counterexample nahi hai, toh logic se $\forall x\in \varnothing .P(x)$ true hai. Yeh step kyun? Yeh vacuous truth hai. Yeh AND-folding se bhi match karta hai true se start karke: kuch nahi pe fold karo toh true milta hai.
2. any_of on {}: "koi element even hai" ka koi witness nahi hai, toh yeh false hai. Yeh step kyun? OR-folding false se start karne se match karta hai.

Part (b) — short-circuit steps.

1. all_of left to right scan karta hai, isEven check karta hai. Figure dekho: 2 ✓, 4 ✓, phir 5 ✗. Yeh step kyun? all_of faltan hi false return karta hai jab ek element fail hota hai — use 6 ya 8 dekhne ki zaroorat nahi.
2. Yeh index 2 pe rukta hai (woh 5). false return karta hai. Yeh step kyun? Short-circuiting ek performance guarantee hai: worst case $O(n)$, lekin jab ho sake jaldi quit kar deta hai.

---

Ex 8 — Word problem: algorithms combine karo (cell K)

Forecast: teeno answers predict karo.

Steps.

1. Total: accumulate(s.begin(), s.end(), 0) → int mein sum karta hai. Sab data ints hain, toh 0 sahi identity hai. Yeh step kyun? Sum ek left fold hai + ke saath; identity 0. $120+0+340+0+275=735$.
2. Kabhi band? any_of(s.begin(), s.end(), [](int x){ return x == 0; }). Yeh step kyun? "Kabhi band" = "kya kam se kam ek zero hai" = existential = any_of. Do zeros hain, toh true.
3. Sorted high-to-low: sort(s.begin(), s.end(), greater<int>()). Yeh step kyun? greater<int>() ek functor hai jo a > b ke equivalent hai ⇒ descending. Zeros bottom pe sort hote hain. Result {340, 275, 120, 0, 0}.

---

Ex 9 — Exam twist: return value exactly padho (cell L)

Forecast: trick yeh hai ki transform kya return karta hai, yeh nahi ki kya likhta hai.

Steps.

1. transform har 3 elements ke liye x+10 likhta hai: out = {11, 12, 13}. Yeh step kyun? Seedha unary map.
2. transform last likhne wale element se ek aage ka iterator return karta hai — yahan out.begin() + 3. Yeh step kyun? Yeh consistent [first, last) philosophy hai: return exactly wohi hai jahan next algorithm likhna continue karta.
3. ret - out.begin() = 3. Yeh step kyun? Start se "last written se ek aage" tak ki distance likhne ki count ke barabar hai.

---

Recall Har cell ke liye ek-line recall

sort ties :::: equals mein order unspecified hai (stable_sort use karo agar matter kare) find absent :::: last return karta hai, kabhi nullptr nahi transform in-place :::: safe hai kyunki slot i ka read+write i+1 se pehle hota hai accumulate int init over doubles :::: har step pe truncate karta hai → galat accumulate identity :::: +→0, *→1, &&→true, ||→false, string→"" copy into empty :::: UB; back_inserter use karo all_of empty / any_of empty :::: true / false algorithm return values :::: transform/copy "last written se ek aage" return karta hai

---

Flashcards