🛠️ Algorithms + Ranges

Why it matters

The container half of the STL gave you data. The algorithm half gives you verbs. std::sort, std::find, std::transform, std::accumulate, std::copy_if, std::lower_bound — about 90 functions that operate on iterator ranges. They’re the toolbox you reach for instead of writing hand-rolled loops.

C++20 added ranges, which take the same toolbox and let you compose its tools into pipelines: vector | filter | transform | take(10). Same verbs, same complexity, dramatically better readability.

This lesson is the payoff lesson for everything before. If you internalize ranges and learn ten algorithms by name, you’ll write less C++ code and the code you write will be more obviously correct.

The classic <algorithm> shape

Every algorithm in <algorithm> takes a range as a pair of iterators and (often) a function or predicate. The pattern repeats:

std::sort(v.begin(), v.end());                       // mutate in place
std::find(v.begin(), v.end(), 42);                   // returns iterator or end
std::count_if(v.begin(), v.end(), is_even);          // counts matches
std::transform(v.begin(), v.end(), out.begin(), f);  // map each element
std::accumulate(v.begin(), v.end(), 0);              // fold left

v.begin(), v.end() is the price you pay for the iterator-pair interface. The tradeoff: std::sort works on std::vector, std::array, raw arrays, custom containers, even a subrange v.begin() + 3, v.begin() + 10. One function. Zero copies.

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

bool is_even(int x) { return x % 2 == 0; }

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

// Sort ascending.
std::sort(v.begin(), v.end());
std::cout << "sorted: ";
for (int x : v) std::cout << x << ' ';
std::cout << "\n";

// Find: returns an iterator. Compare against end() to test existence.
auto it = std::find(v.begin(), v.end(), 7);
std::cout << "found 7? " << (it != v.end() ? "yes" : "no") << "\n";

// Count: count_if with a predicate.
auto n_even = std::count_if(v.begin(), v.end(), is_even);
std::cout << "even count: " << n_even << "\n";

// Accumulate: left-fold. The initial value is also the result type.
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "sum: " << sum << "\n";

// Binary search on a sorted range.
bool has_5 = std::binary_search(v.begin(), v.end(), 5);
std::cout << "binary_search 5? " << (has_5 ? "yes" : "no") << "\n";
return 0;
}

sorted: 1 2 3 4 5 6 7 8 9 
found 7? yes
even count: 4
sum: 45
binary_search 5? yes

g++ -std=c++23 -O2 snippet.cpp && ./a.out

The right way to learn <algorithm> is to skim the reference once (cppreference’s list is the canonical source) and then notice when you’re writing a loop that is one of them. Hand-rolled loops are the #1 source of off-by-one bugs; named algorithms are tested in the standard library.

The composition problem

The iterator-pair API breaks down when you want to compose. Say you want “the squares of all even numbers in v, sorted descending, first three only.” With raw algorithms:

std::vector<int> evens;
std::copy_if(v.begin(), v.end(), std::back_inserter(evens), is_even);

std::vector<int> squared;
std::transform(evens.begin(), evens.end(), std::back_inserter(squared),
               [](int x) { return x * x; });

std::sort(squared.begin(), squared.end(), std::greater<>{});
squared.resize(std::min<size_t>(3, squared.size()));

That’s ugly. Each stage allocates a new vector. Each stage walks the whole range. It’s correct but neither readable nor efficient.

C++20 ranges: composition that’s also lazy

Ranges take the same algorithms and re-shape them as lazy views that compose with |. The same pipeline:

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

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

// The pipeline reads left-to-right, top-to-bottom:
auto pipeline = v
  | std::views::filter([](int x) { return x % 2 == 0; })   // 8, 2, 4, 6
  | std::views::transform([](int x) { return x * x; });    // 64, 4, 16, 36

// The pipeline is lazy. Nothing has been computed yet.
// We materialize by iterating:
std::vector<int> squared(pipeline.begin(), pipeline.end());
std::ranges::sort(squared, std::greater<>{});             // ranges::sort takes a range, not iterators
squared.resize(std::min<size_t>(3, squared.size()));

std::cout << "top 3 squared evens: ";
for (int x : squared) std::cout << x << ' ';
std::cout << "\n";
return 0;
}

top 3 squared evens: 64 36 16 

g++ -std=c++23 -O2 snippet.cpp && ./a.out

Three things to notice:

1. v | views::filter(p) is a range, not a vector. It’s a lightweight wrapper that yields elements lazily as you iterate it. No allocation.
2. std::ranges::sort takes a range directly instead of two iterators. Every algorithm in std::ranges:: has a range-taking overload.
3. The materialization is explicit. std::vector<int> result(pipeline.begin(), pipeline.end()); is when the work actually happens. Until then, the pipeline is just a description.

The view zoo

The most useful views in <ranges>:

Most of these are pure functions in disguise. The iota + take combo is the standard way to generate a finite sequence:

#include <iostream>
#include <ranges>
#include <numeric>

int main() {
// First 10 squares of natural numbers.
auto squares = std::views::iota(1)
  | std::views::transform([](int n) { return n * n; })
  | std::views::take(10);

std::cout << "first 10 squares: ";
for (int s : squares) std::cout << s << ' ';
std::cout << "\n";

// Sum of the first 100 squares — no vector ever exists.
auto first100 = std::views::iota(1)
  | std::views::transform([](int n) { return n * n; })
  | std::views::take(100);
int sum = 0;
for (int s : first100) sum += s;
std::cout << "sum of first 100: " << sum << "\n";
return 0;
}

first 10 squares: 1 4 9 16 25 36 49 64 81 100 
sum of first 100: 338350

g++ -std=c++23 -O2 snippet.cpp && ./a.out

The infinite ranges sound exotic but they’re the same idea as Python generators: a description of a sequence that yields elements on demand.

Algorithms vs views: when each fits

The mental model:

• Algorithms (std::sort, std::accumulate, std::ranges::sort) do the work. They consume a range and return a result (or mutate in place).
• Views (views::filter, views::transform) describe a transformation. They yield nothing until iterated. Use them to set up the data the algorithm will consume.

The combination: build a view pipeline that shapes the data, then call an algorithm on it.

auto positives_squared = v
  | std::views::filter([](int x) { return x > 0; })
  | std::views::transform([](int x) { return x * x; });

int sum = std::ranges::fold_left(positives_squared, 0, std::plus<>{});

That’s the modern C++ shape. The pipeline reads like a sentence. The optimizer compiles it to a single loop.

What’s NOT zero-cost: views with side effects

The “zero-cost” promise holds for pure views over containers. It breaks when:

• A view triggers an allocation (views::split on a string can).
• A view requires multi-pass iteration (some algorithms call begin() twice on the range, which forces re-evaluation).
• The compiler can’t see through the lambda (rare with -O2+ but possible with virtual calls or function pointers in captures).

The general advice: write the readable pipeline first. Profile if you suspect overhead. The compiler is excellent at fusing views.

Useful one-liners

A short list of “this is now one line” patterns:

// Remove duplicates from a sorted vector.
v.erase(std::unique(v.begin(), v.end()), v.end());

// Sort by a key.
std::ranges::sort(v, {}, &Item::priority);   // projection: sort by .priority

// Sum a vector.
auto sum = std::accumulate(v.begin(), v.end(), 0);

// Maximum element.
auto max_it = std::ranges::max_element(v);

// All elements satisfy a predicate.
bool ok = std::ranges::all_of(v, is_valid);

// Reverse a string.
std::ranges::reverse(s);

// Hash a vector by reducing.
std::size_t h = std::accumulate(v.begin(), v.end(), std::size_t{0},
                                [](std::size_t acc, int x) { return acc * 31 + x; });

Reading existing C++ code, you’ll see hand-rolled versions of all of these. They were correct (usually). Replacing them with the standard spelling makes the intent readable, not just the code.

Key takeaways

• <algorithm> is a toolbox of ~90 free functions on iterator ranges. Learn ten by name; reach for the reference for the rest.
• Don’t write a for loop without first asking “is this find, count_if, transform, or accumulate?” Named algorithms are tested and obvious.
• C++20 ranges turn the toolbox into a pipeline language. Views are lazy; nothing computes until you iterate the result.
• The view zoo: filter, transform, take, drop, iota, reverse, zip, chunk. Compose with |.
• Algorithms in std::ranges:: accept a range directly — no more .begin(), .end() pair.
• The pipeline + algorithm combination preserves zero-cost in almost all practical cases. The compiler fuses the views into one loop.

What’s next

Phase 4 — Generic Programming. Lesson 09 builds templates from first principles (the machinery that makes std::sort work for every type), and lesson 10 introduces concepts (the C++20 fix to the unreadable error messages templates were famous for).