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. They are highly optimized and use intro-sort (a hybrid of quick sort, heap sort, and insertion sort) under the hood:

#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 perform inline optimizations when calling them. This makes lambdas significantly faster than traditional C style function pointers.

* 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.