STL Function Objects

Item 20. STL Function Objects

How did we ever get by without the STL? Not only is it easier and faster to write complex code, but that code is both standard and highly optimized.

std::vector<std::string> names;
std::sort( names.begin(), names.end() );

Another nice thing about the STL is that it's highly configurable. In the code above, we used string's less-than operator to sort a vector of strings, but we don't always have a less-than operator to work with, or we may not want to sort in ascending order.

class State {
    int population() const;
    float aveTempF() const;

The State class (which represents a state of the union) doesn't have a less-than operator, and we probably don't want to implement one because it's not clear what it would mean for one state to be less than another (do we compare names, population, percentage of elected officials under indictment, ...?). Fortunately, the STL generally allows us to specify an alternate less-than-like operation in situations like this. Such an operation is called a "comparator," because it compares two values:

inline bool popLess( const State &a, const State &b )
    { return a.population() < b.population(); }

Once we have a comparator for States, we can use it to sort them:

State union[50];
std::sort( union, union+50, popLess ); // sort by population

Here we've passed a pointer to the popLess function as the comparator (recall that a function name "decays" into a pointer to function when passed as an argument, just as the array name union decays into a pointer to its first element). Because popLess is passed as a function pointer, it will not be inlined in sort, which is unfortunate if we want a fast sort operation (see Function Pointers [14, 49]).

We can do better if we use a function object as a comparator:

struct PopLess : public std::binary_function<State,State,bool> {
    bool operator ()( const State &a, const State &b ) const
        { return popLess( a, b ); }

The PopLess type is a typical example of a properly constructed STL function object. First, it's a function object. It overloads the function call operator so that it may be called with the usual function call syntax. This is important, because STL generic algorithms like sort are written in such a way that either a function pointer or function object may be used to instantiate them, provided that they may be called with the typical function call syntax; a function object with an overloaded operator () satisfies this syntactic requirement.

Second, it's derived from the standard binary_function base class. This is a mechanism that allows other parts of the STL implementation to ask compile-time questions of the function object (see Embedded Type Information [53, 189]). In this case, deriving from binary_function allows one to find out the argument and return types of the function object. We're not using that capability here, but you can bet that somebody else will, and we want our PopLess type to be used by others.

Third, the function object has no data members, no virtual functions, and no explicitly declared constructors or destructor, and the implementation of operator () is inline. Function objects used as STL comparators are assumed to be small, simple, and fast. It's possible to design STL function objects with significant implementations, but it's rarely advisable. Another reason to avoid or minimize the use of data members in a function object to be used with the STL is that STL implementations may make several copies of a function object and may assume that all the copies are identical. One easy way to ensure that all copies of an object are identical is for the object to have no data at all.

Now we can sort this country out by using a function object:

sort( union, union+50, PopLess() );

Note the parentheses that follow PopLess in this call to sort. PopLess is a type, but we have to pass an object of that type as a function argument. By appending parentheses to the PopLess type name, we create an unnamed temporary PopLess object that exists for the duration of the function call. (These nameless objects are known as "anonymous temporaries," a term I've always enjoyed because it sounds vaguely racy.) We could have declared and passed a named object:

PopLess comp;
sort( union, union+50, comp );

However, it's more conventional, and less typing, simply to pass an anonymous temporary object.

A beneficial side effect of using a function object as our comparator is that the comparison will be inlined whereas use of a function pointer did not permit inlining. The reason the call is inlined is that the compiler knows that the type of the comparator is PopLess when the sort function template is instantiated, which in turn allows it to know that PopLess::operator () will be called, which in turn allows it to inline that function, which in turn allows it to inline the nested call to popLess.

Another common use of a function object in the STL is as a predicate. A predicate is an operation that asks a true/false question about a single object. (You can think of a comparator as a kind of binary predicate.)

struct IsWarm : public std::unary_function<State,bool> {
    bool operator ()( const State &a ) const
        { return a.aveTempF() > 60; }

The design guidelines for STL predicates are identical to those for STL comparators with the exception, of course, that they're unary rather than binary functions. Starting with our previous sorted State results, the appropriate predicate makes it trivial to find a warm place without too many dang people:

State *warmandsparse = find_if( union, union+50, IsWarm() );

     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows