Thinking In C++. Volume 2: Practical Programming

To demonstrate remove_if( ), the address of the standard C library function isupper( ) (in is called inside the function object class IsUpper, an object of which is passed as the predicate for remove_if( ). This returns true only if a character is uppercase, so only lowercase characters will remain. Here, the end of the range is used in the call to print( ) so only the remaining elements will appear. The copying versions of remove( ) and remove_if( ) are not shown because they are a simple variation on the noncopying versions, which you should be able to use without an example.

The range of lowercase letters is sorted in preparation for testing the "unique" functions. (The "unique" functions are not undefined if the range isn’t sorted, but it’s probably not what you want.).. First, unique_copy( ) puts the unique elements into a new vector using the default element comparison, and then the form of unique( ) that takes a predicate is used; the predicate used is the built-in function object equal_to( ), which produces the same results as the default element comparison.

Sorting and operations on sorted ranges

A significant category of STL algorithms requires that the range they operate on be in sorted order.

STL provides a number of separate sorting algorithms, depending on whether the sort should be stable, partial, or just regular (non-stable). Oddly enough, only the partial sort has a copying version; otherwise you’ll need to make your own copy before sorting if that’s what you want^.

Once your sequence is sorted, you can perform many operations on that sequence, from simply locating an element or group of elements to merging with another sorted sequence or manipulating sequences as mathematical sets.

Each algorithm involved with sorting or operations on sorted sequences has two versions. The first uses the object’s own operator< to perform the comparison, and the second uses operator( )(a, b) to determine the relative order of a and b. Other than this, there are no differences, so this distinction will not be pointed out in the description of each algorithm.

Sorting

The sort algorithms require ranges delimited by random-access iterators, such as a vector or deque. The list container has its own built-in sort( ) function, since it only supports bi-directional iteration^.

void sort(RandomAccessIterator first, RandomAccessIterator last); void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);

Sorts [first, last) into ascending order. The first form uses operator< and the second form uses the supplied comparator object to determine the order.

void stable_sort(RandomAccessIterator first, RandomAccessIterator last); void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);

Sorts [first, last) into ascending order, preserving the original ordering of equivalent elements. (This is important if elements can be equivalent but not identical.)^.

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering binary_pred);

Sorts the number of elements from [first, last) that can be placed in the range [first, middle). The rest of the elements end up in [middle, last) and have no guaranteed order^.

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering binary_pred);

Sorts the number of elements from [first, last) that can be placed in the range [result_first, result_last) and copies those elements into [result_first, result_last). If the range [first, last) is smaller than [result_first, result_last), the smaller number of elements is used^.

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering binary_pred);