9. STL Algorithms & Lambdas¶

What & why¶

The standard library has over 100 algorithms: sorting, searching, transforming, partitioning, set operations, numeric reductions. They're tested, optimized, and — most importantly — they name what your loop does. std::ranges::any_of(v, is_negative) says more than a for loop with a flag and a break. Lambdas make them pleasant to use.

Lambdas¶

A lambda is an anonymous function object:

auto add = [](int a, int b) { return a + b; };
add(2, 3);   // 5

Anatomy: [captures](parameters) specifiers -> return_type { body }

auto square = [](double x) -> double { return x * x; };   // explicit return type (rarely needed)
auto greet = [] { std::cout << "hi\n"; };                  // no params: () optional
auto print = [](const auto& x) { std::cout << x << '\n'; }; // generic lambda

Captures¶

Lambdas can use variables from the surrounding scope by capturing them:

int threshold = 10;
std::string prefix = ">> ";

auto above    = [threshold](int x) { return x > threshold; };     // by value (copy)
auto log      = [&prefix](std::string_view m) { std::cout << prefix << m; };  // by reference
auto all_val  = [=](int x) { return x > threshold; };  // everything used, by value
auto all_ref  = [&](int x) { return x > threshold; };  // everything used, by reference
auto init     = [n = threshold * 2](int x) { return x > n; };     // init capture
auto moved    = [s = std::move(prefix)] { return s.size(); };     // move into lambda

By value captures a copy at the moment the lambda is created. Later changes to the original aren't seen.
By reference sees the current value — but dangles if the lambda outlives the variable.
Captured-by-value variables are const inside the lambda unless you mark it mutable:

auto counter = [count = 0]() mutable { return ++count; };
counter();  // 1
counter();  // 2

Inside a member function, capture this (or *this for a copy) to access members.

Prefer explicit capture lists ([threshold], [&prefix]) over [=] / [&] for anything that outlives the current statement.

`std::function`¶

A lambda's type is unique and unnamed. To store callables of different types in one variable, use std::function:

#include <functional>

std::function<int(int, int)> op = [](int a, int b) { return a + b; };
op = [](int a, int b) { return a * b; };

std::map<std::string, std::function<double(double, double)>> ops{
    {"+", std::plus<>{}},
    {"-", std::minus<>{}},
    {"max", [](double a, double b) { return std::max(a, b); }},
};
ops["max"](3, 7);   // 7

std::function has overhead (type erasure, possibly a heap allocation). For parameters of functions that just call the callable, a template is cheaper:

void repeat(int n, const auto& fn) {      // any callable
    for (int i = 0; i < n; ++i) fn(i);
}

Iterators, briefly¶

Algorithms operate on ranges described by iterators [first, last). Iterators come in categories that determine which algorithms work:

Category	Can	Example container
input / forward	`++`, `*`	`std::forward_list`, streams
bidirectional	also `--`	`std::list`, `std::map`, `std::set`
random access	also `+ n`, `[]`, `<`	`std::vector`, `std::deque`, `std::array`
contiguous	elements adjacent in memory	`std::vector`, `std::array`, `std::string`

That's why std::sort works on a vector but not a std::list (which has its own .sort()).

Classic vs. ranges algorithms¶

std::sort(v.begin(), v.end());       // classic: iterator pair
std::ranges::sort(v);                // C++20: pass the container

Ranges algorithms also accept projections:

struct Employee { std::string name; int age; double salary; };
std::vector<Employee> staff = /* ... */;

std::ranges::sort(staff, {}, &Employee::age);                      // sort by age
std::ranges::sort(staff, std::greater<>{}, &Employee::salary);     // by salary, descending
auto it = std::ranges::find(staff, "Ada", &Employee::name);        // find by name

Prefer the std::ranges:: versions in new code.

The algorithms you'll use most¶

Searching and testing¶

std::ranges::find(v, 42);
std::ranges::find_if(v, [](int x) { return x < 0; });
std::ranges::contains(v, 42);                          // C++23; use find() != end() in C++20
std::ranges::count(v, 0);
std::ranges::count_if(v, is_even);
std::ranges::any_of(v, is_negative);
std::ranges::all_of(v, is_positive);
std::ranges::none_of(v, is_zero);
std::ranges::min_element(v);   std::ranges::max_element(v);   std::ranges::minmax(v);
std::ranges::binary_search(sorted, 42);                // needs sorted input
std::ranges::lower_bound(sorted, 42);                  // first element >= 42

Transforming and copying¶

std::vector<int> out;
std::ranges::transform(v, std::back_inserter(out), [](int x) { return x * x; });
std::ranges::copy_if(v, std::back_inserter(out), is_even);
std::ranges::replace(v, 0, -1);
std::ranges::fill(v, 7);
std::ranges::reverse(v);
std::ranges::rotate(v, v.begin() + 2);

std::back_inserter(out) turns assignments into push_backs.

Sorting and ordering¶

std::ranges::sort(v);
std::ranges::stable_sort(v, {}, &Employee::age);    // keeps equal elements in original order
std::ranges::partial_sort(v, v.begin() + 10);       // top 10 only
std::ranges::nth_element(v, v.begin() + v.size() / 2);   // median in O(n)
std::ranges::partition(v, is_even);                 // evens first
std::ranges::is_sorted(v);

Removing: erase_if¶

std::erase(v, 0);                                   // C++20: remove all zeros
std::erase_if(v, [](int x) { return x < 0; });      // remove all negatives

Before C++20 this was the "erase-remove idiom": v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());. std::remove_if alone doesn't shrink the container — a classic bug.

Uniqueness¶

std::ranges::sort(v);
auto [first, last] = std::ranges::unique(v);   // moves duplicates to the end
v.erase(first, last);

Numeric (`<numeric>`)¶

std::accumulate(v.begin(), v.end(), 0);                     // sum
std::accumulate(v.begin(), v.end(), 1LL, std::multiplies<>{});   // product
std::reduce(v.begin(), v.end());                            // like accumulate, may reorder (parallelizable)
std::transform_reduce(a.begin(), a.end(), b.begin(), 0.0);  // dot product
std::iota(v.begin(), v.end(), 1);                           // fill with 1, 2, 3, ...
std::partial_sum(v.begin(), v.end(), out.begin());          // running totals

Note: std::accumulate(v.begin(), v.end(), 0) sums into an int because the initial value is 0. For doubles, write 0.0.

Putting it together¶

Top 3 highest-paid employees over 30, by name:

std::vector<Employee> result;
std::ranges::copy_if(staff, std::back_inserter(result),
                     [](const Employee& e) { return e.age > 30; });
std::ranges::sort(result, std::greater<>{}, &Employee::salary);
if (result.size() > 3) {
    result.resize(3);
}
for (const auto& e : result) {
    std::cout << e.name << '\n';
}

C++20 views can do this lazily without the intermediate vector — see the advanced track's Ranges & views.

Common mistakes¶

Dangling reference captures — returning or storing a lambda that captured locals by &.
std::remove_if without erase — the container keeps its size.
std::accumulate with the wrong initial type — 0 instead of 0.0 truncates.
Invalid comparators — the comparator must be a strict weak ordering (<, not <=), otherwise std::sort is UB.
binary_search / lower_bound on unsorted data.
Writing a raw loop when an algorithm names the intent.
Modifying a container while an algorithm iterates it.

Exercises¶

Given std::vector<std::string> words, use algorithms (no raw loops) to: count words longer than 5 characters, check whether any word is capitalized, find the longest word, and produce a vector of their lengths.
Remove duplicates from a vector while preserving first-occurrence order (hint: an unordered_set in an erase_if predicate).
Sort Employees by department, then by salary descending within department (a comparator lambda returning std::tie(...) < std::tie(...), or two stable_sorts).
Build a simple command dispatcher: std::map<std::string, std::function<void(const std::vector<std::string>&)>>.
Write make_counter() that returns a lambda producing 1, 2, 3, ... on each call. Then write a buggy version that captures a local by reference and observe the result under -fsanitize=address.
Compute the median of a vector in O(n) with std::ranges::nth_element.

Recap¶

Lambdas: [captures](params) { body }; capture explicitly; beware dangling & captures.
std::function stores any callable (with overhead); templates/auto params are cheaper for parameters.
Iterator categories decide which algorithms work on which containers.
Prefer std::ranges:: algorithms and use projections (&T::member).
std::erase_if to remove; sort/stable_sort/nth_element to order; <numeric> for reductions.
Replace raw loops with named algorithms when it makes intent clearer.

Next: Build systems: CMake →