stable_sort

Prototype

template<class RandomAccessRange>
RandomAccessRange& stable_sort(RandomAccessRange& rng);

template<class RandomAccessRange>
const RandomAccessRange& stable_sort(const RandomAccessRange& rng);

template<class RandomAccessRange, class BinaryPredicate>
RandomAccessRange& stable_sort(RandomAccessRange& rng, BinaryPredicate pred);

template<class RandomAccessRange, class BinaryPredicate>
const RandomAccessRange& stable_sort(const RandomAccessRange& rng, BinaryPredicate pred);

Description

stable_sort sorts the elements in rng into ascending order. stable_sort is guaranteed to be stable. The order is preserved for equivalent elements.

For versions of the stable_sort function without a predicate ascending order is defined by operator<() such that for all adjacent elements [x,y], y < x == false.

For versions of the stable_sort function with a predicate, ascending order is designed by pred such that for all adjacent elements [x,y], pred(y,x) == false.

Definition

Defined in the header file boost/range/algorithm/stable_sort.hpp

Requirements

For versions of stable_sort without a predicate

RandomAccessRange is a model of the Random Access Range Concept.
RandomAccessRange is mutable.
RandomAccessRange's value type is a model of the LessThanComparableConcept.
The ordering relation on RandomAccessRange's value type is a strict weak ordering, as defined in the LessThanComparableConcept requirements.

For versions of stable_sort with a predicate:

RandomAccessRange is a model of the Random Access Range Concept.
RandomAccessRange is mutable.
BinaryPredicate is a model of the StrictWeakOrderingConcept.
RandomAccessRange's value type is convertible to both of BinaryPredicate's argument types.

Complexity

Best case: O(N) where N is distance(rng). Worst case: O(N log(N)^2) comparisons, where N is distance(rng).

Boost C++ Libraries