STL Algorithms

Generic algorithms for efficiency and portability

Dan is a project manager with Wink Communications. He can be reached at [email protected].

To use the generic programming tools in the C++ Standard Template Library (STL), you need to understand STL iterators, algorithms, and containers. Of these, the last is probably the most straightforward, because there are only a handful of containers manipulated primarily through iterators and algorithms. In "STL Iterators" (DDJ, June 1996), I focused on iterators, which form the universal "glue" that holds STL together. In this article, I'll turn my attention to generic algorithms.

Generic algorithms generally have two properties:

• They are independent of any particular data representation, and have only general requirements for how the underlying data must be accessed.
• They are as efficient as an algorithm hand-coded for a given data structure, as long as that data structure meets the algorithm's access requirements.

The find algorithm discussed in my last article is a perfect example of this. It works with any data structure for which you can define a class meeting the input-iterator requirements. For these structures (C arrays or a simple linked_list, for instance), it will be as efficient as hand-coded algorithms (like find_in_array and find_in_list).

Not every algorithm can be made generic. For example, the hypothetical generic algorithm, size (see Listing One), is intended to find the size of a structure given iterators pointing to the first and last element; in other words, it computes the distance between two input iterators (like distance, a real generic algorithm). Why is size not included as a generic algorithm in the library? If you recall the definitions of wc and uwc in the June article, I used a size member function to count the number elements in a vector or set. Why not supply size as a generic algorithm instead of defining distinct size member functions for each collection?

The answer to both questions is that, when compared to the hypothetical generic algorithm, containers usually compute size more efficiently. Of course, some will not. The simple linked_list structure would need to use an algorithm like the hypothetical size that executes in linear time. The size of a container with 1000 elements will take roughly ten times as long to compute as the size of one with only 100. Still, almost all real-world data structures lend themselves to a constant time solution. The size of anything that can support a random-access iterator, for example, can be computed with the expression last -first. The STL implementation of structures like set and list, which do not support random-access iterators, cache the size to avoid performing a linear-time computation.

In summary, although it is possible to define a size algorithm in very generic terms, the resulting definition fails the second requirement -it does not operate as efficiently as hand-coded, data-structure-specific definitions.

Manipulating Sequences

The simplest sort of generic algorithm goes through a sequence, looking for something or doing something that doesn't change the sequence in any way. The generic algorithm find was one example. It is called "nonmutating," because it does not change any of the sequences involved.

Listing Two(a) is the standard declaration of find, taken from the STL code. Listing Two(b) is find_if, a minor variation on find. Instead of specifying some value to search for (as in find), the third argument to find_if is a predicate-a function expected to return a True or False value. This predicate is called on each item of the sequence in turn. The iterator representing the first item for which the predicate returns True is returned, or the iterator given as the second argument to find_if is returned if no item works. In Listing Two(c), find_if is defined much the same as find. You can use this, as Listing Two(d) illustrates, to find the first whitespace character in a C-style string.

Another in the find family is find_adjacent, which looks for consecutive elements that are duplicates. Given a first and last input iterator, find_adjacent returns the first iterator i in the sequence (or last, if there is none) such that *i == *(i+1). Another version of this algorithm takes a predicate p as a third argument and returns the first i such that p(*i, *(i+1)) == true.

A further variation on this theme is provided by count and count_if, which return the number of matches (rather than an iterator) to a value or predicate; see Listing Three(a). Both of these algorithms take four arguments; the last of these is a reference argument modified to hold the actual count. So to count the amount of whitespace in the_line, you would write something like Listing Three(b). To count only the number of actual space characters (rather than tabs and the like), you could use Listing Three(c).

One of the most useful of these nonmodifying sequence algorithms, equal, comes in two flavors: One uses the == operator to do the comparisons, the other takes a predicate as an additional argument and uses it instead. See Listing Four(a). In either case, equal takes three input iterators: first1, last1, and first2. equal starts by dereferencing first1 and first2 and comparing the results. If they're not the same, based either on operator== or the predicate passed as a fourth argument, equal returns False. Otherwise, first1 and first2 are incremented. If first1 is now the same as last1, equal returns True. If not, you dereference, compare, and increment all over again (if necessary).

Perhaps the most fundamental of the nonmodifying sequence algorithms is for_each, which takes three arguments: the standard first and last input iterators, and a function. See Listing Four(b). For_each applies the function given in the third argument to the result of dereferencing every iterator from first to last, in order. The function is not supposed to apply any nonconstant operation on the dereferenced elements. This last requirement may be a little surprising. Obviously, if the original sequence was modified by calling a nonconstant function on its members, you couldn't very well call for_each a nonmodifying sequence algorithm. On the other hand, consider Listing Four(c), in which the second line will calculate the sin of all the elements stored in numbers. What good is this? The results aren't stored anywhere, and sin doesn't modify its argument. After the call to for_each, there's no evidence at all that the call ever took place (and a smart compiler could skip it altogether).

The for_each algorithm is really only useful when combined with a function that has some side-effects, unlike sin and other "pure" functions. The rules for for_each state that these side-effects can't be on the arguments themselves, but other sorts of effects are allowed, like printing or counting in Listing Four(d).

Mutating Sequences

Another sort of generic algorithm is intended to manipulate one sequence of data to produce another. An example of this is copy, which takes a sequence of information and deposits it somewhere else without performing any transformation on it; see Listing Five(a). In this algorithm, the initial sequence is untouched, but the destination sequence is changed dramatically. Because first and last are used only as sources of information, they must be at least input iterators; result, used only as a destination for information, must be at least an output iterator.

The transform algorithm in Listing Five(b) combines copy and for_each. Transform runs through a sequence, performing a function on each element and storing the result in another container. For example, transform(first, last, result, sin) dereferences all the elements between first and last, calls sin on the resulting numbers, and stores the results in the iterators from result to result + (last - first). Another way of using transform is with a function that takes two arguments. This version takes the form transform(first1, last1, first2, result, function).

Sometimes it's useful to transform a sequence in place, rather than storing the results elsewhere. You can do this with transform by using the same iterator for first (or first1 in the five-argument form) and result. You can modify the original for_each example; see Listing Six(a). Now all the sins will be stored in the numbers array, replacing the original values.

Some more-specialized algorithms are designed to change sequences in other ways: replace finds all instances of a given value and replaces it with another; and remove compacts a sequence by finding all instances of a value and taking them out; see Listing Six(b). Neither of these changes the size of a sequence. This may be surprising, especially with remove. Somewhat nonintuitively, remove simply returns an iterator to the last element in the sequence once it has been compacted, and leaves it to the user to actually free up the elements after this point. (Since replace always does one-for-one replacements, returning such a value would be unnecessary.) For example, after the call to remove in Listing Six(c), the array still has five numbers, but the numbers are now {1,3,7,9,9} and end points to numbers + 4. In other words, as far as remove is concerned, the second nine is now past-the-end, rather than part of the sequence.

Both of these algorithms come in several varieties. Special versions of each are provided to put the results in another sequence rather than modifying the first (replace_copy and remove_copy), to use a predicate rather than a value in deciding whether an element is a candidate for replacement or removal (replace_if and remove_if), and to do both (replace_copy_if and remove_ copy_if). In all of the noncopying versions, the iterators must be forward iterators (because we need to assign through them as well as read them); the copying versions use input iterators for the sources and output iterators for the destinations.

Listing Seven is reverse, another commonly used algorithm that reverses the sequence from first to last. Several algorithms exist to "fill in" a sequence. Two of these, fill and fill_n, fill a sequence with the same value, as in Listing Eight(a). The only difference between them is that fill takes a forward iterator to specify both the start and end positions in the sequence, while fill_n takes an output iterator to mark the start and a value to represent the number of elements to fill. The reason one of these uses forward iterators and the other uses an output iterator is clearer if you look at the implementation; see Listing Eight(b).

In fill, you have to compare first and last using != to decide when to terminate the while loop, whereas fill_n only needs to compare n, a variable of type Size (usually an integer) rather than an iterator. Unlike all other iterators, output iterators are not required to provide != (or ==).

Another pair of algorithms, generate and generate_n, work by repeatedly calling a generator function (with no arguments) to produce the elements for the sequences; see Listing Nine.

Sorting

Programmers are always sorting things. I recently learned that one software company in California tests its job applicants by asking them to write a short program that does nothing but sort a list of numbers. Fortunately for would-be professional programmers, we can write a sort program using STL in just a few lines, as Listing Ten(a) illustrates.

There are other ways to write such a program (you've seen in the June article that you can store values in a set as a way of automatically sorting), but Listing Ten(b) demonstrates the basic usage of sort. The second version allows you to sort by something other than the standard < operator.

A useful variation on sort is stable_sort, which, as expected, guarantees that the relative ordering of equal elements is unchanged. (When sorting based on a supplied comparison function, comp, elements a and b are considered equal if both a comp b and b comp a are false.) The prototype of stable_sort is identical to that of sort.

Another variation, partial_sort, is useful when you are interested in an initial subset of the sorted sequence; see Listing Ten(c). The first middle - first elements are placed into the sequence from first to middle. The remaining elements are placed somewhere between middle and last, in an undefined order. If you want to know the top 10 scorers out of a list of 10,000 high scores, for example, this would be faster than sorting the whole list and then extracting the first 10.

Listing Ten(d) is the related function partial_sort_copy (although it isn't quite as closely related as the other _copy algorithms are to their noncopying counterparts). Instead of specifying the number of elements to be sorted using a middle iterator, the number in this case is the smaller of last - first and result_last - result_first. Presumably, it is usually the latter; otherwise it might be clearer to simply use copy followed by plain sort. (Because this two-step method is as fast as a sort_copy or stable_sort_copy would be, those two algorithms aren't provided.) Exactly this many elements are copied from the source sequence (from first to last) to the destination sequence (from result_first to result_last), and, as with the other versions of partial_sort, these are the elements that would be the first in a fully sorted version of the original sequence.

Although this may seem like a somewhat convoluted and obscure algorithm, it is perhaps more useful than the plain partial_sort. Imagine again that you have a list of high scorers and scores. You can now construct a shorter list of top scores with the line partial_sort_copy(scores .begin(), scores.end(), top_scores.begin(), top_scores.end());. The size of our top_ scores structure automatically controls how many scores are copied from our main list. This initial list is left undisturbed, which may be useful if it is frequently referenced in another way, like by the names of the players concerned.

After partial_sort, you can safely say for all elements i in the range from first to middle and for element j in the range from middle to last that the expression i > j (or i comp j) is False. The nth_element algorithm provides a more efficient means of establishing exactly this sort of partition, without taking the extra step of actually sorting the first middle - first elements; see Listing Eleven(a). After a call to nth_ element, the element pointed to by nth is the element that would be in that position if the whole sequence from first to last were sorted, and the sequence were partitioned as explained previously.

The simplest "sorting" algorithms are min and max, described in Listing Eleven(b). Both return a if the two are equal. A version that takes a third argument, a comparison function, is also provided. The versions of these two functions that check whole sequences for a minimum or maximum value are slightly more complicated; see Listing Eleven(c).

Miscellaneous Algorithms

Clearly, STL includes a lot of algorithms, and it's hard to predict in advance which ones you'll use almost daily and which ones you'll forget are even in the library. I think those I've described here are useful, even though I've yet to use some of them in a program. The STL includes some more-obscure algorithms. I'll briefly cover some of them, just so you'll know they're there.

Once a sequence is sorted, there are many algorithms for further manipulating it. The functions lower_bound, upper_bound, and equal_range help determine where in a sequence you can place a given element without disturbing the ordering. The algorithm binary_search returns True if it can locate a given value in a sequence, performing at most log(last - first) + 2 comparisons. Merge combines two sorted sequences, putting the resulting sequence in a third location, so as not to disturb either. Sometimes it is useful to strip a sorted sequence of adjacent duplicates; unique does this.

You can also operate on sorted sequences as if they were sets, using the standard set operations: set_union, set_ intersection, set_difference, and set_symmetric_difference. A final set-like algorithm, includes, tells if every element in one sequence is also in another (that is, whether one sequence is a subset of another).

Nonmodifying sequence operations include find_first_of (which finds a subsequence in a sequence), adjacent_find (which finds adjacent duplicates), mismatch (for finding where two sequences are dissimilar), and search (for finding where in a sequence another sequence is contained).

For altering sequences, the library also contains swap (for exchanging two values without explicitly introducing a temporary), swap_ranges (for exchanging elements of a sequence), iter_swap (for exchanging values defined by two iterators), rotate and rotate_copy (for left rotating a sequence around a specified location), random_shuffle (for randomizing a sequence), and partition and stable_partition (for partitioning a sequence based on a Boolean predicate, rather than a comparison function). There are also algorithms for treating sequences as heaps (push_heap, pop_heap, make_ heap, and sort_heap), for permuting sequences (next_permutation and prev_ permutation), and for doing lexicographic comparisons (lexicographical_compare).

Conclusion

Because each component is really only useful in combination with the other two, it is difficult to examine STL algorithms without also considering iterators and containers. By now, however, you should be able to effectively use most of the STL algorithms. In a future article, I'll drill deeper inside STL, looking at how a few of its pieces are actually implemented, and introduce some of STL's trickier coding.

Listing One

template<class InputIterator, class Size}
void size(InputIterator first, InputIterator last, Size& n)
{
  while (first != last)
  {
    ++n;
    ++first;
  }
}

Listing Two

(a)
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

(b)
template<class InputIterator, class Predicate>
InputIterator find(InputIterator first, InputIterator last, Predicate pred);

(c)
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred){
    while (first != last && !pred(*first)) ++first;
    return first;
}

(d)
const char* the_line = "This is a line of text.";
char* the_space =
  find_if(the_line, the_line + strlen(the_line), isspace);

Listing Three

(a)
template<class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value, Size& n);

template<class InputIterator, class Predicate, class Size>
void count_if(InputIterator first,InputIterator last,Predicate pred,Size& n);

(b)
int n = 0;
count_if(the_line, the_line + strlen(the_line), isspace, n);

(c)
count(the_line, the_line + strlen(the_line), ' ', n);

Listing Four

(a)
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,  InputIterator2 first2, BinaryPredicate pred);

(b)
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

(c)
int numbers[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
for_each(numbers, numbers+10, sin);

(d)
static unsigned counter = 0;
void print_and_count(int i)
{
  cout << "The number is: " << i << endl;
  ++counter;
}
void main()
{
  int numbers[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
  for_each(numbers, numbers+10, print_and_count);
  cout << "The total number of numbers printed is: " << counter;
}

(a)
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InutIterator last,
OutputIterator result);

(b)
template<class InputIterator, class OutputIterator,
    class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);

Listing Six

(a)
int numbers[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
transform(numbers, numbers+10, numbers, sin);

(b)
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
   const T& old_value, const T& new_value);
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
   const T& value);

(c)
int numbers[5] = {1, 3, 5, 7, 9};
int* end = remove(numbers, numbers+5, 5); 

Listing Seven

template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last)

template<class BidirectionalIterator, class OutputIterator>
void reverse_copy(BidirectionalIterator first,
   BidirectionalIterator last, OutputIterator result)

Listing Eight

(a)
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);

template<class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);

(b)
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) {
  while (first != last) *first++ = value;
}
template <class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value) {
  while (n-- > 0) *first++ = value;
}

Listing Nine

template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
template <class OutputIterator, class Size, class Generator>
void generate(OutputIterator first, Size n, Generator gen);

Listing Ten

(a)
void main() {
  vector< int > numbers;
  copy(istream_iterator< int >(cin),
  istream_iterator< int >(),
  inserter(numbers, numbers.end()));
  sort(numbers.begin(), numbers.end());
  copy(numbers.begin(), numbers.end(),
  ostream_iterator< int >(cout, ' '));
}

(b)
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

(c)
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,

   RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
   RandomAccessIterator last, Compare comp);

(d)
template<class InputIterator, class RandomAccessIterator>
void partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first, RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
void partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);

Listing Eleven

(a)
template<class RandomAccessIterator>

void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  RandomAccessIterator last, Compare comp);

(b)
template<class T>
const T& min(const T& a, const T& b);

template<class T>
const T& max(const T& a, const T& b);

(c)
template<class InputIterator>
InputIterator min_element(InputIterator first, InputIterator last);

template<class InputIterator, class Compare>
InputIterator min_element(InputIterator first,InputIterator last,Compare comp);

template<class InputIterator>
InputIterator max_element(InputIterator first, InputIterator last);

template<class InputIterator, class Compare>
InputIterator max_element(InputIterator first,InputIterator last,Compare comp);