Node:Algorithms, Next:Adaptors, Previous:Stream iterators, Up:Top
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 user defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms.
Both in-place and copying versions are provided for certain
algorithms. 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
since the cost of sorting is much more
significant, and users might as well do copy followed by sort.
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 class is used whenever an algorithm expects a function
object that when applied to the result of dereferencing the corresponding
iterator returns a value convertible to bool. 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 if
(pred(*first)){...}.
The function object pred is assumed not to apply
any non-constant function through the dereferenced iterator.
The BinaryPredicate class 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 convertible to bool.
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 if
(binary_pred(*first,*first2)){...}.
BinaryPredicate always takes the first iterator type as
its first argument, that is, in those cases when T value is part of
the signature, it should work correctly in the context of if
(binary_pred(*first, value)){...}.
It is expected that binary_pred will
not apply any non-constant function through the dereferenced iterators.
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 a-b is the same as that of
{ Distance n; distance(a, b, n); return n; }.