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

---

The scenario matrix

Before solving anything, let's map out every case class these 7 algorithms can hit. Each row is a "corner" of behaviour; the last column names the worked example that lands on it.

#	Algorithm	Case class (the 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	combine several algorithms	Ex 8
L	Exam twist	reading the return value precisely	Ex 9

Nine examples, twelve cells. Let's go.

---

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

Forecast: guess the descending result, and guess whether (b) crashes.

Part (a) — steps.

1. Write the comparator [](int a, int b){ return a > b; }. Why this step? sort calls cmp(a,b) and puts a before b when it returns true. "a > b is true when a is bigger" ⇒ bigger elements come first ⇒ descending. The default < gives ascending.
2. Apply sort(v.begin(), v.end(), cmp). Why this step? Random-access iterators from std::vector let introsort do its $O(n\log n)$ work (see Time complexity Big-O).
3. The two 1s are tied. std::sort is not guaranteed stable, so their relative order is unspecified — but since both are 1, we cannot tell, and it does not matter. Why this step? Ties are a real corner: if you needed to preserve original order among equals, you'd use stable_sort.

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

Part (b) — degenerate steps.

1. Empty range: first == last, so the "smart loop" runs zero iterations. No crash, vector stays {}.
2. Single element: nothing to compare against, loop body never swaps. Stays {7}. Why this step? The half-open range [first, last) makes both these the natural base cases — never a special if.

---

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

Forecast: what iterator comes back in each case, and what index?

Steps.

1. auto it1 = find(v.begin(), v.end(), 30); Why this step? find is a linear $O(n)$ scan returning an iterator to the first match.
2. Since 30 is present, it1 != v.end(). Index = it1 - v.begin() = 2. Why this step? Subtracting begin() from a found iterator gives the position — valid only for random-access iterators.
3. auto it2 = find(v.begin(), v.end(), 99); Why this step? Now test the failure path — the whole point of the scenario matrix is that this path exists.
4. 99 is absent ⇒ it2 == v.end(). Do not dereference it, and do not compare to nullptr. Why this step? The sentinel is the same last you passed in — this always exists, even for empty vectors.

---

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

Forecast: will overwriting the source corrupt later elements?

Part (a) — steps.

1. transform(v.begin(), v.end(), v.begin(), [](int x){ return x*x*x; }); Why this step? The 3rd argument is dest. Setting dest == first means "write results back onto the source."
2. Is that safe? transform reads element i, computes, writes element i — all before touching i+1. No element is read after it's overwritten. Why this step? Aliasing is only dangerous when a write clobbers something a later read needs; here the read and write of the same slot are paired, so it's safe.

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

Part (b) — two-range steps.

1. Make a destination with room: vector<int> net(3); Why this step? Unlike copy mistakes later, we pre-size so writing to net.begin() is legal.
2. transform(p.begin(), p.end(), d.begin(), net.begin(), [](int a, int b){ return a - b; }); Why this step? The binary form walks both ranges in lockstep, calling g(p[i], d[i]). The 2nd range only needs a first (d.begin()) — its length is assumed ≥ the first range's.

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

---

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

Forecast: guess both sums — one of them is wrong on purpose.

Steps.

1. accumulate(v.begin(), v.end(), 0) — the accumulator type is the type of init, here int. Why this step? The parent note's rule: result type = init type. This is the whole trap.
2. Trace the fold with truncation to int at each +: ${\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$. Why this step? Each partial sum is stored as int, so fractional parts vanish at every step, not just at the end.
3. Result of (a) = 6. Now (b): accumulate(v.begin(), v.end(), 0.0) keeps double accuracy. Why this step? Passing 0.0 makes the accumulator a double; the true sum survives.
4. True sum $=1.5+2.5+3.0=7.0$.

---

Ex 5 — accumulate as a non-sum fold: identity matters (cell G)

Forecast: guess (a), then predict the disaster in (b).

Steps.

1. accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a*b; }); Why this step? For multiplication the identity element (the value that changes nothing) is 1, since $1\times x=x$. So init must be 1.
2. Fold: $1\to 1\cdot 2=2\to 2\cdot 3=6\to 6\cdot 4=24$. Answer 24.
3. (b) With init = 0: $0\to 0\cdot 2=0\to 0\to 0$. Answer 0 — always zero! Why this step? 0 is the absorbing element of multiplication, not the identity. Pick the wrong init and the answer is meaningless.
4. (c) accumulate(w.begin(), w.end(), string(""), [](string a, string b){ return a + b; }); Why this step? The identity for string concatenation is the empty string "". Left-fold: "" + "a" + "b" + "c" = "abc".

Recall The identity rule

Every fold needs init = the operation's identity: +→0, *→1, &&→true, ||→false, string +→"". Otherwise you shift or corrupt the result.

---

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

Forecast: what goes wrong in (a)?

Steps.

1. (a) vector<int> dst; copy(src.begin(), src.end(), dst.begin()); Why this step? This looks right — we point dest at dst.begin(). But dst has size 0, so dst.begin() == dst.end(). There is no slot to assign into.
2. Result: undefined behaviour (writing past the end). It may crash, may silently corrupt memory. It does not grow dst. Why this step? copy assigns; it never calls push_back. This is the corner the matrix demands.
3. (b) copy(src.begin(), src.end(), back_inserter(dst)); Why this step? back_inserter(dst) is an output iterator whose "assign" actually calls dst.push_back(...), so dst grows to hold each element.

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

---

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

Forecast: guess the two booleans in (a) before reading on.

Part (a) — steps.

1. all_of on {}: there is no counterexample to "every element is even," so by logic $\forall x\in \varnothing .P(x)$ is true. Why this step? This is vacuous truth. It also matches AND-folding starting from true: fold over nothing leaves true.
2. any_of on {}: there is no witness to "some element is even," so it is false. Why this step? Matches OR-folding starting from false.

Part (b) — short-circuit steps.

1. all_of scans left to right, checking isEven. Look at the figure: 2 ✓, 4 ✓, then 5 ✗. Why this step? all_of returns false the instant one element fails — it does not need to see 6 or 8.
2. It stops at index 2 (the 5). Returns false. Why this step? Short-circuiting is a performance guarantee: worst case $O(n)$, but it quits early when it can.

---

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

Forecast: predict all three answers.

Steps.

1. Total: accumulate(s.begin(), s.end(), 0) → sums as int. All data are ints, so 0 is the right identity. Why this step? Sum is a left fold with +; identity 0. $120+0+340+0+275=735$.
2. Ever closed? any_of(s.begin(), s.end(), [](int x){ return x == 0; }). Why this step? "Ever closed" = "is there at least one zero" = existential = any_of. There are two zeros, so true.
3. Sorted high-to-low: sort(s.begin(), s.end(), greater<int>()). Why this step? greater<int>() is a functor equivalent to a > b ⇒ descending. Zeros sort to the bottom. Result {340, 275, 120, 0, 0}.

---

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

Forecast: the trick is what transform returns, not what it writes.

Steps.

1. transform writes x+10 for each of the 3 elements: out = {11, 12, 13}. Why this step? Straightforward unary map.
2. transform returns the iterator one past the last written element — here out.begin() + 3. Why this step? This is the consistent [first, last) philosophy: the return is exactly where the next algorithm would continue writing.
3. ret - out.begin() = 3. Why this step? The distance from the start to "one past last written" equals the count written.

---

Recall One-line recall for every cell

sort ties :::: order among equals unspecified (use stable_sort if it matters) find absent :::: returns last, never nullptr transform in-place :::: safe because read+write of slot i happen before i+1 accumulate int init over doubles :::: truncates at every step → wrong accumulate identity :::: +→0, *→1, &&→true, ||→false, string→"" copy into empty :::: UB; use back_inserter all_of empty / any_of empty :::: true / false algorithm return values :::: transform/copy return "one past last written"

---

Flashcards