Thinking In C++. Volume 2: Practical Programming

Sometimes the number of operations an algorithm takes cannot be measured with such precision. In such cases, the standard specifies the algorithm’s asymptotic complexity, which is a measure of how the algorithm behaves with large sequences compared to well-known formulas. A good example is the sort( ) algorithm, which the standard says takes "approximately n log n comparisons on average" (n is the number of elements in the sequence).^[80] Such complexity measures give a "feel" for the cost of an algorithm and at least give a meaningful basis for comparing algorithms. As you’ll see in the next chapter, the find( ) member function for the set container has logarithmic complexity, which means that the cost of searching for an element in a set will, for large sets, be proportional to the logarithm of the number of elements. This is much smaller than the number of elements for large n, so it is always better to search a set by using its find( ) member function rather than by using the generic find( ) algorithm^.

Function objects

As you study some of the examples earlier in this chapter, you will probably notice the limited utility of the function gt15( ). What if you want to use a number other than 15 as a comparison threshold? You may need a gt20( ) or gt25( ) or others as well. Having to write a separate function for each such comparison has two distasteful difficulties:

1.       You may have to write a lot of functions!

2.      You must know all required values when you write your application code.

The second limitation means that you can’t use runtime values^[81] to govern your searches, which is downright unacceptable. Overcoming this difficulty requires a way to pass information to predicates at runtime. For example, you would need a greater-than function that you can initialize with an arbitrary comparison value. Unfortunately, you can’t pass that value as a function parameter, because unary predicates, such as our gt15( ), are applied to each value in a sequence individually and must therefore take only one parameter.

The way out of this dilemma is, as always, to create an abstraction. In this case, we need an abstraction that can act like a function as well as store state, without disturbing the number of function parameters it accepts when used. This abstraction is called a function object.^[82]

A function object is an instance of a class that overloads operator( ), the function call operator. This operator allows an object to be used with function call syntax. As with any other object, you can initialize it via its constructors. Here is a function object that can be used in place of gt15( ):

//: C06:GreaterThanN.cpp

#include

using namespace std;

class gt_n {

  int value;

public:

  gt_n(int val) : value(val) {}

  bool operator()(int n) {

    return n > value;

  }

};

int main() {

  gt_n f(4);

  cout << f(3) << endl;  // Prints 0 (for false)

  cout << f(5) << endl;  // Prints 1 (for true)

} ///:~

The fixed value to compare against (4) is passed when the function object f is created. The expression f(3) is then evaluated by the compiler as the following function call:

f.operator()(3);

which returns the value of the expression 3 > value, which is false when value is 4, as it is in this example.

Since such comparisons apply to types other than int, it would make sense to define gt_n( ) as a class template. It turns out you don’t have to do it yourself, though—the standard library has already done it for you. The following descriptions of function objects should not only make that topic clear, but also give you a better understanding of how the generic algorithms work^.

Classification of function objects

The standard C++ library classifies function objects based on the number of arguments that their operator( ) takes and the kind of value it returns. This classification is organized according to whether a function object’s operator( ) takes zero, one, or two arguments, as the following definitions illustrate^.

Generator: A type of function object that takes no arguments and returns a value of an arbitrary type. A random number generator is an example of a generator. The standard library provides one generator, the function rand( ) declared in , and has some algorithms, such as generate_n( ), which apply generators to a sequence^.

Unary Function: A type of function object that takes a single argument of any type and returns a value that may be of a different type (which may be void)^.

Binary Function: A type of function object that takes two arguments of any two (possibly distinct) types and returns a value of any type (including void)^.

Unary Predicate: A Unary Function that returns a bool.