Standard Template Library Programmer's Guide

Stable_partition is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is at most N*log(N) swaps, where N is last – first , and best case (if a large enough auxiliary memory buffer is available) is linear in N . In either case, pred is applied exactly N times.

Reorder a sequence so that even numbers precede odd numbers.

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

const int N = sizeof(A)/sizeof(int);

stable_partition(A, A + N, compose1(bind2nd(equal_to(), 0), bind2nd(modulus(), 2)));

copy(A, A + N, ostream_iterator(cout, " "));

// The output is "2 4 6 8 10 1 3 5 7 9". [1]

[1] Note that the complexity of stable_partition is greater than that of partition : the guarantee that relative order will be preserved has a significant runtime cost. If this guarantee isn't important to you, you should use partition .

partition , Predicate, function object

Category: algorithms

Component type: function

Sort is an overloaded name; there are actually two sort functions.

template

void sort(RandomAccessIterator first, RandomAccessIterator last);

template

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

Sort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j , then *j is not less than *i . Note: sort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by sort . [1]

The two versions of sort differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version, the one that takes two arguments:

• RandomAccessIterator is a model of Random Access Iterator.

• RandomAccessIterator is mutable.

• RandomAccessIterator 's value type is LessThan Comparable.

• The ordering relation on RandomAccessIterator 's value type is a strict weak ordering , as defined in the LessThan Comparable requirements.

For the second version, the one that takes three arguments:

• RandomAccessIterator is a model of Random Access Iterator.

• RandomAccessIterator is mutable.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• RandomAccessIterator 's value type is convertible to StrictWeakOrdering 's argument type.

• [first, last) is a valid range.

O(N log(N)) comparisons (both average and worst-case), where N is last – first . [2]

int A[] = {1, 4, 2, 8, 5, 7};

const int N = sizeof(A) / sizeof(int);

sort(A, A + N);

copy(A, A + N, ostream_iterator(cout, " "));

// The output is " 1 2 4 5 7 8".

[1] Stable sorting is sometimes important if you are sorting records that have multiple fields: you might, for example, want to sort a list of people by first name and then by last name. The algorithm stable_sort does guarantee to preserve the relative ordering of equivalent elements.

[2] Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching . Addison-Wesley, 1975.) The current implementation of sort , however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)) . Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.

stable_sort , partial_sort , partial_sort_copy , sort_heap , is_sorted , binary_search , lower_bound , upper_bound , less , StrictWeakOrdering, LessThan Comparable

Category: algorithms

Component type: function

Stable_sort is an overloaded name; there are actually two stable_sort functions.

template

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template

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

Stable_sort is much like sort : it sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j , then *j is not less than *i . Stable_sort differs from sort in two ways. First, stable_sort uses an algorithm that has different run-time complexity than sort . Second, as the name suggests, stable_sort is stable: it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [first, last) such that x precedes y , and if the two elements are equivalent (neither x < y nor y < x ) then a postcondition of stable_sort is that x still precedes y . [1]

The two versions of stable_sort differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.