```
______________________________________________________________________

25   Algorithms library                     [lib.algorithms]

______________________________________________________________________

1 This clause describes components that C++ programs may use to  perform
algorithmic  operations  on  containers  (_lib.containers_)  and other
sequences.

2 The following subclauses describe components for non-mutating sequence
operation,  mutating  sequence  operations, sorting and related opera­
tions, and algorithms from the ISO C library, as summarized  in  Table
1:

Table 1--Algorithms library summary

+-------------------------------------------------------------------------+
+-------------------------------------------------------------------------+
|_lib.alg.nonmutating_ Non-mutating sequence operations                   |
|_lib.alg.mutating.operations_ Mutating sequence operations   <algorithm> |
|_lib.alg.sorting_ Sorting and related operations                         |
+-------------------------------------------------------------------------+
|_lib.alg.c.library_ C library algorithms                     <cstdlib>   |
+-------------------------------------------------------------------------+

namespace std {
// subclause _lib.alg.nonmutating_, non-mutating sequence operations:
template<class InputIterator, class Function>
void for_each(InputIterator first, InputIterator last, Function f);
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last,
const T& value);
template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
BinaryPredicate pred);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);

template<class InputIterator>
template<class InputIterator, class BinaryPredicate>
BinaryPredicate pred);
template<class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value,
Size& n);
template<class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred,
Size& n);
template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
template<class ForwardIterator, class Size, class T>
ForwardIterator search(ForwardIterator first, ForwardIterator last,
Size count, const T& value);
template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator1 search(ForwardIterator first, ForwardIterator last,
Size count, T value,
BinaryPredicate pred);
// subclause _lib.alg.mutating.operations_, mutating sequence operations:
// _lib.alg.copy_, copy:
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);

// _lib.alg.swap_, swap:
template<class T>
void swap(T& a, T& b);
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2);
template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value);
template<class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
OutputIterator result,
Predicate pred, const T& new_value);
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
template<class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);
template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);
template<class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);
template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
template<class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result);
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred);
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result);
template<class BidirectionalIterator>
void rotate(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);
template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result);
template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand);
// _lib.alg.partitions_, partitions:
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
template<class BidirectionalIterator, class Predicate>
ForwardIterator stable_partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
// subclause _lib.alg.sorting_, sorting and related operations:
// _lib.alg.sort_, sorting:
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
// _lib.alg.binary.search_, binary search:
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
Compare comp);
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

// _lib.alg.merge_, merge:
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
// _lib.alg.set.operations_, set operations:
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
// _lib.alg.heap.operations_, heap operations:
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

// _lib.alg.min.max_, minimum and maximum:
template<class T>
T min(const T& a, const T& b);
template<class T, class Compare>
T min(const T& a, const T& b, Compare comp);
template<class T>
T max(const T& a, const T& b);
template<class T, class Compare>
T max(const T& a, const T& b, Compare comp);
template<class InputIterator>
InputIterator max_element(InputIterator first, InputIterator last);
template<class InputIterator, class Compare>
InputIterator max_element(InputIterator first, InputIterator last,
Compare comp);
template<class InputIterator>
InputIterator min_element(InputIterator first, InputIterator last);
template<class InputIterator, class Compare>
InputIterator min_element(InputIterator first, InputIterator last,
Compare comp);
template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
// _lib.alg.permutation.generators_, permutations
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp);
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp);
}

3 All  of  the  algorithms are separated from the particular implementa­
tions 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.

4 Both   in-place   and   copying  versions  are  provided  for  certain
algorithms.1) When such a version is  provided  for  algorithm  it  is
_________________________
1) The decision whether to include a copying version was usually based
on  complexity  considerations.   When the cost of doing the operation

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

5 The Predicate class is used whenever an algorithm expects  a  function
object  that  when  applied  to the result of dereferencing the corre­
sponding 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  if
(pred(*first)){...}.  The function object pred is assumed not to apply
any non-constant function through the dereferenced iterator.

6 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  Tis  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  first2as its iterator arguments, it should
work correctly  in  the  construct  if  (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  signa­
ture,  it  should  work  correctly  in the context of if (pred(*first,
value)){...}.  It is expected that binary_pred will not apply any non-
constant function through the dereferenced iterators.

7 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 is that of
{ X tmp = a;
return tmp;
}
and that of a-b is the same as of
{ Distance n;
distance(a, b, n);
return n;
}

+-------                 BEGIN BOX 1                -------+
For  the  following  algorithms: reverse, rotate, random_shuffle, sta­
ble_partition,  sort,  stable_sort  and  inplace_merge  the   iterator
requirement can be relaxed to ForwardIterator.  These algorithms could
then be dispatched upon the iterator category tags  to  use  the  most
efficient  implementation  for  each  iterator  category.  We have not
included the relaxation at this stage since it is not yet fully imple­
mented.
+-------                  END BOX 1                 -------+

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

25.1  Non-mutating sequence operations           [lib.alg.nonmutating]

25.1.1  For each                                     [lib.alg.foreach]

template<class InputIterator, class Function>
void for_each(InputIterator first, InputIterator last, Function f);

Effects:
Applies f to the result of dereferencing every iterator in the range
[first, last).
Requires:
f shall not apply any non-constant function through the dereferenced
iterator.
Complexity:
Applies f exactly last - first times.
Notes:
If f returns a result, the result is ignored.

25.1.2  Find                                            [lib.alg.find]

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last,
const T& value);

template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);

Returns:
The  first  iterator i in the range [first, last) for which the fol­
lowing corresponding conditions hold: *i == value, pred(*i) == true.
Returns last if no such iterator is found.
Complexity:
At most last - first applications of the corresponding predicate.

25.1.3  Find End                                    [lib.alg.find.end]

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);

Effects:
Finds a subsequence of equal values in a sequence.
Returns:
The  last  iterator  i in the range [first1 + (last2-first2), last1)

such that for any non-negative integer n < (last2-first2), the  fol­
lowing   corresponding   conditions   hold:  *(i-n)  ==  *(last2-n),
pred(*(i-n),*(last2-n)) == true.  Returns last1 if no such  iterator
is found.
Complexity:
At  most last1 - first1 applications of the corresponding predicate.

25.1.4  Find First                             [lib.alg.find.first.of]

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);

Effects:
Finds a subsequence of equal values in a sequence.
Returns:
The first iterator i in  the  range  [first1,  last1-(last2-first2))
such  that for any non-negative integer n < (last2-first2), the fol­
lowing   corresponding   conditions   hold:   *i   ==   *(first2+n),
pred(i,first2+n)  ==  true.   Returns  last1  if no such iterator is
found.
Complexity:
Exactly  find_first_of(first1,last1,first2+n)  applications  of  the
corresponding predicate.

template<class InputIterator>

template<class InputIterator, class BinaryPredicate>
BinaryPredicate pred);

Returns:
The  first  iterator  i  such that both i and i + 1 are in the range
[first, last) for which the following corresponding conditions hold:
*i == *(i + 1), pred(*i, *(i + 1)) == true.  Returns last if no such
iterator is found.
Complexity:
At most max((last - first) - 1, 0) applications of the corresponding
predicate.

25.1.6  Count                                          [lib.alg.count]

template<class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value,
Size& n);

template<class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred,
Size& n);

Effects:
Adds  to  n the number of iterators i in the range [first, last) for
which the following corresponding  conditions  hold:  *i  ==  value,
pred(*i) == true.
Complexity:
Exactly last - first applications of the corresponding predicate.
Notes:
count  must  store  the  result into a reference argument instead of
returning the result because the size type cannot  be  deduced  from
built-in iterator types such as int*.

25.1.7  Mismatch                                        [lib.mismatch]

template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);

template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);

Returns:
A pair of iterators i and j such that j == first2 + (i - first1) and
i is the first iterator in the range [first1, last1) for  which  the
following corresponding conditions hold:
!(*i == *(first2 + (i - first1))), pred(*i, *(first2 + (i - first1))) == false
Returns  the  pair  last1  and  first2 + (last1 - first1) if such an
Complexity:
At most last1 - first1 applications of the corresponding  predicate.

25.1.8  Equal                                          [lib.alg.equal]

template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);

template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);

Returns:
true  if  for every iterator i in the range [first1, last1) the fol­
lowing  corresponding  conditions  hold:  *i  ==  *(first2  +  (i  -
first1)),  pred(*i,  *(first2  + (i - first1))) == true.  Otherwise,
returns false.
Complexity:
At most last1 - first1 applications of the corresponding  predicate.

25.1.9  Search                                        [lib.alg.search]

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);

Effects:
Finds a subsequence of equal values in a sequence.
Returns:
The first iterator i in the range [first1, last1 - (last2 - first2))
such that for any non-negative integer n less than  last2  -  first2
the  following corresponding conditions hold: *(i + n) == *(first2 +
n), pred(*(i + n), *(first2 + n)) == true.  Returns last1 if no such
iterator is found.2)

template<class ForwardIterator, class Size, class T>
ForwardIterator
search(ForwardIterator first, ForwardIterator last,
Size count, const T& value);

template<class ForwardIterator, class Size, class T,
class BinaryPredicate>
ForwardIterator1
search(ForwardIterator first, ForwardIterator last,
Size count, T value,
BinaryPredicate pred);
_________________________
2)  The  Knuth-Morris-Pratt algorithm is not used here.  While the KMP
algorithm guarantees linear time, it tends to be slower in most  prac­
tical  cases than the naive algorithm with worst-case quadratic behav­
ior.  The worst case is extremely unlikely.  We expect that  most  im­
plementations will provide a specialization:
char* search(char* first1, char* last1,
char* first2,  char* last2);

1 that will use a variation of the Boyer-Moore algorithm for fast string
searching.

Effects:
Finds a subsequence of equal values in a sequence.
Returns:
The first iterator i in the range [first, last - count) such  that
for  any non-negative integer n less than count the following cor­
responding  conditions  hold:  *(i  +  n)  ==  value,  pred(*(i  +
n),value) == true.  Returns last if no such iterator is found.

25.2  Mutating sequence                [lib.alg.mutating.operations]
operations

25.2.1  Copy                                          [lib.alg.copy]

25.2.1.1  copy                                            [lib.copy]

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);

Effects:
Copies elements.  For  each  non-negative  integer  n  <  (last  -
first), performs *(result + n) = *(first + n).
Returns:
result + (last - first).
Requires:
result shall not be in the range [first, last).
Complexity:
Exactly last - first assignments.

25.2.1.2  copy_backward                          [lib.copy.backward]

template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);

Effects:
Copies  elements in the range [first, last) into the range [result
- (last - first), result) starting from last - 1 and proceeding to
first.  For each positive integer n <= (last  -  first),  Performs
*(result - n) = *(last - n).
Requires:
result shall not be in the range [first, last).
Returns:
result - (last - first).
Complexity:
Exactly last - first assignments.

_________________________
3)  copy_backward (_lib.copy.backward_) should be used instead of copy
when last is in the range [result - (last - first), result).

25.2.2  Swap                                          [lib.alg.swap]

25.2.2.1  swap                                            [lib.swap]

template<class T>
void swap(T& a, T& b);

Effects:
Exchanges values stored in two locations.

25.2.2.2  swap_ranges                              [lib.swap.ranges]

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2);

Effects:
For  each  non-negative  integer  n  <  (last1 - first1) performs:
swap(*(first1 + n), *(first2 + n)).
Requires:
The two ranges [first1, last1) and  [first2,  first2  +  (last1  -
first1)) shall not overlap.
Returns:
first2 + (last1 - first1).
Complexity:
Exactly last1 - first1 swaps.

25.2.3  Transform                                [lib.alg.transform]

template<class InputIterator, class OutputIterator,
class UnaryOperation>
OutputIterator
transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator
transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);

Effects:
Assigns  through  every  iterator i in the range [result, result +
(last1 - first1)) a new corresponding value equal to op(*(first1 +
(i  - result)) or binary_op(*(first1 + (i - result), *(first2 + (i
- result))).
Requires:
op and binary_op shall not have any side effects.
Returns:
result + (last1 - first1).

Complexity:
Exactly last1 - first1 applications of op or binary_op.
Notes:
result may be equal to first in case of  unary  transform,  or  to
first1 or first2 in case of binary transform.

25.2.4  Replace                                    [lib.alg.replace]

25.2.4.1  replace                                      [lib.replace]

template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);

template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);

Effects:
Substitutes  elements  referred  by  the  iterator  i in the range
[first, last) with new_value,  when  the  following  corresponding
conditions hold: *i == old_value, pred(*i) == true.
Complexity:
Exactly  last - first applications of the corresponding predicate.

25.2.4.2  replace_copy                            [lib.replace.copy]

template<class InputIterator, class OutputIterator, class T>
OutputIterator
replace_copy(InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value);

template<class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator
replace_copy_if(Iterator first, Iterator last,
OutputIterator result,
Predicate pred, const T& new_value);

Effects:
Assigns to every iterator i in the range [result, result + (last -
first))  either  new_value or *(first + (i - result)) depending on
whether the following corresponding conditions hold:
*(first + (i - result)) == old_value,
pred(*(first + (i - result))) == true
Returns:
result + (last - first).
Complexity:
Exactly last - first applications of the corresponding  predicate.

25.2.5  Fill                                          [lib.alg.fill]

template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);

template<class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);

Effects:
Assigns  value  through  all  the  iterators  in the range [first,
last)or [first, first + n).
Complexity:
Exactly last - first (or n) assignments.

25.2.6  Generate                                  [lib.alg.generate]

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);

template<class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);

Effects:
Invokes the function object gen and assigns the  return  value  of
gen though all the iterators in the range [first, last) or [first,
first + n).
Requires:
gen takes no arguments.
Complexity:
Exactly last - first (or n) invocations of gen and assignments.

25.2.7  Remove                                      [lib.alg.remove]

25.2.7.1  remove                                        [lib.remove]

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);

Effects:
Eliminates all the elements referred to by iterator i in the range
[first,  last)  for  which  the following corresponding conditions
hold: *i == value, pred(*i) == true.
Returns:
The end of the resulting range.
Notes:
Stable:  the relative order of the elements that are  not  removed
is the same as their relative order in the original range.

Complexity:
Exactly  last - first applications of the corresponding predicate.

25.2.7.2  remove_copy                              [lib.remove.copy]

template<class InputIterator, class OutputIterator, class T>
OutputIterator
remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);

template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator
remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);

Effects:
Copies all the elements referred to by the iterator i in the range
[first,  last) for which the following corresponding conditions do
not hold: *i == value, pred(*i) == true.
Returns:
The end of the resulting range.
Complexity:
Exactly last - first applications of the corresponding  predicate.
Notes:
Stable:  the relative order of the elements in the resulting range
is the same as their relative order in the original range.

25.2.8  Unique                                      [lib.alg.unique]

25.2.8.1  unique                                        [lib.unique]

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);

Effects:
Eliminates all but the first element from every consecutive  group
of  equal  elements  referred  to  by  the iterator i in the range
[first, last) for which  the  following  corresponding  conditions
hold: *i == *(i - 1) or pred(*i, *(i - 1)) == true
Returns:
The end of the resulting range.
Complexity:
Exactly (last - first) - 1 applications of the corresponding pred­
icate.

25.2.8.2  unique_copy                              [lib.unique.copy]

template<class InputIterator, class OutputIterator>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result);

template<class InputIterator, class OutputIterator,
class BinaryPredicate>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred);

Effects:
Copies only the first element  from  every  consecutive  group  of
equal  elements referred to by the iterator i in the range [first,
last) for which the following corresponding conditions hold: *i ==
*(i - 1) or pred(*i, *(i - 1)) == true
Returns:
The end of the resulting range.
Complexity:
Exactly  last - first applications of the corresponding predicate.

25.2.9  Reverse                                    [lib.alg.reverse]

25.2.9.1  reverse                                      [lib.reverse]

template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

Effects:
For each non-negative integer i <= (last - first)/2, applies  swap
to all pairs of iterators first + i, (last - i) - 1.
Complexity:
Exactly (last - first)/2 swaps.

25.2.9.2  reverse_copy                            [lib.reverse.copy]

template<class BidirectionalIterator, class OutputIterator>
OutputIterator
reverse_copy(BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result);

Effects:
Copies  the  range  [first,  last)  to the range [result, result +
(last - first)) such that for any non-negative integer i < (last -
first) the following assignment takes place:

*(result + (last - first) - i) = *(first + i)

Requires:
The  ranges  [first,  last)  and [result, result + (last - first))
shall not overlap.
Returns:
result + (last - first).

Complexity:
Exactly last - first assignments.

25.2.10  Rotate                                     [lib.alg.rotate]

25.2.10.1  rotate                                       [lib.rotate]

template<class BidirectionalIterator>
void rotate(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);

1   For each non-negative integer i < (last - first), places the element
from  the  position  first  + i into position first + (i + (middle -
first)) % (last - first).
Complexity:
At most last - first swaps.

25.2.10.2  rotate_copy                             [lib.rotate.copy]

template<class ForwardIterator, class OutputIterator>
OutputIterator
rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result);

Effects:
Copies the range [first, last) to  the  range  [result,  result  +
(last  - first)) such that for each non-negative integer i < (last
- first) the following assignment takes place:
*(first + i) =  *(result + (i + (middle - first)) % (last - first))
Returns:
result + (last - first).
Requires
The ranges [first, last) and [result, result  +  (last  -  first))
shall not overlap.
Complexity:
Exactly last - first assignments.

25.2.11  Random shuffle                     [lib.alg.random.shuffle]

template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);

template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator& rand);

Effects:
Shuffles the elements in the range [first, last) with uniform dis­
tribution.
Complexity:
Exactly (last - first) - 1 swaps.

Notes:
random_shuffle can take  a  particular  random  number  generating
function object rand such that rand returns a randomly chosen dou­
ble in the interval [0, 1).

25.2.12  Partitions                             [lib.alg.partitions]

25.2.12.1  partition                                 [lib.partition]

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);

Effects:
Places all the elements in the range [first,  last)  that  satisfy
pred before all the elements that do not satisfy it.
Returns:
An  iterator  i  such that for any iterator j in the range [first,
i), pred(*j) == true, and for any iterator  k  in  the  range  [i,
last), pred(*j) == false.
Complexity:
At most (last - first)/2 swaps.  Exactly last - first applications
of the predicate is done.

25.2.12.2  stable_partition                   [lib.stable.partition]

template<class BidirectionalIterator, class Predicate>
ForwardIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);

Effects:
Places all the elements in the range [first,  last)  that  satisfy
pred before all the elements that do not satisfy it.
Returns:
An  iterator  i  such that for any iterator j in the range [first,
i), pred(*j) == true, and for any iterator  k  in  the  range  [i,
last),  pred(*j)  == false.  The relative order of the elements in
both groups is preserved.
Complexity:
At most (last - first) * log(last - first) swaps, but only  linear
number  of  swaps if there is enough extra memory.  Exactly last -
first applications of the predicate.

25.3  Sorting and related operations               [lib.alg.sorting]

1   All the operations in this section have two versions: one that takes
a function object of type Compare and one that uses an operator<.

2   Compare is used as a function object which returns true if the first
argument is less than the second, and false otherwise.  Compare comp
is used throughout for algorithms assuming an ordering relation.  It

is assumed that  comp  will  not  apply  any  non-constant  function
through  the  dereferenced  iterator.   For all algorithms that take
Compare, there is a version that uses operator< instead.   That  is,
comp(*i,  *j)  ==  true  defaults to *i < *j == true.  For the algo­
rithms to work correctly, comp has to induce a total ordering on the
values.

3   A  sequence  is  sorted with respect to a comparator comp if for any
iterator i pointing to the sequence and any non-negative  integer  n
such  that  i  + n is a valid iterator pointing to an element of the
sequence, comp(*(i + n), *i) == false.

4   In the descriptions of the functions that deal with  ordering  rela­
tionships  we  frequently  use a notion of equality to describe con­
cepts such as stability.  The equality to which we refer is not nec­
essarily  an  operator==,  but  an  equality relation induced by the
total ordering.  That is, two element a and b are  considered  equal
if and only if !(a < b) && !(b < a).

25.3.1  Sorting                                       [lib.alg.sort]

25.3.1.1  sort                                            [lib.sort]

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Effects:
Sorts the elements in the range [first, last).
Complexity:
Approximately  NlogN  (where N == last - first) comparisons on the
average.4)

25.3.1.2  stable_sort                              [lib.stable.sort]

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);

_________________________
4)   If    the    worst    case    behavior    is    important    sta­
ble_sort(_lib.stable.sort_)   or   partial_sort   (_lib.partial.sort_)
should be used.

Effects:
Sorts the elements in the range [first, last).
Complexity:
It does at most Nlog2N (where N == last - first)  comparisons;  if
enough extra memory is available, it is NlogN.
Notes:
Stable:  the relative order of the equal elements is preserved.

25.3.1.3  partial_sort                            [lib.partial.sort]

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);

Effects:
Places  the  first  middle  - first sorted elements from the range
[first, last) into the range [first, middle).   The  rest  of  the
elements  in  the  range [middle, last) are placed in an undefined
order.
Complexity:
It takes approximately (last - first) * log(middle -  first)  com­
parisons.

25.3.1.4  partial_sort_copy                  [lib.partial.sort.copy]

template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);

Effects:
Places  the  first  min(last  - first, result_last - result_first)
sorted elements  into  the  range  [result_first,  result_first  +
min(last - first, result_last - result_first)).
Returns:
The smaller of: result_last or result_first + (last - first)
Complexity:
Approximately (last - first) * log(min(last - first, result_last -
result_first))comparisons.

25.3.2  Nth element                            [lib.alg.nth.element]

template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);

1   After nth_element the element in the position pointed to by  nth  is
the  element  that would be in that position if the whole range were
sorted.  Also for any iterator i in the range [first, nth)  and  any
iterator  j  in  the  range [nth, last) it holds that: !(*i > *j) or
comp(*i, *j) == false.
Complexity:
Linear on average.

25.3.3  Binary search                        [lib.alg.binary.search]

1   All of the algorithms in this section are versions of binary search.
They  work  on  non-random access iterators minimizing the number of
comparisons, which will be logarithmic for all types  of  iterators.
They  are  especially appropriate for random access iterators, since
these algorithms do a logarithmic number of steps through  the  data
structure.   For  non-random  access iterators they execute a linear
number of steps.

25.3.3.1  lower_bound                              [lib.lower.bound]

template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

Effects:
Finds the first position into which value can be inserted  without
violating the ordering.
Returns:
The  furthermost  iterator  i in the range [first, last) such that
for any iterator j in the range [first, i)  the  following  corre­
sponding conditions hold: *j < value or comp(*j, value) == true
Complexity:
At most log(last - first) + 1 comparisons.

25.3.3.2  upper_bound                              [lib.upper.bound]

template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

Effects:
Finds  the  furthermost  position into which value can be inserted
without violating the ordering.
Returns:
The furthermost iterator i in the range [first,  last)  such  that
for  any  iterator  j in the range [first, i) the following corre­
sponding conditions hold: !(value <  *j)  or  comp(value,  *j)  ==
false
Complexity:
At most log(last - first) + 1 comparisons.

25.3.3.3  equal_range                              [lib.equal.range]

template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last, const T& value,
Compare comp);

Effects:
Finds  the  largest  subrange  [i,  j)  such that the value can be
inserted at any iterator k in it.  k satisfies  the  corresponding
conditions:  !(*k  < value) && !(value < *k) or comp(*k, value) ==
false && comp(value, *k) == false.
Complexity:
At most 2 * log(last - first) comparisons.

25.3.3.4  binary_search                          [lib.binary.search]

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);

Returns:
true if there is an iterator i in the range [first last) that sat­
isfies  the  corresponding  conditions: !(*i < value) && !(value <
*i) or comp(*i, value) == false && comp(value, *i) == false.
Complexity:
At most log(last - first) + 1 comparisons.

25.3.4  Merge                                        [lib.alg.merge]

25.3.4.1  merge                                          [lib.merge]

template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

Effects:
Merges two sorted ranges [first1, last1) and [first2, last2)  into
the  range [result, result + (last1 - first1) + (last2 - first2)).

1   The resulting range shall not overlap with either  of  the  original
ranges.
Returns:
result + (last1 - first1) + (last2 - first2).
Complexity:
At most (last1 - first1) + (last2 - first2) - 1 comparisons.
Notes:
Stable:   for  equal elements in the two ranges, the elements from
the first range always precede the elements from the second.

25.3.4.2  inplace_merge                          [lib.inplace.merge]

template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);

Effects:
Merges two sorted consecutive ranges [first, middle) and  [middle,

last),  putting  the  result  of  the merge into the range [first,
last).
Complexity:
At most last - first comparisons.   If  no  additional  memory  is
available, the number of assignments can be equal to NlogN where N
is equal to last - first.
Notes:
Stable:  for equal elements in the two ranges, the  elements  from
the first range always precede the elements from the second.

25.3.5  Set operations on sorted            [lib.alg.set.operations]
structures

1   This section defines all the basic set operations on  sorted  struc­
tures.  They even work with multiset s containing multiple copies of
equal elements.  The semantics of the set operations is  generalized
to multisets in a standard way by defining union to contain the max­
imum number of occurrences of every element, intersection to contain
the minimum, and so on.

25.3.5.1  includes                                    [lib.includes]

template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);

template<class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);

Returns:
true if every element in the range [first2, last2) is contained in
the range [first1, last1).  Returns false otherwise.
Complexity:
At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons.

25.3.5.2  set_union                                  [lib.set.union]

template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

Effects:
Constructs a sorted union of the elements from the two ranges.
Requires:
The  resulting range shall not overlap with either of the original
ranges.
Returns:
The end of the constructed range.
Complexity:
At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons.
Notes:
Stable:  if an element is present in both ranges, the one from the
first range is copied.

25.3.5.3  set_intersection                    [lib.set.intersection]

template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

Effects:
Constructs a sorted intersection of  the  elements  from  the  two
ranges.
Requires:
The  resulting range shall not overlap with either of the original
ranges.
Returns:
The end of the constructed range.
Complexity:
At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons.
Notes:
Stable,  that is, if an element is present in both ranges, the one
from the first range is copied.

25.3.5.4  set_difference                        [lib.set.difference]

template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

Effects:
Constructs a sorted  difference  of  the  elements  from  the  two
ranges.
Requires:
The  resulting range shall not overlap with either of the original
ranges.
Returns:
The end of the constructed range.
Complexity:
At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons.

25.3.5.5                              [lib.set.symmetric.difference]
set_symmetric_difference

template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);

template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);

Effects:
Constructs a sorted symmetric difference of the elements from  the
two ranges.
Requires:
The  resulting range shall not overlap with either of the original
ranges.
Returns:
The end of the constructed range.
Complexity:
At most ((last1 - first1) + (last2 - first2)) * 2 - 1 comparisons.

25.3.6  Heap operations                    [lib.alg.heap.operations]

1   A  heap  is a particular organization of elements in a range between
two random access iterators [a, b).  Its two key properties are: (1)
*a  is the largest element in the range and (2) *a may be removed by
pop_heap, or a new element added  by  push_heap,  in  O(logN)  time.
These  properties  make  heaps useful as priority queues.  make_heap
converts a range into a heap and  sort_heap  turns  a  heap  into  a
sorted sequence.

25.3.6.1  push_heap                                  [lib.push.heap]

template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Requires:
The range [first, last - 1) shall be a valid heap.
Effects:
Places  the value in the location last - 1 into the resulting heap
[first, last).
Complexity:
At most log(last - first) comparisons.

25.3.6.2  pop_heap                                    [lib.pop.heap]

template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Requires:
The range [first, last) shall be a valid heap.
Effects:
Swaps the value in the location first with the value in the  loca­
tion last - 1 and makes [first, last - 1) into a heap.
Complexity:
At most 2 * log(last - first) comparisons.

25.3.6.3  make_heap                                  [lib.make.heap]

template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Effects:
Constructs a heap out of the range [first, last).
Complexity:
At most 3*(last - first) comparisons.

25.3.6.4  sort_heap                                  [lib.sort.heap]

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

Effects:
Sorts elements in the heap [first, last).
Complexity:
At most NlogN comparisons, where N == last - first.
Notes:
Not stable.

25.3.7  Minimum and maximum                        [lib.alg.min.max]

25.3.7.1  min                                              [lib.min]

template<class T>
T min(const T& a, const T& b);

template<class T, class Compare>
T min(const T& a, const T& b, Compare comp);

Returns:
The smaller value.
Notes:
Returns the first argument when their arguments are equal.

25.3.7.2  max                                              [lib.max]

template<class T>
T max(const T& a, const T& b);

template<class T, class Compare>
T max(const T& a, const T& b, Compare comp);

Returns:
The larger value.
Notes:
Returns the first argument when their arguments are equal.

25.3.7.3  max_element                              [lib.max.element]

template<class InputIterator>
InputIterator max_element(InputIterator first, InputIterator last);

template<class InputIterator, class Compare>
InputIterator max_element(InputIterator first, InputIterator last,
Compare comp);

Returns:
The  first iterator i in the range [first, last) such that for any
iterator j in the range [first, last) the following  corresponding
conditions hold: !(*i < *j) or comp(*i, *j) == false.
Complexity:
Exactly max((last - first) - 1, 0) applications of the correspond­
ing comparisons.

25.3.7.4  min_element                              [lib.min.element]

template<class InputIterator>
InputIterator min_element(InputIterator first, InputIterator last);

template<class InputIterator, class Compare>
InputIterator min_element(InputIterator first, InputIterator last,
Compare comp);

Returns:
The first iterator i in the range [first, last) such that for  any
iterator  j in the range [first, last) the following corresponding
conditions hold: !(*j < *i) or comp(*j, *i) == false
Complexity:
Exactly max((last - first) - 1, 0) applications of the correspond­
ing comparisons.

25.3.8  Lexicographical comparison          [lib.alg.lex.comparison]

template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2);

template<class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
Compare comp);

Returns:
true  if  the  sequence  of elements defined by the range [first1,
last1) is lexicographically less than  the  sequence  of  elements
defined by the range [first2, last2).
Returns false otherwise.

Complexity:
At  most  min((last1  - first1), (last2 - first2)) applications of
the corresponding comparison.

25.3.9  Permutation generators      [lib.alg.permutation.generators]

25.3.9.1  next_permutation                    [lib.next.permutation]

template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp);

Effects:
Takes a sequence defined by the range [first, last) and transforms
it into the next permutation.  The next permutation  is  found  by
assuming  that  the  set  of all permutations is lexicographically
sorted with respect to operator< or comp.  If such  a  permutation
exists,  it  returns  true.  Otherwise, it transforms the sequence
into the smallest permutation, that  is,  the  ascendingly  sorted
one, and returns false.
Complexity:
At most (last - first)/2 swaps.

25.3.9.2  prev_permutation                    [lib.prev.permutation]

template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp);

Effects:
Takes a sequence defined by the range [first, last) and transforms
it into the previous permutation.   The  previous  permutation  is
found by assuming that the set of all permutations is lexicograph­
ically sorted with respect to operator< or comp.
Returns:
true if such a permutation exists.  Otherwise, it  transforms  the
sequence  into  the largest permutation, that is, the descendingly
sorted one, and returns false.
Complexity:
At most (last - first)/2 swaps.

25.4  C library algorithms                       [lib.alg.c.library]

1   Header <cstdlib> (partial, Table 2):

+-----------------------------+
|   Type          Name(s)     |
+-----------------------------+
|Functions:   bsearch   qsort |
+-----------------------------+

2   The contents are the same as the Standard C library.  SEE ALSO:  ISO
C subclause 7.10.5.

```