algorithms.tex

\rSec0[algorithms]{Algorithms library}

\rSec1[algorithms.general]{General}

\pnum
This Clause describes components that \Cpp programs may use to perform
algorithmic operations on containers (Clause~\ref{containers}) and other sequences.

\pnum
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~\ref{tab:algorithms.summary}.

\begin{libsumtab}{Algorithms library summary}{tab:algorithms.summary}
\ref{alg.nonmodifying} & Non-modifying sequence operations  &           \\
\ref{alg.modifying.operations} & Mutating sequence operations & \tcode{<algorithm>} \\
\ref{alg.sorting} & Sorting and related operations      &           \\ \hline
\ref{alg.c.library} & C library algorithms          & \tcode{<cstdlib>} \\ \hline
\end{libsumtab}

\synopsis{Header \tcode{<algorithm>} synopsis}
\indexlibrary{\idxhdr{algorithm}}%

\begin{codeblock}
#include <initializer_list>

namespace std {

  // \ref{alg.nonmodifying}, non-modifying sequence operations:
  template <class InputIterator, class Predicate>
    bool all_of(InputIterator first, InputIterator last, Predicate pred);
  template <class InputIterator, class Predicate>
    bool any_of(InputIterator first, InputIterator last, Predicate pred);
  template <class InputIterator, class Predicate>
    bool none_of(InputIterator first, InputIterator last, Predicate pred);

  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 InputIterator, class Predicate>
    InputIterator find_if_not(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 InputIterator, class ForwardIterator>
    InputIterator
      find_first_of(InputIterator first1, InputIterator last1,
                    ForwardIterator first2, ForwardIterator last2);
  template<class InputIterator, class ForwardIterator,
     class BinaryPredicate>
    InputIterator
      find_first_of(InputIterator first1, InputIterator last1,
                    ForwardIterator first2, ForwardIterator 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>
    bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2);
  template<class ForwardIterator1, class ForwardIterator2,
                   class BinaryPredicate>
    bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 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);

  // \ref{alg.modifying.operations}, modifying sequence operations:
  // \ref{alg.copy}, copy:
  template<class InputIterator, class OutputIterator>
    OutputIterator copy(InputIterator first, InputIterator last,
                        OutputIterator result);
  template<class InputIterator, class Size, class OutputIterator>
    OutputIterator copy_n(InputIterator first, Size n,
                          OutputIterator result);
  template<class InputIterator, class OutputIterator, class Predicate>
    OutputIterator copy_if(InputIterator first, InputIterator last,
                          OutputIterator result, Predicate pred);
  template<class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2 copy_backward(
      BidirectionalIterator1 first, BidirectionalIterator1 last,
      BidirectionalIterator2 result);

  // \ref{alg.move}, move:
  template<class InputIterator, class OutputIterator>
    OutputIterator move(InputIterator first, InputIterator last,
                        OutputIterator result);
  template<class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2 move_backward(
      BidirectionalIterator1 first, BidirectionalIterator1 last,
      BidirectionalIterator2 result);

  // \ref{alg.swap}, swap:
  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 InputIterator, class OutputIterator, class Predicate, class T>
    OutputIterator replace_copy_if(InputIterator first, InputIterator 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>
    OutputIterator 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>
    OutputIterator 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>
    ForwardIterator 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);
  template<class RandomAccessIterator, class UniformRandomNumberGenerator>
    void shuffle(RandomAccessIterator first,
                        RandomAccessIterator last,
                        UniformRandomNumberGenerator&& rand);

  // \ref{alg.partitions}, partitions:
  template <class InputIterator, class Predicate>
    bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);

  template<class ForwardIterator, class Predicate>
    ForwardIterator partition(ForwardIterator first,
                              ForwardIterator last,
                              Predicate pred);
  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator stable_partition(BidirectionalIterator first,
                                           BidirectionalIterator last,
                                           Predicate pred);
  template <class InputIterator, class OutputIterator1,
            class OutputIterator2, class Predicate>
    pair<OutputIterator1, OutputIterator2>
    partition_copy(InputIterator first, InputIterator last,
                   OutputIterator1 out_true, OutputIterator2 out_false,
                   Predicate pred);
  template<class ForwardIterator, class Predicate>
    ForwardIterator partition_point(ForwardIterator first,
                                    ForwardIterator last,
                                    Predicate pred);

  // \ref{alg.sorting}, sorting and related operations:
  // \ref{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 ForwardIterator>
    bool is_sorted(ForwardIterator first, ForwardIterator last);
  template<class ForwardIterator, class Compare>
    bool is_sorted(ForwardIterator first, ForwardIterator last,
                   Compare comp);
  template<class ForwardIterator>
    ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
  template<class ForwardIterator, class Compare>
    ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator 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);

  // \ref{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);

  // \ref{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);

  // \ref{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);

  // \ref{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);

  template<class RandomAccessIterator>
    bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
  template<class RandomAccessIterator, class Compare>
    bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  template<class RandomAccessIterator>
    RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
  template<class RandomAccessIterator, class Compare>
    RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
                                       Compare comp);

  // \ref{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>
    T min(initializer_list<T> t);
  template<class T, class Compare>
    T min(initializer_list<T> t, 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 T>
    T max(initializer_list<T> t);
  template<class T, class Compare>
    T max(initializer_list<T> t, Compare comp);

  template<class T> pair<const T&, const T&> minmax(const T& a, const T& b);
  template<class T, class Compare>
    pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
  template<class T>
    pair<T, T> minmax(initializer_list<T> t);
  template<class T, class Compare>
    pair<T, T> minmax(initializer_list<T> t, 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 ForwardIterator>
    pair<ForwardIterator, ForwardIterator>
      minmax_element(ForwardIterator first, ForwardIterator last);
  template<class ForwardIterator, class Compare>
    pair<ForwardIterator, ForwardIterator>
      minmax_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);

  // \ref{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);
}
\end{codeblock}

\pnum
All of the algorithms are separated from the particular implementations of data structures and are
parameterized by iterator types.
Because of this, they can work with program-defined data structures, as long
as these data structures have iterator types satisfying the assumptions on the algorithms.

\pnum
For purposes of determining the existence of data races, algorithms shall
not modify objects referenced through an iterator argument unless the
specification requires such modification.

\pnum
Throughout this Clause, the names of template parameters
are used to express type requirements.
If an algorithm's template parameter is
\tcode{InputIterator},
\tcode{InputIterator1},
or
\tcode{InputIterator2},
the actual template argument shall satisfy the
requirements of an input iterator~(\ref{input.iterators}).
If an algorithm's template parameter is
\tcode{OutputIterator},
\tcode{OutputIterator1},
or
\tcode{OutputIterator2},
the actual template argument shall satisfy the requirements
of an output iterator~(\ref{output.iterators}).
If an algorithm's template parameter is
\tcode{ForwardIterator},
\tcode{ForwardIterator1},
or
\tcode{ForwardIterator2},
the actual template argument shall satisfy the requirements
of a forward iterator~(\ref{forward.iterators}).
If an algorithm's template parameter is
\tcode{BidirectionalIterator},
\tcode{Bidirectional\-Iterator1},
or
\tcode{BidirectionalIterator2},
the actual template argument shall satisfy the requirements
of a bidirectional iterator~(\ref{bidirectional.iterators}).
If an algorithm's template parameter is
\tcode{RandomAccessIterator},
\tcode{Random\-AccessIterator1},
or
\tcode{RandomAccessIterator2},
the actual template argument shall satisfy the requirements
of a random-access iterator~(\ref{random.access.iterators}).

\pnum
If an algorithm's
\synopsis{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~(\ref{iterator.requirements}).
\enternote
This requirement does not affect arguments that are declared as
\tcode{OutputIterator},
\tcode{OutputIterator1},
or
\tcode{OutputIterator2},
because output iterators must always be mutable.
\exitnote

\pnum
Both in-place and copying versions are provided for certain
algorithms.\footnote{The decision whether to include a copying version was
usually based on complexity considerations. When the cost of doing the operation
dominates the cost of copy, the copying version is not included. For example,
\tcode{sort_copy} is not included because the cost of sorting is much more
significant, and users might as well do \tcode{copy} followed by \tcode{sort}.}
When such a version is provided for \textit{algorithm} it is called
\textit{algorithm\tcode{_copy}}. Algorithms that take predicates end with the
suffix \tcode{_if} (which follows the suffix \tcode{_copy}).

\pnum
The
\tcode{Predicate}
parameter is used whenever an algorithm expects a function object~(\ref{function.objects})
that, when applied to the result
of dereferencing the corresponding iterator, returns a value testable as
\tcode{true}.
In other words, if an algorithm
takes
\tcode{Predicate pred}
as its argument and \tcode{first}
as its iterator argument, it should work correctly in the
construct
\tcode{pred(*first)} contextually converted to \tcode{bool} (Clause~\ref{conv}).
The function object
\tcode{pred}
shall not apply any non-constant
function through the dereferenced iterator.

\pnum
The
\tcode{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
\tcode{T}
when
\tcode{T}
is part of the signature returns a value testable as
\tcode{true}.
In other words, if an algorithm takes
\tcode{BinaryPredicate binary_pred}
as its argument and \tcode{first1} and \tcode{first2} as
its iterator arguments, it should work correctly in
the construct
\tcode{binary_pred(*first1, *first2)} contextually converted to \tcode{bool} (Clause~\ref{conv}).
\tcode{BinaryPredicate}
always takes the first
iterator's \tcode{value_type}
as its first argument, that is, in those cases when
\tcode{T value}
is part of the signature, it should work
correctly in the
construct \tcode{binary_pred(*first1, value)} contextually converted to \tcode{bool} (Clause~\ref{conv}).
\tcode{binary_pred} shall not
apply any non-constant function through the dereferenced iterators.

\pnum
\enternote
Unless otherwise specified, algorithms that take function objects as arguments
are permitted to copy those function objects freely. Programmers for whom object
identity is important should consider using a wrapper class that points to a
noncopied implementation object such as \tcode{reference_wrapper<T>}~(\ref{refwrap}), or some equivalent solution.
\exitnote

\pnum
When the description of an algorithm gives an expression such as
\tcode{*first == value}
for a condition, the expression shall evaluate to
either true or false in boolean contexts.

\pnum
In the description of the algorithms operators
\tcode{+}
and
\tcode{-}
are used for some of the iterator categories for which
they do not have to be defined.
In these cases the semantics of
\tcode{a+n}
is the same as that of

\begin{codeblock}
X tmp = a;
advance(tmp, n);
return tmp;
\end{codeblock}

and that of
\tcode{b-a}
is the same as of

\begin{codeblock}
return distance(a, b);
\end{codeblock}

\rSec1[alg.nonmodifying]{Non-modifying sequence operations}

\rSec2[alg.all_of]{All of}

\indexlibrary{\idxcode{all_of}}%
\begin{itemdecl}
template <class InputIterator, class Predicate>
  bool all_of(InputIterator first, InputIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\tcode{pred(*i)} is \tcode{true} for every iterator \tcode{i} in the range \range{first}{last}, and \tcode{false} otherwise.

\pnum
\complexity At most \tcode{last - first} applications of the predicate.
\end{itemdescr}

\rSec2[alg.any_of]{Any of}

\indexlibrary{\idxcode{any_of}}%
\begin{itemdecl}
template <class InputIterator, class Predicate>
  bool any_of(InputIterator first, InputIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{false} if \range{first}{last} is empty or
if there is no iterator \tcode{i} in the range
\range{first}{last} such that \tcode{pred(*i)} is \tcode{true}, and \tcode{true} otherwise.

\pnum
\complexity At most \tcode{last - first} applications of the predicate.
\end{itemdescr}

\rSec2[alg.none_of]{None of}

\indexlibrary{\idxcode{none_of}}%
\begin{itemdecl}
template <class InputIterator, class Predicate>
  bool none_of(InputIterator first, InputIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\tcode{pred(*i)} is \tcode{false} for every iterator \tcode{i} in the range \range{first}{last}, and \tcode{false} otherwise.

\pnum
\complexity At most \tcode{last - first} applications of the predicate.
\end{itemdescr}

\rSec2[alg.foreach]{For each}

\indexlibrary{\idxcode{for_each}}%
\begin{itemdecl}
template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function f);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{Function} shall meet the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}).
\enternote \tcode{Function} need not meet the requirements of
\tcode{CopyConstructible} (Table~\ref{copyconstructible}). \exitnote

\pnum
\effects
Applies
\tcode{f} to the result of dereferencing every iterator in the range
\range{first}{last},
starting from
\tcode{first}
and proceeding to
\tcode{last - 1}.
\enternote If the type of \tcode{first} satisfies the
requirements of a mutable iterator, \tcode{f} may apply nonconstant
functions through the dereferenced iterator.\exitnote

\pnum
\returns
\tcode{std::move(f)}.

\pnum
\complexity
Applies \tcode{f}
exactly
\tcode{last - first}
times.

\pnum
\notes
If \tcode{f} returns a result, the result is ignored.
\end{itemdescr}

\rSec2[alg.find]{Find}

\indexlibrary{\idxcode{find}}%
\indexlibrary{\idxcode{find_if}}%
\indexlibrary{\idxcode{find_if_not}}%
\begin{itemdecl}
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 InputIterator, class Predicate>
  InputIterator find_if_not(InputIterator first, InputIterator last,
                            Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
in the range
\range{first}{last}
for which the following corresponding
conditions hold:
\tcode{*i == value}, \tcode{pred(*i) != false}, \tcode{pred(*i) == false}.
Returns \tcode{last} if no such iterator is found.

\pnum
\complexity
At most
\tcode{last - first}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.find.end]{Find end}

\indexlibrary{\idxcode{find_end}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Finds a subsequence of equal values in a sequence.

\pnum
\returns
The last iterator
\tcode{i}
in the range \range{first1}{last1 - (last2 - first2)}
such that for any non-negative integer
\tcode{n < (last2 - first2)},
the following corresponding conditions hold:
\tcode{*(i + n) == *(\brk{}first2 + n), pred(*(i + n), *(first2 + n)) != false}.
Returns \tcode{last1}
if
\range{first2}{last2} is empty or if
no such iterator is found.

\pnum
\complexity
At most
\tcode{(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.find.first.of]{Find first}

\indexlibrary{\idxcode{find_first_of}}%
\begin{itemdecl}
template<class InputIterator, class ForwardIterator>
  InputIterator
    find_first_of(InputIterator first1, InputIterator last1,
                  ForwardIterator first2, ForwardIterator last2);

template<class InputIterator, class ForwardIterator,
          class BinaryPredicate>
  InputIterator
    find_first_of(InputIterator first1, InputIterator last1,
                  ForwardIterator first2, ForwardIterator last2,
                  BinaryPredicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Finds an element that matches one of a set of values.

\pnum
\returns
The first iterator
\tcode{i}
in the range \range{first1}{last1}
such that for some
iterator
\tcode{j}
in the range \range{first2}{last2}
the following conditions hold:
\tcode{*i == *j, pred(*i,*j) != false}.
Returns \tcode{last1}
if \range{first2}{last2} is empty or
if no such iterator is found.

\pnum
\complexity
At most
\tcode{(last1-first1) * (last2-first2)}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.adjacent.find]{Adjacent find}

\indexlibrary{\idxcode{adjacent_find}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
  ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                              BinaryPredicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
such that both
\tcode{i}
and
\tcode{i + 1}
are in
the range
\range{first}{last}
for which
the following corresponding conditions hold:
\tcode{*i == *(i + 1), pred(*i, *(i + 1)) != false}.
Returns \tcode{last}
if no such iterator is found.

\pnum
\complexity
For a nonempty range, exactly
\tcode{min((i - first) + 1, (last - first) - 1)}
applications of the corresponding predicate, where \tcode{i} is
\tcode{adjacent_find}'s
return value.
\end{itemdescr}

\rSec2[alg.count]{Count}

\indexlibrary{\idxcode{count}}%
\indexlibrary{\idxcode{count_if}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Returns the number of iterators
\tcode{i}
in the range \range{first}{last}
for which the following corresponding
conditions hold:
\tcode{*i == value, pred(*i) != false}.

\pnum
\complexity
Exactly
\tcode{last - first}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[mismatch]{Mismatch}

\indexlibrary{\idxcode{mismatch}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
A pair of iterators
\tcode{i}
and
\tcode{j}
such that
\tcode{j == first2 + (i - first1)}
and
\tcode{i}
is the first iterator
in the range \range{first1}{last1}
for which the following corresponding conditions hold:

\begin{codeblock}
!(*i == *(first2 + (i - first1)))
pred(*i, *(first2 + (i - first1))) == false
\end{codeblock}

Returns the pair \tcode{last1} and
\tcode{first2 + (last1 - first1)}
if such an iterator
\tcode{i}
is not found.

\pnum
\complexity
At most
\tcode{last1 - first1}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.equal]{Equal}

\indexlibrary{\idxcode{equal}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if for every iterator
\tcode{i}
in the range \range{first1}{last1}
the following corresponding conditions hold:
\tcode{*i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false}.
Otherwise, returns
\tcode{false}.

\pnum
\complexity
At most
\tcode{last1 - first1}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.is_permutation]{Is permutation}

\indexlibrary{\idxcode{is_permutation}}%
\begin{itemdecl}
template<class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2);
template<class ForwardIterator1, class ForwardIterator2,
                 class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                      ForwardIterator2 first2, BinaryPredicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires: \tcode{ForwardIterator1} and \tcode{ForwardIterator2} shall have the same
value type. The comparison function shall be an equivalence relation.

\pnum
\returns \tcode{true} if there exists a permutation of the elements in the
range \range{first2}{first2 + (last1 - first1)}, beginning with \tcode{ForwardIterator2
begin}, such that \tcode{equal(first1, last1, begin)} returns \tcode{true} or 
\tcode{equal(first1, last1, begin, pred)} returns \tcode{true}; otherwise, returns
\tcode{false}.

\pnum
\complexity Exactly \tcode{distance(first1, last1)} applications of the
corresponding predicate if \tcode{equal(\brk{}first1, last1, first2)}
would return \tcode{true}
or \tcode{equal(first1, last1, first2, pred)} would return \tcode{true}; otherwise, at
worst \bigoh{N^2}, where $N$ has the value \tcode{distance(first1, last1)}.
\end{itemdescr}

\rSec2[alg.search]{Search}

\indexlibrary{\idxcode{search}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Finds a subsequence of equal values in a sequence.

\pnum
\returns
The first iterator
\tcode{i}
in the range \range{first1}{last1 - (last2-first2)}
such that for any non-negative integer
\tcode{n}
less than
\tcode{last2 - first2}
the following corresponding conditions hold:
\tcode{*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false}.
Returns \tcode{first1}
if \range{first2}{last2} is empty,
otherwise returns \tcode{last1}
if no such iterator is found.

\pnum
\complexity
At most
\tcode{(last1 - first1) * (last2 - first2)}
applications of the corresponding predicate.
\end{itemdescr}

\indexlibrary{\idxcode{search_n}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The type
\tcode{Size}
shall be convertible to integral type~(\ref{conv.integral}, \ref{class.conv}).

\pnum
\effects
Finds a subsequence of equal values in a sequence.

\pnum
\returns
The first iterator
\tcode{i}
in the range \range{first}{last-count}
such that for any non-negative integer
\tcode{n}
less than
\tcode{count}
the following corresponding conditions hold:
\tcode{*(i + n) == value, pred(*(i + n),value) != false}.
Returns \tcode{last}
if no such iterator is found.

\pnum
\complexity
At most
\tcode{last - first}
applications of the corresponding predicate.
\end{itemdescr}

\rSec1[alg.modifying.operations]{Mutating sequence operations}

\rSec2[alg.copy]{Copy}

\indexlibrary{\idxcode{copy}}%
\begin{itemdecl}
template<class InputIterator, class OutputIterator>
  OutputIterator copy(InputIterator first, InputIterator last,
                      OutputIterator result);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Copies elements in the range \range{first}{last} into the range \range{result}{result + (last - first)} starting from \tcode{first} and proceeding to \tcode{last}. For each non-negative integer \tcode{n < (last - first)}, performs \tcode{*(result + n) = *(first + n)}.

\pnum
\returns \tcode{result + (last - first)}.

\pnum
\requires \tcode{result} shall not be in the range \range{first}{last}.

\pnum
\complexity Exactly \tcode{last - first} assignments.
\end{itemdescr}

\indexlibrary{\idxcode{copy_n}}%
\begin{itemdecl}
template<class InputIterator, class Size, class OutputIterator>
  OutputIterator copy_n(InputIterator first, Size n,
                        OutputIterator result);
\end{itemdecl}


\begin{itemdescr}
\pnum
\effects For each non-negative integer 
$i < n$, performs \tcode{*(result + i) = *(first + i)}.

\pnum
\returns \tcode{result + n}.

\pnum
\complexity Exactly \tcode{n} assignments.
\end{itemdescr}

\indexlibrary{\idxcode{copy_n}}%
\begin{itemdecl}
template<class InputIterator, class OutputIterator, class Predicate>
  OutputIterator copy_if(InputIterator first, InputIterator last,
                         OutputIterator result, Predicate pred);
\end{itemdecl}


\begin{itemdescr}
\pnum
\requires The ranges \range{first}{last} and \range{result}{result + (last - first)} shall not overlap.

\pnum
\effects Copies all of the elements referred to by the iterator \tcode{i} in the range \range{first}{last}
for which \tcode{pred(*i)} is \tcode{true}.

\pnum
\complexity Exactly \tcode{last - first} applications of the corresponding predicate.

\pnum
\remarks Stable.
\end{itemdescr}


\indexlibrary{\idxcode{copy_backward}}%
\begin{itemdecl}
template<class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2
    copy_backward(BidirectionalIterator1 first,
                  BidirectionalIterator1 last,
                  BidirectionalIterator2 result);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Copies elements in the range \range{first}{last}
into the
range \range{result - (last-first)}{result}
starting from
\tcode{last - 1}
and proceeding to \tcode{first}.\footnote{\tcode{copy_backward}
should be used instead of copy when \tcode{last}
is in
the range
\range{result - (last - first)}{result}.}
For each positive integer
\tcode{n <= (last - first)},
performs
\tcode{*(result - n) = *(last - n)}.

\pnum
\requires
\tcode{result}
shall not be in the range
\brange{first}{last}.

\pnum
\returns
\tcode{result - (last - first)}.

\pnum
\complexity
Exactly
\tcode{last - first}
assignments.
\end{itemdescr}

\rSec2[alg.move]{Move}

\indexlibrary{move\tcode{move}}%
\begin{itemdecl}
template<class InputIterator, class OutputIterator>
  OutputIterator move(InputIterator first, InputIterator last,
                      OutputIterator result);
\end{itemdecl}


\begin{itemdescr}
\pnum
\effects
Moves elements in the range \range{first}{last}
into the range \range{result}{result + (last - first)}
starting from first and proceeding to last.
For each non-negative integer
\tcode{n < (last-first)},
performs
\tcode{*(result + n)} \tcode{= std::move(*(first + n))}.

\pnum
\returns
\tcode{result + (last - first)}.

\pnum
\requires
\tcode{result}
shall not be in the range
\range{first}{last}.

\pnum
\complexity
Exactly
\tcode{last - first}
move assignments.
\end{itemdescr}

\indexlibrary{\idxcode{move_backward}}%
\begin{itemdecl}
template<class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2
    move_backward(BidirectionalIterator1 first,
                  BidirectionalIterator1 last,
                  BidirectionalIterator2 result);
\end{itemdecl}


\begin{itemdescr}
\pnum
\effects
Moves elements in the range \range{first}{last}
into the
range \range{result - (last-first)}{result}
starting from
\tcode{last - 1}
and proceeding to first.\footnote{\tcode{move_backward}
should be used instead of move when last
is in
the range
\range{result - (last - first)}{result}.}
For each positive integer
\tcode{n <= (last - first)},
performs
\tcode{*(result - n) = std::move(*(last - n))}.

\pnum
\requires
\tcode{result}
shall not be in the range
\brange{first}{last}.

\pnum
\returns
\tcode{result - (last - first)}.

\pnum
\complexity
Exactly
\tcode{last - first}
assignments.
\end{itemdescr}

\rSec2[alg.swap]{swap}

\indexlibrary{\idxcode{swap_ranges}}%
\begin{itemdecl}
template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2
    swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                ForwardIterator2 first2);
\end{itemdecl}


\begin{itemdescr}
\pnum
\effects
For each non-negative integer
\tcode{n < (last1 - first1)}
performs:
\tcode{swap(*(first1 + n), \brk{}*(first2 + n))}.

\pnum
\requires
The two ranges \range{first1}{last1}
and
\range{first2}{first2 + (last1 - first1)}
shall not overlap.
\tcode{*(first1 + n)} shall be swappable with~(\ref{swappable.requirements})
\tcode{*(first2 + n)}.

\pnum
\returns
\tcode{first2 + (last1 - first1)}.

\pnum
\complexity
Exactly
\tcode{last1 - first1}
swaps.
\end{itemdescr}

\indexlibrary{\idxcode{iter_swap}}%
\begin{itemdecl}
template<class ForwardIterator1, class ForwardIterator2>
  void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
\end{itemdecl}


\begin{itemdescr}
\pnum
\effects
\tcode{swap(*a, *b)}.

\pnum
\requires
\tcode{a} and \tcode{b} shall be dereferenceable. \tcode{*a} shall be
swappable with~(\ref{swappable.requirements}) \tcode{*b}.
\end{itemdescr}

\rSec2[alg.transform]{Transform}

\indexlibrary{\idxcode{transform}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Assigns through every iterator
\tcode{i}
in the range
\range{result}{result + (last1 - first1)}
a new
corresponding value equal to
\tcode{op(*(first1 + (i - result))}
or
\tcode{binary_op(*(first1 + (i - result)), *(first2 + (i - result)))}.

\pnum
\requires
\tcode{op} and \tcode{binary_op}
shall not invalidate iterators or subranges, or modify elements in the ranges
\crange{first1}{last1},
\crange{first2}{first2 + (last1 - first1)},
and
\crange{result}
{result + (last1 - first1)}.\footnote{The use of fully
closed ranges is intentional.}

\pnum
\returns
\tcode{result + (last1 - first1)}.

\pnum
\complexity
Exactly
\tcode{last1 - first1}
applications of
\tcode{op} or \tcode{binary_op}.

\pnum
\notes
\tcode{result} may be equal to \tcode{first}
in case of unary transform,
or to \tcode{first1} or \tcode{first2}
in case of binary transform.
\end{itemdescr}

\rSec2[alg.replace]{Replace}

\indexlibrary{\idxcode{replace}}%
\indexlibrary{\idxcode{replace_if}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The expression
\tcode{*first = new_value}
shall be valid.

\pnum
\effects
Substitutes elements referred by the iterator
\tcode{i}
in the range \range{first}{last}
with \tcode{new_value},
when the following corresponding conditions hold:
\tcode{*i == old_value}, \tcode{pred(*i) != false}.

\pnum
\complexity
Exactly
\tcode{last - first}
applications of the corresponding predicate.
\end{itemdescr}

\indexlibrary{\idxcode{replace_copy}}%
\indexlibrary{\idxcode{replace_copy_if}}%
\begin{itemdecl}
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 InputIterator, class OutputIterator, class Predicate, class T>
  OutputIterator
    replace_copy_if(InputIterator first, InputIterator last,
                    OutputIterator result,
                    Predicate pred, const T& new_value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The results of the expressions
\tcode{*first}
and
\tcode{new_value}
shall be writable to the
\tcode{result}
output iterator.
The ranges
\range{first}{last}
and
\range{result}{result + (last - first)}
shall not overlap.

\pnum
\effects
Assigns to every iterator
\tcode{i}
in the
range
\range{result}{result + (last - first)}
either
\tcode{new_value}
or
\tcode{*\brk(first + (i - result))}
depending on whether the following corresponding conditions hold:

\begin{codeblock}
*(first + (i - result)) == old_value
pred(*(first + (i - result))) != false
\end{codeblock}

\pnum
\returns
\tcode{result + (last - first)}.

\pnum
\complexity
Exactly
\tcode{last - first}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.fill]{Fill}

\indexlibrary{\idxcode{fill}}%
\indexlibrary{\idxcode{fill_n}}%
\begin{itemdecl}
template<class ForwardIterator, class T>
  void fill(ForwardIterator first, ForwardIterator last, const T& value);

template<class OutputIterator, class Size, class T>
  OutputIterator fill_n(OutputIterator first, Size n, const T& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The expression
\tcode{value}
shall be writable to the output iterator. The type
\tcode{Size}
shall be convertible to an integral type~(\ref{conv.integral}, \ref{class.conv}).

\pnum
\effects
The first algorithm assigns \tcode{value} through all the iterators in the range
\range{first}{last}. The second algorithm assigns \tcode{value}
through all the iterators in the range \range{first}{first + n}
if \tcode{n} is positive, otherwise it does nothing.

\pnum
\returns \tcode{fill_n} returns \tcode{first + n} for non-negative values of \tcode{n}
and \tcode{first} for negative values.

\pnum
\complexity
Exactly
\tcode{last - first},
\tcode{n}, or 0 assignments, respectively.
\end{itemdescr}

\rSec2[alg.generate]{Generate}

\indexlibrary{\idxcode{generate}}%
\indexlibrary{\idxcode{generate_n}}%
\begin{itemdecl}
template<class ForwardIterator, class Generator>
  void generate(ForwardIterator first, ForwardIterator last,
                Generator gen);

template<class OutputIterator, class Size, class Generator>
  OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
The first algorithm invokes the function object \tcode{gen} and assigns the return
value of \tcode{gen} through all the iterators in the range
\range{first}{last}. The second algorithm invokes the function object
\tcode{gen} and assigns the return value of \tcode{gen} through all the iterators in
the range \range{first}{first + n} if \tcode{n} is positive,
otherwise it does nothing.

\pnum
\requires
\tcode{gen} takes no arguments,
\tcode{Size}
shall be convertible to an integral type~(\ref{conv.integral}, \ref{class.conv}).

\pnum
\returns \tcode{generate_n} returns \tcode{first + n} for non-negative values of \tcode{n}
and \tcode{first} for negative values.

\pnum
\complexity
Exactly
\tcode{last - first},
\tcode{n}, or 0
invocations of \tcode{gen} and assignments, respectively.
\end{itemdescr}

\rSec2[alg.remove]{Remove}

\indexlibrary{\idxcode{remove}}%
\indexlibrary{\idxcode{remove_if}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The type of
\tcode{*first}
shall satisfy the \tcode{MoveAssignable}
requirements (Table~\ref{moveassignable}).

\pnum
\effects
Eliminates all the elements referred to by iterator
\tcode{i}
in the range \range{first}{last}
for which the following corresponding conditions hold:
\tcode{*i == value, pred(*i) != false}.

\pnum
\returns
The end of the resulting range.

\pnum
\notes
Stable.

\pnum
\complexity
Exactly
\tcode{last - first}
applications of the corresponding predicate.

\pnum
\realnote each element in the range \range{ret}{last}, where \tcode{ret} is
the returned value, has a valid but unspecified state, because the algorithms
can eliminate elements by swapping with or moving from elements that were originally
in that range.
\end{itemdescr}

\indexlibrary{\idxcode{remove_copy}}%
\indexlibrary{\idxcode{remove_copy_if}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The ranges
\range{first}{last}
and
\range{result}{result + (last - first)}
shall not overlap. The expression \tcode{*result = *first} shall ve valid.

\pnum
\effects
Copies all the elements referred to by the iterator
\tcode{i}
in the range
\range{first}{last}
for which the following corresponding conditions do not hold:
\tcode{*i == value, pred(*i) != false}.

\pnum
\returns
The end of the resulting range.

\pnum
\complexity
Exactly
\tcode{last - first}
applications of the corresponding predicate.

\pnum
\notes
Stable.
\end{itemdescr}

\rSec2[alg.unique]{Unique}

\indexlibrary{\idxcode{unique}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                         BinaryPredicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
For a nonempty range, eliminates all but the first element from every
consecutive group of equivalent elements referred to by the iterator
\tcode{i}
in the range
\range{first + 1}{last}
for which the following conditions hold:
\tcode{*(i - 1) == *i}
or
\tcode{pred(*(i - 1), *i) != false}.

\pnum
\requires
The comparison function shall be an equivalence relation.
The type of \tcode{*first} shall satisfy the
\tcode{MoveAssignable} requirements (Table~\ref{moveassignable}).

\pnum
\returns
The end of the resulting range.

\pnum
\complexity
For nonempty ranges, exactly
\tcode{(last - first) - 1}
applications of the corresponding predicate.
\end{itemdescr}

\indexlibrary{\idxcode{unique_copy}}%
\begin{itemdecl}
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);
\end{itemdecl}


\begin{itemdescr}
\pnum
\requires
The comparison function shall be an equivalence relation.
The ranges
\range{first}{last}
and
\range{result}{result+(last-first)}
shall not overlap. The expression
\tcode{*result = *first}
shall be valid. If neither
\tcode{InputIterator}
nor
\tcode{OutputIterator}
meets the requirements of forward iterator then the value type of
\tcode{InputIterator}
shall be \tcode{CopyConstructible} (Table~\ref{copyconstructible}) and
\tcode{CopyAssignable} (Table~\ref{copyassignable}).
Otherwise \tcode{CopyConstructible} is not required.

\pnum
\effects
Copies only the first element from every consecutive group of equal elements referred to by
the iterator
\tcode{i}
in the range
\range{first}{last}
for which the following corresponding conditions hold:
\tcode{*i == *(i - 1)}
or
\tcode{pred(*i, *(i - 1)) != false}.

\pnum
\returns
The end of the resulting range.

\pnum
\complexity
For nonempty ranges, exactly
\tcode{last - first - 1}
applications of the corresponding predicate.
\end{itemdescr}

\rSec2[alg.reverse]{Reverse}

\indexlibrary{\idxcode{reverse}}%
\begin{itemdecl}
template<class BidirectionalIterator>
  void reverse(BidirectionalIterator first, BidirectionalIterator last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
For each non-negative integer
\tcode{i <= (last - first)/2},
applies
\tcode{iter_swap}
to all pairs of iterators
\tcode{first + i, (last - i) - 1}.

\pnum
\requires
\tcode{*first} shall be swappable~(\ref{swappable.requirements}).

\pnum
\complexity
Exactly
\tcode{(last - first)/2}
swaps.
\end{itemdescr}

\indexlibrary{\idxcode{reverse_copy}}%
\begin{itemdecl}
template<class BidirectionalIterator, class OutputIterator>
  OutputIterator
    reverse_copy(BidirectionalIterator first,
                 BidirectionalIterator last, OutputIterator result);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Copies the range
\range{first}{last}
to the range
\range{result}{result+(last-first)}
such that
for any non-negative integer
\tcode{i < (last - first)}
the following assignment takes place:
\tcode{*(result + (last - first) - i) = *(first + i)}.

\pnum
\requires
The ranges
\range{first}{last}
and
\range{result}{result+(last-first)}
shall not overlap.

\pnum
\returns
\tcode{result + (last - first)}.

\pnum
\complexity
Exactly
\tcode{last - first}
assignments.
\end{itemdescr}

\rSec2[alg.rotate]{Rotate}

\indexlibrary{\idxcode{rotate}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
              ForwardIterator last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
For each non-negative integer
\tcode{i < (last - first)},
places the element from the position
\tcode{first + i}
into position
\tcode{first + (i + (last - middle)) \% (last - first)}.

\pnum
\returns \tcode{first + (last - middle)}.

\pnum
\notes
This is a left rotate.

\pnum
\requires
\range{first}{middle}
and
\range{middle}{last}
shall be valid ranges.
\tcode{ForwardIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type of \tcode{*first} shall satisfy
the requirements of \tcode{MoveConstructible}
(Table~\ref{moveconstructible}) and the
requirements of
\tcode{MoveAssignable}
(Table~\ref{moveassignable}).


\pnum
\complexity
At most
\tcode{last - first}
swaps.
\end{itemdescr}

\indexlibrary{\idxcode{rotate_copy}}%
\begin{itemdecl}
template<class ForwardIterator, class OutputIterator>
  OutputIterator
    rotate_copy(ForwardIterator first, ForwardIterator middle,
                ForwardIterator last, OutputIterator result);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Copies the range
\range{first}{last}
to the range
\range{result}{result + (last - first)}
such that for each non-negative integer
\tcode{i < (last - first)}
the following assignment takes place:
\tcode{*(result + i) =  *(first +
(i + (middle - first)) \% (last - first))}.

\pnum
\returns
\tcode{result + (last - first)}.

\pnum
\requires
The ranges
\range{first}{last}
and
\range{result}{result + (last - first)}
shall not overlap.

\pnum
\complexity
Exactly
\tcode{last - first}
assignments.
\end{itemdescr}

\rSec2[alg.random.shuffle]{Random shuffle}

\indexlibrary{\idxcode{random_shuffle}}%
\indexlibrary{\idxcode{shuffle}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void random_shuffle(RandomAccessIterator first,
                      RandomAccessIterator last);

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

template<class RandomAccessIterator, class UniformRandomNumberGenerator>
  void shuffle(RandomAccessIterator first,
                      RandomAccessIterator last,
                      UniformRandomNumberGenerator&& g);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Permutes the elements in the range
\range{first}{last}
such that each possible permutation of those elements has equal probability of appearance.

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The random number
generating function object \tcode{rand} shall have a return type that is
convertible to \tcode{iterator_traits<RandomAccessItera\-tor>::difference_type},
and the call \tcode{rand(n)} shall return a randomly chosen value in the
interval \range{0}{n}, for \tcode{n > 0} of type
\tcode{iterator_traits<Random\-Access\-Itera\-tor>::difference_type}. The type
\tcode{UniformRandomNumberGenerator} shall meet the requirements of a uniform
random number generator~(\ref{rand.req.urng}) type whose return type is
convertible to
\tcode{iterator_traits<Random\-Access\-Itera\-tor>::difference_type}.

\pnum
\complexity
Exactly
\tcode{(last - first) - 1}
swaps.

\pnum
\notes
To the extent that the implementation of these functions makes use of random numbers, the implementation shall use the following sources of randomness:

The underlying source of random numbers for the first form of the function
is \impldef{underlying source of random numbers for \tcode{random_shuffle}}. An implementation may use the
\tcode{rand}
function from the standard C library.

In the second form of the function, the
 function object
\tcode{rand} shall serve as the implementation's source of randomness.

In the third \tcode{shuffle} form of the function, the object \tcode{g} shall serve as the implementation's source of randomness.

\end{itemdescr}

\rSec2[alg.partitions]{Partitions}

\indexlibrary{\idxcode{is_partitioned}}%
\begin{itemdecl}
template <class InputIterator, class Predicate>
  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{InputIterator}'s value type shall be convertible to \tcode{Predicate}'s argument type.

\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\range{first}{last} is partitioned by \tcode{pred}, i.e. if all elements that satisfy \tcode{pred} appear before those that do not.

\pnum
\complexity Linear. At most \tcode{last - first} applications of \tcode{pred}.
\end{itemdescr}

\indexlibrary{\idxcode{partition}}%
\begin{itemdecl}
template<class ForwardIterator, class Predicate>
  ForwardIterator
    partition(ForwardIterator first,
              ForwardIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Places all the elements in the range \range{first}{last} that satisfy \tcode{pred} before all the elements that do not satisfy it.

\pnum
\returns An iterator \tcode{i} such that for any iterator \tcode{j} in the range \range{first}{i} \tcode{pred(*j) != false}, and for any iterator \tcode{k} in the range \range{i}{last}, \tcode{pred(*k) == false}.

\pnum
\requires
\tcode{ForwardIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}).

\pnum
\complexity If ForwardIterator meets the requirements for a BidirectionalIterator, at most
\tcode{(last - first) / 2} swaps are done; otherwise at most \tcode{last - first} swaps
are done. Exactly \tcode{last - first} applications of the predicate are done.
\end{itemdescr}

\indexlibrary{\idxcode{stable_partition}}%
\begin{itemdecl}
template<class BidirectionalIterator, class Predicate>
  BidirectionalIterator
    stable_partition(BidirectionalIterator first,
                     BidirectionalIterator last, Predicate pred);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Places all the elements in the range
\range{first}{last}
that satisfy \tcode{pred} before all the
elements that do not satisfy it.

\pnum
\returns
An iterator
\tcode{i}
such that for any iterator
\tcode{j}
in the range
\range{first}{i},
\tcode{pred(*j) != false},
and for any iterator
\tcode{k}
in the range
\range{i}{last},
\tcode{pred(*k) == false}.
The relative order of the elements in both groups is preserved.

\pnum
\requires
\tcode{BidirectionalIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).

\pnum
\complexity
At most
\tcode{(last - first) * log(last - first)}
swaps, but only linear number of swaps if there is enough extra memory.
Exactly
\tcode{last - first}
applications of the predicate.
\end{itemdescr}

\indexlibrary{\idxcode{partition_copy}}%
\begin{itemdecl}
template <class InputIterator, class OutputIterator1,
          class OutputIterator2, class Predicate>
  pair<OutputIterator1, OutputIterator2>
  partition_copy(InputIterator first, InputIterator last,
                 OutputIterator1 out_true, OutputIterator2 out_false,
                 Predicate pred);
\end{itemdecl}


\begin{itemdescr}
\pnum
\requires \tcode{InputIterator}'s value type shall be Assignable, and shall be writable to the \tcode{out_true} and \tcode{out_false} \tcode{OutputIterator}s, and shall be convertible to \tcode{Predicate}'s argument type. The input range shall not overlap with either of the output ranges.

\pnum
\effects For each iterator \tcode{i} in \range{first}{last}, copies \tcode{*i} to the output range beginning with \tcode{out_true} if \tcode{pred(*i)} is \tcode{true}, or to the output range beginning with \tcode{out_false} otherwise.

\pnum
\returns A pair \tcode{p} such that \tcode{p.first} is the end of the output range beginning at \tcode{out_true} and \tcode{p.second} is the end of the output range beginning at \tcode{out_false}.

\pnum
\complexity Exactly \tcode{last - first} applications of \tcode{pred}.
\end{itemdescr}

\indexlibrary{\idxcode{partition_point}}%
\begin{itemdecl}
template<class ForwardIterator, class Predicate>
  ForwardIterator partition_point(ForwardIterator first,
                                  ForwardIterator last,
                                  Predicate pred);
\end{itemdecl}


\begin{itemdescr}
\pnum
\requires \tcode{ForwardIterator}'s value type shall be convertible to \tcode{Predicate}'s argument type. \range{first}{last} shall be partitioned by \tcode{pred}, i.e. all elements that satisfy \tcode{pred} shall appear before those that do not.

\pnum
\returns An iterator \tcode{mid} such that \tcode{all_of(first, mid, pred)} and \tcode{none_of(mid, last, pred)} are both true.

\pnum
\complexity \bigoh{log(last - first)} applications of \tcode{pred}.
\end{itemdescr}


\rSec1[alg.sorting]{Sorting and related operations}

\pnum
All the operations in~\ref{alg.sorting} have two versions: one that takes a function object of type
\tcode{Compare}
and one that uses an
\tcode{operator<}.

\pnum
\tcode{Compare}
is a function object
type~(\ref{function.objects}). The return value of the function call operation applied to
an object of type \tcode{Compare}, when contextually converted to \tcode{bool}~(\ref{conv}),
yields \tcode{true} if the first argument of the call
is less than the second, and
\tcode{false}
otherwise.
\tcode{Compare comp}
is used throughout for algorithms assuming an ordering relation.
It is assumed that
\tcode{comp}
will not apply any non-constant function through the dereferenced iterator.

\pnum
For all algorithms that take
\tcode{Compare},
there is a version that uses
\tcode{operator<}
instead.
That is,
\tcode{comp(*i, *j) != false}
defaults to
\tcode{*i < *j != false}.
For algorithms other than those described in~\ref{alg.binary.search} to work correctly,
\tcode{comp} has to induce a strict weak ordering on the values.

\pnum
The term
\techterm{strict}
refers to the
requirement of an irreflexive relation (\tcode{!comp(x, x)} for all \tcode{x}),
and the term
\techterm{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
\tcode{equiv(a, b)}
as
\tcode{!comp(a, b) \&\& !comp(b, a)},
then the requirements are that
\tcode{comp}
and
\tcode{equiv}
both be transitive  relations:

\begin{itemize}
\item
\tcode{comp(a, b) \&\& comp(b, c)}
implies
\tcode{comp(a, c)}
\item
\tcode{equiv(a, b) \&\& equiv(b, c)}
implies
\tcode{equiv(a, c)}
\enternote
Under these conditions, it can be shown that
\begin{itemize}
\item
\tcode{equiv}
is an equivalence relation
\item
\tcode{comp}
induces a well-defined relation on the equivalence
classes determined by
\tcode{equiv}
\item
The induced relation is a strict total ordering.
\exitnote
\end{itemize}
\end{itemize}

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

\pnum
A sequence
\range{start}{finish}
is
\techterm{partitioned with respect to an expression}
\tcode{f(e)}
if there exists an integer
\tcode{n}
such that for all
\tcode{0 <= i < distance(start, finish)},
\tcode{f(*(start + i))}
is true if and only if
\tcode{i < n}.

\pnum
In the descriptions of the functions that deal with ordering relationships we frequently use a notion of
equivalence to describe concepts such as stability.
The equivalence to which we refer is not necessarily an
\tcode{operator==},
but an equivalence relation induced by the strict weak ordering.
That is, two elements
\tcode{a}
and
\tcode{b}
are considered equivalent if and only if
\tcode{!(a < b) \&\& !(b < a)}.

\rSec2[alg.sort]{Sorting}

\rSec3[sort]{\tcode{sort}}

\indexlibrary{\idxcode{sort}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void sort(RandomAccessIterator first, RandomAccessIterator last,
            Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Sorts the elements in the range
\range{first}{last}.

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).

\pnum
\complexity
\bigoh{N\log(N)}
(where
\tcode{$N$ == last - first})
comparisons.
\end{itemdescr}

\rSec3[stable.sort]{\tcode{stable_sort}}

\indexlibrary{\idxcode{stable_sort}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Sorts the elements in the range \range{first}{last}.

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\complexity
It does at most $N \log^2(N)$
(where
\tcode{$N$ == last - first})
comparisons; if enough extra memory is available, it is
$N \log(N)$.

\pnum
\notes
Stable.
\end{itemdescr}

\rSec3[partial.sort]{\tcode{partial_sort}}

\indexlibrary{\idxcode{partial_sort}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Places the first
\tcode{middle - first}
sorted elements from the range
\range{first}{last}
into the range
\range{first}{middle}.
The rest of the elements in the range
\range{middle}{last}
are placed in an unspecified order.
\indextext{unspecified}%

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\complexity
It takes approximately
\tcode{(last - first) * log(middle - first)}
comparisons.
\end{itemdescr}

\rSec3[partial.sort.copy]{\tcode{partial_sort_copy}}

\indexlibrary{\idxcode{partial_sort_copy}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Places the first
\tcode{min(last - first, result_last - result_first)}
sorted elements into the range
\range{result_first}{result_first + min(last - first, result_last - result_first)}.

\pnum
\returns
The smaller of:
\tcode{result_last} or
\tcode{result_first + (last - first)}.

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*result_first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{Move\-Assignable} (Table~\ref{moveassignable}).


\pnum
\complexity
Approximately
\tcode{(last - first) * log(min(last - first, result_last - result_first))}
comparisons.
\end{itemdescr}

\rSec3[is.sorted]{\tcode{is_sorted}}

\indexlibrary{\idxcode{is_sorted}}%
\begin{itemdecl}
template<class ForwardIterator>
  bool is_sorted(ForwardIterator first, ForwardIterator last);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns \tcode{is_sorted_until(first, last) == last}
\end{itemdescr}

\indexlibrary{\idxcode{is_sorted}}%
\begin{itemdecl}
template<class ForwardIterator, class Compare>
  bool is_sorted(ForwardIterator first, ForwardIterator last,
    Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns \tcode{is_sorted_until(first, last, comp) == last}
\end{itemdescr}

\indexlibrary{\idxcode{is_sorted_until}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
    Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns If \tcode{distance(first, last) < 2}, returns
\tcode{last}. Otherwise, returns
the last iterator \tcode{i} in \crange{first}{last} for which the
range \range{first}{i} is sorted.

\pnum
\complexity Linear.
\end{itemdescr}

\rSec2[alg.nth.element]{Nth element}

\indexlibrary{\idxcode{nth_element}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
After
\tcode{nth_element}
the element in the position pointed to by \tcode{nth}
is the element that would be
in that position if the whole range were sorted.
Also for any iterator
\tcode{i}
in the range
\range{first}{nth}
and any iterator
\tcode{j}
in the range
\range{nth}{last}
it holds that:
\tcode{!(*i > *j)}
or
\tcode{comp(*j, *i) == false}.

\pnum
\requires
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\complexity
Linear on average.
\end{itemdescr}

\rSec2[alg.binary.search]{Binary search}

\pnum
All of the algorithms in this section are versions of binary search
and assume that the sequence being searched is partitioned with respect to
an expression formed by binding the search key to an argument of 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 appropriate for random access iterators,
because these algorithms do a logarithmic number of steps
through the data structure.
For non-random access iterators they execute a linear number of steps.

\rSec3[lower.bound]{\tcode{lower_bound}}

\indexlibrary{\idxcode{lower_bound}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The elements
\tcode{e}
of
\range{first}{last}
shall be partitioned with respect to the expression
\tcode{e < value}
or
\tcode{comp(e, value)}.

\pnum
\returns
The furthermost iterator
\tcode{i}
in the range
\crange{first}{last}
such that for any iterator
\tcode{j}
in the range
\range{first}{i}
the following corresponding conditions hold:
\tcode{*j < value}
or
\tcode{comp(*j, value) != false}.

\pnum
\complexity
At most
$\log_2(last - first) + \bigoh{1}$
comparisons.
\end{itemdescr}

\rSec3[upper.bound]{\tcode{upper_bound}}

\indexlibrary{\idxcode{upper_bound}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The elements
\tcode{e}
of
\range{first}{last}
shall be partitioned with respect to the expression
\tcode{!(value < e)}
or
\tcode{!comp(\brk{}value, e)}.

\pnum
\returns
The furthermost iterator
\tcode{i}
in the range
\crange{first}{last}
such that for any iterator
\tcode{j}
in the range
\range{first}{i}
the following corresponding conditions hold:
\tcode{!(value < *j)}
or
\tcode{comp(value, *j) == false}.

\pnum
\complexity
At most
$\log_2(last - first) + \bigoh{1}$
comparisons.
\end{itemdescr}

\rSec3[equal.range]{\tcode{equal_range}}

\indexlibrary{\idxcode{equal_range}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The elements
\tcode{e}
of
\range{first}{last}
shall be partitioned with respect to the expressions
\tcode{e < value}
and
\tcode{!(value < e)}
or
\tcode{comp(e, value)}
and
\tcode{!comp(value, e)}.
Also, for all elements
\tcode{e}
of
\tcode{[first, last)},
\tcode{e < value}
shall imply
\tcode{!(value < e)}
or
\tcode{comp(e, value)}
shall imply
\tcode{!comp(value, e)}.

\pnum
\returns
\begin{codeblock}
make_pair(lower_bound(first, last, value),
          upper_bound(first, last, value))
\end{codeblock}
or
\begin{codeblock}
make_pair(lower_bound(first, last, value, comp),
          upper_bound(first, last, value, comp))
\end{codeblock}

\pnum
\complexity
At most
$2 * \log_2(last - first) + \bigoh{1}$
comparisons.
\end{itemdescr}

\rSec3[binary.search]{\tcode{binary_search}}

\indexlibrary{\idxcode{binary_search}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The elements
\tcode{e}
of
\range{first}{last}
are partitioned with respect to the expressions
\tcode{e < value}
and
\tcode{!(value < e)}
or
\tcode{comp(e, value)}
and
\tcode{!comp(value, e)}.
Also, for all elements
\tcode{e}
of
\tcode{[first, last)},
\tcode{e < value}
implies
\tcode{!(value < e)}
or
\tcode{comp(e, value)}
implies
\tcode{!comp(value, e)}.

\pnum
\returns
\tcode{true}
if there is an iterator
\tcode{i}
in the range
\range{first}{last}
that satisfies the corresponding conditions:
\tcode{!(*i < value) \&\& !(value < *i)}
or
\tcode{comp(*i, value) == false \&\& comp(value, *i) == false}.

\pnum
\complexity
At most
\tcode{log2(last - first)} + \bigoh{1}
comparisons.
\end{itemdescr}

\rSec2[alg.merge]{Merge}

\indexlibrary{\idxcode{merge}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects\ Copies all the elements of the two ranges \range{first1}{last1} and
\range{first2}{last2} into the range \range{result}{result_last}, where \tcode{result_last}
is \tcode{result + (last1 - first1) + (last2 - first2)}, such that the resulting range satisfies
\tcode{is_sorted(result, result_last)} or \tcode{is_sorted(result, result_last, comp)}, respectively.

\pnum
\requires The ranges \range{first1}{last1} and \range{first2}{last2} shall be
sorted with respect to \tcode{operator<} or \tcode{comp}.
The resulting range shall not overlap with either of the original ranges.

\pnum
\returns
\tcode{result + (last1 - first1) + (last2 - first2)}.

\pnum
\complexity
At most
\tcode{(last1 - first1) + (last2 - first2) - 1}
comparisons.

\pnum
\notes
Stable.
\end{itemdescr}

\indexlibrary{\idxcode{inplace_merge}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Merges two sorted consecutive ranges
\range{first}{middle}
and
\range{middle}{last},
putting the result of the merge into the range
\range{first}{last}.
The resulting range will be in non-decreasing order;
that is, for every iterator
\tcode{i}
in
\range{first}{last}
other than
\tcode{first},
the condition
\tcode{*i < *(i - 1)}
or, respectively,
\tcode{comp(*i, *(i - 1))}
will be false.

\pnum
\requires
The ranges \range{first}{middle} and \range{middle}{last} shall be
sorted with respect to \tcode{operator<} or \tcode{comp}.
\tcode{BidirectionalIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\complexity
When enough additional memory is available,
\tcode{(last - first) - 1}
comparisons.
If no additional memory is available, an algorithm with complexity
$N \log(N)$
(where
\tcode{N}
is equal to
\tcode{last - first})
may be used.

\pnum
\notes
Stable.
\end{itemdescr}

\rSec2[alg.set.operations]{Set operations on sorted structures}

\pnum
This section defines all the basic set operations on sorted structures.
They also work with
\tcode{multiset}s~(\ref{multiset})
containing multiple copies of equivalent elements.
The semantics of the set operations are generalized to
\tcode{multiset}s
in a standard way by defining
\tcode{set_union()}
to contain the maximum number of occurrences of every element,
\tcode{set_intersection()}
to contain the minimum, and so on.

\rSec3[includes]{\tcode{includes}}

\indexlibrary{\idxcode{includes}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if \range{first2}{last2} is empty or
if every element in the range
\range{first2}{last2}
is contained in the range
\range{first1}{last1}.
Returns
\tcode{false}
otherwise.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
comparisons.
\end{itemdescr}

\rSec3[set.union]{\tcode{set_union}}

\indexlibrary{\idxcode{set_union}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\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.

\pnum
\requires
The resulting range shall not overlap with either of the original ranges.

\pnum
\returns
The end of the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
comparisons.

\pnum
\notes If \range{first1}{last1} contains $m$ elements that are equivalent to
each other and \range{first2}{last2} contains $n$ elements that are equivalent
to them, then all $m$ elements from the first range shall be copied to the output
range, in order, and then $\max(n - m, 0)$ elements from the second range shall
be copied to the output range, in order.
\end{itemdescr}

\rSec3[set.intersection]{\tcode{set_intersection}}

\indexlibrary{\idxcode{set_intersection}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\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.

\pnum
\requires
The resulting range shall not overlap with either of the original ranges.

\pnum
\returns
The end of the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
comparisons.

\pnum
\notes If \range{first1}{last1} contains $m$ elements that are equivalent to
each other and \range{first2}{last2} contains $n$ elements that are equivalent
to them, the first $\min(m, n)$ elements shall be copied from the first range
to the output range, in order.
\end{itemdescr}

\rSec3[set.difference]{\tcode{set_difference}}

\indexlibrary{\idxcode{set_difference}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Copies the elements of the range
\range{first1}{last1}
which are not present in the range
\range{first2}{last2}
to the range beginning at
\tcode{result}.
The elements in the constructed range are sorted.

\pnum
\requires
The resulting range shall not overlap with either of the original ranges.

\pnum
\returns
The end of the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
comparisons.

\pnum
\notes
If
\range{first1}{last1}
contains $m$
elements that are equivalent to each other and
\range{first2}{last2}
contains $n$
elements that are equivalent to them, the last
$\max(m - n, 0)$
elements from
\range{first1}{last1}
shall be copied to the output range.
\end{itemdescr}

\rSec3[set.symmetric.difference]{\tcode{set_symmetric_difference}}

\indexlibrary{\idxcode{set_symmetric_difference}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Copies the elements of the range
\range{first1}{last1}
that are not present in the range
\range{first2}{last2},
and the elements of the range
\range{first2}{last2}
that are not present in the range
\range{first1}{last1}
to the range beginning at
\tcode{result}.
The elements in the constructed range are sorted.

\pnum
\requires
The resulting range shall not overlap with either of the original ranges.

\pnum
\returns
The end of the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
comparisons.

\pnum
\notes
If \range{first1}{last1} contains $m$ elements that are equivalent to each other and
\range{first2}{last2} contains $n$ elements that are equivalent to them, then
$|m - n|$ of those elements shall be copied to the output range: the last
$m - n$ of these elements from \range{first1}{last1} if $m > n$, and the last 
$n - m$ of these elements from \range{first2}{last2} if $m < n$.
\end{itemdescr}

\rSec2[alg.heap.operations]{Heap operations}

\pnum
A
\techterm{heap}
is a particular organization of elements in a range between two random access iterators
\range{a}{b}.
Its two key properties are:

\begin{description}
\item{(1)} There is no element greater than
\tcode{*a}
in the range and
\item{(2)} \tcode{*a}
may be removed by
\tcode{pop_heap()},
or a new element added by
\tcode{push_heap()},
in
$\mathcal{O}(\log(N))$
time.
\end{description}

\pnum
These properties make heaps useful as priority queues.

\pnum
\tcode{make_heap()}
converts a range into a heap and
\tcode{sort_heap()}
turns a heap into a sorted sequence.

\rSec3[push.heap]{\tcode{push_heap}}

\indexlibrary{\idxcode{push_heap}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Places the value in the location
\tcode{last - 1}
into the resulting heap
\range{first}{last}.

\pnum
\requires
The range
\range{first}{last - 1}
shall be a valid heap.
The type of \tcode{*first} shall satisfy
the \tcode{MoveConstructible} requirements
(Table~\ref{moveconstructible}) and the
\tcode{MoveAssignable} requirements
(Table~\ref{moveassignable}).


\pnum
\complexity
At most
\tcode{log(last - first)}
comparisons.
\end{itemdescr}

\rSec3[pop.heap]{\tcode{pop_heap}}

\indexlibrary{\idxcode{pop_heap}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The range
\range{first}{last}
shall be a valid non-empty heap.
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\effects
Swaps the value in the location \tcode{first}
with the value in the location
\tcode{last - 1}
and makes
\range{first}{last - 1}
into a heap.

\pnum
\complexity
At most
\tcode{2 * log(last - first)}
comparisons.
\end{itemdescr}

\rSec3[make.heap]{\tcode{make_heap}}

\indexlibrary{\idxcode{make_heap}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs a heap out of the range
\range{first}{last}.

\pnum
\requires The type of \tcode{*first} shall satisfy
the \tcode{MoveConstructible} requirements
(Table~\ref{moveconstructible}) and the
\tcode{MoveAssignable} requirements
(Table~\ref{moveassignable}).

\pnum
\complexity
At most
\tcode{3 * (last - first)}
comparisons.
\end{itemdescr}

\rSec3[sort.heap]{\tcode{sort_heap}}

\indexlibrary{\idxcode{sort_heap}}%
\begin{itemdecl}
template<class RandomAccessIterator>
  void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
  void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Sorts elements in the heap
\range{first}{last}.

\pnum
\requires The range \range{first}{last} shall be a valid heap.
\tcode{RandomAccessIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}). The type
of \tcode{*first} shall satisfy the requirements of
\tcode{MoveConstructible} (Table~\ref{moveconstructible}) and of
\tcode{MoveAssignable} (Table~\ref{moveassignable}).


\pnum
\complexity
At most $N \log(N)$
comparisons (where
\tcode{N == last - first}).
\end{itemdescr}

\rSec3[is.heap]{\tcode{is_heap}}

\indexlibrary{\idxcode{is_heap}}%
\begin{itemdecl}
  template<class RandomAccessIterator>
    bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns \tcode{is_heap_until(first, last) == last}
\end{itemdescr}

\indexlibrary{\idxcode{is_heap}}%
\begin{itemdecl}
  template<class RandomAccessIterator, class Compare>
    bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns \tcode{is_heap_until(first, last, comp) == last}
\end{itemdescr}

\indexlibrary{\idxcode{is_heap_until}}%
\begin{itemdecl}
  template<class RandomAccessIterator>
    RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
  template<class RandomAccessIterator, class Compare>
    RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
      Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns If \tcode{distance(first, last) < 2}, returns
\tcode{last}. Otherwise, returns
the last iterator \tcode{i} in \crange{first}{last} for which the
range \range{first}{i} is a heap.

\pnum
\complexity Linear.
\end{itemdescr}


\rSec2[alg.min.max]{Minimum and maximum}

\indexlibrary{\idxcode{min}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
Type
\tcode{T}
is
\tcode{LessThanComparable} (Table~\ref{lessthancomparable}).

\pnum
\returns
The smaller value.

\pnum
\notes
Returns the first argument when the arguments are equivalent.
\end{itemdescr}

\indexlibrary{\idxcode{min}}%
\begin{itemdecl}
template<class T>
  T min(initializer_list<T> t);
template<class T, class Compare>
  T min(initializer_list<T> t, Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{T} is \tcode{LessThanComparable} and \tcode{CopyConstructible} and
\tcode{t.size() > 0}.

\pnum
\returns The smallest value in the initializer_list.

\pnum
\remarks Returns a copy of the leftmost argument when several arguments are equivalent to the smallest.\
\end{itemdescr}

\indexlibrary{\idxcode{max}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
Type
\tcode{T}
is
\tcode{LessThanComparable} (Table~\ref{lessthancomparable}).

\pnum
\returns
The larger value.

\pnum
\notes
Returns the first argument when the arguments are equivalent.
\end{itemdescr}

\indexlibrary{\idxcode{max}}%
\begin{itemdecl}
template<class T>
  T max(initializer_list<T> t);
template<class T, class Compare>
  T max(initializer_list<T> t, Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{T} is \tcode{LessThanComparable} and \tcode{CopyConstructible} and \tcode{t.size() > 0}.

\pnum
\returns The largest value in the initializer_list.

\pnum
\remarks Returns a copy of the leftmost argument when several arguments are equivalent to the largest.
\end{itemdescr}

\indexlibrary{\idxcode{minmax}}%
\begin{itemdecl}
template<class T> pair<const T&, const T&> minmax(const T& a, const T& b);
template<class T, class Compare>
  pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\requires
Type
\tcode{T}
shall be
\tcode{LessThanComparable} (Table~\ref{lessthancomparable}).

\pnum
\returns
\tcode{pair<const T\&, const T\&>(b, a)} if \tcode{b} is smaller
than \tcode{a}, and
\tcode{pair<const T\&, const T\&>(a, b)} otherwise.

\pnum
\notes
Returns \tcode{pair<const T\&, const T\&>(a, b)} when the arguments are equivalent.

\pnum
\complexity
Exactly one comparison.
\end{itemdescr}

\indexlibrary{\idxcode{minmax}}%
\begin{itemdecl}
template<class T>
  pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
  pair<T, T> minmax(initializer_list<T> t, Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{T} is \tcode{LessThanComparable} and \tcode{CopyConstructible} and \tcode{t.size() > 0}.

\pnum
\returns \tcode{pair<T, T>(x, y)}, where \tcode{x} has the smallest and \tcode{y} has the
largest value in the initializer list.

\pnum
\remarks \tcode{x} is a copy of the leftmost argument when several arguments are equivalent to
the smallest. \tcode{y} is a copy of the rightmost argument when several arguments are
equivalent to the largest.

\pnum
\complexity At most \tcode{(3/2) * t.size()} applications of the corresponding predicate.
\end{itemdescr}

\indexlibrary{\idxcode{min_element}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>
  ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
in the range
\range{first}{last}
such that for any iterator
\tcode{j}
in the range
\range{first}{last}
the following corresponding conditions hold:
\tcode{!(*j < *i)}
or
\tcode{comp(*j, *i) == false}.
Returns
\tcode{last}
if
\tcode{first == last}.

\pnum
\complexity
Exactly
\tcode{max((last - first) - 1, 0)}
applications of the corresponding comparisons.
\end{itemdescr}

\indexlibrary{\idxcode{max_element}}%
\begin{itemdecl}
template<class ForwardIterator>
  ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
in the range
\range{first}{last}
such that for any iterator
\tcode{j}
in the range
\range{first}{last}
the following corresponding conditions hold:
\tcode{!(*i < *j)}
or
\tcode{comp(*i, *j) == false}.
Returns
\tcode{last}
if
\tcode{first == last}.

\pnum
\complexity
Exactly
\tcode{max((last - first) - 1, 0)}
applications of the corresponding comparisons.
\end{itemdescr}

\indexlibrary{\idxcode{minmax_element}}%
\begin{itemdecl}
template<class ForwardIterator>
  pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
\end{itemdecl}


\begin{itemdescr}
\pnum
\returns
\tcode{make_pair(first, first)} if \range{first}{last} is empty, otherwise
\tcode{make_pair(m, M)}, where \tcode{m} is
the first iterator in \range{first}{last} such that no iterator in the range refers to a smaller element, and where \tcode{M} is the last iterator in \range{first}{last} such that no iterator in the range refers to a larger element.

\pnum
\complexity
At most
$max(\lfloor{\frac{3}{2}} (N-1)\rfloor, 0)$
applications of the corresponding predicate, where $N$ is \tcode{distance(first, last)}.
\end{itemdescr}

\rSec2[alg.lex.comparison]{Lexicographical comparison}

\indexlibrary{\idxcode{lexicographical_compare}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if the sequence of elements defined by the range
\range{first1}{last1}
is lexicographically less than the sequence of elements defined by the range
\range{first2}{last2} and
\tcode{false}
otherwise.

\pnum
\complexity
At most
\tcode{2*min((last1 - first1), (last2 - first2))}
applications of the corresponding comparison.

\pnum
\notes
If two sequences have the same number of elements and their corresponding
elements are equivalent, then neither sequence is lexicographically
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 corresponding pair of
elements that are not equivalent.

\begin{codeblock}
for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2) {
  if (*first1 < *first2) return true;
  if (*first2 < *first1) return false;
}
return first1 == last1 && first2 != last2;
\end{codeblock}

\pnum
\remarks\ An empty sequence is lexicographically less than any non-empty sequence, but
not less than any empty sequence.

\end{itemdescr}

\rSec2[alg.permutation.generators]{Permutation generators}

\indexlibrary{\idxcode{next_permutation}}%
\begin{itemdecl}
template<class BidirectionalIterator>
  bool next_permutation(BidirectionalIterator first,
                        BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
  bool next_permutation(BidirectionalIterator first,
                        BidirectionalIterator last, Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Takes a sequence defined by the range
\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
\tcode{operator<}
or \tcode{comp}.
If such a permutation exists, it returns
\tcode{true}.
Otherwise, it transforms the sequence into the smallest permutation,
that is, the ascendingly sorted one, and returns
\tcode{false}.

\pnum
\requires
\tcode{BidirectionalIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}).


\pnum
\complexity
At most
\tcode{(last - first)/2}
swaps.
\end{itemdescr}

\indexlibrary{\idxcode{prev_permutation}}%
\begin{itemdecl}
template<class BidirectionalIterator>
  bool prev_permutation(BidirectionalIterator first,
                        BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
  bool prev_permutation(BidirectionalIterator first,
                        BidirectionalIterator last, Compare comp);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Takes a sequence defined by the range
\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
\tcode{operator<}
or \tcode{comp}.

\pnum
\returns
\tcode{true}
if such a permutation exists.
Otherwise, it transforms the sequence into the largest permutation,
that is, the descendingly sorted one, and returns
\tcode{false}.

\pnum
\requires
\tcode{BidirectionalIterator} shall satisfy the requirements of
\tcode{ValueSwappable}~(\ref{swappable.requirements}).


\pnum
\complexity
At most
\tcode{(last - first)/2}
swaps.
\end{itemdescr}

\rSec1[alg.c.library]{C library algorithms}

\pnum
Table~\ref{tab:algorithms.hdr.cstdlib} describes some of the contents of the header \tcode{<cstdlib>}.

\begin{libsyntab3}{cstdlib}{tab:algorithms.hdr.cstdlib}
\type   & \tcode{size_t}  &         \\ \hline
\functions  & \tcode{bsearch} & \tcode{qsort} \\
\end{libsyntab3}

\pnum
The contents are the same as the Standard C library header
\tcode{<stdlib.h>}
with the following exceptions:

\pnum
The function signature:

\begin{codeblock}
bsearch(const void *, const void *, size_t, size_t,
  int (*)(const void *, const void *));
\end{codeblock}

is replaced by the two declarations:

\begin{codeblock}
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 *));
\end{codeblock}

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

\pnum
The function signature:

\begin{codeblock}
qsort(void *, size_t, size_t,
  int (*)(const void *, const void *));
\end{codeblock}

is replaced by the two declarations:

\begin{codeblock}
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*));
\end{codeblock}

both of which have the same behavior as the original declaration. The behavior is
undefined unless the objects in the array pointed to by \tcode{base} are of trivial type.

\enternote
Because the function argument \tcode{compar()} may throw an exception,
\tcode{bsearch()}
and
\tcode{qsort()}
are allowed to propagate the exception~(\ref{res.on.exception.handling}).
\exitnote

\xref
ISO C 7.10.5.