```
______________________________________________________________________

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   (_lib.alg.nonmutating_),   mutating   sequence  operations
(_lib.alg.mutating.operations_), and sorting  and  related  operations
(_lib.alg.sorting_).

--<stl algorithms (TBD)>

--<cstdlib>    (partial)

4 Table 1:

Table 1--Header <stl algorithms (TBD)> synopsis

+-----------------------------------------------------------+
|           Type                         Name(s)            |
+-----------------------------------------------------------+
|Template functions:                                        |
|binary_search [2]             push_heap [2]                |
|copy                          random_shuffle [2]           |
|copy_backward                 remove                       |
|count                         remove_copy                  |
|count_if                      remove_copy_if               |
|equal [2]                     remove_if                    |
|equal_range [2]               replace                      |
|fill                          replace_copy                 |
|fill_n                        replace_copy_if              |
|find                          replace_if                   |
|find_if                       reverse                      |
|for_each                      reverse_copy                 |
|generate                      rotate                       |
|generate_n                    rotate_copy                  |
|includes [2]                  search [2]                   |
|inplace_merge [2]             set_difference [2]           |
|lexicographical_compare [2]   set_intersection [2]         |
|lower_bound [2]               set_symmetric_difference [2] |
|make_heap [2]                 set_union [2]                |
|max [2]                       sort [2]                     |
|max_element [2]               sort_heap [2]                |
|merge [2]                     stable_partition             |
|min [2]                       stable_sort [2]              |
|min_element [2]               swap                         |
|mismatch [2]                  swap_ranges                  |
|next_permutation [2]          transform [2]                |
|nth_element [2]               unique [2]                   |
|partial_sort [2]              unique_copy [2]              |
|partial_sort_copy [2]         upper_bound [2]              |
|partition                                                  |
|pop_heap [2]                                               |
+-----------------------------------------------------------+

5 Table 2:

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

6 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 user defined data structures, as
long as these data  structures  have  iterator  types  satisfying  the
assumptions on the algorithms.

7 Both  in-place  and  copying  versions  are provided for certain algo­
rithms.  The decision whether to include a copying version was usually
based on complexity considerations.  When the cost of doing the opera­
tion 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).

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

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

10In 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,  parti­
tion, stable_partition, sort, stable_sort and inplace_merge the itera­
tor 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                 -------+

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

1 Applies f to the result of dereferencing every iterator in  the  range
[first,  last).   f  shall not apply any non-constant function through
the dereferenced iterator.

2 Complexity: f is applied exactly last - first times.

3 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);

1 Returns the first iterator i in the range [first, last) for which  the
following  corresponding  conditions  hold:  *i  == value, pred(*i) ==
true.  Returns last if no such iterator is found.

2 Complexity: At most last - first  applications  of  the  corresponding
predicate are done.

template <class InputIterator>

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

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

2 Complexity: At most max((last - first) - 1,  0)  applications  of  the
corresponding predicate are done.

25.1.4  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);

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

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

3 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.5  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);

1 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 iterator i  is

2 Complexity:  At  most last1 - first1 applications of the corresponding
predicate are done.

25.1.6  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);

1 Returns true if for every iterator i in the range [first1, last1)  the
following  corresponding  conditions  hold:  *i  ==  *(first2  +  (i -
first1)), pred(*i, *(first2 + (i  -  first1)))  ==  true.   Otherwise,
returns false.

2 Complexity:  At  most last1 - first1 applications of the corresponding
predicate are done.

25.1.7  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);

1 Finds a subsequence of equal values in a sequence.

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

25.2  Mutating sequence operations       [lib.alg.mutating.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);

_________________________
1) 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);

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

1 Copies  elements.   For  each non-negative integer n < (last - first),
*(result + n) = *(first + n) is  performed.   copy  returns  result  +
(last - first).

2 result shall not be in the range [first, last).

3 Complexity: Exactly last - first assignments are done.

25.2.1.2  copy_backward                            [lib.copy.backward]
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last, BidirectionalIterator2 result);

1 Copies  elements  in  the range [first, last) into the range [result -
(last - first), result) starting from  last  -  1  and  proceeding  to
first.2) For each positive integer n <= (last - first), *(result -  n)
= *(last - n) is performed.

2 result shall not be in the range [first, last).

3 Returns result - (last - first).

4 Complexity: Exactly last - first assignments are done.

25.2.2  Swap                                            [lib.alg.swap]

25.2.2.1  swap                                              [lib.swap]
template <class T>
void swap(T& a, T& b);

1 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);

1 For  each  non-negative  integer n < (last1 - first1) the swap is per­
formed: swap(*(first1 + n), *(first2 + n)).

2 The two ranges [first1, last1) and [first2, first2 + (last1 - first1))
shall not overlap.

3 Returns first2 + (last1 - first1).

4 Complexity: Exactly last1 - first1 swaps are done.

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

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

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

2 op and binary_op shall not have any side effects.

3 Returns result + (last1 - first1).

4 Complexity: Exactly last1 - first1 applications of op or binary_op are
performed.

5 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);

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

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

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

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

2 Returns result + (last - first).

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

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

1 Assigns  value through all the iterators in the range [first, last) or
[first, first + n).

2 Complexity: Exactly last - first (or n) assignments are done.

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

1 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).  gen takes no arguments.

2 Complexity: Exactly last - first (or n) invocations of gen and assign­
ments are done.

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

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

2 Returns  the  end  of the resulting range.  remove is stable, that is,
the relative order of the elements that are not removed is the same as
their relative order in the original range.

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

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

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

2 Returns the end of the resulting range.

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

4 Notes:  remove_copy is stable, that is, the relative order of the ele­
ments 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);

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

2 Returns the end of the resulting range.

3 Complexity: Exactly (last - first) - 1 applications of the correspond­
ing predicate are done.

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

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

2 Returns the end of the resulting range.

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

25.2.9  Reverse                                      [lib.alg.reverse]

25.2.9.1  reverse                                        [lib.reverse]
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

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

2 Complexity: Exactly (last - first)/2 swaps are performed.

25.2.9.2  reverse_copy                              [lib.reverse.copy]
template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result);

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

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

3 Returns result + (last - first).

4 Complexity: Exactly last - first assignments are done.

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),  rotate  places  the
element from the position first + i into position first + (i + (middle
- first)) % (last - first).

2 Complexity: At most last - first swaps are done.

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

1 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 + (mid­
dle - first)) % (last - first)).  rotate_copy returns result + (last -
first).

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

3 Complexity: Exactly last - first assignments are done.

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

1 Shuffles  the elements in the range [first, last) with uniform distri­
bution.

2 Complexity: Exactly (last - first) - 1 swaps are done.

3 Notes: random_shuffle can take a particular random  number  generating
function  object  rand such that rand returns a randomly chosen double
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);

1 Places all the elements in the range [first, last) that  satisfy  pred
before all the elements that do not satisfy it.

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

3 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);

1 Places all the elements in the range [first, last) that  satisfy  pred
before all the elements that do not satisfy it.

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

3 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 are done.

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 algorithms to work cor­
rectly, 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 relation­
ships we frequently use a notion of equality to describe concepts such
as  stability.   The  equality to which we refer is not necessarily 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);

1 Sorts the elements in the range [first, last).

2 Complexity: Approximately NlogN (where N equals to last - first)  com­
parisons on the average.3)

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

1 Sorts the elements in the range [first, last).

2 Complexity:  It  does  at most Nlog2N (where N equals to last - first)
comparisons; if enough extra memory is available, it is NlogN.

3 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);

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

2 Complexity:  It  takes  approximately  (last  -  first) * log(middle -
first) comparisons.

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

1 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)).
_________________________
3)   If   the   worst   case   behavior   is   important   stable_sort
(_lib.stable.sort_) or  partial_sort  (_lib.partial.sort_)  should  be
used.

2 Returns either result_last or result_first + (last - first)  whichever
is smaller.

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

2 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 com­
parisons, 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  struc­
ture.  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);

1 Finds the first position into which value can be inserted without vio­
lating  the  ordering.  lower_bound returns the furthermost iterator i
in the range [first, last) such that for any iterator j in  the  range
[first,  i) the following corresponding conditions hold: *j < value or
comp(*j, value) == true.

2 Complexity: At most log(last - first) + 1 comparisons are done.

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

1 Finds the furthermost position into which value can be inserted  with­
out violating the ordering.  upper_bound returns the furthermost iter­
ator i in the range [first, last) such that for any iterator j in  the
range  [first, i) the following corresponding conditions hold: !(value
< *j) or comp(value, *j) == false.

2 Complexity: At most log(last - first) + 1 comparisons are done.

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

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

2 Complexity: At most 2 * log(last - first) comparisons are done.

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

1 Returns  true if there is an iterator i in the range [first last) that
satisfies the corresponding conditions: !(*i < value) && !(value < *i)
or comp(*i, value) == false && comp(value, *i) == false.

2 Complexity: At most log(last - first) + 1 comparisons are done.

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

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

2 The resulting range shall not overlap  with  either  of  the  original
ranges.

3 Returns result + (last1 - first1) + (last2 - first2).

4 Complexity:  At  most  (last1 - first1) + (last2 - first2) - 1 compar­
isons are performed.

5 Notes: The merge is stable, that is, 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);

1 Merges two sorted consecutive  ranges  [first,  middle)  and  [middle,
last) putting the result of the merge into the range [first, last).

2 Complexity:  At  most  last  - first comparisons are performed.  If no
additional memory is available, the number of assignments can be equal
to NlogN where N is equal to last - first.

3 Notes:  The  merge  is  stable, that is, 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 multisets 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 maximum
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);

1 Returns true if every element in the range  [first2,  last2)  is  con­
tained in the range [first1, last1).  Returns false otherwise.

2 Complexity: At most ((last1 - first1) + (last2 - first2)) * 2 - 1 com­
parisons are performed.

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

1 Constructs a sorted union of the elements from the two ranges.

2 The resulting range shall not overlap  with  either  of  the  original
ranges.

3 Returns the end of the constructed range.

4 Complexity: At most ((last1 - first1) + (last2 - first2)) * 2 - 1 com­
parisons are performed.

5 Notes: set_union is stable, that is, 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);

1 Constructs  a sorted intersection of the elements from the two ranges.

2 The resulting range shall not overlap  with  either  of  the  original
ranges.

3 Returns the end of the constructed range.

4 Complexity: At most ((last1 - first1) + (last2 - first2)) * 2 - 1 com­
parisons are performed.

5 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);

1 Constructs a sorted difference of the elements from the two ranges.

2 The  resulting  range  shall  not  overlap with either of the original
ranges.

3 Returns the end of the constructed range.

4 Complexity: At most ((last1 - first1) + (last2 - first2)) * 2 - 1 com­
parisons are performed.

25.3.5.5  set_symmetric_difference      [lib.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);

1 Constructs a sorted symmetric difference of the elements from the  two
ranges.

2 The  resulting  range  shall  not  overlap with either of the original
ranges.

3 Returns the end of the constructed range.

4 Complexity: At most ((last1 - first1) + (last2 - first2)) * 2 - 1 com­
parisons are performed.

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

1 The range [first, last - 1) shall be a valid heap.

2 Places the value in the location last -  1  into  the  resulting  heap
[first, last).

3 Complexity: At most log(last - first) comparisons are performed.

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

1 The range [first, last) shall be a valid heap.

2 Swaps  the  value in the location first with the value in the location
last - 1 and makes [first, last - 1) into a heap.

3 Complexity: At most 2 * log(last - first) comparisons are performed.

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

1 Constructs a heap out of the range [first, last).

2 Complexity: At most 3*(last - first) comparisons are performed.

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

1 Sorts elements in the heap [first, last).

2 Complexity: At most NlogN comparisons are performed where N  is  equal
to last - first.

3 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);

25.3.7.2  max                                                [lib.max]

1 Returns  the  smaller  value.   Returns  the first argument when their
arguments are equal.
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);

2 Returns the larger value.  Returns the first argument when their argu­
ments 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);

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

2 Complexity:  Exactly  max((last  -  first) - 1, 0) applications of the
corresponding comparisons are done.

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

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

2 Complexity: Exactly max((last - first) - 1,  0)  applications  of  the
corresponding comparisons are done.

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

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

2 Complexity:  At  most min((last1 - first1), (last2 - first2)) applica­
tions of the corresponding comparison are done.

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

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

2 Complexity: At most (last - first)/2 swaps are performed.

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

1 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 lexicographically sorted
with respect to operator< or comp.

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

3 Complexity: At most (last - first)/2 swaps are performed.

```