STL algorithms, iterators, and ranges

Lesson 13 gave you the containers — vector, map, unordered_map, list — each an ownership-and-layout decision with its own cost table. But a container that only stores is half a tool: real work is sorting, searching, summing, transforming. The naive design would write each of those once per container — M algorithms times N containers is M×N functions. The STL writes M+N instead, and the single idea that collapses the multiplication into a sum is the iterator: a uniform protocol both sides speak, so the algorithm never names the container. This is the generic programming of Lesson 12 cashed out as a library — and, it turns out, exactly the "compose small pieces" lesson functional programming teaches, said in C++.

The thesis, here

An iterator is a zero-overhead abstraction in the strict sense of Lesson 00: for a vector it is literally a pointer, and std::sort on it compiles to the same machine code a hand-written quicksort over a raw array would. You get the decoupling — write the algorithm once, run it on anything iterable — and you pay nothing at runtime for it, because the iterator's type is resolved at compile time (Lesson 12) and inlined away. The bill for "generic" is paid entirely by the compiler, not the CPU.

Linear position

Prerequisite: Lesson 12 (templates — the compiler stamps out one concrete version of an algorithm per iterator type, which is how the decoupling is free) and Lesson 13 (the containers these algorithms run over, and their iterator/reference-invalidation rules).
New capability: use <algorithm> and <numeric> with lambdas and comparators, reason about the half-open range [begin, end), read iterator-category requirements off an algorithm's signature, and build composable, lazy std::ranges view pipelines.

The plan

Six moves. (1) The M×N problem and the iterator as its solution — the STL's central design insight. (2) The half-open range [begin, end) and why that convention is quietly excellent. (3) The iterator categories and why every algorithm states the weakest one it needs. (4) <algorithm> and <numeric> in practice — sort, find, count_if, transform, accumulate — driven by lambdas. (5) The same algorithms running unchanged across a vector and a std::list — the decoupling, proven. (6) C++20 ranges and views: composable, lazy pipelines, and why that is the FP composition idea in C++.

1 · The M×N problem and the iterator

Imagine the library without iterators. You want to sort, and you have a vector, a deque, and a built-in array. So you write sort_vector, sort_deque, sort_array. Now you add find: three more. count_if, transform, accumulate: nine more. With M kinds of algorithm and N kinds of container you need M×N functions, each one re-coupling the same logic to a different storage layout. Add one container and you owe M new functions; add one algorithm and you owe N. The design does not scale.

The STL's insight is to insert one thin layer between the two. An iterator is an object that points at one element of a sequence and knows how to advance to the next — a generalization of a pointer. Every container offers a pair of iterators: c.begin() (points at the first element) and c.end() (points one past the last). Every algorithm is written against that pair and nothing else — it never mentions vector or list. Both sides speak the same small protocol:

dereference — *it

Read (or write) the element the iterator currently points at. The algorithm touches data only through this; it has no idea where the data physically lives.

advance — ++it

Move to the next element. For a vector this is pointer arithmetic; for a list it follows a next link. The algorithm doesn't care which — it just writes ++it.

compare — it != end

Has the iterator reached the end sentinel? When it == end, the algorithm stops. No length is passed; the end is an iterator.

Now an algorithm is written once, against the protocol, and a container is written once, to offer the protocol. M algorithms plus N containers = M+N pieces of code, and any algorithm runs on any container that exposes the iterators it needs. This is the decoupling: the algorithm is named for what it does, not what it does it to. It is precisely the compile-time polymorphism of Lesson 12 — the algorithm is a template parameterized on the iterator type, and the compiler stamps out a tailored version for each container it is actually used with, so the abstraction has zero runtime cost.

2 · The half-open range `[begin, end)`

The pair an algorithm receives is a range: [begin, end) — begin is included, end is excluded, which is what the asymmetric bracket-then-paren notation means. end does not point at a valid element; it points one step past the last one. Dereferencing end is undefined behavior (Lesson 19). This "half-open" convention looks arbitrary until you see what it buys:

size is a subtraction

The number of elements is end - begin (for random-access iterators, §3). No off-by-one: [0, 5) holds 0,1,2,3,4 — five elements, 5 - 0.

empty is an equality

A range is empty exactly when begin == end. An empty range needs no special case — the loop while (begin != end) simply never runs its body.

ranges adjoin cleanly

Split a sequence at m and you get [begin, m) and [m, end) with no gap and no overlap — m belongs to exactly the second. This is why end() being "one past" makes splitting, sorting partitions, and binary search land exactly.

"not found" has a name

Search algorithms return end to mean "absent" — a value guaranteed distinct from every valid position, with no need for a magic index like -1.

So the standard loop is for (auto it = c.begin(); it != c.end(); ++it) — and the range-based for (auto& x : c) you have seen is just sugar the compiler rewrites into exactly that, calling begin() and end() for you.

3 · Iterator categories — and why an algorithm states the one it needs

Not every container can offer the same operations cheaply. A vector is contiguous, so "jump to element 1000" is one addition. A std::list is a chain of nodes, so reaching element 1000 means following 1000 links — there is no cheap jump. The STL refuses to hide this: iterators come in categories, each a strict superset of the previous, and an iterator advertises which it satisfies. An algorithm, in turn, requires the weakest category that lets it work, and that requirement is part of its contract.

Category	Can do	Typical source	Enables, e.g.
Input	read `*it`, `++it`, single pass only	reading from a stream	`find`, `count_if`, `accumulate`
Forward	input + multi-pass (can revisit)	`forward_list`, `unordered_map`	`replace`, `search`
Bidirectional	forward + `--it` (step back)	`list`, `map`, `set`	`reverse`, `copy_backward`
Random-access	bidirectional + `it + n`, `it - it`, `it[n]`, all in O(1)	`vector`, `deque`, array	`sort`, `nth_element`, binary `lower_bound`

This is why std::sort requires random-access iterators: an efficient sort needs to pick pivots and partition by index in O(1), which only contiguous-style storage offers. Hand std::sort a std::list's iterators and it will not compile — a deliberate, useful failure. The category requirement is the algorithm honestly stating "I am O(n log n) only if your container can jump in constant time; if it can't, this is the wrong algorithm." That honesty is the zero-overhead thesis again: the cost is in the open, encoded in the type, not papered over with a silent slow path.

The list exception

Because std::sort needs random access, std::list — being only bidirectional — cannot use it. So list provides its own list::sort() member function, which sorts by splicing nodes (rewiring pointers) instead of moving elements. The category mismatch forces a different algorithm, and the library makes that visible rather than hiding a quadratic surprise.

4 · `<algorithm>` and `<numeric>` with lambdas

The standard algorithms live in <algorithm> (and the numeric ones in <numeric>). Most take a range and, optionally, a callable — a function, function pointer, or lambda — to customize what they do. A lambda is an anonymous function written inline: [capture](params){ body }, where the [] lists variables from the surrounding scope it captures. Here are the workhorses:

#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> v{5, 2, 8, 1, 9, 3};

// sort: ascending by default; a comparator lambda overrides the order.
std::sort(v.begin(), v.end());                          // 1 2 3 5 8 9
std::sort(v.begin(), v.end(),
          [](int a, int b){ return a > b; });           // 9 8 5 3 2 1, descending

// find: returns an iterator to the first match, or end() if absent.
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) { /* found at position it - v.begin() */ }

// count_if: how many elements satisfy a predicate (a bool-returning callable)?
int evens = std::count_if(v.begin(), v.end(),
                          [](int x){ return x % 2 == 0; });   // 2

// transform: apply a function to each element, writing into an output range.
std::vector<int> sq(v.size());
std::transform(v.begin(), v.end(), sq.begin(),
               [](int x){ return x * x; });             // each element squared

// accumulate (in <numeric>): fold the range to a single value. Start at 0, add.
int total = std::accumulate(v.begin(), v.end(), 0);     // sum of all elements
// ...or fold with any binary op — here, product, starting at 1:
long prod = std::accumulate(v.begin(), v.end(), 1L,
                            [](long acc, int x){ return acc * x; });

Note the shape: every one of these names a range with two iterators and (where it customizes behavior) a small lambda. find returning end() for "not found" is §2's convention in action. accumulate is the classic fold — start with a seed, combine it with each element left to right — which a functional programmer will recognize instantly; here it is, in the standard library, with the combining step you choose.

5 · Worked example — the same algorithm across two containers

Worked example: decoupling, proven

The decoupling is not a slogan; here it is mechanically. We write one generic function that finds the largest element of any range, then run it over a vector and a list with no change — and run accumulate over both as well.

#include <algorithm>
#include <numeric>
#include <vector>
#include <list>
#include <iterator>   // std::distance

// One template, written against the iterator protocol only — no container named.
template <typename It>
It largest(It begin, It end) {
    return std::max_element(begin, end);   // returns an iterator to the max
}

std::vector<int> v{5, 2, 8, 1, 9};
std::list<int>   l{5, 2, 8, 1, 9};   // a linked list: bidirectional iterators only

auto vmax = largest(v.begin(), v.end());   // works: *vmax == 9
auto lmax = largest(l.begin(), l.end());   // SAME function, *lmax == 9

// accumulate needs only input iterators, so both containers qualify:
int vsum = std::accumulate(v.begin(), v.end(), 0);   // 25
int lsum = std::accumulate(l.begin(), l.end(), 0);   // 25, identical call shape

// But sort needs RANDOM-ACCESS iterators:
std::sort(v.begin(), v.end());   // OK — vector is contiguous
// std::sort(l.begin(), l.end()); // COMPILE ERROR: list iterators aren't random-access
l.sort();                         // list's own splice-based sort instead

What this shows. largest and accumulate are written exactly once and consume both containers because both expose at least input/forward iterators. sort refuses the list at compile time because the category isn't met — the M+N economy and the honest cost model in a single screen. The compiler stamps out a vector-specialized largest and a list-specialized one (Lesson 12); each is as tight as a hand-written loop, so the abstraction costs nothing at runtime.

6 · C++20 ranges and views — composable, lazy pipelines

The classic algorithms have two rough edges. First, you always pass begin() and end() as a pair, which is verbose and lets you accidentally mix iterators from different containers. Second, composing them is clumsy: filter-then-transform means a copy_if into a scratch vector, then a transform into another — two passes and a throwaway allocation for the intermediate. C++20 ranges fix both.

A range in the new sense is anything with a begin() and an end() — so a whole container is a range, and std::ranges::sort(v) takes the container directly. A view is a lightweight, non-owning range that describes a transformation of another range without storing the result. Views compose with the pipe operator |, and they are lazy: nothing is computed until you iterate, and each element flows through the whole pipeline one at a time — no intermediate container is ever materialized.

#include <ranges>
#include <vector>
#include <iostream>
namespace rv = std::views;

std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// A pipeline: keep evens, then square them. Reads left-to-right, like the data flows.
auto pipeline = v
              | rv::filter([](int x){ return x % 2 == 0; })   // 2 4 6 8 10
              | rv::transform([](int x){ return x * x; });    // 4 16 36 64 100

// Nothing has run yet. The work happens here, element by element, on demand:
for (int y : pipeline) std::cout << y << ' ';   // prints: 4 16 36 64 100

Why laziness matters. The classic two-step version allocates a scratch vector of the evens, then walks it again to square. The view pipeline allocates nothing: when the loop asks for the next value, filter pulls elements from v until one is even, transform squares that single element, and it is handed to the loop — then the process repeats. One pass, no intermediate storage. If you only consume the first three results, the rest of v is never touched at all. That is the zero-overhead principle reaching composition: you pay only for the elements you actually pull through.

This is FP composition, in C++

filter and transform are map and filter from functional programming, and the | operator is function composition: each view is a small, single-purpose, side-effect-free piece, and you build a complex transformation by stringing them together rather than by writing one big loop with nested conditionals. The lesson FP teaches — compose small, pure pieces — is here verbatim. The difference is the C++ accent: the composition is resolved at compile time and the laziness means it adds no allocation, so you get the readability of a pipeline at the cost of a hand-written loop.

7 · Common mistakes and failure modes

Dereferencing end()

*v.end() is undefined behavior (Lesson 19) — end is one-past-the-last, not an element. Always check it != end() before dereferencing a result from find.

Mutating a container mid-algorithm

Inserting into or erasing from a container invalidates iterators (Lesson 13's rules). An algorithm holding an iterator into a container you grow underneath it will read freed or moved memory — a use-after-free in disguise.

A dangling view

A view does not own its data. If the underlying container is destroyed (or a temporary it was built on dies) while the view lives on, iterating it is undefined behavior. A view is a borrowed window, not a copy — its lifetime is the container's (Lesson 05).

Wrong iterator category

std::sort(myList.begin(), myList.end()) won't compile because list isn't random-access. The error is verbose but it is the contract protecting you; use list::sort().

Forgetting transform's output room

transform writes through the output iterator; the destination must already have space (e.g. sized vector) or use std::back_inserter to push. Writing past the end is UB.

Capturing by reference into a stored lambda

A lambda that captures a local by reference [&] and outlives that local dangles. For lambdas kept past the enclosing scope, capture by value [=] or capture exactly what you need.

Checkpoint exercise

Try it

Take a std::vector<int> v{1..10}. (1) Predict, then verify with output, the result of std::count_if(v.begin(), v.end(), [](int x){ return x > 5; }). (2) Write a std::ranges pipeline that keeps the odd numbers and triples them, and print it — confirm no intermediate vector is created (you can convince yourself by putting a std::cout inside the filter lambda and watching that it fires lazily, interleaved with the loop, not all up front). (3) Try std::sort on a std::list's iterators and read the compiler error — find the phrase about random access in it, then switch to l.sort(). The goal is to feel the three claims: lambdas customize, views are lazy, and the iterator category is a real, enforced contract.

Where this points next

We can now express computation generically and compose it cleanly — but every example so far assumed nothing went wrong. find can fail to find; transform can call code that throws; a file you open might not exist. Lesson 15 takes up error handling and exception safety: the two channels for reporting failure (exceptions, which unwind the stack — and are safe only because RAII from Lesson 05 runs destructors as they unwind — versus value-based errors like std::optional and std::expected), the cost model of each, and the no-throw / strong / basic exception-safety guarantees. The thread connecting it here: an algorithm operating over a range must leave the container in a sane state even if an element's operation throws mid-traversal — exactly the safety guarantee Lesson 15 makes precise.

Takeaway

The iterator is the abstraction that decouples algorithm from container: both sides speak one small protocol (*it, ++it, it != end), so M algorithms plus N containers cost M+N pieces of code instead of M×N — generic programming (Lesson 12) realized as a library, and free at runtime because the iterator type is resolved and inlined at compile time. The half-open range [begin, end) makes size a subtraction, empty an equality, splits gapless, and "not found" a returned end(). Iterators come in categories (input → forward → bidirectional → random-access), and each algorithm requires the weakest one it needs — which is why sort takes a vector but rejects a list at compile time, the cost model honest in the type. With lambdas you customize sort, find, count_if, transform, and accumulate; with C++20 ranges and views you compose them into lazy | pipelines that materialize no intermediates — the functional-programming lesson of composing small, pure pieces, spoken in C++ at zero overhead.

Interview prompts

Why does the STL need M+N code instead of M×N, and what makes that possible? (§1 — the iterator is a uniform protocol both algorithms and containers speak, so an algorithm is written once against iterators and never names a container; any container offering the needed iterators works with any algorithm.)
What does the half-open range [begin, end) buy you? (§2 — size is end - begin, empty is begin == end, adjacent ranges split with no gap or overlap, and "not found" is a returned end() distinct from every valid position.)
Why does std::sort require random-access iterators, and what happens with a std::list? (§3 — an efficient sort needs O(1) indexed jumps to partition; a list is only bidirectional, so the call fails to compile and you use the splice-based list::sort() member instead.)
How is an iterator a zero-overhead abstraction? (§1, source-note — for a vector it is literally a pointer, its type is resolved at compile time via templates, and the algorithm is inlined into the same machine code a hand-written loop over a raw array would produce.)
What does it mean that ranges views are lazy, and why does it matter? (§6 — no work happens until iteration; elements flow through the whole pipeline one at a time with no intermediate container allocated, so a filter|transform costs one pass and zero scratch storage, and unused tail elements are never touched.)
In what sense is a ranges pipeline the same idea as functional composition? (§6 — filter/transform are filter/map, the | is composition of small single-purpose side-effect-free pieces, so a complex transform is built by stringing pieces together rather than one big imperative loop.)
Name two ways an iterator or view can become a use-after-free. (§7 — mutating a container that invalidates iterators an algorithm still holds, and a view outliving the container or temporary it borrows from; both read freed/moved memory.)