# 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 **result every time it's evaluated, and it must yield the same result if a copy of either operand is substituted for the operand.**

`bool`

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*,

*) is a sequence ordered by operator*

`Last`

**if, for each**

`<`

*N*in the range [0,

*-*

`Last`

*) and for each*

`First`

*M*in the range (

*N*,

*-*

`Last`

*) the predicate !(*(*

`First`

*+*

`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 **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.**

`bool`

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* -

*) the predicate !(**

`First`

*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 **result every time it's evaluated, and it must yield the same result if a copy of either operand is substituted for the operand.**

`bool`

The C++ Standard Library algorithms are located in the `<algorithm>`

and `<numeric>`

header files.

## See also

C++ Standard Library Reference

Thread Safety in the C++ Standard Library

## Feedback

https://aka.ms/ContentUserFeedback.

Coming soon: Throughout 2024 we will be phasing out GitHub Issues as the feedback mechanism for content and replacing it with a new feedback system. For more information see:Submit and view feedback for