26 Algorithms library [algorithms]

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

Compare is a function object type ([function.objects]) that meets the requirements for a template parameter named BinaryPredicate ([algorithms.requirements]).

The return value of the function call operation applied to an object of type Compare, when converted to bool, yields true if the first argument of the call is less than the second, and false 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 equiv both be transitive relations:

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

A sequence is sorted with respect to a comp and proj for a comparator and projection comp and proj if for every iterator i pointing to the sequence and every non-negative integer n such 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 comp for a comparator comp if it is sorted with respect to comp and identity{} (the identity projection).

A sequence [start, finish) is partitioned with respect to an expression f(e) if there exists an integer n such 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).