The sorting and partitioning algorithms provide various strategies for ordering the elements of a sequence.
Each of the sorting and partitioning algorithms provides stable and unstable versions (§ 10.3.1, p. 387). A stable algorithm maintains the relative order of equal elements. The stable algorithms do more work and so may run more slowly and use more memory than the unstable counterparts.
A partition
divides elements in the input range into two groups. The first group consists of those elements that satisfy the specified predicate; the second, those that do not. For example, we can partition elements in a sequence based on whether the elements are odd, or on whether a word begins with a capital letter, and so forth. These algorithms require bidirectional iterators.
is_partitioned(beg, end, unaryPred)
Returns true
if all the elements for which unaryPred
succeeds precede those for which unaryPred
is false
. Alsoreturns true
if the sequence is empty.
partition_copy(beg, end, dest1, dest2, unaryPred)
Copies elements for which unaryPred
succeeds to dest1
and copies those for which unaryPred
fails to dest2
. Returns a pair
(§ 11.2.3, p. 426) of iterators. The first
member denotes the end of the elements copied to dest1
, and the second
denotes the end of the elements copied to dest2
. The input sequence may not overlap either of the destination sequences.
partition_point(beg, end, unaryPred)
The input sequence must be partitioned by unaryPred
. Returns an iterator one past the subrange for which unaryPred
succeeds. If the returned iterator is not end
, then unaryPred
must be false
for the returned iterator and for all elements that follow that point.
stable_partition(beg, end, unaryPred)
partition(beg, end, unaryPred)
Uses unaryPred
to partition the input sequence. Elements for which unaryPred
succeeds are put at the beginning of the sequence; those for which the predicate is false
are at the end. Returns an iterator just past the last element for which unaryPred
succeeds, or beg
if there are no such elements.
These algorithms require random-access iterators. Each of the sorting algorithms provides two overloaded versions. One version uses the element’s operator <
to compare elements; the other takes an extra parameter that specifies an ordering relation (§ 11.2.2, p. 425). partial_sort_copy
returns an iterator into the destination; the other sorting algorithms return void
.
The partial_sort
and nth_element
algorithms do only part of the job of sorting the sequence. They are often used to solve problems that might otherwise be handled by sorting the entire sequence. Because these algorithms do less work, they typically are faster than sorting the entire input range.
sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)
Sorts the entire range.
is_sorted(beg, end)
is_sorted(beg, end, comp)
is_sorted_until(beg, end)
is_sorted_until(beg, end, comp)
is_sorted
returns a bool
indicating whether the entire input sequence is sorted. is_sorted_until
finds the longest initial sorted subsequence in the input and returns an iterator just after the last element of that subsequence.
partial_sort(beg, mid, end)
partial_sort(beg, mid, end, comp)
Sorts a number of elements equal to mid
– beg
. That is, if mid
– beg
is equal to 42, then this function puts the lowest-valued elements in sorted order in the first 42 positions in the sequence. After partial_sort
completes, the elements in the range from beg
up to but not including mid
are sorted. No element in the sorted range is larger than any element in the range after mid
. The order among the unsorted elements is unspecified.
partial_sort_copy(beg, end, destBeg, destEnd)
partial_sort_copy(beg, end, destBeg, destEnd, comp)
Sorts elements from the input range and puts as much of the sorted sequence as fits into the sequence denoted by the iterators destBeg
and destEnd
. If the destination range is the same size or has more elements than the input range, then the entire input range is sorted and stored starting at destBeg
. If the destination size is smaller, then only as many sorted elements as will fit are copied.
Returns an iterator into the destination that refers just past the last element that was sorted. The returned iterator will be destEnd
if that destination sequence is smaller than or equal in size to the input range.
nth_element(beg, nth, end)
nth_element(beg, nth, end, comp)
The argument nth
must be an iterator positioned on an element in the input sequence. After nth_element
, the element denoted by that iterator has the value that would be there if the entire sequence were sorted. The elements in the sequence are partitioned around nth
: Those before nth
are all smaller than or equal to the value denoted by nth
, and the ones after it are greater than or equal to it.