Standard C/C++

Columns

Standard C/C++

P. J. Plauger

Last of the Algorithms

Rounding out STL's collection of algorithms are a handful of operations that may be classified as miscellaneous. They merit study no less than their easily classified brethren.

Introduction

This installment concludes a four-part series on the algorithms provided by the Standard Template Library (STL). (See "Standard C/C++: Algorithms,'' CUJ, August 1996, "Standard C/C++: Introduction to <algorithm>,'' CUJ, September 1996, and "Standard C/C++: Ordering Algorithms,'' CUJ, October 1996.) What's left are several distinct groups of template functions. All but the last group occupy the header <algorithm>.

Binary Searching

Listing 1 shows several template functions that search a sequence of increasing values ordered by operator<. As usual, I omit the companion versions that take a function object argument to specify the ordering rule:

To determine the first element in an ordered sequence not less than a specified value, call lower_bound.

To determine the last element in an ordered sequence not less than a specified value, call upper_bound.

To determine both the lower and upper bounds for a specified value in an ordered sequence as above, call equal_range.

To determine whether an ordered sequence contains a member with ordering equivalent to a specified value, call binary_search. Note that "equivalent ordering'' is not necessarily equality, as I described in the August installment.

All of these functions perform a traditional binary chop to locate the desired element or elements in time proportional to the logarithm of the number of elements in the sequence.

Set Operations

Listing 2 shows several template functions that take as input two sequences of increasing values, both ordered by operator<. Versions also exist that take a function object argument:

To determine whether one ordered sequence includes elements equivalent to each of the elements in a second sequence, call includes.

To merge two ordered sequences to generate a new sequence, preserving no elements from the second sequence with ordering equivalent to the first, call set_union. This operation is roughly equivalent to forming the union (logical OR) of two sets of values.

To merge two ordered sequences to generate a new sequence, preserving only elements from the first sequence with ordering equivalent to the second, call set_intersection. This operation is roughly equivalent to forming the intersection (logical AND) of two sets of values.

To merge two ordered sequences to generate a new sequence, preserving only elements from the first sequence with ordering not equivalent to the second, call set_difference. This operation is roughly equivalent to forming the difference of two sets of values.

To merge two ordered sequences to generate a new sequence, preserving only elements from either sequence with ordering not equivalent to the other, call set_symmetric_difference. This operation is roughly equivalent to forming the symmetric difference of two sets of values.

The implementation of all these functions is fairly straightforward.

Heap Operations

Listing 3 shows several template functions that administer a sequence as a heap (also defined in the August installment). The values in a heap are ordered by operator< in the versions shown here. Versions also exist, as usual, that take a function object argument:

To reorder a sequence as a heap, call make_heap.

To add an element to a heap, call push_heap.

To remove the largest element from a heap, call pop_heap.

To sort a heap (in ascending order), call sort_heap.

The heap template functions maintain a typical heap discipline within a sequence:

Element zero is the top of the heap, and stores the largest element.

The child elements at 2 * k + 1 and
2 * k + 2, if present, are smaller than the parent element at k.

Template function push_heap assumes that the heap sequence has been extended with a new element at the end. It copies this value, creating a "hole'' at the end of the heap. Template function _Push_heap percolates the hole toward the top of the heap until it is high enough or until the new value is not greater than the parent of the hole. The parameter j determines how high is "high enough.'' It is always zero in this case.

Template function pop_heap calls _Pop_heap to swap the top of the heap with the element at the end, then restore the heap discipline. That function, in turn, tells _Adjust_heap that a hole now exists at element zero, and that the value originally stored at the end of the sequence must now be properly inserted in the heap.

Template function _Adjust_heap percolates a hole down the heap until it has no children. It then calls _Push_heap to percolate the hole back up the heap to the proper place to store the specified value. _Adjust_heap is called from template function _Partial_sort_copy (described las month) and from several places among the heap template functions.

Template function make_heap simply creates a hole at each element in the first half of the heap sequence, then calls _Adjust_heap to establish the heap discipline among the children of that element.

Permutations

Listing 4 shows two template functions that generate all the permutations of a sequence ordered by operator< (or a function object, with companion versions):

To permute the elements in a sequence, call next_permutation. The template function returns false when it leaves the elements all in ascending order.

To permute the elements in a sequence, you can also call prev_permutation. The template function returns false when it leaves the elements all in descending order. Note that this template function generates permutations in exactly the reverse order of next_permutation.

Template function prev_permutation looks for the rightmost pair of adjacent elements that are in sort order. If no such pair exists, the function restores the initial permutation, by reversing the entire sequence, and returns true. Otherwise, it rearranges the remainder of the sequence, beginning with that pair, so as to generate the next permutation, and returns true. (Walk through all the permutations of three or four elements to see how the permutations are generated in lexicographically decreasing order.)

Template function next_permutation behaves the same as prev_permutation, except that it inverts the predicates that test the order of pairs of elements.

The Header <numeric>

The last batch of algorithm template functions occupy the separate header <numeric>. Listing 5 shows one way to implement this header:

To sum all the elements of a sequence, using operator+ or a specified binary operator, call accumulate.

To sum the products of corresponding elements of two sequences, using operator+ and operator* or two specified binary operators, call inner_product.

To generate a sequence of sums, each adding one more element from a sequence, using operator+ or a specified binary operator, call partial_sum.

To generate a sequence of differences between adjacent pairs of elements from a sequence, using operator- or a specified binary operator, call adjacent_difference.

Once again, all these operations are straightforward. o

P.J. Plauger is senior editor of C/C++ Users Journal. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v4.2. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, WG21. 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.