Function pointer adapters

Wherever a function-like entity is expected by an algorithm, you can supply either a pointer to an ordinary function or a function object. When the algorithm issues a call, if it is through a function pointer, than the native function-call mechanism is used. If it through a function object, then that objects operator( ) member executes. You saw earlier, for example, that we passed a raw function, gt_15( ), as a predicate to remove_copy_if( ) in the program CopyInts2.cpp. We also passed pointers to functions returning random numbers to generate( ) and generate_n( ).

You cannot, however, use raw functions with function object adapters, such as bind2nd( ), because they assume the existence of type definitions for the argument and result types. Instead of manually converting your native functions into function objects yourself, the standard library provides a family of adapters to do the work for you. The ptr_fun( ) adapters take a pointer to a function and turn it into a function object. They are not designed for a function that takes no arguments?they must only be used with unary functions or binary functions.

The following program uses ptr_fun( ) to wrap a unary function.

We can?t simply pass isEven to not1, because not1 needs to know the actual argument type and return type its argument uses. The ptr_fun( ) adapter deduces those types through template argument deduction. The definition of the unary version of ptr_fun( ) looks something like this:

template <class Arg, class Result>
pointer_to_unary_function<Arg, Result>
ptr_fun(Result (*fptr)(Arg))
return pointer_to_unary_function<Arg, Result>(fptr);

As you can see, this version of ptr_fun( ) deduces the argument and result types from fptr and uses them to initialize a pointer_to_unary_function object that stores fptr. The function call operator for pointer_to_unary_function just calls fptr, as you can see by the last line of its code:

Since pointer_to_unary_function derives from unary_function, the appropriate type definitions come along for the ride and are available to not1.
There is also a binary version of ptr_fun( ), which returns a pointer_to_binary_function object (which derives from binary_function, of course) that behaves analogously to the unary case. The following program uses the binary version of ptr_fun( ) to raise numbers in a sequence to a power. It also reveals a ?gotcha? when passing overloaded functions to ptr_fun( ).

The pow( ) function is overloaded in the standard C++ header <cmath> for each of the floating-point data types, as follows:
float pow(float, int); // efficient int power versions?
double pow(double, int);
long double pow(long double, int);
float pow(float, float);
double pow(double, double);
long double pow(long double, long double);

Since there are multiple versions of pow( ), the compiler has no way of knowing which to choose. In this case, we have to help the compiler by using explicit function template specialization.

An even trickier problem is that of converting a member function into a function object suitable for using with the generic algorithms. As a simple example, suppose we have the classical ?shape? problem and want to apply the draw( ) member function to each pointer in a container of Shape:

The for_each( ) algorithm does just what it sounds like it: it passes each element in a sequence to the function object denoted by its third argument. In this case, we want the function object to wrap one of the member functions of the class itself, and so the function object?s ?argument? becomes the pointer to the object that the member function is called for. To produce such a function object, the mem_fun( ) template takes a pointer to a member as its argument. The purge( ) function is just a little something we wrote that calls delete on every element of sequence.

The mem_fun( ) functions are for producing function objects that are called using a pointer to the object that the member function is called for, while mem_fun_ref( ) is used for calling the member function directly for an object. One set of overloads of both mem_fun( ) and mem_fun_ref( ) is for member functions that take zero arguments and one argument, and this is multiplied by two to handle const vs. non-const member functions. However, templates and overloading takes care of sorting all that out; all you need to remember is when to use mem_fun( ) vs. mem_fun_ref( ).

Suppose you have a container of objects (not pointers), and you want to call a member function that takes an argument. The argument you pass should come from a second container of objects. To accomplish this, use the second overloaded form of the transform( ) algorithm:

Because the container is holding objects, mem_fun_ref( ) must be used with the pointer-to-member function. This version of transform( ) takes the start and end point of the first range (where the objects live); the starting point of the second range, which holds the arguments to the member function; the destination iterator, which in this case is standard output; and the function object to call for each object. This function object is created with mem_fun_ref( ) and the desired pointer to member. Notice that the transform( ) and for_each( ) template functions are incomplete; transform( ) requires that the function it calls return a value, and there is no for_each( ) that passes two arguments to the function it calls. Thus, you cannot call a member function that returns void and takes an argument using transform( ) or for_each( ).

Most any member function works with mem_fun_ref( ). You can also use standard library member functions, if your compiler doesn?t add any default arguments beyond the normal arguments specified in the standard . For example, suppose you?d like to read a file and search for blank lines; your compiler may allow you to use the string::empty( ) member function like this:

This example uses find_if( ) to locate the first blank line in the given range using mem_fun_ref( ) with string::empty( ). After the file is opened and read into the vector, the process is repeated to find every blank line in the file. Each time a blank line is found, it is replaced with the characters ?A BLANK LINE.? All you have to do to accomplish this is dereference the iterator to select the current string.

A catalog of STL algorithms

This section provides a quick reference for when you?re searching for the appropriate algorithm. We leave the full exploration of all the STL algorithms to other references, along with the more intimate details of performance, and so on. Our goal here is for you to become rapidly comfortable and facile with the algorithms, and we?ll assume you will look into the more specialized references if you need more depth of detail.

Although you will often see the algorithms described using their full template declaration syntax, we?re not doing that here because you already know they are templates, and it?s quite easy to see what the template arguments are from the function declarations. The type names for the arguments provide descriptions for the types of iterators required. We think you?ll find this form is easier to read, and you can quickly find the full declaration in the template header file if for some reason you feel the need.

The names of the iterator classes describe the iterator type to which they must conform. There are no interface base classes to enforce these iteration operations?they are just expected to be there. If they are not, your compiler will complain. The various flavors of iterators are described briefly as follows.

InputIterator. An input iterator only allows reading elements of its sequence in a single, forward pass using operator++ and operator*. Input iterators can also be tested with operator== and operator!=. That?s all.

OutputIterator. An output iterator only allows writing elements to a sequence in a single, forward pass using operator++ and operator*. OutputIterators cannot be tested with operator== and operator!=, however, because you assume that you can just keep sending elements to the destination and that you don?t have to see if the destination?s end marker has been reached. That is, the container that an OutputIterator references can take an infinite number of objects, so no end-checking is necessary. This requirement is important so that an OutputIterator can be used with ostreams (via ostream_iterator), but you?ll also commonly use the ?insert? iterators such as are the type of iterator returned by back_inserter( )).

There ius no way to determine whether multiple InputIterators or OutputIterators point within the same range, so there is no way to us multiple such iterators in concert. Just think in terms of iterators to support istreams and ostreams, and InputIterator and OutputIterator will make perfect sense. Also note that algorithms that use InputIterators or OutputIterators put the weakest restrictions on the types of iterators they will accept, which means that you can use any ?more sophisticated? type of iterator when you see InputIterator or OutputIterator used as STL algorithm template arguments.

ForwardIterator. Because you can only read from an InputIterator and write to an OutputIterator, you can?t use either of them to simultaneously read and modify a range, and you can?t dereference such an iterator more than once. With a ForwardIterator these restrictions are relaxed; you can still only move forward using operator++, but you can both write and read, and you can compare such iterators in the same range for equality. Since forward iterators can both read and write, they can of course be used wherever an input or output iterator is called for.

BidirectionalIterator. Effectively, this is a ForwardIterator that can also go backward. That is, a BidirectionalIterator supports all the operations that a ForwardIterator does, but in addition it has an operator–.

RandomAccessIterator. This type of iterator supports all the operations that a regular pointer does: you can add and subtract integral values to move it forward and backward by jumps (rather than just one element at a time), you can subscript it with operator[ ], you can subtract one iterator from another, and you can compare iterators to see which is greater using operator<, operator>, and so on. If you?re implementing a sorting routine or something similar, random access iterators are necessary to be able to create an efficient algorithm.

The names used for the template parameter types in the algorithm descriptions later in this tutorial consist of the listed iterator types (sometimes with a “1” or “2” appended to distinguish different template arguments) and can also include other arguments, often function objects.

When describing the group of elements that an operation is performed on, mathematical ?range? notation is often used. In this, the square bracket means ?includes the end point,? and the parenthesis means ?does not include the end point.? When using iterators, a range is determined by the iterator pointing to the initial element and by the ?past-the-end? iterator, pointing past the last element. Since the past-the-end element is never used, the range determined by a pair of iterators can thus be expressed as [first, last), in which first is the iterator pointing to the initial element, and last is the past-the-end iterator.

Most books and discussions of the STL algorithms arrange them according to side-effects: non-mutating algorithms don?t change the elements in the range, mutating algorithms do change the elements, and so on. These descriptions are based primarily on the underlying behavior or implementation of the algorithm?that is, on the designer?s perspective. In practice, we don?t find this a useful categorization, so instead we?ll organize them according to the problem you want to solve: are you searching for an element or set of elements, performing an operation on each element, counting elements, replacing elements, and so on. This should help you find the algorithm you want more easily.

Note that all the algorithms are in the namespace std. If you do not see a different header such as <utility> or <numeric> above the function declarations, it appears in <algorithm>.