C++ Primer Plus

There are two main generic components to the algorithm function designs. First, they use templates to provide generic types. Second, they use iterators to provide a generic representation for accessing data in a container. Thus, the copy() function can work with a container that holds type double values in an array, with a container that holds string values in a linked list, or with a container that stores user-defined objects in a tree structure, such as is used by set. Because pointers are a special case of iterators, STL functions such as copy() can be used with ordinary arrays.

The uniform container design allows meaningful relationships between containers of different kinds. For example, you can use copy() to copy values from an ordinary array to a vector object, from a vector object to a list object, and from a list object to a set object. You can use == to compare different kinds of containers—for example, deque and vector. This is possible because the overloaded == operator for containers uses iterators to compare contents, so a deque object and a vector object test as equal if they have the same content in the same order.

Algorithm Groups

The STL divides the algorithm library into four groups:

• Nonmodifying sequence operations

• Mutating sequence operations

• Sorting and related operations

• Generalized numeric operations

The first three groups are described in the algorithm (formerly algo.h) header file, and the fourth group, being specifically oriented toward numeric data, gets its own header file, called numeric. (Formerly, they, too, were in algo.h.)

Nonmodifying sequence operations operate on each element in a range. These operations leave a container unchanged. For example, find() and for_each() belong to this category.

Mutating sequence operations also operate on each element in a range. As the name suggests, however, they can mutate, or change, the contents of a container. The change could be in values or in the order in which the values are stored. The transform(), random_shuffle(), and copy() functions fall into this category.

Sorting and related operations include several sorting functions (including sort()) and a variety of other functions, including the set operations.

The numeric operations include functions to sum the contents of a range, calculate the inner product of two containers, calculate partial sums, and calculate adjacent differences. Typically, these are operations that are characteristic of arrays, so vector is the container most likely to be used with them.

Appendix G provides a complete summary of these functions.

General Properties of Algorithms

As you’ve seen again and again in this chapter, STL functions work with iterators and iterator ranges. The function prototype indicates the assumptions made about the iterators. For example, the copy() function has this prototype:

template

OutputIterator copy(InputIterator first, InputIterator last,

                     OutputIterator result);

Because the identifiers InputIterator and OutputIterator are template parameters, they just as easily could have been T and U. However, the STL documentation uses the template parameter names to indicate the concept that the parameter models. So this declaration tells you that the range parameters must be input iterators or better and that the iterator indicating where the result goes must be an output parameter or better.

One way of classifying algorithms is on the basis of where the result of the algorithm is placed. Some algorithms do their work in place, and others create copies. For example, when the sort() function is finished, the result occupies the same location that the original data did. So sort() is an in-place algorithm. The copy() function, however, sends the result of its work to another location, so it is a copying algorithm. The transform() function can do both. Like copy(), it uses an output iterator to indicate where the results go. Unlike copy(), transform() allows the output iterator to point to a location in the input range, so it can copy the transformed values over the original values.

Some algorithms come in two versions: an in-place version and a copying version. The STL convention is to append _copy to the name of the copying version. The latter version takes an additional output iterator parameter to specify the location to which to copy the outcome. For example, there is a replace() function that has this prototype:

template

void replace(ForwardIterator first, ForwardIterator last,

              const T& old_value, const T& new_value);

It replaces each instance of old_value with new_value. This occurs in place. Because this algorithm both reads from and writes to container elements, the iterator type has to be ForwardIterator or better. The copying version has this prototype:

template

OutputIterator replace_copy(InputIterator first, InputIterator last,

              OutputIterator result,