Functors are not dead: the double functor trick

When C++11 arrived, lambdas were massively used in the places where functors used before. Lambdas are more elegant, involve less typing and can do pretty much all that functor did.

Pretty much. But not quite.

We covered how to make code expressive by using lambdas in a dedicated post, but there are a few use cases where you still need to use functors, and one of these cases is “the double functor trick”.

If you’re unsure about what I call functors and lambdas, you can read all about it in the first section of the post on function objects in the STL. Strictly speaking, “functor” may actually not be a good name, because it means something very specific in category theory (Adi if you hear me…), but the term has spread in the C++ community so let’s use it here.

The use case: comparing elements with a value of a different type

You may have come across the following need. You have a collection of elements of a certain type T, and you want to compare them with one or several values of another type, U. But T and U are not implicitly convertible to one another. An operation is needed to get a T from an U, or an U from a T, or you may even be able to deduce only one from the other, and not the other way round.

A typical use case is searching for a subpart of an object. For example, objects of the following class have an id:

class Employee
{
public:
    int getId() const
    ...

private:
    int id_;
};

Let’s consider the case where there are several of them in a vector in no particular order:

std::vector<Employee> employees;

… or in sorted order by id:

bool operator<(Employee const& e1, Employee const& e2)
{
    return e1.getId() < e2.getId();
}

std::set<Employee> employees;

and you have an id (of type int), you need to retrieve the object corresponding to this id (of type Employee).

Most STL algorithms (such as std::count, std::find, std::equal_range, std::set_intersection, …) accept values of the type of the elements of the range they operate on (or implicitly convertible into it). And you can’t build an Employee object out of an id.

This is a particular case of a more general need: comparing elements with the result of an operation applied to them. Here the operation is getId but you may have to apply a more complex computation and searching for the element that would produce the result you’re looking for.

How to do this with the STL?

The cases where the STL got you covered: the *_if algorithms

Let’s consider a collection of objects in unsorted order:

std::vector<Employee> employees;

You can’t use std::find to search for an employee having the id 42:

std::find(employees.begin(), employees.end(), 42); // doesn't compile

The STL has you covered by providing with std::find_if which lets you explain how to compare an id to an employee and determine whether there is a match:

std::find_if(employees.begin(), employees.end(), [](Employee const& e){return e.getId() == 42;}); // OK

And the same logic applies for std::count and std::count_if, although in this particular case each id probably can’t appear more than once in a collection.

std::lower_bound and std::upper_bound

Now let’s take the case of a sorted collection:

bool operator<(Employee const& e1, Employee const& e2)
{
    return e1.getId() < e2.getId();
}

std::set<Employee> employees;

How to efficiently search for an employee by its id? We saw in the series about searching that we should use equal_range, preferably by invoking the method on the class set.

But here this won’t do:

auto employeesWith42 = employees.equal_range(42); // doesn't compile

Indeed, 42 cannot be compared to objects of the type Employee.

C++03 brought a few changes to the standard over C++98, and one of them fixes this. It concerns the algorithms std::lower_bound and std::upper_bound. C++03 added them the guarantee that they always compare the elements of the collection with the searched value in the same order.

std::lower_bound performs comparisons with elements on the left-hand side of the operator and with the searched value on the right-hand side.

std::upper_bound performs comparisons with elements on the right-hand side of the operator and with the searched value on the left-hand side.

Therefore you can pass them a comparison function that compares an employee with an id:

bool compareWithIdLeft(Employee const& employee, int id)
{
    return employee.getId() < id;
}

auto lowerPosition = std::lower_bound(employees.begin(), employees.end(), 42, compareWithIdLeft);

and for std::upper_bound:

bool compareWithIdRight(int id, Employee const& employee)
{
    return id < employee.getId();
}

auto upperPosition = std::upper_bound(lowerPosition, employees.end(), 42, compareWithIdRight);

Note that compareWithIdLeft and compareWithIdRight can’t have the same name, otherwise passing them as argument to the algorithm would be ambiguous. Also note that all this could also be implemented with lambdas, if you find that the lambda mechanics don’t impede readability on this example.

Finally note how you can reuse the output of std::lower_bound in the call to std::upper_bound, in order to efficiently get the two iterators that std::equal_range would have returned.

In this particular case where at most one employee has a given id, you may find it better to compare the result of lower_bound to the end of the collection and to the value 42, instead of calling upper_bound and checking if its result is different from the one of lower_bound. You decide which trade-off suits you best.

The general case: the double functor trick

So far we’ve covered solutions for specific algorithms, but these are by all means no general solutions.

Take the example of an algorithm on sets: we have a sorted collection of employees, a sorted collection of ids, and we want the ids that don’t correspond to any employee, for example to clean the ids of employees that are no longer in the company.

This is a job cut for std::set_difference. If you’re not yet familiar with algorithms on sets you may want to have a look at this presentation on them, because they are quite useful in day-to-day code.

But you can’t pass collection of different types to algorithms on sets, and contrary to std::lower_bound seen above, they don’t provide any guarantee about which order they will use to compare elements of the two collections. You would like to pass two functions then, one taking an id on the left-hand side, and one taking an id on the right-hand side, but there is only one comparator that you can pass to the algorithm.

This is were functors come back from the dead:

struct CompareWithId
{
    bool operator()(Employee const& employee, int id)
    {
        return employee.getId() < id;
    }
    bool operator()(int id, Employee const& employee)
    {
        return id < employee.getId();
    }
};

Functors let you package several functions in a function object and – to my knowledge – lambdas can’t do that.

The functor is then used the following way:

std::set<Employee> employees = ...
std::set<int> ids = ...

std::vector<int> idsToClean;

std::set_difference(ids.begin(), ids.end(),
                    employees.begin(), employees.end(),
                    std::back_inserter(idsToClean),
                    CompareWithId());

And functors saved the day.

The future of functors

I recently became aware of the following future features planned for C++. Some of them were pointed out by the useful comments posted in the comment section below or the reddit thread of this article.

Someday, functors should become extinct. Indeed, this need for several overloads in the same function object is found elsewhere than in the STL. When using std::variant (and boost::variant before it), function objects with several operators are used to make visitors. For this reason, a proposal was made for the language to add a function std::overload that builds up a function object from several lambdas it is passed, thus avoiding to write the whole functor boilerplate manually. But this was not included in C++17.

As pointed out in this comment, an equivalent feature can be realized by inheriting from lambdas. And by using a combination of features available in C++17, (variadic using declarations, and deduction guides for class constructors template parameter deduction), this can already be achieved even more elegantly as showed in this great video from Jason Turner’s C++ Weekly (5 minutes of awesomeness!).

But before C++17, the double functor trick uses standard components only and is simple to put in place locally, even if it isn’t maybe the most hip solution.

In a future post we’ll talk more about function objects and understand how they can shed some light on the design of the STL and of the C++ language itself.

Don't want to miss out ? Follow:   
Share this post!