25 Algorithms library [algorithms]

25.2 Algorithms requirements [algorithms.requirements]

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 are not found by argument-dependent name lookup ([basic.lookup.argdep]).
When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
[Example
:
void foo() {
  using namespace std::ranges;
  std::vector<int> vec{1,2,3};
  find(begin(vec), end(vec), 2); // #1
}
The function call expression at #1 invokes std::ranges::find, not std::find, despite that (a) the iterator type returned from begin(vec) and end(vec) may be associated with namespace std and (b) std::find is more specialized ([temp.func.order]) than std::ranges::find since the former requires its first two parameters to have the same type.
end example
]
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.
  • If an algorithm's template parameter is named InputIterator, InputIterator1, or InputIterator2, the template argument shall satisfy the Cpp17InputIterator requirements ([input.iterators]).
  • If an algorithm's template parameter is named OutputIterator, OutputIterator1, or OutputIterator2, the template argument shall satisfy the Cpp17OutputIterator requirements ([output.iterators]).
  • If an algorithm's template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall satisfy the Cpp17ForwardIterator requirements ([forward.iterators]).
  • If an algorithm's template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall satisfy the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]).
  • If an algorithm's template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall satisfy the Cpp17RandomAccessIterator requirements ([random.access.iterators]).
If an algorithm's Effects: element specifies that a value pointed to by any iterator passed as an argument is modified, then that algorithm has an additional type requirement: The type of that argument shall satisfy the requirements of a mutable iterator ([iterator.requirements]).
[Note
:
This requirement does not affect arguments that are named OutputIterator, OutputIterator1, or OutputIterator2, because output iterators must always be mutable, nor does it affect arguments that are constrained, for which mutability requirements are expressed explicitly.
end note
]
Both in-place and copying versions are provided for certain algorithms.234
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.
In other words, if an algorithm takes Predicate pred as its argument and first as its iterator argument with value type T, it should work correctly in the construct pred(*first) contextually converted to bool ([conv]).
The function object pred shall not apply any non-constant function through the dereferenced iterator.
Given a glvalue u of type (possibly const) T that 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 T when T is part of the signature returns a value testable as true.
In other words, if an algorithm takes BinaryPredicate binary_­pred as its argument and first1 and first2 as its iterator arguments with respective value types T1 and T2, it should work correctly in the construct binary_­pred(*first1, *first2) contextually converted to bool ([conv]).
Unless otherwise specified, BinaryPredicate always takes the first iterator's value_­type as its first argument, that is, in those cases when T value is part of the signature, it should work correctly in the construct binary_­pred(*first1, value) contextually converted to bool ([conv]).
binary_­pred shall not apply any non-constant function through the dereferenced iterators.
Given a glvalue u of type (possibly const) T1 that designates the same object as *first1, and a glvalue v of type (possibly const) T2 that designates the same object as *first2, binary_­pred(u, *first2), binary_­pred(*first1, v), and binary_­pred(u, v) shall each be a valid expression that is equal to binary_­pred(*first1, *first2), and binary_­pred(u, value) shall be a valid expression that is equal to binary_­pred(*first1, value).
The parameters UnaryOperation, BinaryOperation, BinaryOperation1, and BinaryOperation2 are used whenever an algorithm expects a function object ([function.objects]).
[Note
:
Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely.
Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_­wrapper<T> ([refwrap]), or some equivalent solution.
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 of
auto 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 of
iter_difference_t<remove_reference_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 of
iter_difference_t<remove_reference_t<decltype(b)>> n = 0;
for (auto tmp = b; tmp != a; ++tmp) --n;
return 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 using ranges::next(i, s).
Overloads of algorithms that take Range arguments ([range.range]) behave as if they are implemented by calling ranges::begin and ranges::end on the Range(s) and dispatching to the overload in namespace ranges that takes separate iterator and sentinel arguments.
The number and order of deducible template parameters for algorithm declarations are unspecified, except where explicitly stated otherwise.
[Note
:
Consequently, the algorithms may not be called with explicitly-specified template argument lists.
end note
]
The class templates binary_­transform_­result, for_­each_­result, minmax_­result, mismatch_­result, copy_­result, and partition_­copy_­result have the template parameters, data members, and special members specified below.
They have no base classes or members other than those specified.
The decision whether to include a copying version was usually based on complexity considerations.
When the cost of doing the operation dominates the cost of copy, the copying version is not included.
For example, sort_­copy is not included because the cost of sorting is much more significant, and users might as well do copy followed by sort.