[algorithms.requirements] (original) (raw)

26 Algorithms library [algorithms]

All of the algorithms are separated from the particular implementations of data structures and are parameterized by iterator types.

Because of this, they can work with program-defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms.

The entities defined in the std​::​ranges namespace in this Clause and specified as function templates are algorithm function objects ([alg.func.obj]).

For purposes of determining the existence of data races, algorithms shall not modify objects referenced through an iterator argument unless the specification requires such modification.

Throughout this Clause, where the template parameters are not constrained, the names of template parameters are used to express type requirements.

[Note 1:

These requirements do not affect iterator arguments that are constrained, for which iterator category and mutability requirements are expressed explicitly.

— _end note_]

Both in-place and copying versions are provided for certain algorithms.201

When such a version is provided for algorithm it is called_algorithm_copy_.

Algorithms that take predicates end with the suffix _if(which follows the suffix _copy).

When not otherwise constrained, the Predicate parameter is used whenever an algorithm expects a function object ([function.objects]) that, when applied to the result of dereferencing the corresponding iterator, returns a value testable as true.

If an algorithm takes Predicate pred as its argument andfirst as its iterator argument with value type T, the expression pred(*first) shall be well-formed and the type decltype(pred(*first)) shall modelboolean-testable ([concept.booleantestable]).

The function object pred shall not apply any non-constant function through its argument.

Given a glvalue u of type (possibly const) Tthat designates the same object as *first,pred(u) shall be a valid expression that is equal to pred(*first).

When not otherwise constrained, the BinaryPredicate parameter is used whenever an algorithm expects a function object that, when applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type Twhen T is part of the signature, returns a value testable as true.

If an algorithm takes BinaryPredicate binary_pred as its argument andfirst1 and first2 as its iterator arguments with respective value types T1 and T2, the expression binary_pred(*first1, *first2) shall be well-formed and the type decltype(binary_pred(*first1, *first2)) shall modelboolean-testable.

Unless otherwise specified,BinaryPredicate always takes the first iterator's value_typeas its first argument, that is, in those cases when T valueis part of the signature, the expression binary_pred(*first1, value) shall be well-formed and the type decltype(binary_pred(*first1, value)) shall modelboolean-testable.

binary_pred shall not apply any non-constant function through any of its arguments.

Given a glvalue u of type (possibly const) T1that designates the same object as *first1, and a glvalue v of type (possibly const) T2that designates the same object as *first2,binary_pred(u, *first2),binary_pred(*first1, v), andbinary_pred(u, v)shall each be a valid expression that is equal tobinary_pred(*first1, *first2), andbinary_pred(u, value)shall be a valid expression that is equal tobinary_pred(*first1, value).

The parametersUnaryOperation,BinaryOperation,BinaryOperation1, and BinaryOperation2are used whenever an algorithm expects a function object ([function.objects]).

[Note 2:

Unless otherwise specified, algorithms that take function objects as arguments can copy those function objects freely.

If object identity is important, a wrapper class that points to a non-copied implementation object such as reference_wrapper<T> ([refwrap]), or some equivalent solution, can be used.

— _end note_]

When the description of an algorithm gives an expression such as*first == value for a condition, the expression shall evaluate to either true or false in boolean contexts.

In the description of the algorithms, operator +is used for some of the iterator categories for which it does not have to be defined.

In these cases the semantics of a + n are the same as those ofauto tmp = a;for (; n < 0; ++n) --tmp;for (; n > 0; --n) ++tmp;return tmp;

Similarly, operator - is used for some combinations of iterators and sentinel types for which it does not have to be defined.

If [a, b) denotes a range, the semantics of b - a in these cases are the same as those ofiter_difference_t<decltype(a)> n = 0;for (auto tmp = a; tmp != b; ++tmp) ++n;return n;and if [b, a) denotes a range, the same as those ofiter_difference_t<decltype(b)> n = 0;for (auto tmp = b; tmp != a; ++tmp) --n;return n;

In the description of the algorithms, given an iterator a whose difference type is D, and an expression n of integer-like type other than cv D, the semantics of a + n and a - n are, respectively, those of a + D(n) and a - D(n).

In the description of algorithm return values, a sentinel value s denoting the end of a range [i, s) is sometimes returned where an iterator is expected.

In these cases, the semantics are as if the sentinel is converted into an iterator usingranges​::​next(i, s).

Overloads of algorithms that take range arguments ([range.range]) behave as if they are implemented by calling ranges​::​begin andranges​::​end on the range(s) and dispatching to the overload in namespace rangesthat takes separate iterator and sentinel arguments.

The well-formedness and behavior of a call to an algorithm with an explicitly-specified template argument list is unspecified, except where explicitly stated otherwise.

[Note 3:

Consequently, an implementation can declare an algorithm with different template parameters than those presented.

— _end note_]