Algorithms & Lambdas

Standard algorithms

Algorithms live in <algorithm> and operate on iterator ranges, usually [begin, end) of a container. They are free functions — they do not belong to the container, so the same sort works on vectors, arrays, and more.

Sorting and finding

#include <algorithm>
#include <vector>

std::vector<int> scores{70, 90, 60, 85};
std::sort(scores.begin(), scores.end());       // 60 70 85 90

auto it = std::find(scores.begin(), scores.end(), 85);
if (it != scores.end()) {                       // always check!
    std::cout << "Found at " << (it - scores.begin()) << "\n";
}

The [begin, end) convention means the end is one past the last element — that is why a "not found" result equals end(). Every algorithm documents its requirements: sort needs random access, find only needs to compare.

Lambda expressions

A lambda is an anonymous function written inline. It has the form [captures](params) { body } and can be passed directly to algorithms as a custom predicate or operation.

std::vector<int> v{3, 1, 4, 1, 5};
// Sort in descending order using a lambda as the comparison.
std::sort(v.begin(), v.end(),
          [](int a, int b) { return a > b; });
// v is now 5 4 3 1 1

If the body needs no captured state, the lambda behaves like a normal function — here it just compares two values. Lambdas shine because the logic lives next to the call that uses it.

Captures

The square brackets capture variables from the surrounding scope so the lambda can use them: [x] copies, [&x] references, [=] copies all used variables, [&] references all. Capture only what you need.

int limit = 4;
// Count values greater than limit — limit is captured by value.
int above = std::count_if(v.begin(), v.end(),
                          [limit](int x) { return x > limit; });
std::cout << above;    // 2 (the 5 and the second... only one is > 4 here)

Prefer by-value captures [limit] unless you must modify the outer variable — then use a reference capture explicitly. Never let a lambda outlive the variables it captures by reference.

Composing algorithms

Algorithms compose: the output shape of one call feeds the next. A typical pipeline — filter, transform, accumulate — replaces several hand-written loops:

#include <numeric>    // std::accumulate

std::vector<int> temps{20, -3, 15, -8, 24};

// Sum of the positive temperatures.
int sum = std::accumulate(
    temps.begin(), temps.end(), 0,
    [](int acc, int t) { return (t > 0) ? acc + t : acc; });
std::cout << sum;    // 59

Read it like a sentence: "accumulate over temps, starting at 0, adding positives". The <ranges> library (C++20) pushes this further with composable views — the modern C++ lesson touches it.

Complexity awareness

Each algorithm documents its complexity — how work grows with input size. sort is O(n log n), a single find on a vector is O(n), map lookup is O(log n). Choosing the wrong structure turns hours into days at scale:

• Frequent lookup by key → map or unordered_map, not a linear scan.
• Already-sorted data → binary_search instead of find.
• Small vectors (under ~50 elements) → linear scans often win; measure before optimizing.

The performance-conscious engineer profiles first and optimizes only the measured hotspots.

Practice

1. Sort a vector of std::string alphabetically and by length (two lambdas).
2. Use std::transform to square every element of a vector into a new vector.
3. Count the words longer than five letters in a sentence using count_if and a capture.
4. Rewrite a for loop that sums even numbers as an accumulate call with a lambda.