Generic Algorithms

Chapter 1: Read-Only Algorithms

Read-only algorithms examine elements without modifying them. They are the safest algorithms — you can't corrupt your data by calling them.

c++
vector<int> v = {3, 1, 4, 1, 5, 9};

// find returns an iterator
auto it = find(v.cbegin(), v.cend(), 5);  // points to 5

// accumulate sums — third arg sets type AND initial value
int total = accumulate(v.cbegin(), v.cend(), 0);  // 23

// count how many 1s
auto n = count(v.cbegin(), v.cend(), 1);  // 2

Chapter 2: Write & Reorder Algorithms

Some algorithms assign new values to elements. Others rearrange element order. Both categories share a critical rule: the destination must have enough room.

Algorithms That Write

back_inserter: The Safety Net

A back_inserter creates a special iterator that calls push_back on the container each time you assign to it. This lets write algorithms grow the container as needed:

c++
vector<int> v;  // empty
// WRONG: fill_n writes to 10 nonexistent elements
// fill_n(v.begin(), 10, 0);  // undefined behavior!

// RIGHT: back_inserter creates elements via push_back
fill_n(back_inserter(v), 10, 0);  // v now has 10 zeros

Algorithms That Reorder

sort arranges elements in ascending order using <. unique rearranges so adjacent duplicates are moved to the end, returning an iterator to the first "garbage" element:

c++
vector<string> words = {"the", "fox", "the", "red", "fox"};
sort(words.begin(), words.end());
// words: {"fox","fox","red","the","the"}
auto end_unique = unique(words.begin(), words.end());
// words: {"fox","red","the", ?, ?}  — last two are garbage
words.erase(end_unique, words.end());
// words: {"fox","red","the"}

Chapter 3: Lambda Expressions

Many algorithms take a predicate — a callable that returns a value convertible to bool. Predicates let you customize what an algorithm does. A unary predicate takes one argument; a binary predicate takes two.

c++
// sort by length using a binary predicate
sort(words.begin(), words.end(),
     [](const string &a, const string &b) {
         return a.size() < b.size();
     });

That [](...){...} syntax is a lambda expression — an anonymous, inline function. Lambdas are the most important feature added to C++11 for working with algorithms.

Anatomy of a Lambda

c++
// A lambda that tests if a string is longer than a given size
auto isLong = [](const string &s) { return s.size() > 5; };

// Use with find_if
auto it = find_if(words.begin(), words.end(), isLong);
// it points to the first word longer than 5 characters

// Use with count_if
auto n = count_if(words.begin(), words.end(), isLong);
// n = number of words longer than 5 characters

for_each

The for_each algorithm applies a callable to every element in a range. It's useful for performing side effects like printing:

c++
for_each(words.begin(), words.end(),
         [](const string &s) { cout << s << " "; });
cout << endl;

Chapter 4: Lambda Captures

A lambda can only use variables from its enclosing scope if it captures them. The capture list specifies which variables and how:

c++
size_t sz = 5;

// Capture sz by value — lambda gets a COPY of sz
auto wc = find_if(words.begin(), words.end(),
    [sz](const string &s) { return s.size() >= sz; });

// Capture by reference — lambda uses the actual variable
ostream &os = cout;
for_each(words.begin(), words.end(),
    [&os](const string &s) { os << s << " "; });

Mutable Lambdas

By default, a lambda cannot modify its value-captured variables. Adding mutable lifts this restriction:

c++
int v = 42;
auto f = [v]() mutable { return ++v; };
v = 0;
auto j = f();  // j is 43 (lambda's copy was 42, incremented to 43)

Chapter 5: bind — The Adaptor

Lambdas are great for one-off predicates. But what if you have an existing function that takes extra arguments? The bind function (from <functional>) lets you adapt it:

c++
#include <functional>
using namespace std::placeholders;

// A function that takes two args
bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}

// bind fixes the second argument to 6
auto check6 = bind(check_size, _1, 6);
// check6(s) calls check_size(s, 6)

auto it = find_if(words.begin(), words.end(), check6);

Placeholders (_1, _2, ...) mark which arguments the bound function receives from its caller. _1 means "use the first argument passed to the bound callable."

Reordering Arguments

c++
// sort descending: swap argument order
sort(v.begin(), v.end(), bind(less<int>(), _2, _1));
// _2 is the second arg of the comparator, _1 the first
// so less compares (b, a) instead of (a, b) → descending

Binding Reference Arguments

By default, bind copies its non-placeholder arguments. To bind a reference, wrap it with ref() or cref():

c++
ostream &print(ostream &os, const string &s, char c) {
    return os << s << c;
}
// ref(os) passes os by reference, not copy
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

Chapter 6: Iterator Categories

Different algorithms need different iterator capabilities. The standard defines five iterator categories, forming a hierarchy from weakest to strongest:

Insert Iterators

Three special iterators that turn writes into container insertions:

Reverse Iterators

Reverse iterators traverse backward. rbegin() points to the last element; rend() points before the first. ++ on a reverse iterator moves backward:

c++
// Find last occurrence of a comma
auto rcomma = find(line.crbegin(), line.crend(), ',');
// Convert reverse iterator to forward: .base()
cout << string(rcomma.base(), line.cend());

Chapter 7: Algorithm Pipeline Simulator

Real-world code chains algorithms together. Let's build the classic "sort, unique, filter" pipeline step by step and watch each algorithm transform the data.

Container-Specific Algorithms

Some containers define their own versions of algorithms. list and forward_list have member versions of sort, merge, remove, reverse, and unique. These are more efficient because they can rewire pointers instead of copying elements:

c++
list<int> lst = {4, 2, 5, 1, 3};
lst.sort();              // member sort — rewires nodes, no copies
lst.unique();            // member unique — actually erases nodes
lst.reverse();           // member reverse — rewires prev/next pointers

Chapter 8: Beyond — Connections

Generic algorithms are the bridge between containers and custom logic. With lambdas and iterators, you can express complex data transformations in a few clean lines.

Continue Reading

Next up: Chapter 12: Dynamic Memory — smart pointers, RAII, and the art of never leaking memory.