# Algorithms

Algorithms are a fundamental part of the C++ Standard Library. Algorithms don't work with containers themselves but rather with iterators. Therefore, the same algorithm can be used by most if not all of the C++ Standard Library containers. This section discusses the conventions and terminology of the C++ Standard Library algorithms.

## Remarks

The descriptions of the algorithm function templates 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), you can 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 isn't 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" 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 doesn't 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 that performs a pairwise comparison, such as with `operator==`, to yield a `bool` result. The predicate function `operator==`, or any replacement for it, must not alter either of its operands. It must yield the same `bool` result every time it's evaluated, and it must yield the same result if a copy of either operand is substituted for the operand.

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

• Strict means that pred(X, X) is false.

• Weak means that X and Y have an equivalent ordering if !pred(X, Y) && !pred(Y, X) (X == Y doesn't need to be defined).

• Ordering means that pred(X, Y) && pred(Y, Z) implies pred(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 don't 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. It must yield the same `bool` result every time it's evaluated, and it must yield the same result if a copy of either operand is substituted for the operand. 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. It must yield the same `bool` result every time it's evaluated, and it must yield the same result if a copy of either operand is substituted for the operand.

The C++ Standard Library algorithms are located in the `<algorithm>` and `<numeric>` header files.