Algorithm Conventions

The descriptions of the algorithm template functions employ several shorthand phrases:

• The phrase ``in the range [A, B)'' means the sequence of zero or more discrete values beginning with A up to but not including B. A range is valid only if B is reachable from A — you can store A in an object N (N = A), increment the object zero or more times (++N), and have the object compare equal to B after a finite number of increments (N == B).
• The phrase ``each N in the range [A, B)'' means that N begins with the value A and is incremented zero or more times until it equals the value B. The case N == B is not in the range.
• The phrase ``the lowest value of N in the range [A, B) such that X'' means that the condition X is determined for each N in the range [A, B) until the condition X is met.
• The phrase ``the highest value of N in the range [A, B) such that X'' usually means that X is determined for each N in the range [A, B). The function stores in K a copy of N each time the condition X is met. If any such store occurs, the function replaces the final value of N (which equals B) with the value of K. For a bidirectional or random-access iterator, however, it can also mean that N begins with the highest value in the range and is decremented over the range until the condition X is met.
• Expressions such as X - Y, where X and Y can be iterators other than random-access iterators, are intended in the mathematical sense. The function does not necessarily evaluate operator- if it must determine such a value. The same is also true for expressions such as X + N and X - N, where N is an integer type.

Several algorithms make use of a predicate, using operator==, that must impose an equivalence relationship on pairs of elements from a sequence. For all elements X, Y, and Z:

• X == X is true.
• If X == Y is true, then Y == X is true.
• If X == Y && Y == Z is true, then X == Z is true.

Several algorithms make use of a predicate that must impose a strict weak ordering on pairs of elements from a sequence. For the predicate pr(X, Y):

• ``strict'' means that pr(X, X) is false
• ``weak'' means that X and Y have an equivalent ordering if !pr(X, Y) && !pr(Y, X) (X == Y need not be defined)
• ``ordering'' means that pr(X, Y) && pr(Y, Z) implies pr(X, Z)

Some of these algorithms implicitly use the predicate X < Y. Other predicates that typically satisfy the ``strict weak ordering'' requirement are X > Y, less(X, Y), and greater(X, Y). Note, however, that predicates such as X <= Y and X >= Y do not satisfy this requirement.

A sequence of elements designated by iterators in the range [first, last) is ``a sequence ordered by operator<'' if, for each N in the range [0, last - first) and for each M in the range (N, last - first) the predicate !(*(first + M) < *(first + N)) is true. (Note that the elements are sorted in ascending order.) The predicate function operator<, or any replacement for it, must not alter either of its operands. Moreover, it must impose a strict weak ordering on the operands it compares.

A sequence of elements designated by iterators in the range [first, last) is ``a heap ordered by operator<'' if, for each N in the range [1, last - first) the predicate !(*first < *(first + N)) is true. (The first element is the largest.) Its internal structure is otherwise known only to the template functions make_heap, pop_heap, and push_heap. As with an ordered sequence, the predicate function operator<, or any replacement for it, must not alter either of its operands, and it must impose a strict weak ordering on the operands it compares.