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

Prerequisites we lean on (open them if a word is new): Iterators and ranges, Lambda expressions, Function objects (functors), std::vector. This is a child of STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of.

---

Step 1 — The row of boxes and the two pointers

WHAT. We start with the raw material: a std::vector<int> holding the numbers $2,5,3$. Nothing else exists yet — no formula, no loop, just data in a row.

WHY. Before any algorithm can run we must agree on where the data starts and where it stops. STL answers this with two iterators — think of them as fingers pointing at boxes.

• ==first== points at the first element (box $0$).
• ==last== points one box past the end — at empty air after the last box.

The chunk of boxes from first up to (but not including) last is written $[\text{first},\text{last})$ — a square bracket "included" on the left, a round bracket "excluded" on the right.

PICTURE. The red finger is last; notice it points past the $3$, not at it.

---

Step 2 — The extra ingredient nobody expects: init

WHAT. We add a third thing that is not in the vector: a starting value called ==init==. Here we choose $\text{init}=0$.

WHY. A fold needs somewhere to begin the running total. Imagine a cash register: before the first item is scanned, the display already shows some number. That pre-set number is init. If we chose + as the operation, we want the register to start at $0$ (adding $0$ changes nothing). Choosing the right init is the whole game — get it wrong and every answer is off by that amount.

PICTURE. The red box below the row is init — it lives outside the vector but inside the calculation.

---

Step 3 — The one operation that does all the work: op

WHAT. We introduce a binary operation ==op(a, b)== — a rule that eats two numbers and returns one. For plain summation, op is just addition: op(a, b) = a + b.

WHY. Why a two-argument rule and not a one-argument one? Because folding always combines what we have so far (a = the running total) with the next box (b = the next element). That is fundamentally a two-input act: old total + new value → new total. In C++ you supply op as a lambda or a functor.

PICTURE. op is the red machine: two arrows in (left = running total, right = next box), one arrow out (new total).

---

Step 4 — The recurrence: one box folded in

WHAT. We take the first real box, $e_0=2$, and feed the machine: $\text{op}({\text{acc}}_0,e_0)=0+2=2$. Store that as the new running total ${\text{acc}}_1$.

WHY. This is the atom of the whole algorithm — a single turn of the crank. Everything after is this exact move, repeated. Writing it as a rule that turns ${\text{acc}}_k$ into ${\text{acc}}_{k+1}$ lets us describe any length of vector with one line.

PICTURE. The red arrow shows the old total ($0$) and the box ($2$) entering the machine and the new total ($2$) coming out. first has advanced one box to the right.

---

Step 5 — Turning the crank to the end

WHAT. We repeat Step 4 for every remaining box:

${\text{acc}}_1=0+2=2,{\text{acc}}_2=2+5=7,{\text{acc}}_3=7+3=10.$

When the moving first finger reaches last, we stop. The final total ${\text{acc}}_3=10$ is what accumulate returns.

WHY. We stop exactly at last — never touching it — because last points at empty air (Step 1). This is why the half-open convention is so clean: the loop condition is simply while (first != last), and it works even for an empty vector (the loop body never runs).

PICTURE. The staircase: each red step lifts the running total by the next box's value, ending at $10$.

---

Step 6 — Change op, change the meaning (product)

WHAT. Swap the machine. Let op(a, b) = a * b and — crucially — change init to $1$:

${\text{acc}}_1=1\cdot 2=2,{\text{acc}}_2=2\cdot 5=10,{\text{acc}}_3=10\cdot 3=30.$

WHY. The shape of the fold is identical to Step 5 — same staircase, same recurrence — only the machine and the start value differ. Why start at $1$ and not $0$? Because the start value must be the operation's identity: the number that leaves its partner unchanged. For + that is $0$; for * it is $1$. Start a product at $0$ and every answer collapses to $0$ — a classic bug.

PICTURE. Same staircase skeleton as Step 5 but the red multiplying machine and the init = 1 box; the total climbs multiplicatively to $30$.

---

Step 7 — The degenerate cases you must never trip on

WHAT. Two edge inputs decide whether your mental model is really correct.

1. Empty range (first == last, e.g. vector<int> v;): the crank never turns. The recurrence produces nothing new, so the result is just init.
2. The type trap: the running total's type is the type of init, not the type of the elements. Fold a vector<double> with init = 0 (an int) and every partial total is chopped down to a whole number.

WHY. These are exactly the corners where "it usually works" code breaks. The empty case falls straight out of the half-open rule (Step 1): zero boxes ⇒ zero turns ⇒ answer is the start value. The type case falls out of Step 2: acc was born equal to init, so it inherits init's type for its whole life.

PICTURE. Left: fingers touching (empty), red result box = init. Right: real values $1.5,2.5$ but an int register truncating $1.5\to 1$, then $1+2.5\to 3$ instead of the true $4.0$.

---

The one-picture summary

Everything above — the two fingers, the outside init, the two-input machine, the staircase, the identity element, the empty case — compressed into a single diagram. The red pipeline is accumulate.

Recall Feynman retelling — say it to a friend

Picture a row of numbered boxes and two fingers: one on the first box, one pointing at the empty spot just past the last box. Off to the side you hold a little scratch pad with a starting number written on it — that is init. Now you have a machine with two slots: you drop the number on your scratch pad into the left slot and the next box's number into the right slot; it hands back a new number, which you write over your scratch pad. Slide your finger one box right and do it again. When your finger reaches the empty spot, stop and read the scratch pad — that's the answer. Choose the machine to be "add" and start the pad at $0$: you get a sum. Choose "multiply" and start at $1$: you get a product. If the boxes are decimals, make sure the scratch pad itself is a decimal (0.0), or the machine keeps rounding your total down. And if there are no boxes at all, you never turn the crank, so the answer is simply whatever you started the pad with. That is the entire secret of accumulate — and every other STL algorithm is the same walk with a different machine bolted on.

Recall Quick self-test

What does accumulate return on an empty range? ::: Exactly init — the crank never turns. Why must init be 0.0 (not 0) for a vector<double> sum? ::: The accumulator's type equals init's type; int init truncates every partial sum. What is the correct init for a product fold? ::: 1, the identity element of multiplication (0 would zero everything out). Which side does the running total go into op? ::: The left: op(acc, element) — it's a left fold.

Flashcards