The algorithm find we have seen, has a variant called find_if that searches for a value that satisfies a given condition (predicate):
template <class Iterator, class Predicate>
Iterator find_if (Iterator begin, Iterator end,
Predicate pred)
{
while (begin != end && pred(*begin))
++begin;
return begin;
}
The object pred is an example of a function object or functor, an object with the operator() defined.
There are two basic kinds of function objects:
bool is_even (int x) { return (x&1) == 0; }
// ...
find_if(begin, end, is_even);
struct even {
bool operator() (int x) const { return (x&1) == 0; }
};
// ...
find_if(begin, end, even());
There are advantages to using functors of a class type:
Performance: The second call to find_if above is probably inlined, while the first one probably isn't.
The type identifies the functionality (usually).
struct less {
bool operator() (int a, int b) const { return a < b; }
};
struct greater {
bool operator() (int a, int b) const { return a > b; }
};
// these two sets have a different type
set<int, less> s1;
set<int, greater> s2;
bool is_less (int a, int b) { return a < b; }
bool is_greater (int a, int b) { return a > b; }
// but these two have the same type
set<int, bool (*)(int,int)> s1(is_less);
set<int, bool (*)(int,int)> s2(is_greater);
There can be other members including
struct equal {
equal (int y) : val(y) {}
bool operator() (int x) const { return x==val; }
private:
int val;
};
find_if(begin, end, equal(5));
// is the same as
find(begin, end, 5);
Functor adaptors (see below).
There five basic functor concepts in STL:
There are no requirements besides having an operator() with the right number of arguments and, for predicates, the right return type.
Sometimes the function object is also required to have member types identifying the argument and return types:
Function objects with the appropriate member types are called adaptable. The primary use of the member types is with functor adaptors (see below).
The most convient way to define the member types is to use the standard classes unary_function and binary_function:
struct even : unary_function<int,bool> {
bool operator() (int x) const { return (x&1) == 0; }
};
struct less : binary_function<int,int,bool> {
bool operator() (int a, int b) const { return a < b; }
};
The standard library defines several adaptable function objects corresponding to common operators. For example,
template <class T>
struct less : binary_function<T,T,bool> {
bool operator() (const T& a, const T& b) const {
return a < b;
}
};
There are:
These and other functor related declarations are in the header <functional>.
Suppose we wanted to find an odd value instead of an even value. We could, of course, write another function object for that, but functor adaptors offer an alternative:
struct even : unary_function<int,bool> {
bool operator() (int x) const { return (x&1) == 0; }
};
find_if(begin, end, not1(even()));
Note that not1 is quite different from the standard functor logical_not. While logical_not takes and returns a value of type bool, not1 takes and returns a functor. not1 could be called a higher-order function.
Here is how not1 could be defined:
template <class AdaptableUnaryPredicate>
struct unary_negate
: unary_function<typename AdaptableUnaryPredicate::argument_type,
typename AdaptableUnaryPredicate::result_type>
{
unary_negate(AdaptableUnaryPredicate f) : pred(f) {}
bool operator() (const argument_type& x) const {
return !pred(x);
}
private:
AdaptableUnaryPredicate pred;
};
template <class AdaptableUnaryPredicate>
unary_negate<AdaptableUnaryPredicate>
not1 (AdaptableUnaryPredicate pred) {
return unary_negate<AdaptableUnaryPredicate>(pred);
}
There is also not2 and binary_negate for negating a binary predicate.
Another pair of functor adaptors are bind1st and bind2nd that turn a binary function into a unary function.
find_if (begin, end, bind2nd(less<int>(), 2)); find_if (begin, end, bind1st(greater<int>(), 2));
Here both bind2nd(less<int>(), 2)) and bind1st(greater<int>(), 2) create a unary predicate that returns true if its argument is less than 2.
The current standard has no other functor adaptors, but common extensions are various adaptors for composing functors. The future, though, is bind that is included in the Technical Report on C++ Standard Library Extensions or TR1. More about bind can found in the bind proposal and in the documentation of boost::bind.
Function pointers are function objects but they are not adaptable, i.e., cannot be used with adaptors, because they do not have the associated member types. There are, however, ways to create an adaptable functor from a function pointer:
bool is_even (int x) { return (x&1) == 0; }
pointer_to_unary_function<int,bool> even(is_even);
bool is_less (int a, int b) { return a < b; }
pointer_to_binary_function<int,int,bool> less(is_less);
More convenient is to use the helper function ptr_fun which takes a function pointer and returns the appropriate adaptable function object:
find_if(begin, end, not1(ptr_fun(is_even)));
There are problems, though, when the argument type is a reference:
bool is_cool (const Thing& x) { ... }
find_if(begin, end, not1(ptr_fun(is_cool)));
This will not compile, because not1 tries to form the type const argument_type&, where argument_type is const Thing&. The result is a reference to a reference, which is not allowed (currently). A workaround is to define a function class explicitly.
A useful STL algorithm is for_each that applies an operation to every object in a range:
template <class InputIterator, class UnaryFunction>
for_each (InputIterator begin, InputIterator end,
UnaryFunction f) {
while (begin != end) { f(*begin++); }
}
Suppose we have a class
struct widget {
// ...
void draw();
}
and we want to call the member function draw() for all element of a container. We could define a functor specifically for that purpose but there is a more direct way:
vector<widget> v; for_each (v.begin(), v.end(), mem_fun_ref(&widget::draw));
An explanation:
Also, member functions with one argument can be handled. The result is a binary functor with the member functions argument as the second argument:
struct widget {
// ...
void draw(window*);
}
for_each (v.begin(), v.end(),
bind2nd(mem_fun_ref(&widget::draw), dialog_box));
When dealing with containers of pointers to objects rather than the objects themselves, the adaptor mem_fun can be used instead.
vector<widget*> v; for_each (v.begin(), v.end(), mem_fun(&widget::draw));
This is useful for polymorphic containers. Unfortunately, mem_fun does not support smart pointers.
TR1 defines an improved version mem_fn that supports references, pointers, smart pointers and iterators. See proposal or boost::mem_fn for more information.
As mentioned, functors can have an internal state that affects its operation. In some cases, this is even unavoidable. For example, a generator (nullary functor) without an internal state would not make much sense.
However, one should be careful with functors with state:
Some algorithms, for example for_each, specify precisely what they do with the functor. In other cases, in particular with predicates, the specification is less precise:
There is often no guarantee that the same copy of the functor is used throughout the execution of an algorithm.
For example, a common implementation of remove_if calls first find_if and then remove_copy_if. The following code might remove the third and the sixth element:
struct third : unary_function<int,bool> {
third() : count(0) {}
// implicit copy constructor, copy assignment and destructor
bool operator() (int x) const {
return ++count == 3;
}
private:
int count;
};
remove_if(begin, end, third);
There is often no guarantee that a the functor is applied in a deterministic order.
Therefore, predicates should not have a state that changes as a result of copying or calling operator(). In other words, during the execution of the algorithm, the functor should behave as a pure function: its return value depends only on the argument.