Programmers should not have to reinvent the wheel, much less test it. STL helps you avoid both, by providing tested implementations of the most commonly needed algorithms.
Introduction
Last month, I introduced the general topic of algorithms, at least as they are provided by the Standard Template Library, or STL for short. (See "Standard C/C++: Algorithms,'' CUJ, August 1996.) An algorithm in this context is a template function that performs a widely useful function, such as searching a sequence or sorting it. Such functions are typically parametrized in terms of the types of iterators they manipulate to access or generate sequences. (See "Standard C/C++: Iterators,'' CUJ, February 1996.)
STL provides many dozens of algorithm template functions. The vast majority of them are defined in the template <algorithm>, which is by far the largest of the STL headers. (In my implementation of the draft Standard C++ library, it is more than twice as big as the next largest header. But that is partly an artifact of how I chose to chop up the extensive locale machinery.) A handful also appear in the header <numeric>, for some reason.
Even discounting near duplicates, which I discuss below, you can still count over five dozen different algorithms in STL. That's a real treasure trove. Even nicer is the fact that many of these algorithms are hard to get right. It also helps that the template functions automatically adapt when different categories of iterators can profit from different approaches.
I don't intend to show you every single algorithm defined by the Standard Template Library, but I do intend to show you many of them. In the process of rewriting the code distributed by Hewlett-Packard, I learned a lot about working with iterators in particular and with templates in general. I think you will find many coding techniques worth emulating here.
This is the first of three installments that describe the algorithms of STL. It is also the most eclectic, I believe. What you see this month is a number of fairly small template functions, each of which does a simple job simply and well. The goal, in each case, is to generate code as good as or better than a good programmer can craft by hand for a given specialization. That's what it takes to make a library that is truly reused, not just nominally reusable.
Non-Sequence Functions
Nearly all the STL algorithms manipulate sequences using iterators. A handful, however, do not. For example, Listing 1 shows two versions of the template function max, which returns the larger of its two arguments. Actually, only the first of the two versions is guaranteed to do so. It uses operator< to compare the two arguments and determine which is larger.
The second version accepts a function object argument as well. As I described last month, such a creature is either a function pointer or an object of some class that overloads operator(). In either case, the template function must be able to name the object in a function call expression, with some specified signature. In this particular case, the second form of max replaces x < y with pr(x, y), where pr is the function object.
If you call max with the function object greater<T, T> (defined in the header <functional>), you get the same behavior as when you omit the third argument. But you can trot in any sort of function object in its place, so long as it accepts a signature of the proper form. Using less<T, T> (also defined in <functional>), for example, works just fine, but makes a lie out of the name max.
Nearly all the algorithm template functions come in two versions. One is hard wired for a widely used predicate, such as operator<. The other accepts an additional argument, whose type is a template parameter, so you can supply the predicate in the form of a broad range of function objects. Given the current state of optimization, the duplication of code is often a good idea.
I won't show the other non-sequence template functions, since their implementation is obvious enough given the example in Listing 1. I'll simply mention that they are min, with and without a predicate argument, swap, and iter_swap. Only the last name is less than obvious -- it swaps two items given iterators that designate them.
Searching
Listing 2 shows max_element, the extension of max for a sequence with an arbitrary number of elements. Note that it returns an iterator designating the largest element. In the degenerate case where the sequence is empty (first == last), it returns an iterator just past the end of the empty sequence.
Note also that max_element comes in two versions, one taking a predicate argument, just like its simpler cousin in Listing 1. From now on, I won't show the more general form. There's quite enough code to look at without the added redundancy. I also won't show the obvious companions, template function min_element, with and without a predicate argument.
Sometimes you want to consider a sequence as an ordered group of related elements, much like the characters in a string literal such as "abc". Listing 3 shows template function lexicographical_compare. It compares two sequences element by element to test whether the first is ordered "before'' the second, by the usual rules for ordering words by their spelling. As usual, you can supply a predicate argument to give your own meaning to "before'' for two elements (version not shown).
Listing 3 also shows mismatch, which compares elements from two sequences until it finds a pair that don't compare equal. It then returns an object of class pair that stores the two offending iterators. Template function equal uses mismatch to test whether the two sequences are completely equivalent. Both functions have a version that takes a predicate argument. In this case, however, the predicate replaces operator==, not operator<.
Another slew of algorithms searches a sequence for various conditions. Listing 4 shows a representative sampler. Template function find finds the first element that compares equal to a value you specify. You can replace the value argument with a predicate object, but you must then call the function find_if. Template parameter matching is not smart enough always to safely distinguish between a value and a function object.
adjacent_find finds two adjacent elements that compare equal, or that satisfy a predicate that you specify with an added argument. Note that this function requires forward iterators. You can't use an input iterator to designate any but the latest, unconsumed element in a sequence.
count counts all the elements that compare equal to a value you specify. As with find, the version that takes a predicate argument in place of a comparison value is called count_if. The return type of count has recently been changed to be the type associated with its iterator parameters. That change requires partial specialization of templates, however, which is currently unavailable in commercial compilers. So I replace the proper return type with size_t, which is usually close enough.
search searches for a subsequence within a sequence. Note the standard trick of calling yet another template function (_Search) to determine the types used to store distances between the different iterator types. Once partial specialization becomes widespread, the use of _Dist_type can be discontinued in favor of the notation required for the return type of count. As usual, you can replace the equality comparison for pairs of elements by supplying an added predicate argument. search_n behaves much the same, except that the subsequence to search for is a repetition of n copies of a value you specify.
find_end is like find, except that it returns the last match in the sequence, not the first. And find_first_of is similar to find, except that it returns the first element that matches any of the elements in a second sequence. Both functions accept the usual added predicate argument.
Generators
A handful of template functions perform a specified operation for each element of a sequence. Listing 5 shows these creatures. for_each calls the function object you specify for each element of the sequence. Note that it does nothing with any return value. By contrast, generate stores the return value of the function object you specify in each element of a sequence, but it lets you specify no argument to the function. generate_n does much the same thing for the first n elements of a sequence.
transform puts the two services together. The unary version applies the function object you specify to each element of one sequence to determine the return value to store in another sequence. The binary version calls the function with two arguments -- elements from two sequences -- to generate a third sequence.
A simpler way to generate a sequence is to copy an existing one. Listing 5 shows an assortment of such template functions. copy copies a specified sequence from beginning to end, while copy_backward copies from end to beginning. Knowing which way a copy proceeds is invaluable when you have to copy between areas that overlap.
fill replicates a value you specify throughout a sequence. fill_n, on the other hand, copies the value you specify to the first n elements of a sequence. Note the difference in iterator categories, once again.
Finally, swap_ranges exchanges two sequences. It uses the template function iter_swap that I showed much earlier. (Strictly speaking, this is not a sequence generator, but sometimes it's hard to characterize a group of loosely related functions.)
Sequence Editing
There are various ways to edit a sequence. For the following functions, the code is sufficiently obvious that I won't show it here:
- replace replaces each element with the value you specify with another value you specify.
- replace_if replaces each element that satisfies the predicate you specify with a value you specify.
- replace_copy behaves like replace, except that you also specify where to store the modified sequence.
- replace_copy_if behaves like replace_if, except that you also specify where to store the modified sequence.
- remove removes each element with the value you specify, by copying down subsequent elements.
- remove_if removes each element that satisfies the predicate you specify, by copying down subsequent elements.
- remove_copy removes each element with the value you specify, by omitting such elements as it copies a sequence.
- remove_copy_if removes each element that satisfies the predicate you specify, by omitting such elements as it copies a sequence.
Listing 6 shows two somewhat more interesting functions that edit a sequence. unique_copy omits all but the first element in any subsequence of elements that compare equal, as it copies the sequence. Unix fans will recognize this as the heart of the classic software tool uniq. The code presented here illustrates the use of _Iter_cat to select different approaches based on the category of iterators supplied as function arguments.
Working with input iterators, the function must store an actual copy of an element value. It cannot refer to an earlier value through an iterator once that value has passed by. But working with forward (or stronger) iterators, the function can simply store a copy of the iterator to refer to a value earlier in the sequence. There is less risk that the function will be asked to construct, store, and destroy an object that is expensive in storage or execution time.
In principle, there is no need for the last two overloads. I have found, however, that not all compilers know to select the forward-iterator version for bidirectional or random-access iterators. Thus, the redundant versions are "commented in'' as a practical necessity for the nonce.
Template function unique performs in place much the same function as unique_copy. In this case, the latter function can do all the heavy lifting for the former, once unique determines that any rearranging is necessary. It calls adjacent_find for a relatively quick answer to that question.
As usual, both unique_copy and unique have versions that accept an added predicate argument as well.
Rearranging Elements
The last group of algorithms I show this month are lumped together in Listing 7. All of these rearrange the elements of a sequence in various useful ways. reverse and reverse_copy are the simplest. They reverse the elements, either in place or while copying. The former takes advantage of a slight optimization when handed random-access iterators instead of bidirectional ones.
Rotating a sequence is rather harder, at least if you do the job in place. I believe that template function rotate holds the record for taking most ambitious advantage of the ability to fan out on iterator category. I encourage you to study all three versions of this function. They are quite distinct approaches, and each is clever in its own right.
By comparison, rotate_copy is rather tame. In the coming months, you will see how other algorithms take advantage of the greater simplicity of rotating while copying, when the opportunity presents itself to do so.
Finally, random_shuffle does as its name implies. It rearranges the elements of a sequence by performing pairwise swaps of each element with another element chosen randomly. Most of the complexity here stems from a half-hearted attempt to make the algorithm more general. The code endeavors to use the C library function rand to generate a random number big enough to deal with an arbitrary iterator distance type. All it succeeds in doing, however, is extend a 15-bit function to generate a random unsigned long value. Probably that's good enough for most applications. I haven't yet tried to solve the fully general problem.
P.J. Plauger is senior editor of C/C++ Users Journal. He is convener of the ISO C standards committee, WG14, and active on the C++ committee, WG21. He developed Lib Suite ++, the Plum-Hall validation suite for the Standard C++ library. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at pjp@plauger.com.