______________________________________________________________________

  25   Algorithms library                               [lib.algorithms]

  ______________________________________________________________________

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

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

                   Table 1--Algorithms library summary

  +--------------------------------------------------------------------------+
  |                         Subclause                             Header(s)  |
  +--------------------------------------------------------------------------+
  |_lib.alg.nonmodifying_ Non-modifying sequence operations                  |
  |_lib.alg.modifying.operations_ Mutating sequence operations   <algorithm> |
  |_lib.alg.sorting_ Sorting and related operations                          |
  +--------------------------------------------------------------------------+
  |_lib.alg.c.library_ C library algorithms                      <cstdlib>   |
  +--------------------------------------------------------------------------+

  Header <algorithm> synopsis

  namespace std {
    // _lib.alg.nonmodifying_, non-modifying sequence operations:
    template<class InputIterator, class Function>
      Function 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,
                 BinaryPredicate pred);
    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);
    template<class ForwardIterator>
      ForwardIterator adjacent_find(ForwardIterator first,
                                    ForwardIterator last);
    template<class ForwardIterator, class BinaryPredicate>
      ForwardIterator adjacent_find(ForwardIterator first,
          ForwardIterator last, BinaryPredicate pred);
    template<class InputIterator, class T>
      typename iterator_traits<InputIterator>::difference_type
        count(InputIterator first, InputIterator last, const T& value);
    template<class InputIterator, class Predicate>
      typename iterator_traits<InputIterator>::difference_type
        count_if(InputIterator first, InputIterator last, Predicate pred);
    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_n(ForwardIterator first, ForwardIterator last,
                              Size count, const T& value);
    template<class ForwardIterator, class Size, class T, class BinaryPredicate>
      ForwardIterator1 search_n(ForwardIterator first, ForwardIterator last,
                              Size count, const T& value,
                              BinaryPredicate pred);
    // _lib.alg.modifying.operations_, modifying 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 ForwardIterator1, class ForwardIterator2>
      void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
    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 ForwardIterator>
      void rotate(ForwardIterator first, ForwardIterator middle,
                  ForwardIterator 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>
      BidirectionalIterator stable_partition(BidirectionalIterator first,
                                             BidirectionalIterator last,
                                             Predicate pred);
    // _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> const T& min(const T& a, const T& b);
    template<class T, class Compare>
      const T& min(const T& a, const T& b, Compare comp);
    template<class T> const T& max(const T& a, const T& b);
    template<class T, class Compare>
      const T& max(const T& a, const T& b, Compare comp);
    template<class ForwardIterator>
      ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
    template<class ForwardIterator, class Compare>
      ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                                Compare comp);
    template<class ForwardIterator>
      ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
    template<class ForwardIterator, class Compare>
      ForwardIterator max_element(ForwardIterator first, ForwardIterator 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 Throughout this clause, the names of template parameters are  used  to
  express  type  requirements.   If an algorithm's template parameter is
  InputIterator, InputIterator1, or InputIterator2, the actual  template
  argument   shall   satisfy  the  requirements  of  an  input  iterator
  (_lib.input.iterators_).  If an algorithm's template parameter is Out-
  putIterator,  OutputIterator1, or OutputIterator2, the actual template
  argument  shall  satisfy  the  requirements  of  an  output   iterator
  (_lib.output.iterators_).   If  an  algorithm's  template parameter is
  ForwardIterator, ForwardIterator1,  or  ForwardIterator2,  the  actual
  template argument shall satisfy the requirements of a forward iterator
  (_lib.forward.iterators_).  If an algorithm's  template  parameter  is
  BidirectionalIterator,  BidirectionalIterator1, or BidirectionalItera-
  tor2, the actual template argument shall satisfy the requirements of a
  bidirectional  iterator  (_lib.bidirectional.iterators_).  If an algo-
  rithm's template parameter is RandomAccessIterator, RandomAccessItera-
  tor1,  or  RandomAccessIterator2,  the  actual template argument shall
  satisfy  the  requirements  of  a  random-access  iterator  (_lib.ran-
  dom.access.iterators_).

5 If  an algorithm's Effects section says that a value pointed to by any
  iterator passed as an argument is modified, then that algorithm has an
  additional  type  requirement: The type of that argument shall satisfy
  the requirements of a mutable iterator  (_lib.iterator.requirements_).
  [Note: this requirement does not affect arguments that are declared as
  OutputIterator, OutputIterator1, or  OutputIterator2,  because  output
  iterators must always be mutable.   --end note]

6 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
  dominates the cost of copy, the copying version is not included.   For

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

7 The Predicate parameter is used whenever an algorithm expects a  func-
  tion  object that when applied to the result of dereferencing the cor-
  responding 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 shall not apply any
  non-constant function through the dereferenced iterator.   This  func-
  tion  object may be a pointer to function, or an object of a type with
  an appropriate function call operator.

8 The BinaryPredicate parameter is used whenever an algorithm expects  a
  function  object  that when applied to the result of dereferencing two
  corresponding iterators or to dereferencing an  iterator  and  type  T
  when  T is part of the signature returns a value testable as true.  In
  other words, if an algorithm takes BinaryPredicate binary_pred as  its
  argument  and  first1  and first2 as its iterator arguments, it should
  work   correctly   in   the   construct    if    (binary_pred(*first1,
  *first2)){...}.   BinaryPredicate always takes the first iterator type
  as its first argument, that is, in those cases when T value is part of
  the  signature,  it  should  work  correctly  in  the  context  of  if
  (binary_pred(*first1, value)){...}.  binary_pred shall not  apply  any
  non-constant function through the dereferenced iterators.

9 In  the  description  of the algorithms operators + and - are used for
  some of the iterator categories for which  they  do  not  have  to  be
  defined.  In these cases the semantics of a+n is the same as that of
    { X tmp = a;
      advance(tmp, n);
      return tmp;
    }
  and that of a-b is the same as of
    return distance(a, b);

  25.1  Non-modifying sequence operations         [lib.alg.nonmodifying]

  25.1.1  For each                                     [lib.alg.foreach]

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

  Effects:
    Applies f to the result of dereferencing every iterator in the range
    [first, last), starting from first and proceeding to last - 1.
  Returns:
    f.
  _________________________
  example, sort_copy is not included because the cost of sorting is much
  more significant, and users might as well do copy followed by sort.

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

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_).
  Returns:
    The first iterator i in the range [first, last) for which  the  fol-
    lowing  corresponding  conditions  hold:  *i  ==  value, pred(*i) !=
    false.  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,  last1  -  (last2-first2))
    such  that for any non-negative integer n < (last2-first2), the fol-
    lowing  corresponding  conditions  hold:  *(i+n)   ==   *(first2+n),
    pred(*(i+n),*(first2+n))  != false.  Returns last1 if no such itera-
    tor is found.
  Complexity:
    At most (last2 - first2) * (last1 - first1 - (last2 - first2)  +  1)
    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 an element that matches one of a set of values.
  Returns:
    The first iterator i in the range [first1, last1) such that for some
    integer j in the range  [first2,  last2)  the  following  conditions
    hold:  *i  ==  *j,  pred(*i,*j)  != false.  Returns last1 if no such
    iterator is found.
  Complexity:
    At most (last1-first1) * (last2-first2) applications of  the  corre-
    sponding predicate.

  25.1.5  Adjacent find                          [lib.alg.adjacent.find]

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

  template<class ForwardIterator, class BinaryPredicate>
    ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                                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)) != false.  Returns last if no
    such iterator is found.
  Complexity:
    Exactly find(first, last, value) - first applications of the  corre-
    sponding predicate.

  25.1.6  Count                                          [lib.alg.count]

  template<class InputIterator, class T>
      typename iterator_traits<InputIterator>::difference_type
         count(InputIterator first, InputIterator last, const T& value);

  template<class InputIterator, class Predicate>
      typename iterator_traits<InputIterator>::difference_type
        count_if(InputIterator first, InputIterator last, Predicate pred);

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_) .
  Effects:
    Returns  the  number  of  iterators i in the range [first, last) for
    which the following corresponding  conditions  hold:  *i  ==  value,
    pred(*i) != false.
  Complexity:
    Exactly last - first applications of the corresponding predicate.

  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
    iterator i is not found.
  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))) != false.  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)) != false.   Returns  last1  if  no
    such iterator is found.
  Complexity:
    At most (last1 - first1) * (last2 - first2) applications of the cor-
    responding predicate.

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

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

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_),  type  Size
    is convertible to integral type (_conv.integral_, _class.conv_).
  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  corre-
    sponding conditions hold: *(i + n) == value, pred(*(i + n),value) !=
    false.  Returns last if no such iterator is found.
  Complexity:
    At most (last1 - first1) * count applications of  the  corresponding
    predicate.

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

  25.2.1  Copy                                            [lib.alg.copy]

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

  Effects:
    Copies elements in the range [first, last) into the  range  [result,
    result + (last - first)) starting from first and proceeding to last.
    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.

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

  _________________________
  2)  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]

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

  Requires:
    Type T is Assignable (_lib.container.requirements_).
  Effects:
    Exchanges values stored in two locations.

  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.

  template<class ForwardIterator1, class ForwardIterator2>
    void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

  Effects:
    Exchanges the values pointed to by the two iterators a and b.

  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]

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

  Requires:
    Type   T  is  Assignable  (_lib.container.requirements_)  (and,  for
    replace(), EqualityComparable (_lib.equalitycomparable_)).
  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) != false.
  Complexity:
    Exactly last - first applications of the corresponding predicate.

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

  Requires:
    Type  T  is  Assignable  (_lib.container.requirements_)  (and,   for
    replace_copy(),  EqualityComparable (_lib.equalitycomparable_).  The
    ranges [first, last) and [result, result + (last - first)) shall not
    overlap.
  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)))
    != false.
  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);

  Requires:
    Type T is Assignable (_lib.container.requirements_),  Size  is  con-
    vertible to an integral type (_conv.integral_, _class.conv_).
  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, Size is  convertible  to  an  integral  type
    (_conv.integral_, _class.conv_).
  Complexity:
    Exactly last - first (or n) invocations of gen and assignments.

  25.2.7  Remove                                        [lib.alg.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);

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_).
  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) != false.
  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.

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

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_).  The ranges
    [first, last) and [result, result+(last-first)) shall not overlap.
  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) != false.
  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]

  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)) != false
  Returns:
    The end of the resulting range.
  Complexity:
    If the range (last - first) is not empty, exactly (last - first) - 1
    applications of the corresponding predicate, otherwise  no  applica-
    tions of the predicate.

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

  Requires:
    The ranges [first, last) and [result, result+(last-first)) shall not
    overlap.
  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)) != false
  Returns:
    The end of the resulting range.
  Complexity:
    Exactly last - first applications of the corresponding predicate.

  25.2.9  Reverse                                      [lib.alg.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.

  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]

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

  Effects:
    For each non-negative integer i < (last - first), places the element
    from  the position first + i into position first + (i + (last - mid-
    dle)) % (last - first).
  Notes:
    This is a left rotate.
  Requires:
    [first, middle) and [middle, last) are valid ranges.
  Complexity:
    At most last - first swaps.

  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: *(result + i) =  *(first +  (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(n) (where n is a positive  argu-
    ment of type iterator_traits<RandomAccessIterator>::difference_type)
    returns a randomly chosen value of  a  type  convertible  to  itera-
    tor_traits<RandomAccessIterator>::difference_type)  in  the interval
    [0, n).

  25.2.12  Partitions                               [lib.alg.partitions]

  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) != false, 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 are done.

  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator
      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) != false, 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 _lib.alg.sorting_ have two  versions:  one  that
  takes  a  function  object of type Compare and one that uses an opera-
  tor<.

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.

3 For all algorithms that take Compare, there is  a  version  that  uses
  operator< instead.  That is, comp(*i, *j) != false defaults to *i < *j
  != false.  For the algorithms to work correctly, comp has to induce  a
  strict weak ordering on the values.

4 The  term  strict refers to the requirement of an irreflexive relation
  (!comp(x, x) for all x), and the term weak to  requirements  that  are
  not  as  strong as those for a total ordering, but stronger than those
  for a partial ordering.  If we define equiv(a, b)  as  !comp(a, b)  &&
  !comp(b, a),  then  the  requirements  are that comp and equiv both be
  transitive  relations:

  --comp(a, b) && comp(b, c) implies comp(a, c)

  --equiv(a, b) && equiv(b, c) implies equiv(a, c)  [Note:  Under  these
    conditions, it can be shown that

  --equiv is an equivalence relation

  --comp  induces  a  well-defined  relation  on the equivalence classes
    determined by equiv

  --The induced relation is a strict total ordering.   --end note]

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

6 In the descriptions of the functions that deal with ordering relation-
  ships we frequently use a notion of equivalence to  describe  concepts
  such as stability.  The equivalence to which we refer is not necessar-
  ily an operator==, but an equivalence relation induced by  the  strict
  weak  ordering.   That is, two elements a and b are considered equiva-
  lent 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.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);

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

  _________________________
  3)  If  the  worst case behavior is important stable_sort() (_lib.sta-
  ble.sort_) or partial_sort() (_lib.partial.sort_) should be used.

  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 ele-
    ments in the range [middle,  last)  are  placed  in  an  unspecified
    order.
  Complexity:
    It  takes approximately (last - first) * log(middle - first) compar-
    isons.

  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(*j, *i)  ==
  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
  and assume that the sequence being searched is in order  according  to
  the  implied or explicit comparison function.  They work on non-random
  access iterators minimizing the number of comparisons, which  will  be
  logarithmic for all types of iterators.  They are especially appropri-
  ate for random access iterators, because these algorithms do  a  loga-
  rithmic  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);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  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  corresponding
    conditions hold: *j < value or comp(*j, value) != false

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

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  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 corresponding
    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);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  Effects:
    Finds the largest subrange  [i,  j)  such  that  the  value  can  be
    inserted  at any iterator k in it without violating the ordering.  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) + 1 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);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  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) + 2 comparisons.

  25.3.4  Merge                                          [lib.alg.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.   The list will be sorted in non-decreasing order according to
  the ordering defined by comp; that is, for every iterator i in [first,
  last)  other than first, the condition *i < *(i - 1) or comp(*i, *(i -
  1)) will be false.
  Returns:
    result + (last1 - first1) + (last2 - first2).
  Complexity:
    At most (last1 - first1) + (last2 - first2) - 1 comparisons.
  Notes:
    Stable:  for equivalent elements in the  two  ranges,  the  elements
    from the first range always precede the elements from the second.

  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).
    The  resulting  range  will be in non-decreasing order; that is, for
    every iterator i in [first, last) other than first, the condition *i
    < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.
  Complexity:
    When  enough additional memory is available, (last - first) - 1 com-
    parisons.  If no additional memory is available, an  algorithm  with
    complexity NlogN (where N is equal to last - first) may be used.
  Notes:
    Stable:   for  equivalent  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 also work with multisets (_lib.multiset_) containing mul-
  tiple  copies of equivalent elements.  The semantics of the set opera-
  tions are 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);

  Returns:
    true if every element in the range [first2, last2) is  contained  in
    the range [first1, last1).  Returns false otherwise.
  Complexity:
    At most 2 * ((last1 - first1) + (last2 - first2)) - 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; that
    is, the set of elements that are present  in  one  or  both  of  the
    ranges.
  Requires:
    The  resulting  range  shall not overlap with either of the original
    ranges.
  Returns:
    The end of the constructed range.
  Complexity:
    At most 2 * ((last1 - first1) + (last2 - first2)) - 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; that is, the set of elements that are present in both of the
    ranges.

  Requires:
    The  resulting  range  shall not overlap with either of the original
    ranges.
  Returns:
    The end of the constructed range.
  Complexity:
    At most 2 * ((last1 - first1) + (last2 - first2)) - 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:
    Copies  the elements of the range [first1, last1) which are not pre-
    sent in the range [first2, last2) to the range beginning at  result.
    The elements in the constructed range are sorted.
  Requires:
    The  resulting  range  shall not overlap with either of the original
    ranges.
  Returns:
    The end of the constructed range.
  Complexity:
    At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.

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

  Effects:
    Copies  the elements of the range [first1, last1) which are not pre-
    sent in the range [first2, last2), and the  elements  of  the  range
    [first2,  last2)  which are not present in the range [first1, last1)
    to the range beginning at result.  The elements in  the  constructed
    range are sorted.
  Requires:
    The  resulting  range  shall not overlap with either of the original
    ranges.
  Returns:
    The end of the constructed range.
  Complexity:
    At most 2 * ((last1 - first1) + (last2 - first2)) - 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.

2 These properties make heaps useful as priority queues.

3 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 location
    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]

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

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_) and CopyCon-
    structible (_lib.copyconstructible_).
  Returns:
    The smaller value.
  Notes:
    Returns the first argument when the arguments are equivalent.

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

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_) and CopyCon-
    structible (_lib.copyconstructible_).
  Returns:
    The larger value.
  Notes:
    Returns the first argument when the arguments are equivalent.

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

  template<class ForwardIterator, class Compare>
    ForwardIterator min_element(ForwardIterator first, ForwardIterator 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 corresponding
    comparisons.

  template<class ForwardIterator>
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
  template<class ForwardIterator, class Compare>
    ForwardIterator max_element(ForwardIterator first, ForwardIterator 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 corresponding
    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.
  Notes:
    If two sequences have the same number of elements and  their  corre-
    sponding  elements  are equivalent, then neither sequence is lexico-
    graphically less than the other.  If one sequence is a prefix of the
    other,  then the shorter sequence is lexicographically less than the
    longer sequence.  Otherwise, the lexicographical comparison  of  the
    sequences yields the same result as the comparison of the first cor-
    responding pair of elements that are not equivalent.
      for (i = first1, j = first2;
           i != last1 && j != last2 && !(*i < *j) && !(*j < *i);
           ++i, ++j);
      return j == last2 ? false : i == last1 || *i < *j;

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

  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.

  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  lexicographically
    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):

                    Table 2--Header <cstdlib> synopsis

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

2 The  contents are the same as the Standard C library header <stdlib.h>
  with the following exceptions:

3 The function signature:

  bsearch(const void *, const void *, size_t, size_t,
          int (*)(const void *, const void *));

  is replaced by the two declarations:

  extern "C" void *bsearch(const void *key, const void *base,
                          size_t nmemb, size_t size,
                          int (*compar)(const void *, const void *));
  extern "C++" void *bsearch(const void *key, const void *base,
                          size_t nmemb, size_t size,
                          int (*compar)(const void *, const void *));

  both of which have the same behavior as the original declaration.

4 The function signature:

  qsort(void *, size_t, size_t,
          int (*)(const void *, const void *));

  is replaced by the two declarations:

  extern "C" void qsort(void* base, size_t nmemb, size_t size,
                  int (*compar)(const void*, const void*));
  extern "C++" void qsort(void* base, size_t nmemb, size_t size,
                  int (*compar)(const void*, const void*));

  [Note: Because the function argument compar() may throw an  exception,
  bsearch()   and   qsort()  are  allowed  to  propagate  the  exception
  (_lib.res.on.exception.handling_).   --end note]

  SEE ALSO: ISO C subclause 7.10.5.