The Standard Template Library (STL) contains many things that most C++ programmers can't live without. It also shows the power of C++ in its ability to program conceptually. STL concepts include containers, ranges, algorithms, and functors. In this article, I'll focus on the functor, which is a class that can act like a function by overloading operator(). This concept existed even before STL, but STL has made us see it in a different light. Read on, and you'll see why.
Algorithms, ranges, and functions
STL deals with functions in a generic way. STL algorithms don't care whether an argument that should act like a function is an actual C++ function or a functor. For the purposes of this article, I'll refer to classes that have an overloaded operator() taking one argument as unary functors, and to classes having an overloaded operator() taking two arguments as binary functors.
STL algorithms are applied to ranges. Some use functions and apply them to each element in a range (Listing A). In this matter, they can deal with three types of functions:
- Functions taking zero arguments, also known as generators, which can generate ranges. For example, each call to a function that generates the Fibonacci numbers will return the next number in the Fibonacci sequence.
- Functions taking one argument (unary functions)
- Functions taking two arguments (binary functions)
This covers most cases. Rarely will you need functions taking three arguments or more. If you encounter this situation, you might think about taking another approach. For example, you could pack multiple arguments into a structure and pass it by reference.
Functors: Why and when
Functors were developed because functions can't hold any meaningful state. For example, you can't add an arbitrary value to an element and apply it to a range in a generic way using functions. However, it's trivial to do it using functors, as Listing B shows.
This is the main advantage of functors: They have context (state). Here are factors to remember about functors:
- A functor is passed to an algorithm by value.
- You apply functors one at a time by applying operator() to each element in the range.
- You can use functors to do something for each element in a range (such as multiply each element by 5), compute something meaningful for a range (such as the average of all elements), or both.
- For a given range, a functor does not know the number of elements to which it will be applied.
Say you want to create a function that, given a range, will return for each element the average of the elements processed so far. In other words:
- for x1, return x1
- for x2, return (x1 + x2) / 2
- for x3, return (x1 + x2 + x3) / 3, etc.
Listing C shows how to implement this task.
As you start writing and using functors, you'll see that they reduce complexity. Instead of focusing on a range, you focus on only one element. This will also increase the readability of your code. An example of the generate_fibonacci code is in Listing D.
So far, we've talked about unary functors. Binary functors are as much, if not more, important. Binary functors are applied either to two ranges in parallel or to two elements in a range. A binary functors' operator() takes two arguments instead of one. Suppose you have two ranges, each having the same number of elements, and you want to construct a new range, like this:
- First element: x1 * y1
- Second element: - x2 * y2
- Third element: x3 * y3
- Fourth element: - x4 * y4, etc.
Listing E shows a possible implementation.
The need for predicates
I've saved the best for last: predicates. Predicates are a special case of functors. In fact, many functors you'll write will be predicates. A predicate is a functor that returns a value convertible to bool (which can be treated as true or false). Unary predicates (predicates taking one argument) allow for filtering, as Listing F shows.
Binary predicates allow comparing for equivalence and sorting (comparing two values to determine whether one is less than the other). Listing G shows how you can compare two ranges for "approximate" equality (equivalence).
Don't underestimate the importance of predicates. Next time you write code, see how much time you spend filtering, comparing for equivalence, and sorting. Using predicates will save you a lot of time and protect your nerves. As a bonus, the code will be much easier to understand.
Using bound functors
The true power of functors and predicates comes to light when they are combined with binders. A binder allows you to bind a value to a binary functor or predicate: That value will be fixed. You can bind the first or the second argument. The binary functor will become a unary functor, like this:
- f = std::bind1st( functor, v); 'f( x)' is equivalent to 'functor( v, x)'
- f = std::bind2nd( functor, v); 'f( x)' is equivalent to 'functor( x, v)'
You bind a binary functor, obtain a unary functor, and apply it to a range. To demonstrate, let's find all elements less than 10 from a range. Listing H shows you how to do it.
Combining binders, functors, and algorithms brings you many benefits. As Listing I shows:
- You can print only elements less than a given value.
- You can partition a range into elements that are less than or equal to a value, as well as elements that are not less than that value.
- You can multiply all elements in a range by a value.
- You can remove all elements greater than a given value.
- You can replace all elements greater than or equal to a value.
STL comes with a lot of predefined functors and predicates, including std::less, std::greater, std::plus, and std::minus, which are found in the <functional> header.
We recommend STL documentation from SGI.
Other good references include:
Andrei Alexandrescu, Modern C++ Design
Scott Meyers, Effective STL
In generic programming, when working with functors, you'll sometimes want to know the type of arguments the functor has and/or the return type of the functor. Consider implementing bind2nd, shown in Listing J.
Since bind1st and bind2nd are so important, a solution to accommodate both was found: adaptable functions. An adaptable function has nested typedefs that allow clients to know the function's argument(s) and return type. For unary adaptable functors, we have argument_type and return_type. For binary adaptable functors, we have first_argument_type, second_argument_type, and return_type. The simplest way to acquire these typedefs is to derive them from std::unary_function or std::binary_function, as shown in all the listings.
Note that bind1st and bind2nd are not the only functions that require adaptable functions. There are others, and as you write your own functors, you might need them too. That's why it's recommended that you make your functors adaptable whenever you can.
A few functor constraints
Although functors and predicates are cool, you should be very careful when writing unary and binary functors. Except when used with the std::for_each algorithm, the context they hold should be constant. (If you have any member variables, they should be initialized in the constructor and remain constant afterward.) Therefore, the example shown in Listing C is broken, according to the C++ standard, even though it works as expected on all existing platforms today. (The data members of structure average are changing each time operator() is applied.)
Only the beginning
We've barely scratched the surface of generic programming. To truly understand functors and predicates, you have to write and use them. While doing that, you'll identify more and more cases where they can be applied. You'll also see how well they work together with algorithms.