28 Algorithms library [algorithms]

28.3 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.

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, the names of template parameters are used to express type requirements.

(3.1)
If an algorithm's template parameter is named InputIterator, InputIterator1, or InputIterator2, the template argument shall satisfy the requirements of an input iterator ([input.iterators]).
(3.2)
If an algorithm's template parameter is named OutputIterator, OutputIterator1, or OutputIterator2, the template argument shall satisfy the requirements of an output iterator ([output.iterators]).
(3.3)
If an algorithm's template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall satisfy the requirements of a forward iterator ([forward.iterators]).
(3.4)
If an algorithm's template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall satisfy the requirements of a bidirectional iterator ([bidirectional.iterators]).
(3.5)
If an algorithm's template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall satisfy the requirements of a random-access iterator ([random.access.iterators]).

If an algorithm's Effects: section says 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.

— end note

]

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

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).

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, it should work correctly in the construct pred(*first) contextually converted to bool (Clause [conv]).

The function object pred shall not apply any non-constant function through the dereferenced iterator.

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, it should work correctly in the construct binary_pred(*first1, *first2) contextually converted to bool (Clause [conv]).

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 (Clause [conv]).

binary_pred shall not apply any non-constant function through the dereferenced iterators.

[ 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 operators + and - are used for some of the iterator categories for which they do not have to be defined.

In these cases the semantics of a+n is the same as that of

X tmp = a;
advance(tmp, n);
return tmp;

and that of b-a is the same as of

return distance(a, b);

262)

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.