Functors

A functor is pretty much just a class which defines the operator(). That lets you create objects which "look like" a function:

#include <iostream>
#include<vector>
#include<algorithm>
#include <cassert>
using namespace std;

int main() {
    // this is a functor
    struct add_x {
      add_x(int val) : x(val) {}  // Constructor
      int operator()(int y) const { return x + y; }

    private:
      int x;
    };

    add_x add42(42); // create an instance of the functor class
    int i = add42(8); // and "call" it
    assert(i == 50); // and it added 42 to its argument

    vector<int> in={1,2,4,5,6,7}; // assume this contains a bunch of values)
    vector<int> out(in.size());
    // Pass a functor to std::transform,
    //which calls the functor on every element
    // in the input sequence,
    //and stores the result to the output sequence
    transform(in.begin(), in.end(), out.begin(), add_x(1));

    // Check if each element in 'out' is one greater than the corresponding element in 'in'
       for (int i = 0; i < in.size(); i++) {
           assert(out[i] == in[i] + 1);
       }
    return 0;
}

There are a couple of nice things about functors. One is that, unlike regular functions, they can contain state. The above example creates a function which adds 42 to whatever you give it. But that value 42 is not hardcoded, it was specified as a constructor argument when we created our functor instance. I could create another adder, which added 27, just by calling the constructor with a different value. This makes them nicely customizable.
As the last lines show, you often pass functors as arguments to other functions such as std::transform or the other standard library algorithms. You could do the same with a regular function pointer except, as I said above, functors can be "customized" because they contain state, making them more flexible (If I wanted to use a function pointer, I'd have to write a function which added exactly 1 to its argument. The functor is general, and adds whatever you initialized it with), and they are also potentially more efficient. In the above example, the compiler knows exactly which function std::transform should call. It should call add_x::operator(). That means it can inline that function call. And that makes it just as efficient as if I had manually called the function on each value of the vector.

If I had passed a function pointer instead, the compiler couldn't immediately see which function it points to, so unless it performs some fairly complex global optimizations, it'd have to dereference the pointer at runtime, and then make the call.

Lamdas

Lamdas are a C++ construct that allows writing un-named functions in place

Using Lambdas, variables from the local context can be "captured" and used in the function without being passed in as params

The problem

C++ includes useful generic functions like for_each and transform, which can be very handy. Unfortunately, they can also be quite cumbersome to use, particularly if the functor you would like to apply is unique to the particular function.

#include <algorithm>
#include <vector>
using namespace std;
namespace {
  struct f {
    void operator()(int) {
      // do something
    }
  };
}

void func(vector<int>& v) {
  f f;
  for_each(v.begin(), v.end(), f);
}

If you only use f once and in that specific place it seems overkill to be writing a whole class just to do something trivial and one-off.

In C++03 you might be tempted to write something like the following, to keep the functor local:

void func2(vector<int>& v) {
  struct {
    void operator()(int) {
       // do something
    }
  } f;
  for_each(v.begin(), v.end(), f);
}

however this is not allowed, f cannot be passed to a template function in C++03.

The new solution

C++11 introduces lambdas allowing you to write an inline, anonymous functor to replace the struct f. For small simple examples this can be cleaner to read (it keeps everything in one place) and potentially simpler to maintain, for example in the simplest form:

void func3(vector<int>& v) {
  for_each(v.begin(), v.end(), [](int) { /* do something here*/ });
}

Lambda functions are just syntactic sugar for anonymous functors.

Return types

In simple cases, the return type of the lambda is deduced for you, e.g.:

void func4(vector<double>& v) {
  transform(v.begin(), v.end(), v.begin(),
                 [](double d) { return d < 0.00001 ? 0 : d; }
                 );
}

however, when you start to write more complex lambdas you will quickly encounter cases where the return type cannot be deduced by the compiler, e.g.:

void func4(vector<double>& v) {
    transform(v.begin(), v.end(), v.begin(),
        [](double d) {
            if (d < 0.0001) {
                return 0;
            } else {
                return d;
            }
        });
}

To resolve this you are allowed to explicitly specify a return type for a lambda function, using -> T:

void func4(vector<double>& v) {
    transform(v.begin(), v.end(), v.begin(),
        [](double d) -> double {
            if (d < 0.0001) {
                return 0;
            } else {
                return d;
            }
        });
}

Syntax: []()->{}=> “Square circle and curly”

"Capturing" variables

So far we've not used anything other than what was passed to the lambda within it, but we can also use other variables, within the lambda. If you want to access other variables you can use the capture clause (the [] of the expression), which has so far been unused in these examples, e.g.:

void func5(vector<double>& v, const double& epsilon) {
    transform(v.begin(), v.end(), v.begin(),
        [epsilon](double d) -> double {
            if (d < epsilon) {
                return 0;
            } else {
                return d;
            }
        });
}

You can capture by both reference and value, which you can specify using & and = respectively:

[&epsilon, zeta] captures epsilon by reference and zeta by value
[&] captures all variables used in the lambda by reference
[=] captures all variables used in the lambda by value
[&, epsilon] captures all variables used in the lambda by reference but captures epsilon by value
[=, &epsilon] captures all variables used in the lambda by value but captures epsilon by reference
examples

The generated operator() is const by default, with the implication that captures will be const when you access them by default. This has the effect that each call with the same input would produce the same result, however you can mark the lambda as mutable to request that the operator() that is produced is not const.

Applications

791. Custom Sort String

Sorting an array by increasing/decreasing frequency

LC:1636 Given an array of integers nums, sort the array in increasing order of frequency of the values. If multiple values have the same frequency, sort them in decreasing order of value

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int,int> um; for(int& val:nums) um[val]++;

        sort(nums.begin(), nums.end(),
             [&um](const int& a, const int& b)->bool{
                return um[a]==um[b] ? a>b : um[a] < um[b];
//(increasing order of frequency) vs decreasing order of value
        });
        return nums;
    }
};