[alg.sorting.general] (original) (raw)

26 Algorithms library [algorithms]

26.8 Sorting and related operations [alg.sorting]

26.8.1 General [alg.sorting.general]

The operations in [alg.sorting] defined directly in namespace stdhave two versions: one that takes a function object of type Compare and one that uses an operator<.

The return value of the function call operation applied to an object of type Compare, when converted to bool, yields trueif the first argument of the call is less than the second, andfalse otherwise.

Compare comp is used throughout for algorithms assuming an ordering relation.

For all algorithms that take Compare, there is a version that uses operator< instead.

That is, comp(*i, *j) != false defaults to *i < *j != false.

For algorithms other than those described in [alg.binary.search],comp shall induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering.

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equivboth be transitive relations:

• comp(a, b) && comp(b, c) implies comp(a, c)
• equiv(a, b) && equiv(b, c) implies equiv(a, c)

[Note 1:

Under these conditions, it can be shown that

• equiv is an equivalence relation,
• comp induces a well-defined relation on the equivalence classes determined by equiv, and
• the induced relation is a strict total ordering.

— _end note_]

A sequence is sorted with respect to a comp and projfor a comparator and projection comp and projif for every iterator i pointing to the sequence and every non-negative integer nsuch that i + n is a valid iterator pointing to an element of the sequence,bool(invoke(comp, invoke(proj, *(i + n)), invoke(proj, *i))) is false.

A sequence is sorted with respect to a comparator compfor a comparator compif it is sorted with respect tocomp and identity{} (the identity projection).

A sequence [start, finish) ispartitioned with respect to an expression f(e)if there exists an integer nsuch that for all 0 <= i < (finish - start),f(*(start + i)) is true if and only if i < n.

In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability.

The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering.

That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a).