Sorting, rotating, merging -- it's all done for you by STL. Just add water and fill in the types.
Introduction
I continue this month on the topic of the algorithms provided by the Standard Template Library (STL). (See "Standard C/C++: Algorithms,'' CUJ, August 1996, and "Standard C/C++: Introduction to <algorithm>,'' CUJ, September 1996.) The general theme for this installment is ordering techniques. The idea is that you have one or more sequences and a rule by which you wish to impose some order.
The rule may be implicit -- typically *p < *q, where p and q are iterators that designate elements in the sequence. Or it may be explicit -- a function-object argument pr that returns a Boolean result for the call pr(*p, *q). I discussed function objects in the August 1996 issue. In either case, the sequence is said to be ordered by a rule if no pair of elements in the sequence breaks the rule. For example, if q designates an element later in the sequence than the element designated by p, the predicate !(*q < *p) must be true. (No element after this one compares less than this one.)
An ordering algorithm rearranges elements as needed to impose the desired ordering on a sequence. As a general rule, the more order you wish to impose, the more work you have to perform. Thus, it is nice to have an assortment of algorithms to choose among. You can then pick the one that does the least amount of work to achieve the desired result.
Partitioning
Listing 1 shows the template functions partition and stable_partition. Both require an explicit function object to determine the ordering rule -- such as all the elements less than some fixed value belong in the left partition. partition is demonstrably the simpler function, to be favored whenever possible. You call stable_partition instead when you have an additional constraint on the reordering process. A reordering is said to be stable if pairs of elements that need not be reordered to satisfy the rule are truly left in their original relative order. Effectively, a stable sort promises not to undo any ordering already imposed by some other criterion.
Template function stable_partition makes effective use of a temporary buffer, if one is available. The first overload of the template function _Stable_partition requests a buffer possibly large enough to hold the entire sequence. I described template class _Temp_iterator in conjunction with the header <memory>. (See "Standard C/C++: The Header <memory>,'' CUJ, July 1996.)
Whatever length buffer it gets, the second overload uses to advantage. If the sequence is larger than the buffer, the second function falls back on a classic divide-and-conquer strategy to reduce the problem to one of manageable size. In the absence of any temporary buffer at all, that means repeatedly halving intervals until each is of length one.
Template function _Buffered_rotate, described below in conjunction with inplace_merge, also makes use of any temporary buffer. Its job here is to rearrange the adjacent, but out of order, subpartitions obtained by recursive calls to _Stable_partition.
stable_partition is one of several template functions defined in the header <algorithm> that profits from the use of temporary storage when it is available. Note that all such algorithms run faster given a temporary buffer, but they always work, one way or the other, even without such a buffer.
Sorting
Listing 2 shows the template function sort. It also has a version that takes a function object argument, not shown here. Template function sort makes use of a number of additional functions to do its job as quickly as possible. For any subsequence not longer than _SORT_MAX elements, it relies on the template function _Insertion_sort to perform the actual ordering. It, in turn, calls on _Insertion_sort_1 to perform an insertion sort, which makes up in simplicity (on a short enough sequence) what it lacks in sophistication. The template function _Unguarded_insert gets its name from the trust it puts in its arguments -- it assumes that it will terminate before it runs past the beginning of the (sub)sequence.
Template function _Sort thus performs only a coarse sort. By divide and conquer, it ensures that a long sequence is sorted into chunks of _SORT_MAX elements, where the chunks are in proper order but the elements within each chunk are not. It makes use of the template function _Median to find the median of three values. The median is used to determine a pivot value that is assuredly within the range of values in the subsequence. The function can safely call _Unguarded_partition to partition each subsequence about the pivot value, and that template function can operate somewhat faster than partition because it needn't test for running off the end of a subsequence.
Stable Sorting
Listing 3 shows the template function stable_sort. Like its cousin, template function sort, it also has a version that takes a function-object argument. Template function stable_sort is similar to sort, but it has a slightly more difficult job. The second overload of template function _Stable_sort performs a divide and conquer as needed, until it makes subsequences short enough to order by some other scheme. If the algorithm can acquire a temporary buffer of sufficient size, it uses that buffer in calls to _Buffered_merge_sort. Otherwise, it relies on _Insertion_sort, which fortunately performs a stable sort, to order short subsequences.
Template function _Buffered_merge_sort does almost the exact opposite of sort. First it sorts subsequences of length _CHUNK_SIZE within the sequence, by calling _Insertion_sort, then it merges these chunks into ever larger ordered subsequences until the entire sequence is stably ordered. Each call to _Chunked_merge merges chunks twice as big as the previous call. Merging occurs first to the temporary buffer, then back to the original sequence.
Partial Sorting
Listing 4 shows several template function that perform only a partial reordering. Each has a version that takes an additional function-argument operand, which I once again omit in the interest of space economy in these pages.
Template function partial_sort orders a sequence just enough to determine the leading elements in the ordered sequence. It calls _Partial_sort, which begins by making a heap out of the first n elements of the sequence -- the number of elements to eventually leave ordered. I'll discuss the heap template functions in detail next month. The function then repeatedly compares the top of the heap *first, which is the largest element in the heap, with each element later in the sequence. A call to _Pop_heap (as described next month) exchanges the smaller element with the top of the heap, then restores the heap discipline. Sorting the resultant heap yields the desired partial ordering of the sequence.
Template function partial_sort_copy behaves much the same as partial_sort, but with a few significant differences. It calls the template function _Partial_sort_copy, which copies to the destination sequence enough elements to fill that sequence, if possible, then makes the destination sequence into a heap. Any elements remaining in the source sequence are compared against the top of the heap *first2. A call to _Adjust_heap (also described later) replaces the top of the heap with the smaller element, then restores the heap discipline. Sorting the resultant heap once again yields the desired partial ordering of the sequence.
Template function nth_element is the most miserly of this set of algorithms. It determines only the nth element of the ordered sequence. To do so, it calls _Nth_element to perform the usual divide and conquer sort. I described earlier the use of _Median and _Unguarded_partition. In this case, however, the algorithm ignores any partition that doesn't contain element number n. Once it creates a small enough partition containing that element, it calls _Insertion_sort to finish the (partial) job.
Merging
Finally, Listing 5 shows two template functions that merge two sequences, both ordered by a given rule, to produce a composite sequence ordered by the same rule. As usual, each also has a version that takes an additional function-argument operand. Template function merge is fairly straightforward, since it can generate a new sequence as it proceeds. Merging two adjacent sequences in place, however, takes a bit more work.
Template function inplace_merge incorporates a number of different strategies. The basic approach is divide and conquer, as carried out by _Buffered_merge. That function uses a temporary buffer, for small enough subintervals, to perform a more conventional merge while copying. Note the special template function _Merge_backward for the case where the destination subsequence begins with one of the two source subsequences to merge.
When the temporary buffer is not large enough, _Buffered_merge partitions the larger of the two sequences into two subsequences roughly equal in length. It then determines how much of the other subsequence needs to be swapped with one of these halves. The iterator firstn marks the partition point in the subsequence to the left of mid, while lastn marks the partition point in the right subsequence. Template function _Buffered_rotate performs the exchange by rotating the subsequence [firstn, lastn) about mid. The inplace merge then reduces to two similar but smaller problems.
_Buffered_rotate is used by both stable_partition, described above, and inplace_merge. If it can copy to a temporary buffer the smaller of the two subsequences it wants to exchange, it does so. Otherwise, it falls back on the more general template function rotate to do the job.
P.J. Plauger is senior editor of C/C++ Users Journal. He served for eight years as convener of the ISO C Standards Committee WG14, and is active on the C++ Committee WG21. He developed the Standard C++ Library shipped with Microsoft's Visual C++ Compiler. 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.