algorithms.tex

%!TEX root = std.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~\cxxref{containers}) and other sequences.

\pnum
The following subclauses describe components for
non-modifying sequence operations,
modifying sequence operations,
and sorting and related operations,
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{<experimental/ranges/algorithm>} \\
\ref{alg.sorting}              & Sorting and related operations    & \\ \hline
\end{libsumtab}

\pnum
To ease transition, implementations provide additional algorithm signatures that
are deprecated in this document~(Annex~\ref{depr.algo.range-and-a-half}).

\synopsis{Header \tcode{<experimental/ranges/algorithm>} synopsis}

\indexlibrary{\idxhdr{experimental/ranges/algorithm}}%

\begin{codeblock}
#include <initializer_list>

namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  namespace tag {
    // \ref{alg.tagspec}, tag specifiers~(See \ref{taggedtup.tagged}):
    struct in;
    struct in1;
    struct in2;
    struct out;
    struct out1;
    struct out2;
    struct fun;
    struct min;
    struct max;
    struct begin;
    struct end;
  }

  // \ref{alg.nonmodifying}, non-modifying sequence operations:
  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    bool all_of(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    bool all_of(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    bool any_of(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    bool any_of(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    bool none_of(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    bool none_of(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryInvocable<projected<I, Proj>> Fun>
    tagged_pair<tag::in(I), tag::fun(Fun)>
      for_each(I first, S last, Fun f, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryInvocable<projected<iterator_t<Rng>, Proj>> Fun>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::fun(Fun)>
      for_each(Rng&& rng, Fun f, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
    requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
    I find(I first, S last, const T& value, Proj proj = Proj{});

  template <InputRange Rng, class T, class Proj = identity>
    requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
    safe_iterator_t<Rng>
      find(Rng&& rng, const T& value, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    I find_if(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    safe_iterator_t<Rng>
      find_if(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    I find_if_not(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    safe_iterator_t<Rng>
      find_if_not(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
      Sentinel<I2> S2, class Proj = identity,
      IndirectRelation<I2, projected<I1, Proj>> Pred = equal_to<>>
    I1
      find_end(I1 first1, S1 last1, I2 first2, S2 last2,
               Pred pred = Pred{}, Proj proj = Proj{});

  template <ForwardRange Rng1, ForwardRange Rng2, class Proj = identity,
      IndirectRelation<iterator_t<Rng2>,
        projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
    safe_iterator_t<Rng1>
      find_end(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj proj = Proj{});

  template <InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
      class Proj1 = identity, class Proj2 = identity,
      IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
    I1
      find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
                    Pred pred = Pred{},
                    Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, ForwardRange Rng2, class Proj1 = identity,
      class Proj2 = identity,
      IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
        projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
    safe_iterator_t<Rng1>
      find_first_of(Rng1&& rng1, Rng2&& rng2,
                    Pred pred = Pred{},
                    Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectRelation<projected<I, Proj>> Pred = equal_to<>>
    I
      adjacent_find(I first, S last, Pred pred = Pred{},
                    Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectRelation<projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
    safe_iterator_t<Rng>
      adjacent_find(Rng&& rng, Pred pred = Pred{}, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
    requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
    difference_type_t<I>
      count(I first, S last, const T& value, Proj proj = Proj{});

  template <InputRange Rng, class T, class Proj = identity>
    requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
    difference_type_t<iterator_t<Rng>>
      count(Rng&& rng, const T& value, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    difference_type_t<I>
      count_if(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    difference_type_t<iterator_t<Rng>>
      count_if(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      class Proj1 = identity, class Proj2 = identity,
      IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
    tagged_pair<tag::in1(I1), tag::in2(I2)>
      mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2,
      class Proj1 = identity, class Proj2 = identity,
      IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
        projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
    tagged_pair<tag::in1(safe_iterator_t<Rng1>),
                tag::in2(safe_iterator_t<Rng2>)>
      mismatch(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
    bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
               Pred pred = Pred{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, class Pred = equal_to<>,
      class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
    bool equal(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});


  template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
      Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity,
      class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
    bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                        Pred pred = Pred{},
                        Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
      class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
    bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
                        Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
      Sentinel<I2> S2, class Pred = equal_to<>,
      class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
    I1
      search(I1 first1, S1 last1, I2 first2, S2 last2,
             Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
      class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
    safe_iterator_t<Rng1>
      search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardIterator I, Sentinel<I> S, class T,
      class Pred = equal_to<>, class Proj = identity>
    requires IndirectlyComparable<I, const T*, Pred, Proj>
    I
      search_n(I first, S last, difference_type_t<I> count,
               const T& value, Pred pred = Pred{},
               Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Pred = equal_to<>,
      class Proj = identity>
    requires IndirectlyComparable<iterator_t<Rng>, const T*, Pred, Proj>
    safe_iterator_t<Rng>
      search_n(Rng&& rng, difference_type_t<iterator_t<Rng>> count,
               const T& value, Pred pred = Pred{}, Proj proj = Proj{});

  // \ref{alg.modifying.operations}, modifying sequence operations:
  // \ref{alg.copy}, copy:
  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      copy(I first, S last, O result);

  template <InputRange Rng, WeaklyIncrementable O>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      copy(Rng&& rng, O result);

  template <InputIterator I, WeaklyIncrementable O>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      copy_n(I first, difference_type_t<I> n, O result);

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});

  template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
    requires IndirectlyCopyable<I1, I2>
    tagged_pair<tag::in(I1), tag::out(I2)>
      copy_backward(I1 first, S1 last, I2 result);

  template <BidirectionalRange Rng, BidirectionalIterator I>
    requires IndirectlyCopyable<iterator_t<Rng>, I>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
      copy_backward(Rng&& rng, I result);

  // \ref{alg.move}, move:
  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
    requires IndirectlyMovable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      move(I first, S last, O result);

  template <InputRange Rng, WeaklyIncrementable O>
    requires IndirectlyMovable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      move(Rng&& rng, O result);

  template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
    requires IndirectlyMovable<I1, I2>
    tagged_pair<tag::in(I1), tag::out(I2)>
      move_backward(I1 first, S1 last, I2 result);

  template <BidirectionalRange Rng, BidirectionalIterator I>
    requires IndirectlyMovable<iterator_t<Rng>, I>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
      move_backward(Rng&& rng, I result);

  template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2>
    requires IndirectlySwappable<I1, I2>
    tagged_pair<tag::in1(I1), tag::in2(I2)>
      swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);

  template <ForwardRange Rng1, ForwardRange Rng2>
    requires IndirectlySwappable<iterator_t<Rng1>, iterator_t<Rng2>>
    tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
      swap_ranges(Rng1&& rng1, Rng2&& rng2);

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
      CopyConstructible F, class Proj = identity>
    requires Writable<O, indirect_result_of_t<F&(projected<I, Proj>)>>
    tagged_pair<tag::in(I), tag::out(O)>
      transform(I first, S last, O result, F op, Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O, CopyConstructible F,
      class Proj = identity>
    requires Writable<O, indirect_result_of_t<F&(
      projected<iterator_t<R>, Proj>)>>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      transform(Rng&& rng, O result, F op, Proj proj = Proj{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity,
      class Proj2 = identity>
    requires Writable<O, indirect_result_of_t<F&(projected<I1, Proj1>,
      projected<I2, Proj2>)>>
    tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
      transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
              F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
      CopyConstructible F, class Proj1 = identity, class Proj2 = identity>
    requires Writable<O, indirect_result_of_t<F&(
      projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>)>>
    tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
                 tag::in2(safe_iterator_t<Rng2>),
                 tag::out(O)>
      transform(Rng1&& rng1, Rng2&& rng2, O result,
                F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I, Sentinel<I> S, class T1, class T2, class Proj = identity>
    requires Writable<I, const T2&> &&
      IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
    I
      replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = Proj{});

  template <InputRange Rng, class T1, class T2, class Proj = identity>
    requires Writable<iterator_t<Rng>, const T2&> &&
      IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
    safe_iterator_t<Rng>
      replace(Rng&& rng, const T1& old_value, const T2& new_value, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class T, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires Writable<I, const T&>
    I
      replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = Proj{});

  template <InputRange Rng, class T, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires Writable<iterator_t<Rng>, const T&>
    safe_iterator_t<Rng>
      replace_if(Rng&& rng, Pred pred, const T& new_value, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class T1, class T2, OutputIterator<const T2&> O,
      class Proj = identity>
    requires IndirectlyCopyable<I, O> &&
      IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
    tagged_pair<tag::in(I), tag::out(O)>
      replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                   Proj proj = Proj{});

  template <InputRange Rng, class T1, class T2, OutputIterator<const T2&> O,
      class Proj = identity>
    requires IndirectlyCopyable<iterator_t<Rng>, O> &&
      IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      replace_copy(Rng&& rng, O result, const T1& old_value, const T2& new_value,
                   Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, class T, OutputIterator<const T&> O,
      class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                      Proj proj = Proj{});

  template <InputRange Rng, class T, OutputIterator<const T&> O, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      replace_copy_if(Rng&& rng, O result, Pred pred, const T& new_value,
                      Proj proj = Proj{});

  template <class T, OutputIterator<const T&> O, Sentinel<O> S>
    O fill(O first, S last, const T& value);

  template <class T, OutputRange<const T&> Rng>
    safe_iterator_t<Rng>
      fill(Rng&& rng, const T& value);

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

  template <Iterator O, Sentinel<O> S, CopyConstructible F>
      requires Invocable<F&> && Writable<O, result_of_t<F&()>>
    O generate(O first, S last, F gen);

  template <class Rng, CopyConstructible F>
      requires Invocable<F&> && OutputRange<Rng, result_of_t<F&()>>
    safe_iterator_t<Rng>
      generate(Rng&& rng, F gen);

  template <Iterator O, CopyConstructible F>
      requires Invocable<F&> && Writable<O, result_of_t<F&()>>
    O generate_n(O first, difference_type_t<O> n, F gen);

  template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity>
    requires Permutable<I> &&
      IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
    I remove(I first, S last, const T& value, Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Proj = identity>
    requires Permutable<iterator_t<Rng>> &&
      IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
    safe_iterator_t<Rng>
      remove(Rng&& rng, const T& value, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires Permutable<I>
    I remove_if(I first, S last, Pred pred, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires Permutable<iterator_t<Rng>>
    safe_iterator_t<Rng>
      remove_if(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class T,
      class Proj = identity>
    requires IndirectlyCopyable<I, O> &&
      IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
    tagged_pair<tag::in(I), tag::out(O)>
      remove_copy(I first, S last, O result, const T& value, Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O, class T, class Proj = identity>
    requires IndirectlyCopyable<iterator_t<Rng>, O> &&
      IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      remove_copy(Rng&& rng, O result, const T& value, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
      class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      remove_copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      remove_copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectRelation<projected<I, Proj>> R = equal_to<>>
    requires Permutable<I>
    I unique(I first, S last, R comp = R{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
    requires Permutable<iterator_t<Rng>>
    safe_iterator_t<Rng>
      unique(Rng&& rng, R comp = R{}, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
      class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>>
    requires IndirectlyCopyable<I, O> &&
      (ForwardIterator<I> ||
       (InputIterator<O> && Same<value_type_t<I>, value_type_t<O>>) ||
       IndirectlyCopyableStorable<I, O>)
    tagged_pair<tag::in(I), tag::out(O)>
      unique_copy(I first, S last, O result, R comp = R{}, Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
      IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
    requires IndirectlyCopyable<iterator_t<Rng>, O> &&
      (ForwardIterator<iterator_t<Rng>> ||
       (InputIterator<O> && Same<value_type_t<iterator_t<Rng>>, value_type_t<O>>) ||
       IndirectlyCopyableStorable<iterator_t<Rng>, O>)
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      unique_copy(Rng&& rng, O result, R comp = R{}, Proj proj = Proj{});

  template <BidirectionalIterator I, Sentinel<I> S>
    requires Permutable<I>
    I reverse(I first, S last);

  template <BidirectionalRange Rng>
    requires Permutable<iterator_t<Rng>>
    safe_iterator_t<Rng>
      reverse(Rng&& rng);

  template <BidirectionalIterator I, Sentinel<I> S, WeaklyIncrementable O>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)> reverse_copy(I first, S last, O result);

  template <BidirectionalRange Rng, WeaklyIncrementable O>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      reverse_copy(Rng&& rng, O result);

  template <ForwardIterator I, Sentinel<I> S>
    requires Permutable<I>
    tagged_pair<tag::begin(I), tag::end(I)>
      rotate(I first, I middle, S last);

  template <ForwardRange Rng>
    requires Permutable<iterator_t<Rng>>
    tagged_pair<tag::begin(safe_iterator_t<Rng>),
                tag::end(safe_iterator_t<Rng>)>
      rotate(Rng&& rng, iterator_t<Rng> middle);

  template <ForwardIterator I, Sentinel<I> S, WeaklyIncrementable O>
    requires IndirectlyCopyable<I, O>
    tagged_pair<tag::in(I), tag::out(O)>
      rotate_copy(I first, I middle, S last, O result);

  template <ForwardRange Rng, WeaklyIncrementable O>
    requires IndirectlyCopyable<iterator_t<Rng>, O>
    tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
      rotate_copy(Rng&& rng, iterator_t<Rng> middle, O result);

  // \ref{alg.random.shuffle}, shuffle:
  template <RandomAccessIterator I, Sentinel<I> S, class Gen>
    requires Permutable<I> &&
      UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
      ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
    I shuffle(I first, S last, Gen&& g);

  template <RandomAccessRange Rng, class Gen>
    requires Permutable<I> &&
      UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
      ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
    safe_iterator_t<Rng>
      shuffle(Rng&& rng, Gen&& g);

  // \ref{alg.partitions}, partitions:
  template <InputIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    bool is_partitioned(I first, S last, Pred pred, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    bool
      is_partitioned(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires Permutable<I>
    I partition(I first, S last, Pred pred, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires Permutable<iterator_t<Rng>>
    safe_iterator_t<Rng>
      partition(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires Permutable<I>
    I stable_partition(I first, S last, Pred pred, Proj proj = Proj{});

  template <BidirectionalRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires Permutable<iterator_t<Rng>>
    safe_iterator_t<Rng>
      stable_partition(Rng&& rng, Pred pred, Proj proj = Proj{});

  template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2,
      class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
    requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2>
    tagged_tuple<tag::in(I), tag::out1(O1), tag::out2(O2)>
      partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
                     Proj proj = Proj{});

  template <InputRange Rng, WeaklyIncrementable O1, WeaklyIncrementable O2,
      class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    requires IndirectlyCopyable<iterator_t<Rng>, O1> &&
      IndirectlyCopyable<iterator_t<Rng>, O2>
    tagged_tuple<tag::in(safe_iterator_t<Rng>), tag::out1(O1), tag::out2(O2)>
      partition_copy(Rng&& rng, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectUnaryPredicate<projected<I, Proj>> Pred>
    I partition_point(I first, S last, Pred pred, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
    safe_iterator_t<Rng>
      partition_point(Rng&& rng, Pred pred, Proj proj = Proj{});

  // \ref{alg.sorting}, sorting and related operations:
  // \ref{alg.sort}, sorting:
  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I stable_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      stable_sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I partial_sort(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      partial_sort(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
                   Proj proj = Proj{});

  template <InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
      class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
        IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
    I2
      partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
                        Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, RandomAccessRange Rng2, class Comp = less<>,
      class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyCopyable<iterator_t<Rng1>, iterator_t<Rng2>> &&
        Sortable<iterator_t<Rng2>, Comp, Proj2> &&
        IndirectStrictWeakOrder<Comp, projected<iterator_t<Rng1>, Proj1>,
          projected<iterator_t<Rng2>, Proj2>>
    safe_iterator_t<Rng2>
      partial_sort_copy(Rng1&& rng, Rng2&& result_rng, Comp comp = Comp{},
                        Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    bool is_sorted(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    bool
      is_sorted(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    I is_sorted_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      is_sorted_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I nth_element(I first, I nth, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      nth_element(Rng&& rng, iterator_t<Rng> nth, Comp comp = Comp{}, Proj proj = Proj{});

  // \ref{alg.binary.search}, binary search:
  template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
    I
      lower_bound(I first, S last, const T& value, Comp comp = Comp{},
                  Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      lower_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
    I
      upper_bound(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      upper_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
    tagged_pair<tag::begin(I), tag::end(I)>
      equal_range(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
    tagged_pair<tag::begin(safe_iterator_t<Rng>),
                tag::end(safe_iterator_t<Rng>)>
      equal_range(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
    bool
      binary_search(I first, S last, const T& value, Comp comp = Comp{},
                    Proj proj = Proj{});

  template <ForwardRange Rng, class T, class Proj = identity,
      IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
    bool
      binary_search(Rng&& rng, const T& value, Comp comp = Comp{},
                    Proj proj = Proj{});

  // \ref{alg.merge}, merge:
  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity,
      class Proj2 = identity>
    requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
      merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
            Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>,
      class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
                 tag::in2(safe_iterator_t<Rng2>),
                 tag::out(O)>
      merge(Rng1&& rng1, Rng2&& rng2, O result,
            Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I
      inplace_merge(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <BidirectionalRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      inplace_merge(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
                    Proj proj = Proj{});

  // \ref{alg.set.operations}, set operations:
  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      class Proj1 = identity, class Proj2 = identity,
      IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
    bool
      includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
      class Proj2 = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
        projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
    bool
      includes(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
      set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{},
                Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
      class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
                 tag::in2(safe_iterator_t<Rng2>),
                 tag::out(O)>
      set_union(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
                Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
    O
      set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                       Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
      class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
    O
      set_intersection(Rng1&& rng1, Rng2&& rng2, O result,
                       Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
    tagged_pair<tag::in1(I1), tag::out(O)>
      set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                     Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
      class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
    tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::out(O)>
      set_difference(Rng1&& rng1, Rng2&& rng2, O result,
                     Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
      set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                               Comp comp = Comp{}, Proj1 proj1 = Proj1{},
                               Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
      class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
    requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
    tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
                 tag::in2(safe_iterator_t<Rng2>),
                 tag::out(O)>
      set_symmetric_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
                               Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  // \ref{alg.heap.operations}, heap operations:
  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I push_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      push_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I pop_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      pop_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I make_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      make_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    I sort_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    safe_iterator_t<Rng>
      sort_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    bool is_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    bool
      is_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    I is_heap_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <RandomAccessRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      is_heap_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  // \ref{alg.min.max}, minimum and maximum:
  template <class T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr const T& min(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});

  template <Copyable T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr T min(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    requires Copyable<value_type_t<iterator_t<Rng>>>
    value_type_t<iterator_t<Rng>>
      min(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <class T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr const T& max(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});

  template <Copyable T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr T max(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    requires Copyable<value_type_t<iterator_t<Rng>>>
    value_type_t<iterator_t<Rng>>
      max(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <class T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr tagged_pair<tag::min(const T&), tag::max(const T&)>
      minmax(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});

  template <Copyable T, class Proj = identity,
      IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
    constexpr tagged_pair<tag::min(T), tag::max(T)>
      minmax(initializer_list<T> t, Comp comp = Comp{}, Proj proj = Proj{});

  template <InputRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    requires Copyable<value_type_t<iterator_t<Rng>>>
    tagged_pair<tag::min(value_type_t<iterator_t<Rng>>),
                tag::max(value_type_t<iterator_t<Rng>>)>
      minmax(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    I min_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      min_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    I max_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    safe_iterator_t<Rng>
      max_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
      IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
    tagged_pair<tag::min(I), tag::max(I)>
      minmax_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <ForwardRange Rng, class Proj = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
    tagged_pair<tag::min(safe_iterator_t<Rng>),
                tag::max(safe_iterator_t<Rng>)>
      minmax_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
      class Proj1 = identity, class Proj2 = identity,
      IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
    bool
      lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
                              Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
      class Proj2 = identity,
      IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
        projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
    bool
      lexicographical_compare(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
                              Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

  // \ref{alg.permutation.generators}, permutations:
  template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    bool next_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <BidirectionalRange Rng, class Comp = less<>,
      class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    bool
      next_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});

  template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
      class Proj = identity>
    requires Sortable<I, Comp, Proj>
    bool prev_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

  template <BidirectionalRange Rng, class Comp = less<>,
      class Proj = identity>
    requires Sortable<iterator_t<Rng>, Comp, Proj>
    bool
      prev_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
}}}}
\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
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
\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>}~(\cxxref{refwrap}), or some equivalent solution.
\exitnote

\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}

\pnum
In the description of algorithm return values, sentinel values are sometimes
returned where an iterator is expected. In these cases, the semantics are as
if the sentinel is converted into an iterator as follows:

\begin{codeblock}
I tmp = first;
while(tmp != last)
  ++tmp;
return tmp;
\end{codeblock}

\pnum
Overloads of algorithms that take \tcode{Range} arguments~(\ref{ranges.range})
behave as if they are implemented by calling \tcode{begin} and \tcode{end} on
the \tcode{Range} and dispatching to the overload that takes separate
iterator and sentinel arguments.

\pnum
The number and order of template parameters for algorithm declarations
is unspecified, except where explicitly stated otherwise.

\rSec1[alg.tagspec]{Tag specifiers}

\begin{itemdecl}
namespace tag {
  struct in { /* @\impdef@ */ };
  struct in1 { /* @\impdef@ */ };
  struct in2 { /* @\impdef@ */ };
  struct out { /* @\impdef@ */ };
  struct out1 { /* @\impdef@ */ };
  struct out2 { /* @\impdef@ */ };
  struct fun { /* @\impdef@ */ };
  struct min { /* @\impdef@ */ };
  struct max { /* @\impdef@ */ };
  struct begin { /* @\impdef@ */ };
  struct end { /* @\impdef@ */ };
}
\end{itemdecl}

\begin{itemdescr}
\pnum In the following description, let \tcode{$X$} be the name of a type in the \tcode{tag}
namespace above.

\pnum \tcode{tag::$X$} is a tag specifier~(\ref{taggedtup.tagged}) such that
\tcode{\textit{TAGGET}($D$, tag::$X$, $N$)} names a tagged getter~(\ref{taggedtup.tagged})
with DerivedCharacteristic \tcode{$D$}, ElementIndex \tcode{$N$}, and ElementName \tcode{$X$}.

\pnum \enterexample \tcode{tag::in} is a type such that \tcode{\textit{TAGGET}($D$, tag::in, $N$)}
names a type with the following interface:

\begin{codeblock}
struct @\xname{input_getter}@ {
  constexpr decltype(auto) in() &       { return get<@$N$@>(static_cast<@$D$@&>(*this)); }
  constexpr decltype(auto) in() &&      { return get<@$N$@>(static_cast<@$D$@&&>(*this)); }
  constexpr decltype(auto) in() const & { return get<@$N$@>(static_cast<const @$D$@&>(*this)); }
};
\end{codeblock}
\exitexample
\end{itemdescr}

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

\rSec2[alg.all_of]{All of}

\indexlibrary{\idxcode{all_of}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  bool all_of(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  bool all_of(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\tcode{invoke(pred, invoke(proj, *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
and \tcode{last - first} applications of the projection.
\end{itemdescr}

\rSec2[alg.any_of]{Any of}

\indexlibrary{\idxcode{any_of}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  bool any_of(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  bool any_of(Rng&& rng, Pred pred, Proj proj = Proj{});
\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{invoke(pred, invoke(proj, *i))}
is \tcode{true}, and \tcode{true} otherwise.

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

\rSec2[alg.none_of]{None of}

\indexlibrary{\idxcode{none_of}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  bool none_of(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  bool none_of(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\tcode{invoke(pred, invoke(proj, *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
and \tcode{last - first} applications of the projection.
\end{itemdescr}

\rSec2[alg.foreach]{For each}

\indexlibrary{\idxcode{for_each}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryInvocable<projected<I, Proj>> Fun>
  tagged_pair<tag::in(I), tag::fun(Fun)>
    for_each(I first, S last, Fun f, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryInvocable<projected<iterator_t<Rng>, Proj>> Fun>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::fun(Fun)>
    for_each(Rng&& rng, Fun f, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Calls
\tcode{invoke(f, invoke(proj, *i))} for every iterator
\tcode{i} in the range
\range{first}{last},
starting from
\tcode{first}
and proceeding to
\tcode{last - 1}.
\enternote If the result of
\tcode{invoke(proj, *i)} is a mutable reference, \tcode{f} may apply
nonconstant functions.\exitnote

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

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

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

\pnum
\enternote The requirements of this algorithm are more strict than those
specified in \cxxref{alg.foreach}. This algorithm requires \tcode{Fun} to
satisfy \tcode{CopyConstructible}, whereas the algorithm in the \Cpp Standard
requires only \tcode{MoveConstructible}. \exitnote
\end{itemdescr}

\rSec2[alg.find]{Find}

\indexlibrary{\idxcode{find}}%
\indexlibrary{\idxcode{find_if}}%
\indexlibrary{\idxcode{find_if_not}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
  requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
  I find(I first, S last, const T& value, Proj proj = Proj{});

template <InputRange Rng, class T, class Proj = identity>
  requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
  safe_iterator_t<Rng>
    find(Rng&& rng, const T& value, Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  I find_if(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  safe_iterator_t<Rng>
    find_if(Rng&& rng, Pred pred, Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  I find_if_not(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  safe_iterator_t<Rng>
    find_if_not(Rng&& rng, Pred pred, Proj proj = Proj{});
\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{invoke(proj, *i) == value},
\tcode{invoke(pred, invoke(proj, *i)) != false},
\tcode{invoke(\brk{}pred, invoke(proj, *i)) == false}.
Returns \tcode{last} if no such iterator is found.

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

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

\indexlibrary{\idxcode{find_end}}%
\begin{itemdecl}
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
    Sentinel<I2> S2, class Proj = identity,
    IndirectRelation<I2, projected<I1, Proj>> Pred = equal_to<>>
  I1
    find_end(I1 first1, S1 last1, I2 first2, S2 last2,
             Pred pred = Pred{}, Proj proj = Proj{});

template <ForwardRange Rng1, ForwardRange Rng2,
    class Proj = identity,
    IndirectRelation<iterator_t<Rng2>,
      projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
  safe_iterator_t<Rng1>
    find_end(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj proj = Proj{});
\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 every non-negative integer
\tcode{n < (last2 - first2)},
the following condition holds:
\tcode{invoke(pred, invoke(\brk{}proj, *(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 and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{find_first_of}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
    class Proj1 = identity, class Proj2 = identity,
    IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
  I1
    find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
                  Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, ForwardRange Rng2, class Proj1 = identity,
    class Proj2 = identity,
    IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
      projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
  safe_iterator_t<Rng1>
    find_first_of(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
                  Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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 condition holds:
\tcode{invoke(pred, invoke(proj1, *i), invoke(proj2, *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 and the two projections.
\end{itemdescr}

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

\indexlibrary{\idxcode{adjacent_find}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectRelation<projected<I, Proj>> Pred = equal_to<>>
  I
    adjacent_find(I first, S last, Pred pred = Pred{},
                  Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectRelation<projected<iterator_t<Rng>, Proj>> Pred = equal_to<>>
  safe_iterator_t<Rng>
    adjacent_find(Rng&& rng, Pred pred = Pred{}, Proj proj = Proj{});
\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 condition holds:
\tcode{invoke(pred, invoke(proj, *i), invoke(proj, *(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, and no more than twice as many applications of the projection.
\end{itemdescr}

\rSec2[alg.count]{Count}

\indexlibrary{\idxcode{count}}%
\indexlibrary{\idxcode{count_if}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class T, class Proj = identity>
  requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
  difference_type_t<I>
    count(I first, S last, const T& value, Proj proj = Proj{});

template <InputRange Rng, class T, class Proj = identity>
  requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
  difference_type_t<iterator_t<Rng>>
    count(Rng&& rng, const T& value, Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  difference_type_t<I>
    count_if(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  difference_type_t<iterator_t<Rng>>
    count_if(Rng&& rng, Pred pred, Proj proj = Proj{});
\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{invoke(proj, *i) == value, invoke(pred, invoke(proj, *i)) != false}.

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

\rSec2[mismatch]{Mismatch}

\indexlibrary{\idxcode{mismatch}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    class Proj1 = identity, class Proj2 = identity,
    IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>>
  tagged_pair<tag::in1(I1), tag::in2(I2)>
    mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2,
    class Proj1 = identity, class Proj2 = identity,
    IndirectRelation<projected<iterator_t<Rng1>, Proj1>,
      projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>>
  tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
    mismatch(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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{itemize}
\item \tcode{j} is in the range \tcode{[first2, last2)}.
\item \tcode{*i != *(first2 + (i - first1))}
\item \tcode{!invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))}
\end{itemize}

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

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

\rSec2[alg.equal]{Equal}

\indexlibrary{\idxcode{equal}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
  bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
             Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, class Pred = equal_to<>,
    class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
  bool equal(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
If
\tcode{last1 - first1 != last2 - first2},
return
\tcode{false}.
Otherwise return
\tcode{true}
if for every iterator
\tcode{i}
in the range \range{first1}{last1}
the following condition holds:
\tcode{invoke(pred, invoke(\brk{}proj1, *i), invoke(proj2, *(first2 + (i - first1))))}.
Otherwise, returns
\tcode{fal\-se}.

\pnum
\complexity
No applications of the corresponding predicate and projections if:
\begin{itemize}
\item \tcode{SizedSentinel<S1, I1>} is satisfied, and
\item \tcode{SizedSentinel<S2, I2>} is satisfied, and
\item \tcode{last1 - first1 != last2 - first2}.
\end{itemize}
Otherwise, at most
\tcode{min(last1 - first1, last2 - \brk{}first2)}
applications of the corresponding predicate and projections.
\end{itemdescr}

\rSec2[alg.is_permutation]{Is permutation}

\indexlibrary{\idxcode{is_permutation}}%
\begin{itemdecl}
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
    Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity,
    class Proj2 = identity>
  requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
  bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                      Pred pred = Pred{},
                      Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
    class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
  bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
                      Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns If \tcode{last1 - first1 != last2 - first2}, return \tcode{false}.
Otherwise return \tcode{true} if there exists a permutation of the elements in the
range \range{first2}{first2 + (last1 - first1)}, beginning with
\tcode{I2 begin}, such that
\tcode{equal(first1, last1, begin, pred, proj1, proj2)} returns \tcode{true}
; otherwise, returns \tcode{false}.

\pnum
\complexity
No applications of the corresponding predicate and projections if:
\begin{itemize}
\item \tcode{SizedSentinel<S1, I1>} is satisfied, and
\item \tcode{SizedSentinel<S2, I2>} is satisfied, and
\item \tcode{last1 - first1 != last2 - first2}.
\end{itemize}
Otherwise, exactly \tcode{last1 - first1} applications of the
corresponding predicate and projections if
\tcode{equal(\brk{}first1, last1, first2, last2, pred, proj1, proj2)}
would return \tcode{true}; otherwise, at
worst \bigoh{N^2}, where $N$ has the value \tcode{last1 - first1}.
\end{itemdescr}

\rSec2[alg.search]{Search}

\indexlibrary{\idxcode{search}}%
\begin{itemdecl}
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2,
    Sentinel<I2> S2, class Pred = equal_to<>,
    class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
  I1
    search(I1 first1, S1 last1, I2 first2, S2 last2,
           Pred pred = Pred{},
           Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
    class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2>
  safe_iterator_t<Rng1>
    search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
           Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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 every non-negative integer
\tcode{n}
less than
\tcode{last2 - first2}
the following condition holds:
\begin{codeblock}
invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))) != false.
\end{codeblock}
Returns \tcode{first1}
if \brk{}\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 and projections.
\end{itemdescr}

\indexlibrary{\idxcode{search_n}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class T,
    class Pred = equal_to<>, class Proj = identity>
  requires IndirectlyComparable<I, const T*, Pred, Proj>
  I
    search_n(I first, S last, difference_type_t<I> count,
             const T& value, Pred pred = Pred{},
             Proj proj = Proj{});

template <ForwardRange Rng, class T, class Pred = equal_to<>,
    class Proj = identity>
  requires IndirectlyComparable<iterator_t<Rng>, const T*, Pred, Proj>
  safe_iterator_t<Rng>
    search_n(Rng&& rng, difference_type_t<iterator_t<Rng>> count,
             const T& value, Pred pred = Pred{}, Proj proj = Proj{});
\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{first}{last-count}
such that for every non-negative integer
\tcode{n}
less than
\tcode{count}
the following condition holds:
\tcode{invoke(pred, invoke(proj, *(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 and projection.
\end{itemdescr}

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

\rSec2[alg.copy]{Copy}

\indexlibrary{\idxcode{copy}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    copy(I first, S last, O result);

template <InputRange Rng, WeaklyIncrementable O>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    copy(Rng&& rng, O 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{\{last, 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 <InputIterator I, WeaklyIncrementable O>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    copy_n(I first, difference_type_t<I> n, O result);
\end{itemdecl}

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

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

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

\indexlibrary{\idxcode{copy_if}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
Let $N$ be the number of iterators \tcode{i} in the range \range{first}{last}
for which the condition \tcode{invoke(pred, invoke(proj, *i))} holds.

\pnum
\requires The ranges \range{first}{last} and \range{result}{result + $N$} 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{invoke(pred, invoke(proj, *i))} is \tcode{true}.

\pnum
\returns \tcode{\{last, result + $N$\}}.

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

\pnum
\remarks Stable~(\cxxref{algorithm.stable}).
\end{itemdescr}


\indexlibrary{\idxcode{copy_backward}}%
\begin{itemdecl}
template <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
  requires IndirectlyCopyable<I1, I2>
  tagged_pair<tag::in(I1), tag::out(I2)>
    copy_backward(I1 first, S1 last, I2 result);

template <BidirectionalRange Rng, BidirectionalIterator I>
  requires IndirectlyCopyable<iterator_t<Rng>, I>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
    copy_backward(Rng&& rng, I 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{\{last, result - (last - first)\}}.

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

\rSec2[alg.move]{Move}

\indexlibrary{move\tcode{move}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O>
  requires IndirectlyMovable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    move(I first, S last, O result);

template <InputRange Rng, WeaklyIncrementable O>
  requires IndirectlyMovable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    move(Rng&& rng, O 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) = ranges::iter_move(first + n)}.

\pnum
\returns
\tcode{\{last, 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 <BidirectionalIterator I1, Sentinel<I1> S1, BidirectionalIterator I2>
  requires IndirectlyMovable<I1, I2>
  tagged_pair<tag::in(I1), tag::out(I2)>
    move_backward(I1 first, S1 last, I2 result);

template <BidirectionalRange Rng, BidirectionalIterator I>
  requires IndirectlyMovable<iterator_t<Rng>, I>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(I)>
    move_backward(Rng&& rng, I 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) = ranges::iter_move(last - n)}.

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

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

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

\rSec2[alg.swap]{swap}

\indexlibrary{\idxcode{swap_ranges}}%
\begin{itemdecl}
template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2>
  requires IndirectlySwappable<I1, I2>
  tagged_pair<tag::in1(I1), tag::in2(I2)>
    swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);

template <ForwardRange Rng1, ForwardRange Rng2>
  requires IndirectlySwappable<iterator_t<Rng1>, iterator_t<Rng2>>
  tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)>
    swap_ranges(Rng1&& rng1, Rng2&& rng2);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
For each non-negative integer \tcode{n < min(last1 - first1, last2 - first2)}
performs: \\
\tcode{ranges::iter_swap(first1 + n, first2 + n)}.

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

\pnum
\returns
\tcode{\{first1 + n, first2 + n\}}, where
\tcode{n} is \tcode{min(last1 - first1, last2 - first2)}.

\pnum
\complexity
Exactly
\tcode{min(last1 - first1, last2 - first2)}
swaps.
\end{itemdescr}

\rSec2[alg.transform]{Transform}

\indexlibrary{\idxcode{transform}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
    CopyConstructible F, class Proj = identity>
  requires Writable<O, indirect_result_of_t<F&(projected<I, Proj>)>>
  tagged_pair<tag::in(I), tag::out(O)>
    transform(I first, S last, O result, F op, Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O, CopyConstructible F,
    class Proj = identity>
  requires Writable<O, indirect_result_of_t<F&(
    projected<iterator_t<R>, Proj>)>>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    transform(Rng&& rng, O result, F op, Proj proj = Proj{});

template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, CopyConstructible F, class Proj1 = identity,
    class Proj2 = identity>
  requires Writable<O, indirect_result_of_t<F&(projected<I1, Proj1>,
    projected<I2, Proj2>)>>
  tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
    transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
            F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
    CopyConstructible F, class Proj1 = identity, class Proj2 = identity>
  requires Writable<O, indirect_result_of_t<F&(
    projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>)>>
  tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
               tag::in2(safe_iterator_t<Rng2>),
               tag::out(O)>
    transform(Rng1&& rng1, Rng2&& rng2, O result,
              F binary_op, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\end{itemdecl}

\begin{itemdescr}
\pnum
Let $N$ be \tcode{(last1 - first1)}
for unary transforms, or \tcode{min(last1 - first1, last2 - first2) for binary
transforms.}

\pnum
\effects
Assigns through every iterator
\tcode{i}
in the range
\range{result}{result + $N$}
a new
corresponding value equal to
\tcode{invoke(op, invoke(proj, *(first1 + (i - result))))}
or
\tcode{invoke(\brk{}binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2, *(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}{first1 + $N$},
\crange{first2}{first2 + $N$},
and
\crange{result}{result + $N$}.\footnote{The use of fully
closed ranges is intentional.}

\pnum
\returns
\tcode{\{first1 + $N$, result + $N$\}}
 or \tcode{make_tagged_tuple<tag::in1, tag::in2, tag\colcol{}out\brk{}>(\brk{}first1 + $N$, first2 + $N$, result + $N$)}.

\pnum
\complexity
Exactly
\tcode{$N$}
applications of
\tcode{op} or \tcode{binary_op} and the corresponding projection(s).

\pnum
\notes
\tcode{result} may be equal to \tcode{first1}
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 <InputIterator I, Sentinel<I> S, class T1, class T2, class Proj = identity>
  requires Writable<I, const T2&> &&
    IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
  I
    replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = Proj{});

template <InputRange Rng, class T1, class T2, class Proj = identity>
  requires Writable<iterator_t<Rng>, const T2&> &&
    IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
  safe_iterator_t<Rng>
    replace(Rng&& rng, const T1& old_value, const T2& new_value, Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, class T, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires Writable<I, const T&>
  I
    replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = Proj{});

template <InputRange Rng, class T, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires Writable<iterator_t<Rng>, const T&>
  safe_iterator_t<Rng>
    replace_if(Rng&& rng, Pred pred, const T& new_value, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Assigns \tcode{new_value} through each iterator
\tcode{i}
in the range \range{first}{last}
when the following corresponding conditions hold:
\tcode{invoke(proj, *i) == old_value},
\tcode{invoke(pred, invoke(proj, *i)) != false}.

\pnum
\returns
\tcode{last}.

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

\indexlibrary{\idxcode{replace_copy}}%
\indexlibrary{\idxcode{replace_copy_if}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, class T1, class T2, OutputIterator<const T2&> O,
    class Proj = identity>
  requires IndirectlyCopyable<I, O> &&
    IndirectRelation<equal_to<>, projected<I, Proj>, const T1*>
  tagged_pair<tag::in(I), tag::out(O)>
    replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                 Proj proj = Proj{});

template <InputRange Rng, class T1, class T2, OutputIterator<const T2&> O,
    class Proj = identity>
  requires IndirectlyCopyable<iterator_t<Rng>, O> &&
    IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T1*>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    replace_copy(Rng&& rng, O result, const T1& old_value, const T2& new_value,
                 Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, class T, OutputIterator<const T&> O,
    class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                    Proj proj = Proj{});

template <InputRange Rng, class T, OutputIterator<const T&> O, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    replace_copy_if(Rng&& rng, O result, Pred pred, const T& new_value,
                    Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
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}
invoke(proj, *(first + (i - result))) == old_value
invoke(pred, invoke(proj, *(first + (i - result)))) != false
\end{codeblock}

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

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

\rSec2[alg.fill]{Fill}

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

template <class T, OutputRange<const T&> Rng>
  safe_iterator_t<Rng>
    fill(Rng&& rng, const T& value);

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

\begin{itemdescr}
\pnum
\effects
\tcode{fill} assigns \tcode{value} through all the
iterators in the range \range{first}{last}. \tcode{fill_n}
assigns \tcode{value} through all the iterators in the counted range \range{first}{n}
if \tcode{n} is positive, otherwise it does nothing.

\pnum
\returns
\tcode{last}, where \tcode{last} is \tcode{first + max(n, 0)} for \tcode{fill_n}.

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

\rSec2[alg.generate]{Generate}

\indexlibrary{\idxcode{generate}}%
\indexlibrary{\idxcode{generate_n}}%
\begin{itemdecl}
template <Iterator O, Sentinel<O> S, CopyConstructible F>
    requires Invocable<F&> && Writable<O, result_of_t<F&()>>
  O generate(O first, S last, F gen);

template <class Rng, CopyConstructible F>
    requires Invocable<F&> && OutputRange<Rng, result_of_t<F&()>>
  safe_iterator_t<Rng>
    generate(Rng&& rng, F gen);

template <Iterator O, CopyConstructible F>
    requires Invocable<F&> && Writable<O, result_of_t<F&()>>
  O generate_n(O first, difference_type_t<O> n, F gen);
\end{itemdecl}

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

\pnum
\returns
\tcode{last}, where \tcode{last} is \tcode{first + max(n, 0)} for \tcode{generate_n}.

\pnum
\complexity
Exactly \tcode{last - first} evaluations of \tcode{invoke(gen)} and assignments.
\end{itemdescr}

\rSec2[alg.remove]{Remove}

\indexlibrary{\idxcode{remove}}%
\indexlibrary{\idxcode{remove_if}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity>
  requires Permutable<I> &&
    IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
  I remove(I first, S last, const T& value, Proj proj = Proj{});

template <ForwardRange Rng, class T, class Proj = identity>
  requires Permutable<iterator_t<Rng>> &&
    IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
  safe_iterator_t<Rng>
    remove(Rng&& rng, const T& value, Proj proj = Proj{});

template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires Permutable<I>
  I remove_if(I first, S last, Pred pred, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires Permutable<iterator_t<Rng>>
  safe_iterator_t<Rng>
    remove_if(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\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{invoke(proj, *i) == value},
\tcode{invoke(pred, invoke(proj, *i)) != false}.

\pnum
\returns
The end of the resulting range.

\pnum
\remarks Stable~(\cxxref{algorithm.stable}).

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

\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 moving from elements that were originally
in that range.
\end{itemdescr}

\indexlibrary{\idxcode{remove_copy}}%
\indexlibrary{\idxcode{remove_copy_if}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O, class T,
    class Proj = identity>
  requires IndirectlyCopyable<I, O> &&
    IndirectRelation<equal_to<>, projected<I, Proj>, const T*>
  tagged_pair<tag::in(I), tag::out(O)>
    remove_copy(I first, S last, O result, const T& value, Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O, class T, class Proj = identity>
  requires IndirectlyCopyable<iterator_t<Rng>, O> &&
    IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    remove_copy(Rng&& rng, O result, const T& value, Proj proj = Proj{});

template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
    class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    remove_copy_if(I first, S last, O result, Pred pred, Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    remove_copy_if(Rng&& rng, O result, Pred pred, Proj proj = Proj{});
\end{itemdecl}

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

\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{invoke(proj, *i) == value},
\tcode{invoke(pred, invoke(proj, *i)) != false}.

\pnum
\returns
A pair consisting of \tcode{last} and the end of the resulting range.

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

\pnum
\remarks Stable~(\cxxref{algorithm.stable}).
\end{itemdescr}

\rSec2[alg.unique]{Unique}

\indexlibrary{\idxcode{unique}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectRelation<projected<I, Proj>> R = equal_to<>>
  requires Permutable<I>
  I unique(I first, S last, R comp = R{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
  requires Permutable<iterator_t<Rng>>
  safe_iterator_t<Rng>
    unique(Rng&& rng, R comp = R{}, Proj proj = Proj{});
\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{invoke(proj, *(i - 1)) == invoke(proj, *i)}
or
\tcode{invoke(pred, invoke(proj, *(i - 1)), invoke(proj, *i)) != false}.

\pnum
\returns
The end of the resulting range.

\pnum
\complexity
For nonempty ranges, exactly
\tcode{(last - first) - 1}
applications of the corresponding predicate and no more than twice as many
applications of the projection.
\end{itemdescr}

\indexlibrary{\idxcode{unique_copy}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O,
    class Proj = identity, IndirectRelation<projected<I, Proj>> R = equal_to<>>
  requires IndirectlyCopyable<I, O> &&
    (ForwardIterator<I> ||
     (InputIterator<O> && Same<value_type_t<I>, value_type_t<O>>) ||
     IndirectlyCopyableStorable<I, O>)
  tagged_pair<tag::in(I), tag::out(O)>
    unique_copy(I first, S last, O result, R comp = R{}, Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O, class Proj = identity,
    IndirectRelation<projected<iterator_t<Rng>, Proj>> R = equal_to<>>
  requires IndirectlyCopyable<iterator_t<Rng>, O> &&
    (ForwardIterator<iterator_t<Rng>> ||
     (InputIterator<O> && Same<value_type_t<iterator_t<Rng>>, value_type_t<O>>) ||
     IndirectlyCopyableStorable<iterator_t<Rng>, O>)
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    unique_copy(Rng&& rng, O result, R comp = R{}, Proj proj = Proj{});
\end{itemdecl}

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

\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:
\begin{codeblock}
invoke(proj, *i) == invoke(proj, *(i - 1))
\end{codeblock}
or
\begin{codeblock}
invoke(pred, invoke(proj, *i), invoke(proj, *(i - 1))) != false.
\end{codeblock}

\pnum
\returns
A pair consisting of \tcode{last} and the end of the resulting range.

\pnum
\complexity
For nonempty ranges, exactly
\tcode{last - first - 1}
applications of the corresponding predicate and no more than twice as many
applications of the projection.
\end{itemdescr}

\rSec2[alg.reverse]{Reverse}

\indexlibrary{\idxcode{reverse}}%
\begin{itemdecl}
template <BidirectionalIterator I, Sentinel<I> S>
  requires Permutable<I>
  I reverse(I first, S last);

template <BidirectionalRange Rng>
  requires Permutable<iterator_t<Rng>>
  safe_iterator_t<Rng>
    reverse(Rng&& rng);
\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
\returns \tcode{last}.

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

\indexlibrary{\idxcode{reverse_copy}}%
\begin{itemdecl}
template <BidirectionalIterator I, Sentinel<I> S, WeaklyIncrementable O>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)> reverse_copy(I first, S last, O result);

template <BidirectionalRange Rng, WeaklyIncrementable O>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    reverse_copy(Rng&& rng, O result);
\end{itemdecl}

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

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

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

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

\rSec2[alg.rotate]{Rotate}

\indexlibrary{\idxcode{rotate}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S>
  requires Permutable<I>
  tagged_pair<tag::begin(I), tag::end(I)> rotate(I first, I middle, S last);

template <ForwardRange Rng>
  requires Permutable<iterator_t<Rng>>
  tagged_pair<tag::begin(safe_iterator_t<Rng>), tag::end(safe_iterator_t<Rng>)>
    rotate(Rng&& rng, iterator_t<Rng> middle);
\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), last\}}.

\pnum
\notes
This is a left rotate.

\pnum
\requires
\range{first}{middle}
and
\range{middle}{last}
shall be valid ranges.

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

\indexlibrary{\idxcode{rotate_copy}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, WeaklyIncrementable O>
  requires IndirectlyCopyable<I, O>
  tagged_pair<tag::in(I), tag::out(O)>
    rotate_copy(I first, I middle, S last, O result);

template <ForwardRange Rng, WeaklyIncrementable O>
  requires IndirectlyCopyable<iterator_t<Rng>, O>
  tagged_pair<tag::in(safe_iterator_t<Rng>), tag::out(O)>
    rotate_copy(Rng&& rng, iterator_t<Rng> middle, O 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{\{last, 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]{Shuffle}

\indexlibrary{\idxcode{shuffle}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Gen>
  requires Permutable<I> &&
    UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
    ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
  I shuffle(I first, S last, Gen&& g);

template <RandomAccessRange Rng, class Gen>
  requires Permutable<I> &&
    UniformRandomNumberGenerator<remove_reference_t<Gen>> &&
    ConvertibleTo<result_of_t<Gen&()>, difference_type_t<I>>
  safe_iterator_t<Rng>
    shuffle(Rng&& rng, Gen&& 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
\complexity
Exactly
\tcode{(last - first) - 1}
swaps.

\pnum
\returns \tcode{last}

\pnum
\notes
To the extent that the implementation of this function makes use of random
numbers, 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 <InputIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  bool is_partitioned(I first, S last, Pred pred, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  bool
    is_partitioned(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{true} if
\range{first}{last} is empty or if
\range{first}{last} is partitioned by \tcode{pred} and \tcode{proj}, i.e. if all
iterators \tcode{i} for which
\tcode{invoke(pred, invoke(proj, *i)) != false} come before those that do not,
for every \tcode{i} in \range{first}{last}.

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

\indexlibrary{\idxcode{partition}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires Permutable<I>
  I partition(I first, S last, Pred pred, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires Permutable<iterator_t<Rng>>
  safe_iterator_t<Rng>
    partition(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Permutes the elements in the range \range{first}{last} such that there exists an iterator \tcode{i}
such that for every iterator \tcode{j} in the range \range{first}{i}
\tcode{invoke(pred, invoke(\brk{}proj, *j)) != false}, and for every iterator \tcode{k} in the
range \range{i}{last}, \tcode{invoke(pred, invoke(proj, *k)) == false}.

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

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

\indexlibrary{\idxcode{stable_partition}}%
\begin{itemdecl}
template <BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires Permutable<I>
  I stable_partition(I first, S last, Pred pred, Proj proj = Proj{});

template <BidirectionalRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires Permutable<iterator_t<Rng>>
  safe_iterator_t<Rng>
    stable_partition(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Permutes the elements in the range \range{first}{last} such that there exists an iterator \tcode{i}
such that for every iterator \tcode{j} in the range \range{first}{i}
\tcode{invoke(pred, invoke(proj, *j)) != false}, and for every iterator \tcode{k} in the
range \range{i}{last}, \tcode{invoke(pred, invoke(proj, *k)) == false}.

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

\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 and projection.
\end{itemdescr}

\indexlibrary{\idxcode{partition_copy}}%
\begin{itemdecl}
template <InputIterator I, Sentinel<I> S, WeaklyIncrementable O1, WeaklyIncrementable O2,
    class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred>
  requires IndirectlyCopyable<I, O1> && IndirectlyCopyable<I, O2>
  tagged_tuple<tag::in(I), tag::out1(O1), tag::out2(O2)>
    partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
                   Proj proj = Proj{});

template <InputRange Rng, WeaklyIncrementable O1, WeaklyIncrementable O2,
    class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  requires IndirectlyCopyable<iterator_t<Rng>, O1> &&
    IndirectlyCopyable<iterator_t<Rng>, O2>
  tagged_tuple<tag::in(safe_iterator_t<Rng>), tag::out1(O1), tag::out2(O2)>
    partition_copy(Rng&& rng, O1 out_true, O2 out_false, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires 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{invoke(pred, invoke(proj, *i))} is \tcode{true}, or to
the output range beginning with \tcode{out_false} otherwise.

\pnum
\returns A tuple \tcode{p} such that \tcode{get<0>(p)} is \tcode{last},
\tcode{get<1>(p)} is the end of the output range beginning at \tcode{out_true},
and \tcode{get<2>(p)} is the end of the output range beginning at \tcode{out_false}.

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

\indexlibrary{\idxcode{partition_point}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectUnaryPredicate<projected<I, Proj>> Pred>
  I partition_point(I first, S last, Pred pred, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred>
  safe_iterator_t<Rng>
    partition_point(Rng&& rng, Pred pred, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \range{first}{last} shall be partitioned by \tcode{pred} and \tcode{proj}, i.e.
there shall be an iterator \tcode{mid} such that
\tcode{all_of(first, mid, pred, proj)} and \tcode{none_of(mid, last, pred, proj)}
are both true.

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

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


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

\pnum
All the operations in~\ref{alg.sorting} take an optional binary callable predicate of type \tcode{Comp} that defaults to \tcode{less<>}.

\pnum
\tcode{Comp}
is a callable object~(\cxxref{func.require}). The return value of the \tcode{invoke} operation applied to
an object of type \tcode{Comp}, when contextually converted to
\tcode{bool} (Clause~\cxxref{conv}),
yields \tcode{true} if the first argument of the call
is less than the second, and
\tcode{false}
otherwise.
\tcode{Comp 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
A sequence is
\techterm{sorted with respect to a comparator and projection}
\tcode{comp} and \tcode{proj} if for every iterator
\tcode{i}
pointing to the sequence and every non-negative integer
\tcode{n}
such that
\tcode{i + n}
is a valid iterator pointing to an element of the sequence,
\tcode{invoke(comp, invoke(proj, *(i + n)), invoke(proj, *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 <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\pnum
\returns \tcode{last}.

\pnum
\complexity
\bigoh{N\log(N)}
(where
\tcode{$N$ == last - first})
comparisons, and twice as many applications of the projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{stable_sort}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I stable_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    stable_sort(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\pnum
\returns \tcode{last}.

\pnum
\complexity
Let \tcode{$N$ == last - first}.
If enough extra memory is available, $N \log(N)$ comparisons.
Otherwise, at most $N \log^2(N)$ comparisons.
In either case, twice as many applications of the projection as the number of
comparisons.

\pnum
\remarks Stable~(\cxxref{algorithm.stable}).
\end{itemdescr}

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

\indexlibrary{\idxcode{partial_sort}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I partial_sort(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    partial_sort(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
                 Proj proj = Proj{});
\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
\returns \tcode{last}.

\pnum
\complexity
It takes approximately
\tcode{(last - first) * log(middle - first)}
comparisons, and exactly twice as many applications of the projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{partial_sort_copy}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
    class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
      IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
  I2
    partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
                      Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, RandomAccessRange Rng2, class Comp = less<>,
    class Proj1 = identity, class Proj2 = identity>
  requires IndirectlyCopyable<iterator_t<Rng1>, iterator_t<Rng2>> &&
      Sortable<iterator_t<Rng2>, Comp, Proj2> &&
      IndirectStrictWeakOrder<Comp, projected<iterator_t<Rng1>, Proj1>,
        projected<iterator_t<Rng2>, Proj2>>
  safe_iterator_t<Rng2>
    partial_sort_copy(Rng1&& rng, Rng2&& result_rng, Comp comp = Comp{},
                      Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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
\complexity
Approximately
\begin{codeblock}
(last - first) * log(min(last - first, result_last - result_first))
\end{codeblock}
comparisons, and exactly twice as many applications of the projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{is_sorted}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  bool is_sorted(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  bool
    is_sorted(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\indexlibrary{\idxcode{is_sorted_until}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  I is_sorted_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    is_sorted_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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 <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I nth_element(I first, I nth, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    nth_element(Rng&& rng, iterator_t<Rng> nth, Comp comp = Comp{}, Proj proj = Proj{});
\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, unless \tcode{nth == last}.
Also for every iterator
\tcode{i}
in the range
\range{first}{nth}
and every iterator
\tcode{j}
in the range
\range{nth}{last}
it holds that:
\tcode{invoke(comp, invoke(proj, *j), invoke(proj, *i)) == false}.

\pnum
\returns \tcode{last}.

\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
comparison function and projection.
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 <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
  I
    lower_bound(I first, S last, const T& value, Comp comp = Comp{},
                Proj proj = Proj{});

template <ForwardRange Rng, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    lower_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\pnum
\returns
The furthermost iterator
\tcode{i}
in the range
\crange{first}{last}
such that for every iterator
\tcode{j}
in the range
\range{first}{i}
the following corresponding condition holds:
\tcode{invoke(comp, invoke(proj, *j), value) != false}.

\pnum
\complexity
At most
$\log_2(\tcode{last - first}) + \bigoh{1}$
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{upper_bound}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
  I
    upper_bound(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    upper_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\pnum
\returns
The furthermost iterator
\tcode{i}
in the range
\crange{first}{last}
such that for every iterator
\tcode{j}
in the range
\range{first}{i}
the following corresponding condition holds:
\tcode{invoke(comp, value, invoke(proj, *j)) == false}.

\pnum
\complexity
At most
$\log_2(\tcode{last - first}) + \bigoh{1}$
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{equal_range}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
  tagged_pair<tag::begin(I), tag::end(I)>
    equal_range(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
  tagged_pair<tag::begin(safe_iterator_t<Rng>),
              tag::end(safe_iterator_t<Rng>)>
    equal_range(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

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

\pnum
\complexity
At most
$2 * \log_2(\tcode{last - first}) + \bigoh{1}$
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{binary_search}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
  bool
    binary_search(I first, S last, const T& value, Comp comp = Comp{},
                  Proj proj = Proj{});

template <ForwardRange Rng, class T, class Proj = identity,
    IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
  bool
    binary_search(Rng&& rng, const T& value, Comp comp = Comp{},
                  Proj proj = Proj{});
\end{itemdecl}

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

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

\pnum
\complexity
At most
$\log_2(\tcode{last - first}) + \bigoh{1}$
applications of the comparison function and projection.
\end{itemdescr}

\rSec2[alg.merge]{Merge}

\indexlibrary{\idxcode{merge}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity,
    class Proj2 = identity>
  requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
    merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
          Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>,
    class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
               tag::in2(safe_iterator_t<Rng2>),
               tag::out(O)>
    merge(Rng1&& rng1, Rng2&& rng2, O result,
          Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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)}.
If an element \tcode{a} precedes \tcode{b} in an input range,
\tcode{a} is copied into the output range before \tcode{b}. If \tcode{e1} is
an element of \range{first1}{last1} and \tcode{e2} of \range{first2}{last2},
\tcode{e2} is copied into the output range before \tcode{e1} if and only if
\tcode{bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))} is
\tcode{true}.

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

\pnum
\returns
\tcode{make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result_last)}.

\pnum
\complexity
At most
\tcode{(last1 - first1) + (last2 - first2) - 1}
applications of the comparison function and each projection.

\pnum
\remarks Stable~(\cxxref{algorithm.stable}).
\end{itemdescr}

\indexlibrary{\idxcode{inplace_merge}}%
\begin{itemdecl}
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I
    inplace_merge(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <BidirectionalRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    inplace_merge(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
                  Proj proj = Proj{});
\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{invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1)))}
will be false.

\pnum
\requires
The ranges \range{first}{middle} and \range{middle}{last} shall be
sorted with respect to \tcode{comp} and \tcode{proj}.

\pnum
\returns \tcode{last}

\pnum
\complexity
When enough additional memory is available,
\tcode{(last - first) - 1}
applications of the comparison function and projection.
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
\remarks Stable~(\cxxref{algorithm.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~(\cxxref{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 <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    class Proj1 = identity, class Proj2 = identity,
    IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
  bool
    includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = Comp{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
    class Proj2 = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
      projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
  bool
    includes(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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}
applications of the comparison function and projections.
\end{itemdescr}

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

\indexlibrary{\idxcode{set_union}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
    set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = Comp{},
              Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
    class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
               tag::in2(safe_iterator_t<Rng2>),
               tag::out(O)>
    set_union(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
              Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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
\tcode{make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + $n$)}, \\ where \tcode{$n$} is
the number of elements in the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
applications of the comparison function and projections.

\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 <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
  O
    set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                     Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
    class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
  O
    set_intersection(Rng1&& rng1, Rng2&& rng2, O result,
                     Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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}
applications of the comparison function and projections.

\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 <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
  tagged_pair<tag::in1(I1), tag::out(O)>
    set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                   Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
    class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
  tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::out(O)>
    set_difference(Rng1&& rng1, Rng2&& rng2, O result,
                   Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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
\tcode{\{last1, result + $n$\}}, where $n$
is the number of elements in the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
applications of the comparison function and projections.

\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 <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
    set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                             Comp comp = Comp{}, Proj1 proj1 = Proj1{},
                             Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O,
    class Comp = less<>, class Proj1 = identity, class Proj2 = identity>
  requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
  tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
               tag::in2(safe_iterator_t<Rng2>),
               tag::out(O)>
    set_symmetric_difference(Rng1&& rng1, Rng2&& rng2, O result, Comp comp = Comp{},
                             Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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
\tcode{make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result + $n$)}, \\ where \tcode{$n$} is
the number of elements in the constructed range.

\pnum
\complexity
At most
\tcode{2 * ((last1 - first1) + (last2 - first2)) - 1}
applications of the comparison function and projections.

\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
\bigoh{\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 <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I push_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    push_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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.

\pnum
\returns \tcode{last}

\pnum
\complexity
At most
\tcode{log(last - first)}
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{pop_heap}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I pop_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    pop_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
The range
\range{first}{last}
shall be a valid non-empty heap.

\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
\returns \tcode{last}

\pnum
\complexity
At most
\tcode{2 * log(last - first)}
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{make_heap}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I make_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    make_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\pnum
\returns \tcode{last}

\pnum
\complexity
At most
\tcode{3 * (last - first)}
applications of the comparison function and projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{sort_heap}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  I sort_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  safe_iterator_t<Rng>
    sort_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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.

\pnum
\returns \tcode{last}

\pnum
\complexity
At most $N \log(N)$
comparisons (where
\tcode{N == last - first}), and exactly twice as many applications of the projection.
\end{itemdescr}

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

\indexlibrary{\idxcode{is_heap}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  bool is_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  bool
    is_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

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

\indexlibrary{\idxcode{is_heap_until}}%
\begin{itemdecl}
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  I is_heap_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <RandomAccessRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    is_heap_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr const T& min(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The smaller value.

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

\indexlibrary{\idxcode{min}}%
\begin{itemdecl}
template <Copyable T, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr T min(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  requires Copyable<value_type_t<iterator_t<Rng>>>
  value_type_t<iterator_t<Rng>>
    min(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{distance(rng) > 0}.

\pnum
\returns The smallest value in the \tcode{initializer_list} or range.

\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, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr const T& max(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The larger value.

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

\indexlibrary{\idxcode{max}}%
\begin{itemdecl}
template <Copyable T, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr T max(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  requires Copyable<value_type_t<iterator_t<Rng>>>
  value_type_t<iterator_t<Rng>>
    max(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{distance(rng) > 0}.

\pnum
\returns The largest value in the \tcode{initializer_list} or range.

\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, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr tagged_pair<tag::min(const T&), tag::max(const T&)>
    minmax(const T& a, const T& b, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{\{b, a\}} if \tcode{b} is smaller
than \tcode{a}, and
\tcode{\{a, b\}} otherwise.

\pnum
\notes
Returns \tcode{\{a, b\}} when the arguments are equivalent.

\pnum
\complexity
Exactly one comparison and exactly two applications of the projection.
\end{itemdescr}

\indexlibrary{\idxcode{minmax}}%
\begin{itemdecl}
template <Copyable T, class Proj = identity,
    IndirectStrictWeakOrder<projected<const T*, Proj>> Comp = less<>>
  constexpr tagged_pair<tag::min(T), tag::max(T)>
    minmax(initializer_list<T> rng, Comp comp = Comp{}, Proj proj = Proj{});

template <InputRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj> Comp = less<>>
  requires Copyable<value_type_t<iterator_t<Rng>>>
  tagged_pair<tag::min(value_type_t<iterator_t<Rng>>),
              tag::max(value_type_t<iterator_t<Rng>>)>
    minmax(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{distance(rng) > 0}.

\pnum
\returns \tcode{\{x, y\}}, where \tcode{x} has the smallest and \tcode{y} has the
largest value in the \tcode{initializer_list} or range.

\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) * distance(rng)}
applications of the corresponding predicate, and at most twice as many applications of the projection.
\end{itemdescr}

\indexlibrary{\idxcode{min_element}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  I min_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    min_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
in the range
\range{first}{last}
such that for every iterator
\tcode{j}
in the range
\range{first}{last}
the following corresponding condition holds: \\
\tcode{invoke(comp, invoke(proj, *j), invoke(\brk{}proj, *i)) == false}.
Returns
\tcode{last}
if
\tcode{first == last}.

\pnum
\complexity
Exactly
\tcode{max((last - first) - 1, 0)}
applications of the comparison function and
exactly twice as many applications of the projection.
\end{itemdescr}

\indexlibrary{\idxcode{max_element}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  I max_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  safe_iterator_t<Rng>
    max_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The first iterator
\tcode{i}
in the range
\range{first}{last}
such that for every iterator
\tcode{j}
in the range
\range{first}{last}
the following corresponding condition holds: \\
\tcode{invoke(comp, invoke(proj, *i), invoke(proj, *j)) == false}.
Returns
\tcode{last}
if
\tcode{first == last}.

\pnum
\complexity
Exactly
\tcode{max((last - first) - 1, 0)}
applications of the comparison function and
exactly twice as many applications of the projection.
\end{itemdescr}

\indexlibrary{\idxcode{minmax_element}}%
\begin{itemdecl}
template <ForwardIterator I, Sentinel<I> S, class Proj = identity,
    IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
  tagged_pair<tag::min(I), tag::max(I)>
    minmax_element(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <ForwardRange Rng, class Proj = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
  tagged_pair<tag::min(safe_iterator_t<Rng>),
              tag::max(safe_iterator_t<Rng>)>
    minmax_element(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{\{first, first\}} if \range{first}{last} is empty, otherwise
\tcode{\{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 comparison function and
at most twice as many applications of the projection,
where $N$ is \tcode{distance(first, last)}.
\end{itemdescr}

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

\indexlibrary{\idxcode{lexicographical_compare}}%
\begin{itemdecl}
template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
    class Proj1 = identity, class Proj2 = identity,
    IndirectStrictWeakOrder<projected<I1, Proj1>, projected<I2, Proj2>> Comp = less<>>
  bool
    lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
                            Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template <InputRange Rng1, InputRange Rng2, class Proj1 = identity,
    class Proj2 = identity,
    IndirectStrictWeakOrder<projected<iterator_t<Rng1>, Proj1>,
      projected<iterator_t<Rng2>, Proj2>> Comp = less<>>
  bool
    lexicographical_compare(Rng1&& rng1, Rng2&& rng2, Comp comp = Comp{},
                            Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
\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 and projections.

\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, (void) ++first2) {
  if (invoke(comp, invoke(proj1, *first1), invoke(proj2, *first2))) return true;
  if (invoke(comp, invoke(proj2, *first2), invoke(proj1, *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 <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  bool next_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <BidirectionalRange Rng, class Comp = less<>,
    class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  bool
    next_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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{comp} and \tcode{proj}.
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
\complexity
At most
\tcode{(last - first)/2}
swaps.
\end{itemdescr}

\indexlibrary{\idxcode{prev_permutation}}%
\begin{itemdecl}
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
    class Proj = identity>
  requires Sortable<I, Comp, Proj>
  bool prev_permutation(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});

template <BidirectionalRange Rng, class Comp = less<>,
    class Proj = identity>
  requires Sortable<iterator_t<Rng>, Comp, Proj>
  bool
    prev_permutation(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
\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{comp} and \tcode{proj}.

\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
\complexity
At most
\tcode{(last - first)/2}
swaps.
\end{itemdescr}