Everybody programming in C++ using the standard template library (STL) has come across some kind of strange-looking thing named function object or functor. Although they are regular C++ objects just like any other, they are mostly related to the standard template library (STL) and indeed these objects are heavily used in conjunction with it. To be more precise, they are mostly being used together with the algorithms of the STL.
As with many other parts of the STL, this concept is pretty complex and thus—although we are trying to explain things in a simple way—we have to expect a little bit of knowledge about the basic principles of programming as well as some knowledge of the STL, escpecially about its algorithms, from you. Furthermore, by no means is this supposed to be a complete tutorial to function objects.
Basics of Function Objects
If you separate the two words function and object, you already know each one on its own. If you are already a programmer—which we assume at this point—you know the meaning of each one in regard to software engineering:
-
A function is the typical way of getting a particular job done in C++ programs; in other words, it defines the execution flow of a specific operation. It usually has one defined entry and one defined exit point. There have been many debates on whether there should only be one or several exit point(s); however, this does not matter in regard to this article.
-
An object refers to the concrete creation of a datatype that takes up a certain amount of space at a specific memory location. The term object is interchangeable with the term instance which, in this regard, means the same.
A function object extends the characteristics of regular functions by using object-oriented C++ features such as generic prgoramming and abstraction. Thus, they can be referred to as smart functions that provide several advantages over regular functions:
-
Function objects can have member functions as well as member attributes. Thus, they can carry a state that even can be different at the same time.
-
Due to their nature, function objects can be initialized before their usage.
-
Opposed to regular functions that can only have different types if their signatures differs, function objects can have different types even with the same signature; this ensures the type safety of the C++ language. If you provide a function object as the sorting criteria for a collection, it is guaranteed that you cannot assign, combine, or compare collections with a different sorting criteria.
-
Function objects are usually faster than regular functions.
Creation of Function Objects
Function objects are often referred to as smart functions due to their advantages pointed out in the previous paragraph. That also means that functions and function objects are closely related and indeed...any object that behaves like a function can be both seen and used as one.
So, what is the magical part? Think about what a function call comes down to...
void func(int);
int main()
{
func(3);
return 0;
}
By looking at this (very simple) example, you actually can divide a function call into three pieces:
-
You call a function by name. (To simplify matters, we don't deal with function pointers, RPC calls, and the like here.)
-
You use parentheses.
-
You can (optionally) pass arguments.
To create an object that behaves just like a function, you only need to provide a way to call this object by name using parentheses and (optionally) passing arguments. The solution to the problem is the so-called function call operator that is just another ordinary operator that can be defined. The operator name is simply a pair of parentheses: '()'.
As all of the other available operators, it follows the general layout scheme:
class foo
{
public:
return_type operator operator_name (argument_list);
};
Thus, to create a function object, you simply need to provide a function call operator...
class function_object
{
public:
int operator()(int i) { return i; }
};
That is basically all...this class now can be called just like any regular function:
#include <iostream>
int main()
{
function_object fo;
std::cout << fo(5) << std::endl;
std::cout << fo.operator()(2) << std::endl;
return 0;
}
Classification of Function Objects
Function objects can be classified by more than one criterion, but the most important one is whether or not they carry a state. Three types of function objects can be differentiated:
Stateless
Stateless function objects are the closest correspondent to a regular function. The function object doesn't have data members, or, if it does, they have no impact whatsoever on the function call operator (that is, are not used at all by this operator, either directly nor indirectly):
#include <iostream>
class stateless_function_object
{
public:
int operator()(int i) const { return i * i; }
};
int main()
{
stateless_function_object fo;
std::cout << fo(2) << std::endl;
return 0;
}
Note: If 'stateless_function_object' had any data members, this had been almost a certain sign of poor design: one class, one responsibility is what one should aim for.
Stateful (Invariable)
Invariable stateful function objects do have a state, but the function call operator is declared constant. Semantically, this means that the operation will use the state, but won't change it:
#include <iostream>
class invariant_function_object
{
public:
invariant_function_object(int state): state_(state) {}
int operator()(int i) const { return i * state_; }
private:
int state_;
};
int main()
{
invariant_function_object fo(3);
std::cout << fo(2) << std::endl;
return 0;
}
Make no mistake here: The first line in 'main()' creates the function object, calling its constructor, and setting the internal state to 3. The second line calls the function call operator.
As you see, the function call operator uses the internal state, but doesn't change it. Any result in changing the invariant will result in a compiler error because the function call operator is not allowed to modify any member attributes (this isn't true for 'mutable' member attributes, though).
Stateful (Variable)
Variable stateful functions objects not only have a state, but also can change this state with each operation.
#include <iostream>
#include <vector>
#include <algorithm>
class stateful_function_object
{
public:
stateful_function_object(): state_(0) {}
int operator()(int i) { return state_ += i; }
int get() const { return state_; }
private:
int state_;
};
int main()
{
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
stateful_function_object fo;
fo = std::for_each(vec.begin(), vec.end(), fo);
std::cout << fo.get() << std::endl;
return 0;
}
There is quite a lot going on here...so, take a closer look:
-
The general idea of this function object is to sum all the elements in the collection which in this example consists of the numbers 1 to 5. Summation is being done by passing the collection to the STL algorithm 'for_each'. This algorithm takes the beginning and the end of a collection and either a function object or a regular function that is being called for every element in the specified range of the collection.
The standard does not guarantee in which order the algorithm passes the elements to the function object. The only guarantee it gives is that the algorithm will pass each element once (and only once) to the specified function object (or regular function). When summing up elements, it does not matter. Thus, a stateful function object should never rely on any order in such a case.
-
To be able to get the result (in the example, the sum of all elements), the algorithm 'for_each' returns a copy of the internally modified function object. This is important because the algorithm internally uses a temporary copy of the function object being passed (because it is passed by value). When working with stateful function objects, always keep the copy semantics of them in mind.
Requirements for Function Objects
Because function objects are almost being passed by value, you should adhere to the following concepts:
Function objects need to provide an appropriate function call operator. As indicated, this is the heart of function objects that makes them possible to be used just like regular functions.
Function objects must implement correct copy semantics. Passing by value always introduces the creation of additional copies of the function objects (even as temporary objects). Thus, stateful function objects need to ensure that their state information gets mirrored correctly to additional copies of them. This might require a specialized copy constructor as well as an assignment operator.
Function objects should be small to avoid expensive copies. Passing by value always comes at a performance penalty because instead of simply copying or assigning a small pointer, the complete object needs to be copied or assigned. This performance penalty will increase the bigger the object itself is.
Function objects should not contain any polymorphic elements—in other words no virtual functions. Using polymorphic function objects opens the door to some problems. If a derived class function object is being passed by value into parameters of the corresponding base class type, the slicing problem will be experienced: While copying the object, the additional parts of the derived class are being removed.
Of course, there is still a way to use polymorphic function objects...by refactoring them. In other words, the polymorphic parts are being refactored into a separate class. The remaining monomorphic function object then in turn contains a pointer to this separate class. This is a well-known design pattern, usually referred to as the Bridge or pImpl pattern.
Function Objects and the STL
As indicated at the beginning of this article, function objects are a pretty important concept of the STL, especially its algorithms.
The STL provides many standard algorithms for processing elements of a collection that cover most common general operations such as traversal, sorting, searching, inserting, and removing. These algorithms can be customized by providing function objects that provide information on how the particular algorithm should operate on the elements of the collection.
Because the STL itself relies so heavily on function objects, it does not come as a suprise that it provides predefined function objects and predicates as well as composite function objects through binders, member function adapters, pointer to function adapters, negaters, and function objects base structures. The following paragraphs will take a closer look at all of these.
Predicates
Predicates are function objects that return a boolean value (or anything that can be implicitly converted to one):
#include <iostream>
class predicate
{
public:
bool operator()(int val) const { return val == 10; }
};
int main()
{
predicate p;
std::cout << (p(2) ? "true" : "false") << std::endl;
return 0;
}
Predicates should always be implemented as stateless function objects to avoid unexpected results. There is no guarantee how often an algorithm might internally copy the predicate. Thus, having predicates that are implemented as stateful function objects might have unexecpted results. Consider the following example:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
class predicate
{
public:
predicate(int condition) :
condition_(condition), state_(0) {}
bool operator()(int) { return ++state_ == condition_; }
private:
int condition_;
int state_;
};
int main()
{
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
predicate p(2);
std::vector<int>::iterator pos =
std::remove_if(vec.begin(), vec.end(), p);
vec.erase(pos, v.end());
std::copy(vec.begin(), vec.end(),
std::ostream_iterator<int>(std::cout, " "));
return 0;
}
The example defines a predicate that will return 'true' every time the internal state equals the condition. The purpose is to remove the second element ('condition' equals two) from the collection. However, the output of the example is different from what you would expect:
1 3 5
Clearly, not only the second element has been removed but also the fourth one. The answer to this curiosity is simply that the used algorithm 'remove_if' internally copies the predicate during its execution. And this internal copy creates a new predicate object containing its original state.
This is not a bug of the STL itself because—as was said earlier—there is no guarantee how many times a predicate might get copied internally. Thus, when using predicates you should always make sure that they are implemented as stateless function objects.
Function Adapters
Function adapters are function objects that allow you to combine, transform, or manipulate function objects with each other, certain values, or with special functions and are divided into the following categories:
Binders
A binder can be used to transform a binary function object into an unary one by acting as a converter between the function object and, for example, an algorithm. Binders always store both the binary function object as well as the argument internally. This argument then will being passed as one of the arguments of the function object every time it is being called.
The STL provides two different binders:
template<class Op>
class binder1st : public unary_function
<typename Op::second_argument_type,
typename Op::result_type>
{
Op op_;
typename Op::first_argument_type first_arg_;
public:
binder1st(const Op& op,
const typename Op::first_argument_type&
first_arg) : op_(op),
first_arg_(first_arg) {}
typename Op::result_type operator()
(const typename Op::second_argument_type& arg) const
{
return op_(first_arg_, arg);
}
};
template<class Op, class Arg>
inline binder1st<Op> bind1st(const Op& op,
const Arg& arg)
{
return binder1st<Op>(op, arg);
}
template<class Op>
class binder2nd : public unary_function
<typename Op::first_argument_type,
typename Op::result_type>
{
Op op_;
typename Op::second_argument_type second_arg_;
public:
binder2nd(const Op& op,
const typename Op::second_argument_type&
second_arg) : op_(op),
second_arg_(second_arg) {}
typename Op::result_type operator()(const typename
Op::argument_type& arg) const
{
return op_(arg, second_arg_);
}
};
template<class Op, class Arg>
inline binder2nd<Op> bind2nd(const Op& op,
const Arg& arg)
{
return binder2nd<Op>(op, arg);
}
The first version ('bind1st') calls 'Op' with 'Arg' as its first parameter; the second version ('bind2nd') calls 'Op' with 'Arg' as its second parameter.
For example, if you want to multiply each element of a collection with itself, you would use something like the following:
#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
int main()
{
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
std::transform(vec.begin(),
vec.end(),
vec.begin(),
std::ostream_iterator<int>
(std::cout, " "),
std::multiplies<int>());
return 0;
}
The output will be:
1 4 9 16 25
However, what if you want to multiply each value of the collection with a certain value? The algorithm 'transform' expects an operation that takes one argument (the actual element of the collection) as its fourth argument. In this case, the binder 'bind2nd' can help:
#include <algorithm>
#include <functional>
#include <vector>
#include <iterator>
int main()
{
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
std::transform(vec.begin(),
vec.end(),
std::ostream_iterator<int>
(std::cout, " "),
std::bind2nd(std::multiplies<int>(), 5));
return 0;
}
Now, the output will be
5 10 15 20 25
'bind2nd' combines an operation that take two arguments to get an operation for one argument. Thus, it satisfies the requirements for the algorithm 'transform' and at the same time allows to provide a specific operation with two arguments. The way it works is pretty simple. The binder 'bind2nd' internally stores both the operation and the argument. If the binder is being called by the algorithm, it simply calls the operation with the element passed by the algorithm as the first argument and the internally stored argument as the second argument and returns the result.
Negaters
A negater can be used to express the opposite of a function object, in other words, it simply negates its result. The STL provides two different binders:
template<class Op>
class unary_negate : public unary_function
<typename Op::argument_type, bool>
{
Op op_;
public:
explicit unary_negate(const Op&aml; op) : op_(op) {}
bool operator()(const typename
Op::argument_type& arg) const
{
return !op_(arg);
}
};
template<class Op>
inline unary_negate<Op> not1(const Op& op)
{
return unary_negate<Op>(op);
}
template<class Op>
class binary_negate : public binary_function
<typename Op::first_argument_type,
typename Op::second_argument_type,
bool>
{
Op op_;
public:
explicit binary_negate(const Op& op) : op_(op) {}
bool operator()(const typename
Op::first_argument_type& arg1,
const typename
Op::second_argument_type& arg2) const
{
return !op_(arg1, arg2);
}
};
template<class Op>
inline binary_negate<Op> not2(const Op& op)
{
return binary_negate<Op>(op);
}
