Efficient Use of Lambda Expressions and std::function

Functor classes — classes that implement operator() — are old friends to C++ programmers who, for many years, have used them as predicates for STL algorithms. Nevertheless, implementing simple functor classes is quite cumbersome as the following example shows.

Suppose that v is an STL container of ints and we want to compute how many of its elements are multiple of a certain value n set at runtime. An STL way of doing this is:

std::count_if(v.begin(), v.end(), is_multiple_of(n));

where is_multiple_of is defined by:

class is_multiple_of {
public:
  typedef bool result_type;  	// These two typedefs are recommended but not
  typedef int argument_type; 	// strictly required. More details to come.
  is_multiple_of(int n) : n(n) {}
  bool operator()(int i) const { return i%n == 0; }
private:
  const int n;
};

Having to write all this code pushes many programmers to write their own loops instead of calling std::count_if. By doing this, they lose good opportunities for compiler optimizations.

Lambda expressions make creation of simple functor classes much easier. Although two of the Boost libraries — Boost.Lambda and, more recently, Boost.Phoenix — provide very good implementations of lambda abstractions in C++03, to improve the language expressiveness, the standard committee decided to add language support for lambda expressions in C++11. Using this new feature, the previous example becomes:

std::count_if(v.begin(), v.end(), [n](int i){return i%n == 0;});

Behind the scenes, the lambda expression [n](int i){return i%n == 0;} forces the compiler to implement an unnamed functor class similar to is_multiple_of with some obvious advantages:

1. It's much less verbose.
2. It doesn't introduce a new name just for a temporary use, resulting in less name pollution.
3. Frequently (not in this example, though) the name of the functor class is much less expressive than its actual code. Placing the code closer to where it's called improves code clarity.

The Closure Type

In the previous examples, our functor class was named is_multiple_of. Naturally, the functor class automatically implemented by the compiler has a different name. Only the compiler knows this type's name, and we can think of it as an unnamed type. For presentation purposes, it's called the "closure type," whereas the temporary object resulting from the lambda expression is the "closure object." The type anonymity is not an issue for std::count_if because this is a template function and, therefore, argument type deduction takes place.

Turning a function into a template is a way to make it accept lambda expressions as arguments. Consider, for instance, a scientific library that implements a root-finder; i.e., a function that takes a functor object f and returns a double value x such that f(x) = 0. The root-finder might be a template function:

template <class T>
double find_root(T const& f);

However, this might not be desirable due to a few well-known template weaknesses: The code must be exposed in header files, compiling time increases, and template functions can't be virtual.

Can find_root be a non-template function? If so, what would be its signature?

double find_root(??? const& f);

Argument type deduction for template functions is not a novelty of C++11. Nevertheless, the new standard introduces two keywords — auto and decltype — to support type deduction. (Note: auto was a keyword in C++03, but with a different meaning.) If we want to give a name to a closure object, then we can follow this example:

auto f = [](double x){ return x * x — 0.5; };

Furthermore, an alias for the closure type, say function_t, can be set by:

typedef decltype(f) function_t;

Unfortunately, function_t is set at the same scope as the lambda expression and, therefore, is invisible elsewhere. In particular, it can't be used in find_root's signature.

Now, the other important actor of our play enters the stage: std::function.