NOTE: The example programs described in the following sections have been combined and are included in the file alg7.cpp. As in Chapter13, we generally omit output statements from the descriptions of the programs provided here, although they are included in the executable versions.
The Standard C++ Library provides two fundamental sorting algorithms, described as follows:
void sort (RandomAccessIterator first,
RandomAccessIterator last [, Compare ] );
void stable_sort (RandomAccessIterator first,
RandomAccessIterator last [, Compare ] );
The sort() algorithm is slightly faster, but it does not guarantee that equal elements in the original sequence retain their relative orderings in the final result. If order is important, the stable_sort() version should be used.
Because these algorithms require random access iterators, they can be used only with vectors, deques, and ordinary C pointers. Note, however, that the list container provides its own sort() member function.
The comparison operator can be explicitly provided when the default operator < is not appropriate. This is used in the example program to sort a list into descending, rather than ascending order. An alternative technique for sorting an entire collection in the inverse direction is to describe the sequence using reverse iterators.
NOTE: Another sorting algorithm is provided by the heap operations described in Section 14.8.
The following example program illustrates the sort() algorithm being applied to a vector, and the sort() algorithm with an explicit comparison operator being used with a deque.
void sort_example ()
// illustrates the use of the sort algorithm
// see alg7.cpp for complete source code
{
// fill both a vector and a deque
// with random integers
vector<int> aVec(15);
deque<int> aDec(15);
generate (aVec.begin(), aVec.end(), randomValue);
generate (aDec.begin(), aDec.end(), randomValue);
// sort the vector ascending
sort (aVec.begin(), aVec.end());
// sort the deque descending
sort (aDec.begin(), aDec.end(), greater<int>() );
// alternative way to sort descending
sort (aVec.rbegin(), aVec.rend());
}