6.5 Algorithms, Functors, and Lambda Expressions

C++ separates algorithms from data structures. The <algorithm> library contains generic template functions designed to run on container ranges using iterators. In modern C++, we pass logic parameters to these algorithms using inline functions called Lambdas.

Let's look at sorting algorithms, lambda capture mechanics, and how the compiler maps lambdas to class objects.

Instead of writing sorting loops manually, you use generic STL algorithms. Quality implementations of std::sort are highly tuned; many use introsort (a hybrid of quicksort, heapsort, and insertion sort), though the standard does not mandate a specific algorithm.

#include <iostream>

#include <vector>

#include <algorithm>

int main() {
    std::vector<int> vec{50, 10, 30, 20, 40};
    
    // Sort the vector in ascending order
    std::sort(vec.begin(), vec.end());
    return 0;
}

A lambda expression allows you to write an inline anonymous function to pass custom logic to algorithms. The syntax contains three distinct parts: the capture clause [], parameter list (), and body {}:

std::sort(vec.begin(), vec.end(), [](int a, int b) {
    return a > b;
});

The capture clause [] allows the lambda to access local variables from its outer scope. You can capture variables by value or by reference:

• Capture by Value ([factor]): Copies the variable. The lambda uses the copy, which remains constant unless marked mutable.

• Capture by Reference ([&factor]): Passes the variable by reference. The lambda operates on the real variable directly.

How does the compiler implement lambdas? C++ does not have runtime function pointers for lambdas. Instead, the compiler generates a custom, anonymous class structure called a Functor (a class that overrides the function call operator operator()).

When you write a lambda that captures variables, those variables become member variables of the generated class:

int offset{10};
auto addOffset = [offset](int x) {
    return x + offset;
};

// What the Compiler generates behind the scenes
class AnonymousFunctor {
    int offset;
public:
    AnonymousFunctor(int o) : offset{o} {}
    int operator()(int x) const {
        return x + offset;
    }
};

Because functors are unique class types, the compiler can often inline them at the call site. When you pass a lambda to std::sort, an optimizing compiler may fuse your lambda's body into the sorting loop, avoiding a separate function call.

Captured state may still occupy stack or register space, but in hot paths the call overhead often disappears entirely. Stateless lambdas passed to algorithms are usually easier for the compiler to inline than calls through std::function or non-constexpr function pointers, though inlining is never guaranteed.

• The Gig Worker Metaphor: A lambda expression is like hiring a temporary gig worker for a single task instead of hiring a formal full time employee (a formal global function). The gig worker performs the task inline and is dismissed immediately when the task completes.