In C++, the regular function syntax is extended with the concept of a callable, short for callable entity—a callable is something that can be called in the same way as a function. Some examples of callables are functions (of course), function pointers, or objects with operator(), also known as functors:

void f(int i);
struct G {
    void operator()(int i);
};
f(5);            // Function
G g; g(5);       // Functor

It is often useful to define a callable entity in a local context, right next to the place it is used. For example, to sort a sequence of objects, we may want to define a custom comparison function. We can use an ordinary function for this:

bool compare(int i, int j) { return i < j; }
void do_work() {
    std::vector<int> v;
    .....
    std::sort(v.begin(), v.end(), compare);
}

However, in C++, functions cannot be defined inside other functions, so our compare() function may have to be defined quite far from the place it is used. If it is a single-use comparison function, such separation is inconvenient and reduces the readability and maintainability of the code. 

There is a way around this limitation—while we cannot declare functions inside functions, we can declare classes, and classes can be callable:

void do_work() {
    std::vector<int> v;
    .....
    struct compare {
        bool operator()(int i, int j) const { return i < j; }
    };
    std::sort(v.begin(), v.end(), compare());
}

This is compact and local, but too verbose. We do not actually need to give this class a name, and we only ever want one instance of this class. In C++11, we have a much better option, the lambda expression:

void do_work() {
    std::vector<int> v;
    .....
    auto compare = [](int i, int j) { return i < j; };
    std::sort(v.begin(), v.end(), compare);
}

This is as compact as it gets. The return type can be specified, but can usually be deduced by the compiler. The lambda expression creates an object, so it has a type, but that type is generated by the compiler, so the object declaration must use auto. 

The lambda expressions are objects, so they can have data members. Of course, a local callable class can also have data members. Usually, they are initialized from the local variables in the containing scope:

void do_work() {
    std::vector<double> v;
    .....
    struct compare_with_tolerance {
        const double tolerance;
        explicit compare_with_tolerance(double tol) :
            tolerance(tol) {} 
        bool operator()(double x, double y) const {
            return x < y && std::abs(x - y) > tolerance;
        }
    };
    double tolerance = 0.01;
    std::sort(v.begin(), v.end(), compare_with_tolerance(tolerance));
}

Again, this is a very verbose way to do something simple. We have to mention the tolerance variable three times—as a data member, a constructor argument, and in the member initialization list. A lambda expression makes this code simpler as well because it can capture local variables. In local classes, we are not allowed to reference variables from the containing scope, except by passing them through the constructor arguments, but for the lambda expressions, the compiler automatically generates a constructor to capture all local variables mentioned in the body of the expression:

void do_work() {
    std::vector<double> v;
    .....
    double tolerance = 0.01;
    auto compare_with_tolerance = [=](auto x, auto y) {
        return x < y && std::abs(x - y) > tolerance;
    }    
    std::sort(v.begin(), v.end(), compare_with_tolerance);
}

Here, the name tolerance inside the lambda expression refers to the local variable with the same name. The variable is captured by value, which is specified in the lambda expression's capture clause [=] (we could have captured by reference using [&] instead). Also, instead of changing the arguments of the lambda expression from int in the earlier example to double, we can declare them as auto, which effectively makes the operator() of the lambda expression a template (this is a C++14 feature). 

Lambda expressions are most commonly used as local functions. However, they are not really functions; they are callable objects, and so they are missing one feature that the functions have—the ability to overload them. The last trick we will learn in this section is how to work around that and create an overload set from lambda expressions.

First, the main idea—it is indeed impossible to overload callable objects. On the other hand, it is very easy to overload several operator() methods in the same object—methods are overloaded like any other function. Of course, the operator() of a lambda expression object is generated by the compiler, not declared by us, so it is not possible to force the compiler to generate more than one operator() in the same lambda expression. But classes have their own advantages, the main one being that we can inherit from them. Lambda expressions are objects—their types are classes, so we can inherit from them too. If a class inherits publicly from a base class, all public methods of the base class become public methods of the derived class. If a class inherits publicly from several base classes (multiple inheritance), its public interface is formed from all the public methods of all the base classes. If there are multiple methods with the same name in this set, they become overloaded and the usual overloading resolution rules apply (in particular, it is possible to create an ambiguous set of overloads, in which case the program will not compile). 

So, we need to create a class that automatically inherits from any number of base classes. We have just seen the right tool for that—the variadic templates. As we have learned in the previous section, the usual way to iterate over the arbitrary number of items in the parameter pack of a variadic template is through recursion:

template <typename ... F> struct overload_set;

template <typename F1>
struct overload_set<F1> : public F1 {
    overload_set(F1&& f1) : F1(std::move(f1)) {}
    overload_set(const F1& f1) : F1(f1) {}
    using F1::operator();
};

template <typename F1, typename ... F>
struct overload_set<F1, F ...> : public F1, public overload_set<F ...> {
    overload_set(F1&& f1, F&& ... f) : 
        F1(std::move(f1)), overload_set<F ...>(std::forward<F>(f) ...) {}
    overload_set(const F1& f1, F&& ... f) :
        F1(f1), overload_set<F ...>(std::forward<F>(f) ...) {}
    using F1::operator();
};

template <typename ... F>
auto overload(F&& ... f) {
    return overload_set<F ...>(std::forward<F>(f) ...);
}

The overload_set is a variadic class template; the general template has to be declared before we can specialize it, but it has no definition. The first definition is for the special case of only one lambda expression—the overload_set class inherits from the lambda expression and adds its operator() to its public interface. The specialization for N lambda expressions (N>1) inherits from the first one and from the overload_set constructed from the remaining N-1 lambda expressions. Finally, we have a helper function that constructs the overload set from any number of lambda expressions—in our case, this is a necessity and not a mere convenience, since we cannot explicitly specify the types of the lambda expressions, but have to let the function template deduce them. Now, we can construct an overload set from any number of lambda expressions:

int i = 5;
double d = 7.3;
auto l = overload(
    [](int* i) { std::cout << "i=" << *i << std::endl; },
    [](double* d) { std::cout << "d=" << *d << std::endl; }
);
l(&i);    // i=5
l(&d);    // d=5.3

This solution is not perfect, because it does not handle ambiguous overloads well. In C++17, we can do better, and it gives us a chance to demonstrate the alternative way of using a parameter pack that does not need recursion. Here is the C++17 version:

template <typename ... F>
struct overload_set : public F ... {
    overload_set(F&& ... f) : F(std::forward<F>(f)) ... {}
    using F::operator() ...;    // C++17
};

template <typename ... F>
auto overload(F&& ... f) {
    return overload_set<F ...>(std::forward<F>(f) ...);
}

The variadic template does not rely on partial specializations anymore; instead, it inherits directly from the parameter pack (this part of the implementation works in C++14 as well, but the using declaration needs C++17). The template helper function is the same—it deduces the types of all lambda expressions and constructs an object from the overload_set instantiation with these types. The lambda expressions themselves are passed to the base classes using perfect forwarding, where they are used to initialize all the base objects of the overload_set objects (lambda expressions are movable). Without the need for recursion or partial specialization, this is a much more compact and straightforward template. Its use is identical to the previous version of the overload_set, but it handles near-ambiguous overloads better.

We will see their use in later chapters of this book, when we will need to write a fragment of code and attach it to an object so that it can be executed later.