Sorting and Related Operations
Table G.15 summarizes the sorting and related operations. Arguments are not shown, and overloaded functions are listed just once. Each function has a version that uses < for ordering elements and a version that uses a comparison function object for ordering elements. A fuller description, including the prototypes, follows the table. Thus, you can scan the table to get an idea of what a function does and then look up the details if you find the function appealing.
Table G.15. Sorting and Related Operations
The functions in this section determine the order of two elements by using the < operator defined for the elements or by using a comparison object designated by the template type Compare. If comp is an object of type Compare, then comp(a,b) is a generalization of a < b and returns true if a precedes b in the ordering scheme. If a < b is false and b < a is also false, a and b are equivalent. A comparison object must provide at least strict weak ordering. This means the following:
• The expression comp(a,a) must be false, a generalization of the fact that a value can’t be less than itself. (This is the strict part.)
• If comp(a,b) is true and comp(b,c) is true, then comp(a,c) is true (that is, comparison is a transitive relationship).
• If a is equivalent to b and b is equivalent to c, then a is equivalent to c (that is, equivalency is a transitive relationship).
If you think of applying < to integers, then equivalency implies equality, but this doesn’t have to hold for more general cases. For example, you could define a structure with several members describing a mailing address and define a comp comparison object that orders the structures according to zip code. Then any two addresses with the same zip code would be equivalent but not equal.
Now let’s take a more detailed look at these sorting and related operations. For each function, the discussion shows the prototype(s), followed by a brief explanation. This section is divided into several subsections. As you saw earlier, pairs of iterators indicate ranges, with the chosen template parameter name indicating the type of iterator. As usual, a range in the form [first, last) goes from first up to, but not including, last. Functions passed as arguments are function objects, which can be pointers or objects for which the () operation is defined. As you learned in Chapter 16, a predicate is a Boolean function with one argument, and a binary predicate is a Boolean function with two arguments. (The functions need not be type bool, as long as they return 0 for false and a nonzero value for true.) Also as in Chapter 16, a unary function object is one that takes a single argument, and a binary function object is one that takes two arguments.
Sorting
First, let’s examine the sorting algorithms.
sort()
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The sort() function sorts the range [first, last) in increasing order, using the value type < operator for comparison. The first version uses <, and the second version uses the comparison object comp to determine the order.
stable_sort()
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The stable_sort() function sorts the range [first, last), preserving the relative order of equivalent elements. The first version uses <, and the second version uses the comparison object comp to determine the order.
partial_sort()
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);
The partial_sort() function partially sorts the range [first, last). The first middle - first elements of the sorted range are placed in the range [first, middle), and the remaining elements are unsorted. The first version uses <, and the second version uses the comparison object comp to determine the order.
partial_sort_copy()
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
The partial_sort_copy() function copies the first n elements of the sorted range [first, last) to the range [result_first, result_first + n). The value of n is the lesser of last - first and result_last - result_first. The function returns result_first + n. The first version uses <, and the second version uses the comparison object comp to determine the order.
is_sorted() (C++11)
template<class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
bool is_sorted(ForwardIterator first, ForwardIterator last
Compare comp);
The is_sorted() function returns true if the range [first, last) is sorted and false otherwise. The first version uses <, and the second version uses the comparison object comp to determine the order.
is_sorted_until() (C++11)
template<class ForwardIterator>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last
Compare comp);
The is_sorted_until() function returns last if the range [first, last) has fewer than two elements. Otherwise, it returns the last iterator, it, for which the range [first, it) is sorted. The first version uses <, and the second version uses the comparison object comp to determine the order.
nth_element()
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);
The nth_element() function finds the element in the range [first, last) that would be at position nth were the range sorted, and it places that element at position nth. The first version uses <, and the second version uses the comparison object comp to determine the order.
Binary Searching
The algorithms in the binary searching group assume that the range is sorted. They only require a forward iterator but are most efficient for random-access iterators.
lower_bound()
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The lower_bound() function finds the first position the a sorted range [first, last) in front of which value can be inserted without violating the order. It returns an iterator that points to this position. The first version uses <, and the second version uses the comparison object comp to determine the order.
upper_bound()
template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The upper_bound() function finds the last position in the sorted range [first, last) in front of which value can be inserted without violating the order. It returns an iterator that points to this position. The first version uses <, and the second version uses the comparison object comp to determine the order.
equal_range()
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value,
Compare comp);
The equal_range() function finds the largest subrange [it1, it2) in the sorted range [first, last) such that value can be inserted in front of any iterator in this range without violating the order. The function returns a pair formed of it1 and it2. The first version uses <, and the second version uses the comparison object comp to determine the order.
binary_search()
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
The binary_search() function returns true if the equivalent of value is found in the sorted range [first, last); it returns false otherwise. The first version uses <, and the second version uses the comparison object comp to determine the order.
Recall that if < is used for ordering, the values a and b are equivalent if both a < b and b < a are false. For ordinary numbers, equivalency implies equality, but this is not the case for structures sorted on the basis of just one member. Thus, there may be more than one location where a new value can be inserted and still keep the data ordered. Similarly, if the comparison object comp is used for ordering, equivalency means both comp(a,b) and comp(b,a) are false. (This is a generalization of the statement that a and b are equivalent if a is not less than b and b is not less than a.)
Merging
The merging functions assume that ranges are sorted.
merge()
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator,
class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The merge() function merges elements from the sorted range [first1, last1) and from the sorted range [first2, last2), placing the result in a range starting at result. The target range should not overlap either of the merged ranges. When equivalent elements are found in both ranges, elements from the first range precede elements of the second. The return value is the past-the-end iterator for the resulting merge. The first version uses <, and the second version uses the comparison object comp to determine the order.
inplace_merge()
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last,
Compare comp);
The inplace_merge() function merges two consecutive sorted ranges—[first, middle) and [middle, last)—into a single sorted sequence stored in the range [first, last). Elements from the first range precede equivalent elements from the second range. The first version uses <, and the second version uses the comparison object comp to determine the order.
Working with Sets
Set operations work with all sorted sequences, including set and multiset. For containers that hold more than one instance of a value, such as multiset, definitions are generalized. A union of two multisets contains the larger number of occurrences of each element, and an intersection contains the lesser number of occurrences of each element. For example, suppose Multiset A contains the string "apple" seven times and Multiset B contains the same string four times. Then the union of A and B will contain seven instances of "apple", and the intersection will contain four instances.
includes()
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);
The includes() function returns true if every element in the range [first2, last2) is also found in the range [first1, last1); it returns false otherwise. The first version uses <, and the second version uses the comparison object comp to determine the order.
set_union()
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_union() function constructs the set that is the union of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The union is the set that contains all elements found in either or both sets. The first version uses <, and the second version uses the comparison object comp to determine the order.
set_intersection()
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1,
InputIterator1 last1,InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result,
Compare comp);
The set_intersection() function constructs the set that is the intersection of the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The intersection is the set that contains the elements that are common to both sets. The first version uses <, and the second version uses the comparison object comp to determine the order.
set_difference()
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_difference(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_difference(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result,
Compare comp);
The set_difference() function constructs the set that is the difference between the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The difference is the set that contains the elements found in the first set but not in the second. The first version uses <, and the second version uses the comparison object comp to determine the order.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The set_symmetric_difference() function constructs the set that is the symmetric difference between the ranges [first1, last1) and [first2, last2) and copies the result to the location pointed to by result. The resulting range should not overlap either of the original ranges. The function returns a past-the-end iterator for the constructed range. The symmetric difference is the set that contains the elements found in the first set but not in the second and the elements found in the second set but not the first. It’s the same as the difference between the union and the intersection. The first version uses <, and the second version uses the comparison object comp to determine the order.
Working with Heaps
A heap is a common data form with the property that the first element in a heap is the largest. Whenever the first element is removed or any element is added, the heap may have to be rearranged to maintain that property. A heap is designed so that these two operations are done efficiently.
make_heap()
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The make_heap() function makes a heap of the range [first, last). The first version uses < to determine the ordering, and the second version uses the comp comparison object.
push_heap()
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The push_heap() function assumes that the range [first, last - 1) is a valid heap, and it adds the value at location last - 1 (that is, one past the end of the heap that is assumed to be valid) into the heap, making [first, last) a valid heap. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
pop_heap()
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The pop_heap() function assumes that the range [first, last) is a valid heap. It swaps the value at location last - 1 with the value at first and makes the range [first, last - 1) a valid heap. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
sort_heap()
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
The sort_heap() function assumes that the range [first, last) is a heap and sorts it. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
is_heap() (C++11)
template<class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last
Compare comp);
The is_heap() function returns true if the range [first, last) is a heap and false otherwise. The first version uses <, and the second version uses the comparison object comp to determine the order.
is_heap_until() (C++11)
template<class RandomAccessIterator>
RandomAccessIterator is_heap_until(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until(
RandomAccessIterator first, RandomAccessIterator last
Compare comp);
The is_heap_until() function returns last if the range [first, last) has fewer than two elements. Otherwise, it returns the last iterator, it, for which the range [first, it) is a heap. The first version uses <, and the second version uses the comparison object comp to determine the order.
Finding Minimum and Maximum Values
The minimum and maximum functions return the minimum and maximum values of pairs of values and of sequences of values.
min()
template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
const T& min(const T& a, const T& b, Compare comp);
These versions of the min() function return the lesser of two values. If the two values are equivalent, they return the first value. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
template<class T> T min(initializer_list<T> t);
template<class T, class Compare>
T min(initializer_list<T> t), Compare comp);
These versions of min() function (C++11) return the smallest value in the initializer list t. If the two or more values are equivalent, they return a copy of the first-occurring item having that value. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
max()
template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
const T& max(const T& a, const T& b, Compare comp);
These versions of the max() function return the greater of two values. If the two values are equivalent, they return the first value. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
template<class T> T max(initializer_list<T> t);
template<class T, class Compare>
T max(initializer_list<T> t), Compare comp);
These versions of max() function (C++11) return the largest value in the initializer list t. If the two or more values are equivalent, they return a copy of the first-occurring item having that value. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
minmax() (C++11)
template<class T>
pair<const T&,const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
pair<const T&,const T&> minmax(const T& a, const T& b,
Compare comp);
These versions of the minmax() function return the pair (b,a) if b is less than a, and the pair (a,b) otherwise. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
template<class T> pair<T,T> minmax(initializer_list<T> t);
template<class T, class Compare>
pair<T,T> minmax(initializer_list<T> t), Compare comp);
These versions of minmax() function return copies of the smallest element and largest element in the initializer list t. If several elements are equivalent to the smallest, the first-occurring is returned. If several elements are equivalent to the largest, the last-occurring is returned. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
min_element()
template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
Compare comp);
The min_element() function returns the first iterator it in the range [first, last) such that no element in the range is less than *it. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
max_element()
template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
Compare comp);
The max_element() function returns the first iterator it in the range [first, last) such that there is no element that *it is less than. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
minmax_element() (C++11)
template<class ForwardIterator>
pair<ForwardIterator,ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
pair<ForwardIterator,ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last,
Compare comp);
The max_element() function returns a pair object containing the first iterator, it1, in the range [first, last), such that there is no element that *it1 is less than, and the last iterator, it2, in the range [first, last), such that there is no element that *it2 is less than. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
lexicographical_compare()
template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
The lexicographical_compare() function returns true if the sequence of elements in the range [first1, last1) is lexicographically less than the sequence of elements in the range [first2, last2); it returns false otherwise. A lexicographic comparison compares the first element of one sequence to the first of the second—that is, it compares *first1 to *first2. If *first1 is less than *first2, the function returns true. If *first2 is less than *first1, the function returns false. If the two are equivalent, comparison proceeds to the next element in each sequence. This process continues until two corresponding elements are not equivalent or until the end of a sequence is reached. If two sequences are equivalent until the end of one is reached, the shorter sequence is less. If the two sequences are equivalent and of the same length, neither is less, so the function returns false. The first version of the function uses < to compare elements, and the second version uses the comp comparison object. The lexicographic comparison is a generalization of an alphabetic comparison.
Working with Permutations
A permutation of a sequence is a reordering of the elements. For example, a sequence of three elements has six possible orderings because you have a choice of three elements for the first element. Choosing a particular element for the first position leaves a choice of two for the second, and one for the third. For example, the six permutations of the digits 1, 2, 3 are as follows:
123 132 213 232 312 321
In general, a sequence of n elements has n × (n-1) × ... × 1, or n! possible permutations.
The permutation functions assume that the set of all possible permutations can be arranged in lexicographic order, as in the previous example of six permutations. That means, in general, that there is a specific permutation that precedes and follows each permutation. For example, 213 immediately precedes 232, and 312 immediately follows it. However, the first permutation (123 in the example) has no predecessor, and the last permutation (321 in the example) has no follower.
next_permutation()
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
The next_permutation() function transforms the sequence in the range [first, last) to the next permutation in lexicographic order. If the next permutation exists, the function returns true. If it doesn’t exist (that is, the range contains the last permutation in lexicographic order), the function returns false and transforms the range to the first permutation in lexicographic order. The first version uses < to determine the ordering, and the second version uses the comp comparison object.
prev_permutation()
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
The previous_permutation() function transforms the sequence in the range [first, last) to the previous permutation in lexicographic order. If the previous permutation exists, the function returns true. If it doesn’t exist (that is, the range contains the first permutation in lexicographic order), the function returns false and transforms the range to the last permutation in lexicographic order. The first version uses < to determine the ordering, and the second version uses the comp comparison object.