%!TEX root = std.tex
\rSec0[iterators]{Iterators library}

\rSec1[iterators.general]{General}

\pnum
This Clause describes components that \Cpp{} programs may use to perform
iterations over containers\iref{containers},
streams\iref{iostream.format},
stream buffers\iref{stream.buffers},
and other ranges\iref{ranges}.

\pnum
The following subclauses describe
iterator requirements, and
components for
iterator primitives,
predefined iterators,
and stream iterators,
as summarized in \tref{iterators.summary}.

\begin{libsumtab}{Iterators library summary}{iterators.summary}
\ref{iterator.requirements} & Iterator requirements     & \tcode{<iterator>} \\
\ref{iterator.primitives}   & Iterator primitives       &                    \\
\ref{predef.iterators}      & Iterator adaptors         &                    \\
\ref{stream.iterators}      & Stream iterators          &                    \\
\ref{iterator.range}        & Range access              &                    \\
\end{libsumtab}

\rSec1[iterator.synopsis]{Header \tcode{<iterator>}\ synopsis}

\indexheader{iterator}%
\begin{codeblock}
#include <compare>              // see \ref{compare.syn}
#include <concepts>             // see \ref{concepts.syn}
#include <initializer_list>     // see \ref{initializer.list.syn}

namespace std {
  template<class T> using @\exposid{with-reference}@ = T&;  // \expos
  template<class T> concept @\defexposconcept{can-reference}@       // \expos
    = requires { typename @\placeholdernc{with-reference}@<T>; };
  template<class T> concept @\defexposconcept{dereferenceable}@     // \expos
    = requires(T& t) {
      { *t } -> @\exposconcept{can-reference}@;  // not required to be equality-preserving
    };

  // \ref{iterator.assoc.types}, associated types
  // \ref{incrementable.traits}, incrementable traits
  template<class> struct incrementable_traits;                                      // freestanding
  template<class T>
    using iter_difference_t = @\seebelow@;                                            // freestanding

  // \ref{readable.traits}, indirectly readable traits
  template<class> struct indirectly_readable_traits;                                // freestanding
  template<class T>
    using iter_value_t = @\seebelow@;                                                 // freestanding

  // \ref{iterator.traits}, iterator traits
  template<class I> struct iterator_traits;                                         // freestanding
  template<class T> requires is_object_v<T> struct iterator_traits<T*>;             // freestanding

  template<@\exposconcept{dereferenceable}@ T>
    using @\libglobal{iter_reference_t}@ = decltype(*declval<T&>());                              // freestanding

  namespace ranges {
    // \ref{iterator.cust}, customization point objects
    inline namespace @\unspec@ {
      // \ref{iterator.cust.move}, \tcode{ranges::iter_move}
      inline constexpr @\unspec@ iter_move = @\unspec@;                         // freestanding

      // \ref{iterator.cust.swap}, \tcode{ranges::iter_swap}
      inline constexpr @\unspec@ iter_swap = @\unspec@;                         // freestanding
    }
  }

  template<@\exposconcept{dereferenceable}@ T>
    requires requires(T& t) {
      { ranges::iter_move(t) } -> @\exposconcept{can-reference}@;
    }
  using @\libglobal{iter_rvalue_reference_t}@                                                     // freestanding
    = decltype(ranges::iter_move(declval<T&>()));

  // \ref{iterator.concepts}, iterator concepts
  // \ref{iterator.concept.readable}, concept \libconcept{indirectly_readable}
  template<class In>
    concept indirectly_readable = @\seebelow@;                                        // freestanding

  // \ref{indirectcallable.traits}, indirect callable traits
  template<@\libconcept{indirectly_readable}@ T>
    using @\exposidnc{indirect-value-t}@ = @\seebelow@;         // \expos

  template<@\libconcept{indirectly_readable}@ T>
    using @\libglobal{iter_common_reference_t}@ =                                                 // freestanding
      common_reference_t<iter_reference_t<T>, @\exposid{indirect-value-t}@<T>>;

  // \ref{iterator.concept.writable}, concept \libconcept{indirectly_writable}
  template<class Out, class T>
    concept indirectly_writable = @\seebelow@;                                        // freestanding

  // \ref{iterator.concept.winc}, concept \libconcept{weakly_incrementable}
  template<class I>
    concept weakly_incrementable = @\seebelow@;                                       // freestanding

  // \ref{iterator.concept.inc}, concept \libconcept{incrementable}
  template<class I>
    concept incrementable = @\seebelow@;                                              // freestanding

  // \ref{iterator.concept.iterator}, concept \libconcept{input_or_output_iterator}
  template<class I>
    concept input_or_output_iterator = @\seebelow@;                                   // freestanding

  // \ref{iterator.concept.sentinel}, concept \libconcept{sentinel_for}
  template<class S, class I>
    concept sentinel_for = @\seebelow@;                                               // freestanding

  // \ref{iterator.concept.sizedsentinel}, concept \libconcept{sized_sentinel_for}
  template<class S, class I>
    constexpr bool disable_sized_sentinel_for = false;                              // freestanding

  template<class S, class I>
    concept sized_sentinel_for = @\seebelow@;                                         // freestanding

  // \ref{iterator.concept.input}, concept \libconcept{input_iterator}
  template<class I>
    concept input_iterator = @\seebelow@;                                             // freestanding

  // \ref{iterator.concept.output}, concept \libconcept{output_iterator}
  template<class I, class T>
    concept output_iterator = @\seebelow@;                                            // freestanding

  // \ref{iterator.concept.forward}, concept \libconcept{forward_iterator}
  template<class I>
    concept forward_iterator = @\seebelow@;                                           // freestanding

  // \ref{iterator.concept.bidir}, concept \libconcept{bidirectional_iterator}
  template<class I>
    concept bidirectional_iterator = @\seebelow@;                                     // freestanding

  // \ref{iterator.concept.random.access}, concept \libconcept{random_access_iterator}
  template<class I>
    concept random_access_iterator = @\seebelow@;                                     // freestanding

  // \ref{iterator.concept.contiguous}, concept \libconcept{contiguous_iterator}
  template<class I>
    concept contiguous_iterator = @\seebelow@;                                        // freestanding

  // \ref{indirectcallable}, indirect callable requirements
  // \ref{indirectcallable.indirectinvocable}, indirect callables
  template<class F, class I>
    concept indirectly_unary_invocable = @\seebelow@;                                 // freestanding

  template<class F, class I>
    concept indirectly_regular_unary_invocable = @\seebelow@;                         // freestanding

  template<class F, class I>
    concept indirect_unary_predicate = @\seebelow@;                                   // freestanding

  template<class F, class I1, class I2>
    concept indirect_binary_predicate = @\seebelow@;                                  // freestanding

  template<class F, class I1, class I2 = I1>
    concept indirect_equivalence_relation = @\seebelow@;                              // freestanding

  template<class F, class I1, class I2 = I1>
    concept indirect_strict_weak_order = @\seebelow@;                                 // freestanding

  template<class F, class... Is>
    requires (@\libconcept{indirectly_readable}@<Is> && ...) && @\libconcept{invocable}@<F, iter_reference_t<Is>...>
      using @\libglobal{indirect_result_t}@ = invoke_result_t<F, iter_reference_t<Is>...>;        // freestanding

  // \ref{projected}, projected
  template<@\libconcept{indirectly_readable}@ I, @\libconcept{indirectly_regular_unary_invocable}@<I> Proj>
    using projected = @\seebelow@;                                                    // freestanding

  template<@\libconcept{indirectly_readable}@ I, @\libconcept{indirectly_regular_unary_invocable}@<I> Proj>
  using projected_value_t =                                                         // freestanding
    remove_cvref_t<invoke_result_t<Proj&, iter_value_t<I>&>>;

  // \ref{alg.req}, common algorithm requirements
  // \ref{alg.req.ind.move}, concept \libconcept{indirectly_movable}
  template<class In, class Out>
    concept indirectly_movable = @\seebelow@;                                         // freestanding

  template<class In, class Out>
    concept indirectly_movable_storable = @\seebelow@;                                // freestanding

  // \ref{alg.req.ind.copy}, concept \libconcept{indirectly_copyable}
  template<class In, class Out>
    concept indirectly_copyable = @\seebelow@;                                        // freestanding

  template<class In, class Out>
    concept indirectly_copyable_storable = @\seebelow@;                               // freestanding

  // \ref{alg.req.ind.swap}, concept \libconcept{indirectly_swappable}
  template<class I1, class I2 = I1>
    concept indirectly_swappable = @\seebelow@;                                       // freestanding

  // \ref{alg.req.ind.cmp}, concept \libconcept{indirectly_comparable}
  template<class I1, class I2, class R, class P1 = identity, class P2 = identity>
    concept indirectly_comparable = @\seebelow@;                                      // freestanding

  // \ref{alg.req.permutable}, concept \libconcept{permutable}
  template<class I>
    concept permutable = @\seebelow@;                                                 // freestanding

  // \ref{alg.req.mergeable}, concept \libconcept{mergeable}
  template<class I1, class I2, class Out,
           class R = ranges::less, class P1 = identity, class P2 = identity>
    concept mergeable = @\seebelow@;                                                  // freestanding

  // \ref{alg.req.sortable}, concept \libconcept{sortable}
  template<class I, class R = ranges::less, class P = identity>
    concept sortable = @\seebelow@;                                                   // freestanding

  // \ref{iterator.primitives}, primitives
  // \ref{std.iterator.tags}, iterator tags
  struct input_iterator_tag { };                                                    // freestanding
  struct output_iterator_tag { };                                                   // freestanding
  struct forward_iterator_tag: public input_iterator_tag { };                       // freestanding
  struct bidirectional_iterator_tag: public forward_iterator_tag { };               // freestanding
  struct random_access_iterator_tag: public bidirectional_iterator_tag { };         // freestanding
  struct contiguous_iterator_tag: public random_access_iterator_tag { };            // freestanding

  // \ref{iterator.operations}, iterator operations
  template<class InputIterator, class Distance>
    constexpr void
      advance(InputIterator& i, Distance n);                                        // freestanding
  template<class InputIterator>
    constexpr typename iterator_traits<InputIterator>::difference_type
      distance(InputIterator first, InputIterator last);                            // freestanding
  template<class InputIterator>
    constexpr InputIterator
      next(InputIterator x,                                                         // freestanding
           typename iterator_traits<InputIterator>::difference_type n = 1);
  template<class BidirectionalIterator>
    constexpr BidirectionalIterator
      prev(BidirectionalIterator x,                                                 // freestanding
           typename iterator_traits<BidirectionalIterator>::difference_type n = 1);

  // \ref{range.iter.ops}, range iterator operations
  namespace ranges {
    // \ref{range.iter.op.advance}, \tcode{ranges::advance}
    template<@\libconcept{input_or_output_iterator}@ I>
      constexpr void advance(I& i, iter_difference_t<I> n);                         // freestanding
    template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
      constexpr void advance(I& i, S bound);                                        // freestanding
    template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
      constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n,          // freestanding
                                             S bound);

    // \ref{range.iter.op.distance}, \tcode{ranges::distance}
    template<class I, @\libconcept{sentinel_for}@<I> S>
      requires (!@\libconcept{sized_sentinel_for}@<S, I>)
      constexpr iter_difference_t<I> distance(I first, S last);                     // freestanding
    template<class I, @\libconcept{sized_sentinel_for}@<decay_t<I>> S>
      constexpr iter_difference_t<decay_t<I>> distance(I&& first, S last);          // freestanding
    template<@\libconcept{range}@ R>
      constexpr range_difference_t<R> distance(R&& r);                              // freestanding

    // \ref{range.iter.op.next}, \tcode{ranges::next}
    template<@\libconcept{input_or_output_iterator}@ I>
      constexpr I next(I x);                                                        // freestanding
    template<@\libconcept{input_or_output_iterator}@ I>
      constexpr I next(I x, iter_difference_t<I> n);                                // freestanding
    template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
      constexpr I next(I x, S bound);                                               // freestanding
    template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
      constexpr I next(I x, iter_difference_t<I> n, S bound);                       // freestanding

    // \ref{range.iter.op.prev}, \tcode{ranges::prev}
    template<@\libconcept{bidirectional_iterator}@ I>
      constexpr I prev(I x);                                                        // freestanding
    template<@\libconcept{bidirectional_iterator}@ I>
      constexpr I prev(I x, iter_difference_t<I> n);                                // freestanding
    template<@\libconcept{bidirectional_iterator}@ I>
      constexpr I prev(I x, iter_difference_t<I> n, I bound);                       // freestanding
  }

  // \ref{predef.iterators}, predefined iterators and sentinels
  // \ref{reverse.iterators}, reverse iterators
  template<class Iterator> class reverse_iterator;                                  // freestanding

  template<class Iterator1, class Iterator2>
    constexpr bool operator==(                                                      // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator!=(                                                      // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator<(                                                       // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator>(                                                       // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator<=(                                                      // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator>=(                                                      // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template<class Iterator1, @\libconcept{three_way_comparable_with}@<Iterator1> Iterator2>
    constexpr compare_three_way_result_t<Iterator1, Iterator2>
      operator<=>(const reverse_iterator<Iterator1>& x,                             // freestanding
                  const reverse_iterator<Iterator2>& y);

  template<class Iterator1, class Iterator2>
    constexpr auto operator-(                                                       // freestanding
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
  template<class Iterator>
    constexpr reverse_iterator<Iterator> operator+(                                 // freestanding
      iter_difference_t<Iterator> n,
      const reverse_iterator<Iterator>& x);

  template<class Iterator>
    constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i);         // freestanding

  template<class Iterator1, class Iterator2>
    requires (!@\libconcept{sized_sentinel_for}@<Iterator1, Iterator2>)
    constexpr bool @\libspec{disable_sized_sentinel_for}{reverse_iterator}@<reverse_iterator<Iterator1>,          // freestanding
                                              reverse_iterator<Iterator2>> = true;

  // \ref{insert.iterators}, insert iterators
  template<class Container> class back_insert_iterator;                             // freestanding
  template<class Container>
    constexpr back_insert_iterator<Container> back_inserter(Container& x);          // freestanding

  template<class Container> class front_insert_iterator;                            // freestanding
  template<class Container>
    constexpr front_insert_iterator<Container> front_inserter(Container& x);        // freestanding

  template<class Container> class insert_iterator;                                  // freestanding
  template<class Container>
    constexpr insert_iterator<Container>
      inserter(Container& x, ranges::iterator_t<Container> i);                      // freestanding

  // \ref{const.iterators}, constant iterators and sentinels
  // \ref{const.iterators.alias}, alias templates
  template<@\libconcept{indirectly_readable}@ I>
    using iter_const_reference_t = @\seebelow@;                                       // freestanding
  template<class Iterator>
    concept @\exposconcept{constant-iterator}@ = @\seebelow@; // \expos
  template<@\libconcept{input_iterator}@ I>
    using const_iterator = @\seebelow@;                                               // freestanding
  template<@\libconcept{semiregular}@ S>
    using const_sentinel = @\seebelow@;                                               // freestanding

  // \ref{const.iterators.iterator}, class template \tcode{basic_const_iterator}
  template<@\libconcept{input_iterator}@ Iterator>
    class basic_const_iterator;                                                     // freestanding

  template<class T, @\libconcept{common_with}@<T> U>
    requires @\libconcept{input_iterator}@<common_type_t<T, U>>
  struct common_type<basic_const_iterator<T>, U> {                                  // freestanding
    using type = basic_const_iterator<common_type_t<T, U>>;
  };
  template<class T, @\libconcept{common_with}@<T> U>
    requires @\libconcept{input_iterator}@<common_type_t<T, U>>
  struct common_type<U, basic_const_iterator<T>> {                                  // freestanding
    using type = basic_const_iterator<common_type_t<T, U>>;
  };
  template<class T, @\libconcept{common_with}@<T> U>
    requires @\libconcept{input_iterator}@<common_type_t<T, U>>
  struct common_type<basic_const_iterator<T>, basic_const_iterator<U>> {            // freestanding
    using type = basic_const_iterator<common_type_t<T, U>>;
  };

  template<@\libconcept{input_iterator}@ I>
    constexpr const_iterator<I> @\libglobal{make_const_iterator}@(I it) { return it; }            // freestanding

  template<@\libconcept{semiregular}@ S>
    constexpr const_sentinel<S> @\libglobal{make_const_sentinel}@(S s) { return s; }              // freestanding

  // \ref{move.iterators}, move iterators and sentinels
  template<class Iterator> class move_iterator;                                     // freestanding

  template<class Iterator1, class Iterator2>
    constexpr bool operator==(                                                      // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator<(                                                       // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator>(                                                       // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator<=(                                                      // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template<class Iterator1, class Iterator2>
    constexpr bool operator>=(                                                      // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template<class Iterator1, @\libconcept{three_way_comparable_with}@<Iterator1> Iterator2>
    constexpr compare_three_way_result_t<Iterator1, Iterator2>
      operator<=>(const move_iterator<Iterator1>& x,                                // freestanding
                  const move_iterator<Iterator2>& y);

  template<class Iterator1, class Iterator2>
    constexpr auto operator-(                                                       // freestanding
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y)
        -> decltype(x.base() - y.base());
  template<class Iterator>
    constexpr move_iterator<Iterator>
      operator+(iter_difference_t<Iterator> n, const move_iterator<Iterator>& x);   // freestanding

  template<class Iterator>
    constexpr move_iterator<Iterator> make_move_iterator(Iterator i);               // freestanding

  template<class Iterator1, class Iterator2>
    requires (!@\libconcept{sized_sentinel_for}@<Iterator1, Iterator2>)
    constexpr bool @\libspec{disable_sized_sentinel_for}{move_iterator}@<move_iterator<Iterator1>,             // freestanding
                                              move_iterator<Iterator2>> = true;

  template<@\libconcept{semiregular}@ S> class move_sentinel;                                      // freestanding

  // \ref{iterators.common}, common iterators
  template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
    requires (!@\libconcept{same_as}@<I, S> && @\libconcept{copyable}@<I>)
      class common_iterator;                                                        // freestanding

  template<class I, class S>
    struct incrementable_traits<common_iterator<I, S>>;                             // freestanding

  template<@\libconcept{input_iterator}@ I, class S>
    struct iterator_traits<common_iterator<I, S>>;                                  // freestanding

  // \ref{default.sentinel}, default sentinel
  struct default_sentinel_t;                                                        // freestanding
  inline constexpr default_sentinel_t @\libglobal{default_sentinel}@{};                           // freestanding

  // \ref{iterators.counted}, counted iterators
  template<@\libconcept{input_or_output_iterator}@ I> class counted_iterator;                      // freestanding

  template<@\libconcept{input_iterator}@ I>
    requires @\seebelow@
    struct iterator_traits<counted_iterator<I>>;                                    // freestanding

  // \ref{unreachable.sentinel}, unreachable sentinel
  struct unreachable_sentinel_t;                                                    // freestanding
  inline constexpr unreachable_sentinel_t @\libglobal{unreachable_sentinel}@{};                   // freestanding

  // \ref{stream.iterators}, stream iterators
  template<class T, class charT = char, class traits = char_traits<charT>,
           class Distance = ptrdiff_t>
  class istream_iterator;
  template<class T, class charT, class traits, class Distance>
    bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
                    const istream_iterator<T,charT,traits,Distance>& y);

  template<class T, class charT = char, class traits = char_traits<charT>>
    class ostream_iterator;

  template<class charT, class traits = char_traits<charT>>
    class istreambuf_iterator;
  template<class charT, class traits>
    bool operator==(const istreambuf_iterator<charT,traits>& a,
                    const istreambuf_iterator<charT,traits>& b);

  template<class charT, class traits = char_traits<charT>>
    class ostreambuf_iterator;

  // \ref{iterator.range}, range access
  template<class C> constexpr auto
    begin(C& c) noexcept(noexcept(c.begin())) -> decltype(c.begin());               // freestanding
  template<class C> constexpr auto
    begin(const C& c) noexcept(noexcept(c.begin())) -> decltype(c.begin());         // freestanding
  template<class C> constexpr auto
    end(C& c) noexcept(noexcept(c.end())) -> decltype(c.end());                     // freestanding
  template<class C> constexpr auto
    end(const C& c) noexcept(noexcept(c.end())) -> decltype(c.end());               // freestanding
  template<class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;           // freestanding
  template<class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;             // freestanding
  template<class C> constexpr auto
    cbegin(const C& c) noexcept(noexcept(std::begin(c)))
      -> decltype(std::begin(c));                                                   // freestanding
  template<class C> constexpr auto
    cend(const C& c) noexcept(noexcept(std::end(c))) -> decltype(std::end(c));      // freestanding
  template<class C> constexpr auto
    rbegin(C& c) noexcept(noexcept(c.rbegin())) -> decltype(c.rbegin());            // freestanding
  template<class C> constexpr auto
    rbegin(const C& c) noexcept(noexcept(c.rbegin())) -> decltype(c.rbegin());      // freestanding
  template<class C> constexpr auto
    rend(C& c) noexcept(noexcept(c.rend())) -> decltype(c.rend());                  // freestanding
  template<class C> constexpr auto
    rend(const C& c) noexcept(noexcept(c.rend())) -> decltype(c.rend());            // freestanding
  template<class T, size_t N> constexpr reverse_iterator<T*>
    rbegin(T (&array)[N]) noexcept;                                                 // freestanding
  template<class T, size_t N> constexpr reverse_iterator<T*>
    rend(T (&array)[N]) noexcept;                                                   // freestanding
  template<class E> constexpr reverse_iterator<const E*>
    rbegin(initializer_list<E> il) noexcept;                                        // freestanding
  template<class E> constexpr reverse_iterator<const E*>
    rend(initializer_list<E> il) noexcept;                                          // freestanding
  template<class C> constexpr auto
    crbegin(const C& c) noexcept(noexcept(std::rbegin(c)))
      -> decltype(std::rbegin(c));                                                  // freestanding
  template<class C> constexpr auto
    crend(const C& c) noexcept(noexcept(std::rend(c))) -> decltype(std::rend(c));   // freestanding

  template<class C> constexpr auto
    size(const C& c) noexcept(noexcept(c.size())) -> decltype(c.size());            // freestanding
  template<class T, size_t N> constexpr size_t
    size(const T (&array)[N]) noexcept;                                             // freestanding

  template<class C> constexpr auto
    ssize(const C& c) noexcept(noexcept(c.size()))
      -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>;               // freestanding
  template<class T, ptrdiff_t N> constexpr ptrdiff_t
    ssize(const T (&array)[N]) noexcept;                                            // freestanding

  template<class C> constexpr auto
    empty(const C& c) noexcept(noexcept(c.empty())) -> decltype(c.empty());         // freestanding
  template<class T, size_t N> constexpr bool
    empty(const T (&array)[N]) noexcept;                                            // freestanding

  template<class C> constexpr auto
    data(C& c) noexcept(noexcept(c.data())) -> decltype(c.data());                  // freestanding
  template<class C> constexpr auto
    data(const C& c) noexcept(noexcept(c.data())) -> decltype(c.data());            // freestanding
  template<class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;            // freestanding
}
\end{codeblock}

\rSec1[iterator.requirements]{Iterator requirements}

\rSec2[iterator.requirements.general]{General}

\pnum
\indextext{requirements!iterator}%
Iterators are a generalization of pointers that allow a \Cpp{} program to work with different data structures
(for example, containers and ranges) in a uniform manner.
To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators.
An input iterator
\tcode{i}
supports the expression
\tcode{*i},
resulting in a value of some object type
\tcode{T},
called the
\defn{value type}
of the iterator.
An output iterator \tcode{i} has a non-empty set of types that are
\defn{writable} to the iterator;
for each such type \tcode{T}, the expression \tcode{*i = o}
is valid where \tcode{o} is a value of type \tcode{T}.
For every iterator type
\tcode{X},
there is a corresponding signed integer-like type\iref{iterator.concept.winc} called the
\defn{difference type}
of the iterator.

\pnum
Since iterators are an abstraction of pointers, their semantics are
a generalization of most of the semantics of pointers in \Cpp{}.
This ensures that every
function template
that takes iterators
works as well with regular pointers.
This document defines
six categories of iterators, according to the operations
defined on them:
\term{input iterators},
\term{output iterators},
\term{forward iterators},
\term{bidirectional iterators},
\term{random access iterators},
and
\term{contiguous iterators},
as shown in \tref{iterators.relations}.

\begin{floattable}{Relations among iterator categories}{iterators.relations}
{lllll}
\topline
\textbf{Contiguous}                  &
$\rightarrow$ \textbf{Random Access} &
$\rightarrow$ \textbf{Bidirectional} &
$\rightarrow$ \textbf{Forward}       &
$\rightarrow$ \textbf{Input}         \\
&&&&
$\rightarrow$ \textbf{Output}        \\
\end{floattable}

\pnum
The six categories of iterators correspond to the iterator concepts
\begin{itemize}
\item \libconcept{input_iterator}\iref{iterator.concept.input},
\item \libconcept{output_iterator}\iref{iterator.concept.output},
\item \libconcept{forward_iterator}\iref{iterator.concept.forward},
\item \libconcept{bidirectional_iterator}\iref{iterator.concept.bidir},
\item \libconcept{random_access_iterator}\iref{iterator.concept.random.access},
and
\item \libconcept{contiguous_iterator}\iref{iterator.concept.contiguous},
\end{itemize}
respectively.
The generic term \defn{iterator} refers to any type that models the
\libconcept{input_or_output_iterator} concept\iref{iterator.concept.iterator}.

\pnum
Forward iterators meet all the requirements of input
iterators and can be used whenever
an input iterator is specified;
Bidirectional iterators also meet all the requirements of
forward iterators and can be used whenever a forward iterator is specified;
Random access iterators also meet all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified;
Contiguous iterators also meet all the requirements of random access
iterators and can be used whenever a random access iterator is specified.

\pnum
Iterators that further meet the requirements of output iterators are
called \defnx{mutable iterators}{mutable iterator}. Nonmutable iterators are referred to
as \defnx{constant iterators}{constant iterator}.

\pnum
In addition to the requirements in this subclause,
the nested \grammarterm{typedef-name}{s} specified in \ref{iterator.traits}
shall be provided for the iterator type.
\begin{note}
Either the iterator type must provide the \grammarterm{typedef-name}{s} directly
(in which case \tcode{iterator_traits} pick them up automatically), or
an \tcode{iterator_traits} specialization must provide them.
\end{note}

\pnum
\indextext{past-the-end iterator|see{iterator, past-the-end}}%
\indextext{dereferenceable iterator|see{iterator, dereferenceable}}%
Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence.
Such a value is called a \defnx{past-the-end value}{iterator!past-the-end}.
Values of an iterator \tcode{i}
for which the expression \tcode{*i} is defined
are called \defnx{dereferenceable}{iterator!dereferenceable}.
The library never assumes that past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with any
sequence.
Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that meet the
\oldconcept{DefaultConstructible} requirements, using a value-initialized iterator
as the source of a copy or move operation.
\begin{note}
This guarantee is not
offered for default-initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers.
\end{note}
In these cases the singular
value is overwritten the same way as any other value.
Dereferenceable
values are always non-singular.

\pnum
Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges. A \defn{range} is an iterator and a \defn{sentinel}
that designate the beginning and end of the computation, or an iterator and a
count that designate the beginning and the number of elements to which the
computation is to be applied.
\begin{footnote}
The sentinel denoting the end of a range
can have the same type as the iterator denoting the beginning of the range, or a
different type.
\end{footnote}

\pnum
An iterator and a sentinel denoting a range are comparable.
A range \range{i}{s}
is empty if \tcode{i == s};
otherwise, \range{i}{s}
refers to the elements in the data structure starting with the element
pointed to by
\tcode{i}
and up to but not including the element, if any, pointed to by
the first iterator \tcode{j} such that \tcode{j == s}.

\pnum
A sentinel \tcode{s} is called \defn{reachable from} an iterator \tcode{i} if
and only if there is a finite sequence of applications of the expression
\tcode{++i} that makes \tcode{i == s}. If \tcode{s} is reachable from \tcode{i},
\range{i}{s} denotes a \defnadj{valid}{range}.

\pnum
A \defnadj{counted}{range} \countedrange{i}{n} is empty if \tcode{n == 0};
otherwise, \countedrange{i}{n} refers to
the \tcode{n} elements in the data structure
starting with the element pointed to by \tcode{i} and up to but not including
the element, if any, pointed to by
the result of \tcode{n} applications of \tcode{++i}.
A counted range \countedrange{i}{n} is \defnx{valid}{range!counted!valid} if and only if \tcode{n == 0};
or \tcode{n} is positive, \tcode{i} is dereferenceable,
and \countedrange{++i}{--n} is valid.

\pnum
The result of the application of library functions
to invalid ranges is undefined.

\pnum
For an iterator \tcode{i} of a type that
models \libconcept{contiguous_iterator}\iref{iterator.concept.contiguous},
library functions are permitted
to replace \range{i}{s} with
\range{to_address(i)}{to_address(i + ranges::distance(i, s))}, and
to replace \countedrange{i}{n} with \range{to_address(i)}{to_address(i + n)}.
\begin{note}
This means a program cannot rely on any side effects of
dereferencing a contiguous iterator \tcode{i},
because library functions might operate on
pointers obtained by \tcode{to_address(i)}
instead of operating on \tcode{i}.
Similarly, a program cannot rely on any side effects of
individual increments on a contiguous iterator \tcode{i},
because library functions might advance \tcode{i} only once.
\end{note}

\pnum
All the categories of iterators require only those functions that are realizable for a given category in
constant time (amortized).
Therefore, requirement tables and concept definitions for the iterators
do not specify complexity.

\pnum
Destruction of an iterator may invalidate pointers and references previously
obtained from that iterator if its type does not meet the
\oldconcept{ForwardIterator} requirements and does not model \libconcept{forward_iterator}.

\pnum
An \defnadj{invalid}{iterator}
is an iterator that may be singular.
\begin{footnote}
This definition applies to pointers, since pointers are iterators.
The effect of dereferencing an iterator that has been invalidated
is undefined.
\end{footnote}

\pnum
\indextext{iterator!constexpr}%
Iterators meet the \defn{constexpr iterator} requirements
if all operations provided to meet iterator category requirements
are constexpr functions.
\begin{note}
For example, the types ``pointer to \tcode{int}'' and
\tcode{reverse_iterator<int*>} meet the constexpr iterator requirements.
\end{note}

\rSec2[iterator.assoc.types]{Associated types}

\rSec3[incrementable.traits]{Incrementable traits}

\pnum
To implement algorithms only in terms of incrementable types,
it is often necessary to determine the difference type that
corresponds to a particular incrementable type. Accordingly,
it is required that if \tcode{WI} is the name of a type that models the
\libconcept{weakly_incrementable} concept\iref{iterator.concept.winc},
the type
\begin{codeblock}
iter_difference_t<WI>
\end{codeblock}
be defined as the incrementable type's difference type.

\indexlibraryglobal{incrementable_traits}%
\begin{codeblock}
namespace std {
  template<class> struct incrementable_traits { };

  template<class T>
    requires is_object_v<T>
  struct incrementable_traits<T*> {
    using difference_type = ptrdiff_t;
  };

  template<class I>
  struct incrementable_traits<const I>
    : incrementable_traits<I> { };

  template<class T>
    requires requires { typename T::difference_type; }
  struct incrementable_traits<T> {
    using difference_type = T::difference_type;
  };

  template<class T>
    requires (!requires { typename T::difference_type; } &&
              requires(const T& a, const T& b) { { a - b } -> @\libconcept{integral}@; })
  struct incrementable_traits<T> {
    using difference_type = make_signed_t<decltype(declval<T>() - declval<T>())>;
  };

  template<class T>
    using iter_difference_t = @\seebelow@;
}
\end{codeblock}

\indexlibraryglobal{iter_difference_t}%
\pnum
Let $R_\tcode{I}$ be \tcode{remove_cvref_t<I>}.
The type \tcode{iter_difference_t<I>} denotes
\begin{itemize}
\item
\tcode{incrementable_traits<$R_\tcode{I}$>::difference_type}
if \tcode{iterator_traits<$R_\tcode{I}$>} names a specialization
generated from the primary template, and

\item
\tcode{iterator_traits<$R_\tcode{I}$>::difference_type} otherwise.
\end{itemize}

\pnum
Users may specialize \tcode{incrementable_traits} on program-defined types.

\rSec3[readable.traits]{Indirectly readable traits}

\pnum
To implement algorithms only in terms of indirectly readable types,
it is often necessary
to determine the value type that corresponds to
a particular indirectly readable type.
Accordingly, it is required that if \tcode{R} is the name of a type that
models the \libconcept{indirectly_readable} concept\iref{iterator.concept.readable},
the type
\begin{codeblock}
iter_value_t<R>
\end{codeblock}
be defined as the indirectly readable type's value type.

\indexlibraryglobal{indirectly_readable_traits}%
\begin{codeblock}
template<class> struct @\placeholder{cond-value-type}@ { };     // \expos
template<class T>
  requires is_object_v<T>
struct @\placeholder{cond-value-type}@<T> {
  using value_type = remove_cv_t<T>;
};

template<class T>
  concept @\defexposconcept{has-member-value-type}@ = requires { typename T::value_type; };         // \expos

template<class T>
  concept @\defexposconcept{has-member-element-type}@ = requires { typename T::element_type; };     // \expos

template<class> struct indirectly_readable_traits { };

template<class T>
struct indirectly_readable_traits<T*>
  : @\placeholder{cond-value-type}@<T> { };

template<class I>
  requires is_array_v<I>
struct indirectly_readable_traits<I> {
  using value_type = remove_cv_t<remove_extent_t<I>>;
};

template<class I>
struct indirectly_readable_traits<const I>
  : indirectly_readable_traits<I> { };

template<@\exposconcept{has-member-value-type}@ T>
struct indirectly_readable_traits<T>
  : @\placeholder{cond-value-type}@<typename T::value_type> { };

template<@\exposconcept{has-member-element-type}@ T>
struct indirectly_readable_traits<T>
  : @\placeholder{cond-value-type}@<typename T::element_type> { };

template<@\exposconcept{has-member-value-type}@ T>
  requires @\exposconcept{has-member-element-type}@<T>
struct indirectly_readable_traits<T> { };

template<@\exposconcept{has-member-value-type}@ T>
  requires @\exposconcept{has-member-element-type}@<T> &&
           @\libconcept{same_as}@<remove_cv_t<typename T::element_type>, remove_cv_t<typename T::value_type>>
struct indirectly_readable_traits<T>
  : @\placeholder{cond-value-type}@<typename T::value_type> { };

template<class T> using iter_value_t = @\seebelow@;
\end{codeblock}

\indexlibraryglobal{iter_value_t}%
\pnum
Let $R_\tcode{I}$ be \tcode{remove_cvref_t<I>}.
The type \tcode{iter_value_t<I>} denotes
\begin{itemize}
\item
\tcode{indirectly_readable_traits<$R_\tcode{I}$>::value_type}
if \tcode{iterator_traits<$R_\tcode{I}$>} names a specialization
generated from the primary template, and

\item
\tcode{iterator_traits<$R_\tcode{I}$>::value_type} otherwise.
\end{itemize}

\pnum
Class template \tcode{indirectly_readable_traits} may be specialized
on program-defined types.

\pnum
\begin{note}
Some legacy output iterators declare a nested type named \tcode{value_type}
that is an alias for \keyword{void}.
These types are not \libconcept{indirectly_readable}
and have no associated value types.
\end{note}

\pnum
\begin{note}
Smart pointers like \tcode{shared_ptr<int>} are \libconcept{indirectly_readable} and
have an associated value type, but a smart pointer like \tcode{shared_ptr<void>}
is not \libconcept{indirectly_readable} and has no associated value type.
\end{note}

\rSec3[iterator.traits]{Iterator traits}

\pnum
\indexlibraryglobal{iterator_traits}%
To implement algorithms only in terms of iterators, it is sometimes necessary to
determine the iterator category that corresponds to a particular iterator type.
Accordingly, it is required that if
\tcode{I}
is the type of an iterator,
the type
\indexlibrarymember{iterator_category}{iterator_traits}%
\begin{codeblock}
iterator_traits<I>::iterator_category
\end{codeblock}
be declared as the iterator's iterator category.
In addition, the types
\indexlibrarymember{pointer}{iterator_traits}%
\indexlibrarymember{reference}{iterator_traits}%
\begin{codeblock}
iterator_traits<I>::pointer
iterator_traits<I>::reference
\end{codeblock}
shall be declared as the iterator's pointer and reference types;
that is, for an
iterator object \tcode{a} of class type,
the same type as
\tcode{decltype(a.operator->())} and
\tcode{decltype(*a)},
respectively.
The type
\tcode{iterator_traits<I>::pointer}
shall be \keyword{void}
for an iterator of class type \tcode{I}
that does not support \tcode{operator->}.
Additionally, in the case of an output iterator, the types
\indexlibrarymember{value_type}{iterator_traits}%
\indexlibrarymember{difference_type}{iterator_traits}%
\indexlibrarymember{reference}{iterator_traits}%
\begin{codeblock}
iterator_traits<I>::value_type
iterator_traits<I>::difference_type
iterator_traits<I>::reference
\end{codeblock}
may be declared as \keyword{void}.

\pnum
The definitions in this subclause make use of the following
exposition-only concepts:

\begin{codeblock}
template<class I>
concept @\defexposconcept{cpp17-iterator}@ =
  requires(I i) {
    {   *i } -> @\exposconcept{can-reference}@;
    {  ++i } -> @\libconcept{same_as}@<I&>;
    { *i++ } -> @\exposconcept{can-reference}@;
  } && @\libconcept{copyable}@<I>;

template<class I>
concept @\defexposconcept{cpp17-input-iterator}@ =
  @\exposconcept{cpp17-iterator}@<I> && @\libconcept{equality_comparable}@<I> && requires(I i) {
    typename incrementable_traits<I>::difference_type;
    typename indirectly_readable_traits<I>::value_type;
    typename common_reference_t<iter_reference_t<I>&&,
                                typename indirectly_readable_traits<I>::value_type&>;
    typename common_reference_t<decltype(*i++)&&,
                                typename indirectly_readable_traits<I>::value_type&>;
    requires @\libconcept{signed_integral}@<typename incrementable_traits<I>::difference_type>;
  };

template<class I>
concept @\defexposconcept{cpp17-forward-iterator}@ =
  @\exposconcept{cpp17-input-iterator}@<I> && @\libconcept{constructible_from}@<I> &&
  is_reference_v<iter_reference_t<I>> &&
  @\libconcept{same_as}@<remove_cvref_t<iter_reference_t<I>>,
          typename indirectly_readable_traits<I>::value_type> &&
  requires(I i) {
    {  i++ } -> @\libconcept{convertible_to}@<const I&>;
    { *i++ } -> @\libconcept{same_as}@<iter_reference_t<I>>;
  };

template<class I>
concept @\defexposconcept{cpp17-bidirectional-iterator}@ =
  @\exposconcept{cpp17-forward-iterator}@<I> && requires(I i) {
    {  --i } -> @\libconcept{same_as}@<I&>;
    {  i-- } -> @\libconcept{convertible_to}@<const I&>;
    { *i-- } -> @\libconcept{same_as}@<iter_reference_t<I>>;
  };

template<class I>
concept @\defexposconcept{cpp17-random-access-iterator}@ =
  @\exposconcept{cpp17-bidirectional-iterator}@<I> && @\libconcept{totally_ordered}@<I> &&
  requires(I i, typename incrementable_traits<I>::difference_type n) {
    { i += n } -> @\libconcept{same_as}@<I&>;
    { i -= n } -> @\libconcept{same_as}@<I&>;
    { i +  n } -> @\libconcept{same_as}@<I>;
    { n +  i } -> @\libconcept{same_as}@<I>;
    { i -  n } -> @\libconcept{same_as}@<I>;
    { i -  i } -> @\libconcept{same_as}@<decltype(n)>;
    {  i[n]  } -> @\libconcept{convertible_to}@<iter_reference_t<I>>;
  };
\end{codeblock}

\pnum
The members of a specialization \tcode{iterator_traits<I>} generated from the
\tcode{iterator_traits} primary template are computed as follows:

\begin{itemize}
\item
If \tcode{I} has valid\iref{temp.deduct} member
types \tcode{difference_type}, \tcode{value_type},
\tcode{reference}, and \tcode{iterator_category},
then
\tcode{iterator_traits<I>}
has the following publicly accessible members:
\begin{codeblock}
using @\libmember{iterator_category}{iterator_traits}@ = I::iterator_category;
using @\libmember{value_type}{iterator_traits}@        = I::value_type;
using @\libmember{difference_type}{iterator_traits}@   = I::difference_type;
using @\libmember{pointer}{iterator_traits}@           = @\seebelow@;
using @\libmember{reference}{iterator_traits}@         = I::reference;
\end{codeblock}
If the \grammarterm{qualified-id} \tcode{I::pointer} is valid and
denotes a type, then \tcode{iterator_traits<I>::pointer} names that type;
otherwise, it names \keyword{void}.

\item
Otherwise, if \tcode{I} satisfies the exposition-only concept
\exposconcept{cpp17-input-iterator},
%then
\tcode{iterator_traits<I>} has the following
publicly accessible members:
\begin{codeblock}
using iterator_category = @\seebelow@;
using value_type        = indirectly_readable_traits<I>::value_type;
using difference_type   = incrementable_traits<I>::difference_type;
using pointer           = @\seebelow@;
using reference         = @\seebelow@;
\end{codeblock}
\begin{itemize}
\item If the \grammarterm{qualified-id} \tcode{I::pointer} is valid and denotes a type,
\tcode{pointer} names that type. Otherwise, if
\tcode{decltype(\brk{}declval<I\&>().operator->())} is well-formed, then
\tcode{pointer} names that type. Otherwise, \tcode{pointer}
names \keyword{void}.

\item If the \grammarterm{qualified-id} \tcode{I::reference} is valid and denotes a
type, \tcode{reference} names that type. Otherwise, \tcode{reference}
names \tcode{iter_reference_t<I>}.

\item If the \grammarterm{qualified-id} \tcode{I::iterator_category} is valid and
denotes a type, \tcode{iterator_category} names that type.
Otherwise, \tcode{iterator_category} names:
\begin{itemize}
\item
\tcode{random_access_iterator_tag}
if
\tcode{I} satisfies \exposconcept{cpp17-random-access-iterator},
or otherwise
\item
\tcode{bidirectional_iterator_tag} if
\tcode{I} satisfies \exposconcept{cpp17-bidirectional-iterator},
or otherwise
\item
\tcode{forward_iterator_tag} if
\tcode{I} satisfies \exposconcept{cpp17-forward-iterator},
or otherwise
\item
\tcode{input_iterator_tag}.
\end{itemize}
\end{itemize}

\item
Otherwise, if \tcode{I} satisfies the exposition-only concept
\exposconcept{cpp17-iterator}, then \tcode{iterator_traits<I>}
has the following publicly accessible
members:
\begin{codeblock}
using iterator_category = output_iterator_tag;
using value_type        = void;
using difference_type   = @\seebelow@;
using pointer           = void;
using reference         = void;
\end{codeblock}
If the \grammarterm{qualified-id}
\tcode{incrementable_traits<I>::difference_type} is valid and denotes a type,
then \tcode{difference_type} names that type; otherwise, it names \keyword{void}.

\item
Otherwise, \tcode{iterator_traits<I>}
has no members by any of the above names.
\end{itemize}

\pnum
Explicit or partial specializations of \tcode{iterator_traits} may
have a member type \tcode{\libmember{iterator_concept}{iterator_traits}} that is used to indicate
conformance to the iterator concepts\iref{iterator.concepts}.
\begin{example}
To indicate conformance to the \libconcept{input_iterator} concept
but a lack of conformance to
the \oldconcept{InputIter\-ator} requirements\iref{input.iterators},
an \tcode{iterator_traits} specialization might have
\tcode{iterator_concept} denote \tcode{input_iterator_tag}
but not declare \tcode{iterator_category}.
\end{example}

\pnum
\tcode{iterator_traits} is specialized for pointers as
\begin{codeblock}
namespace std {
  template<class T>
    requires is_object_v<T>
  struct iterator_traits<T*> {
    using iterator_concept  = contiguous_iterator_tag;
    using iterator_category = random_access_iterator_tag;
    using value_type        = remove_cv_t<T>;
    using difference_type   = ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;
  };
}
\end{codeblock}

\pnum
\begin{example}
To implement a generic
\tcode{reverse}
function, a \Cpp{} program can do the following:
\begin{codeblock}
template<class BI>
void reverse(BI first, BI last) {
  typename iterator_traits<BI>::difference_type n = distance(first, last);
  --n;
  while (n > 0) {
    typename iterator_traits<BI>::value_type tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}
\end{codeblock}
\end{example}

\rSec2[iterator.cust]{Customization point objects}

\rSec3[iterator.cust.move]{\tcode{ranges::iter_move}}

\indexlibraryglobal{iter_move}%
\pnum
The name \tcode{ranges::iter_move} denotes
a customization point object\iref{customization.point.object}.
The expression \tcode{ranges::\-iter_move(E)} for a subexpression \tcode{E} is
expression-equivalent to:

\begin{itemize}
\item \tcode{iter_move(E)}, if
\tcode{E} has class or enumeration type and
\tcode{iter_move(E)} is a well-formed expression when treated as an unevaluated operand,
where the meaning of \tcode{iter_move} is established as-if by performing
argument-dependent lookup only\iref{basic.lookup.argdep}.

\item Otherwise, if the expression \tcode{*E} is well-formed:
\begin{itemize}
\item if \tcode{*E} is an lvalue, \tcode{std::move(*E)};

\item otherwise, \tcode{*E}.
\end{itemize}

\item Otherwise, \tcode{ranges::iter_move(E)} is ill-formed.
\begin{note}
This case can result in substitution failure when \tcode{ranges::iter_move(E)}
appears in the immediate context of a template instantiation.
\end{note}
\end{itemize}

\pnum
If \tcode{ranges::iter_move(E)} is not equal to \tcode{*E},
the program is ill-formed, no diagnostic required.

\rSec3[iterator.cust.swap]{\tcode{ranges::iter_swap}}

\indexlibraryglobal{iter_swap}%
\pnum
The name \tcode{ranges::iter_swap} denotes
a customization point object\iref{customization.point.object}
that exchanges the values\iref{concept.swappable} denoted by its
arguments.

\pnum
Let \exposid{iter-exchange-move} be the exposition-only function template:
\begin{itemdecl}
template<class X, class Y>
  constexpr iter_value_t<X> @\exposid{iter-exchange-move}@(X&& x, Y&& y)
    noexcept(noexcept(iter_value_t<X>(iter_move(x))) &&
             noexcept(*x = iter_move(y)));
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
iter_value_t<X> old_value(iter_move(x));
*x = iter_move(y);
return old_value;
\end{codeblock}
\end{itemdescr}

\pnum
The expression \tcode{ranges::iter_swap(E1, E2)} for subexpressions
\tcode{E1} and \tcode{E2} is expression-equivalent to:
\begin{itemize}
\item \tcode{(void)iter_swap(E1, E2)}, if either
\tcode{E1} or \tcode{E2} has class or enumeration type and
\tcode{iter_swap(E1, E2)} is a well-formed expression
with overload resolution performed in a context that includes the declaration
\begin{codeblock}
template<class I1, class I2>
  void iter_swap(I1, I2) = delete;
\end{codeblock}
and does not include a declaration of \tcode{ranges::iter_swap}.
If the function selected by overload resolution does not exchange the values
denoted by \tcode{E1} and \tcode{E2},
the program is ill-formed, no diagnostic required.
\begin{note}
This precludes calling unconstrained \tcode{std::iter_swap}. When the deleted
overload is viable, program-defined overloads need to be more
specialized\iref{temp.func.order} to be selected.
\end{note}

\item Otherwise, if the types of \tcode{E1} and \tcode{E2} each model
\libconcept{indirectly_readable}, and if the reference types of \tcode{E1} and \tcode{E2}
model \libconcept{swappable_with}\iref{concept.swappable},
then \tcode{ranges::swap(*E1, *E2)}.

\item Otherwise, if the types \tcode{T1} and \tcode{T2} of \tcode{E1} and
\tcode{E2} model \tcode{\libconcept{indirectly_movable_storable}<T1, T2>} and
\tcode{\libconcept{indirectly_movable_storable}<T2, T1>}, then
\tcode{(void)(*E1 = \placeholdernc{iter-exchange-move}(E2, E1))},
except that \tcode{E1} is evaluated only once.

\item Otherwise, \tcode{ranges::iter_swap(E1, E2)} is ill-formed.
\begin{note}
This case can result in substitution failure when \tcode{ranges::iter_swap(E1, E2)}
appears in the immediate context of a template instantiation.
\end{note}
\end{itemize}

\rSec2[iterator.concepts]{Iterator concepts}

\rSec3[iterator.concepts.general]{General}

\pnum
For a type \tcode{I}, let \tcode{\placeholdernc{ITER_TRAITS}(I)} denote
the type \tcode{I} if \tcode{iterator_traits<I>} names
a specialization generated from the primary template.
Otherwise, \tcode{\placeholdernc{ITER_TRAITS}(I)} denotes
\tcode{iterator_traits<I>}.
\begin{itemize}
\item If the \grammarterm{qualified-id}
  \tcode{\placeholdernc{ITER_TRAITS}(I)::iterator_concept} is valid
  and names a type, then \tcode{\placeholdernc{ITER_CONCEPT}(I)} denotes that
  type.
\item Otherwise, if the \grammarterm{qualified-id}
  \tcode{\placeholdernc{ITER_TRAITS}(I)\brk{}::iterator_category}
  is valid and names a type, then \tcode{\placeholdernc{ITER_CONCEPT}(I)}
  denotes that type.
\item Otherwise, if \tcode{iterator_traits<I>} names a specialization generated
  from the primary template, then \tcode{\placeholdernc{ITER_CONCEPT}(I)}
  denotes \tcode{random_access_iterator_tag}.
\item Otherwise, \tcode{\placeholdernc{ITER_CONCEPT}(I)} does not denote a type.
\end{itemize}

\pnum
\begin{note}
\tcode{\placeholdernc{ITER_TRAITS}} enables independent syntactic determination
of an iterator's category and concept.
\end{note}
\begin{example}
\begin{codeblock}
struct I {
  using value_type = int;
  using difference_type = int;

  int operator*() const;
  I& operator++();
  I operator++(int);
  I& operator--();
  I operator--(int);

  bool operator==(I) const;
};
\end{codeblock}
\tcode{iterator_traits<I>::iterator_category} denotes \tcode{input_iterator_tag},
and \tcode{\placeholder{ITER_CONCEPT}(I)} denotes \tcode{random_access_iterator_tag}.
\end{example}

\rSec3[iterator.concept.readable]{Concept \cname{indirectly_readable}}

\pnum
Types that are indirectly readable by applying \tcode{operator*}
model the \libconcept{indirectly_readable} concept, including
pointers, smart pointers, and iterators.

\begin{codeblock}
template<class In>
  concept @\defexposconcept{indirectly-readable-impl}@ = @\itcorr[-1]@                   // \expos
    requires(const In in) {
      typename iter_value_t<In>;
      typename iter_reference_t<In>;
      typename iter_rvalue_reference_t<In>;
      { *in } -> @\libconcept{same_as}@<iter_reference_t<In>>;
      { ranges::iter_move(in) } -> @\libconcept{same_as}@<iter_rvalue_reference_t<In>>;
    } &&
    @\libconcept{common_reference_with}@<iter_reference_t<In>&&, iter_value_t<In>&> &&
    @\libconcept{common_reference_with}@<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
    @\libconcept{common_reference_with}@<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;
\end{codeblock}

\begin{codeblock}
template<class In>
  concept @\deflibconcept{indirectly_readable}@ =
    @\exposconcept{indirectly-readable-impl}@<remove_cvref_t<In>>;
\end{codeblock}

\pnum
Given a value \tcode{i} of type \tcode{I}, \tcode{I} models \libconcept{indirectly_readable}
only if the expression \tcode{*i} is equality-preserving.

\rSec3[iterator.concept.writable]{Concept \cname{indirectly_writable}}

\pnum
The \libconcept{indirectly_writable} concept specifies the requirements
for writing a value into an iterator's referenced object.

\begin{codeblock}
template<class Out, class T>
  concept @\deflibconcept{indirectly_writable}@ =
    requires(Out&& o, T&& t) {
      *o = std::forward<T>(t);                          // not required to be equality-preserving
      *std::forward<Out>(o) = std::forward<T>(t);       // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*o) =
        std::forward<T>(t);                             // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
        std::forward<T>(t);                             // not required to be equality-preserving
    };
\end{codeblock}

\pnum
Let \tcode{E} be an expression such that \tcode{decltype((E))} is \tcode{T},
and let \tcode{o} be a dereferenceable object of type \tcode{Out}.
\tcode{Out} and \tcode{T} model \tcode{\libconcept{indirectly_writable}<Out, T>} only if:
\begin{itemize}
\item If \tcode{Out} and \tcode{T} model
  \tcode{\libconcept{indirectly_readable}<Out> \&\& \libconcept{same_as}<iter_value_t<Out>, decay_t<T>>},
  then \tcode{*o} after any above assignment is equal to
  the value of \tcode{E} before the assignment.
\end{itemize}

\pnum
After evaluating any above assignment expression, \tcode{o} is not required to be dereferenceable.

\pnum
If \tcode{E} is an xvalue\iref{basic.lval}, the resulting
state of the object it denotes is valid but unspecified\iref{lib.types.movedfrom}.

\pnum
\begin{note}
The only valid use of an \tcode{operator*} is on the left side of the assignment statement.
Assignment through the same value of the indirectly writable type happens only once.
\end{note}

\pnum
\begin{note}
\libconcept{indirectly_writable} has the awkward \keyword{const_cast} expressions to reject
iterators with prvalue non-proxy reference types that permit rvalue
assignment but do not also permit \keyword{const} rvalue assignment.
Consequently, an iterator type \tcode{I} that returns \tcode{std::string}
by value does not model \tcode{\libconcept{indirectly_writable}<I, std::string>}.
\end{note}

\rSec3[iterator.concept.winc]{Concept \cname{weakly_incrementable}}

\pnum
The \libconcept{weakly_incrementable} concept specifies the requirements on
types that can be incremented with the pre- and post-increment operators.
The increment operations are not required to be equality-preserving,
nor is the type required to be \libconcept{equality_comparable}.

\begin{codeblock}
template<class T>
  constexpr bool @\exposid{is-integer-like}@ = @\seebelow@; @\itcorr[-2]@          // \expos

template<class T>
  constexpr bool @\exposid{is-signed-integer-like}@ = @\seebelow@; @\itcorr[-2]@   // \expos

template<class I>
  concept @\deflibconcept{weakly_incrementable}@ =
    @\libconcept{movable}@<I> &&
    requires(I i) {
      typename iter_difference_t<I>;
      requires @\exposid{is-signed-integer-like}@<iter_difference_t<I>>;
      { ++i } -> @\libconcept{same_as}@<I&>;                           // not required to be equality-preserving
      i++;                                              // not required to be equality-preserving
    };
\end{codeblock}

\pnum
A type \tcode{I} is an \defnadj{integer-class}{type}
if it is in a set of \impldef{set of integer-class types} types
that behave as integer types do, as defined below.
\begin{note}
An integer-class type is not necessarily a class type.
\end{note}

\pnum
The range of representable values of an integer-class type
is the continuous set of values over which it is defined.
For any integer-class type,
its range of representable values is
either $-2^{N-1}$ to $2^{N-1}-1$ (inclusive) for some integer $N$,
in which case it is a \defnadj{signed-integer-class}{type}, or
$0$ to $2^{N}-1$ (inclusive) for some integer $N$,
in which case it is an \defnadj{unsigned-integer-class}{type}.
In both cases, $N$ is called
the \defnx{width}{width!of integer-class type} of the integer-class type.
The width of an integer-class type is greater than
that of every integral type of the same signedness.

\pnum
A type \tcode{I} other than \cv{}~\tcode{bool} is \defn{integer-like}
if it models \tcode{\libconcept{integral}<I>} or
if it is an integer-class type.
An integer-like type \tcode{I} is \defn{signed-integer-like}
if it models \tcode{\libconcept{signed_integral}<I>} or
if it is a signed-integer-class type.
An integer-like type \tcode{I} is \defn{unsigned-integer-like}
if it models \tcode{\libconcept{unsigned_integral}<I>} or
if it is an unsigned-integer-class type.

\pnum
For every integer-class type \tcode{I},
let \tcode{B(I)} be a unique hypothetical extended integer type
of the same signedness with the same width\iref{basic.fundamental} as \tcode{I}.
\begin{note}
The corresponding hypothetical specialization \tcode{numeric_limits<B(I)>}
meets the requirements on \tcode{numeric_limits} specializations
for integral types\iref{numeric.limits}.
\end{note}
For every integral type \tcode{J}, let \tcode{B(J)} be the same type as \tcode{J}.

\pnum
Expressions of integer-class type are
explicitly convertible to any integer-like type, and
implicitly convertible to any integer-class type
of equal or greater width and the same signedness.
Expressions of integral type are
both implicitly and explicitly convertible to any integer-class type.
Conversions between integral and integer-class types
and between two integer-class types do not exit via an exception.
The result of such a conversion is the unique value of the destination type
that is congruent to the source modulo $2^N$,
where $N$ is the width of the destination type.

\pnum
Let \tcode{a} be an object of integer-class type \tcode{I},
let \tcode{b} be an object of integer-like type \tcode{I2}
such that the expression \tcode{b} is implicitly convertible to \tcode{I},
let \tcode{x} and \tcode{y} be, respectively,
objects of type \tcode{B(I)} and \tcode{B(I2)} as described above
that represent the same values as \tcode{a} and \tcode{b}, and
let \tcode{c} be an lvalue of any integral type.
\begin{itemize}
\item
The expressions \tcode{a++} and \tcode{a--} shall be prvalues of type \tcode{I}
whose values are equal to
that of \tcode{a} prior to the evaluation of the expressions.
The expression \tcode{a++} shall modify the value of \tcode{a}
by adding \tcode{1} to it.
The expression \tcode{a--} shall modify the value of \tcode{a}
by subtracting \tcode{1} from it.
\item
The expressions \tcode{++a}, \tcode{--a}, and \tcode{\&a} shall be
expression-equivalent to
\tcode{a += 1}, \tcode{a -= 1}, and \tcode{addressof(a)}, respectively.
\item
  For every \grammarterm{unary-operator} \tcode{@} other than \tcode{\&} for which the expression \tcode{@x}
  is well-formed, \tcode{@a} shall also be well-formed
  and have the same value, effects, and value category as \tcode{@x}.
  If \tcode{@x} has type \tcode{bool}, so too does \tcode{@a};
  if \tcode{@x} has type \tcode{B(I)}, then \tcode{@a} has type \tcode{I}.
\item
  For every assignment operator \tcode{@=}
  for which \tcode{c @= x} is well-formed,
  \tcode{c @= a} shall also be well-formed and
  shall have the same value and effects as \tcode{c @= x}.
  The expression \tcode{c @= a} shall be an lvalue referring to \tcode{c}.
\item
For every assignment operator \tcode{@=}
for which \tcode{x @= y} is well-formed,
\tcode{a @= b} shall also be well-formed and
shall have the same effects as \tcode{x @= y},
except that the value that would be stored into \tcode{x}
is stored into \tcode{a}.
The expression \tcode{a @= b} shall be an lvalue referring to \tcode{a}.
\item
  For every non-assignment binary operator \tcode{@}
  for which \tcode{x @ y} and \tcode{y @ x} are well-formed,
  \tcode{a @ b} and \tcode{b @ a} shall also be well-formed and
  shall have the same value, effects, and value category as
  \tcode{x @ y} and \tcode{y @ x}, respectively.
  If \tcode{x @ y} or \tcode{y @ x} has type \tcode{B(I)},
  then \tcode{a @ b} or \tcode{b @ a}, respectively, has type \tcode{I};
  if \tcode{x @ y} or \tcode{y @ x} has type \tcode{B(I2)},
  then \tcode{a @ b} or \tcode{b @ a}, respectively, has type \tcode{I2};
  if \tcode{x @ y} or \tcode{y @ x} has any other type,
  then \tcode{a @ b} or \tcode{b @ a}, respectively, has that type.
\end{itemize}

\pnum
An expression \tcode{E} of integer-class type \tcode{I} is
contextually convertible to \tcode{bool}
as if by \tcode{bool(E != I(0))}.

\pnum
All integer-class types model
\libconcept{regular}\iref{concepts.object} and
\tcode{\libconcept{three_way_comparable}<strong_ordering>}\iref{cmp.concept}.

\pnum
A value-initialized object of integer-class type has value 0.

\pnum
For every (possibly cv-qualified) integer-class type \tcode{I},
\tcode{numeric_limits<I>} is specialized such that
each static data member \tcode{m}
has the same value as \tcode{numeric_limits<B(I)>::m}, and
each static member function \tcode{f}
returns \tcode{I(numeric_limits<B(I)>::f())}.

\pnum
For any two integer-like types \tcode{I1} and \tcode{I2},
at least one of which is an integer-class type,
\tcode{common_type_t<I1, I2>} denotes an integer-class type
whose width is not less than that of \tcode{I1} or \tcode{I2}.
If both \tcode{I1} and \tcode{I2} are signed-integer-like types,
then \tcode{common_type_t<I1, I2>} is also a signed-integer-like type.

\pnum
\tcode{\exposid{is-integer-like}<I>} is \tcode{true}
if and only if \tcode{I} is an integer-like type.
\tcode{\exposid{is-signed-integer-like}<I>} is \tcode{true}
if and only if \tcode{I} is a signed-integer-like type.

\pnum
Let \tcode{i} be an object of type \tcode{I}. When \tcode{i} is in the domain of
both pre- and post-increment, \tcode{i} is said to be \defn{incrementable}.
\tcode{I} models \tcode{\libconcept{weakly_incrementable}<I>} only if:
\begin{itemize}
\item The expressions \tcode{++i} and \tcode{i++} have the same domain.
\item If \tcode{i} is incrementable, then both \tcode{++i}
  and \tcode{i++} advance \tcode{i} to the next element.
\item If \tcode{i} is incrementable, then
  \tcode{addressof(++i)} is equal to
  \tcode{addressof(i)}.
\end{itemize}

\pnum
\recommended
The implementation of an algorithm on a weakly incrementable type
should never attempt to pass through the same incrementable value twice;
such an algorithm should be a single-pass algorithm.
\begin{note}
For \libconcept{weakly_incrementable} types, \tcode{a} equals \tcode{b} does not imply that \tcode{++a}
equals \tcode{++b}. (Equality does not guarantee the substitution property or referential
transparency.)
Such algorithms
can be used with istreams as the source of the input data through the \tcode{istream_iterator} class
template.
\end{note}

\rSec3[iterator.concept.inc]{Concept \cname{incrementable}}

\pnum
The \libconcept{incrementable} concept specifies requirements on types that can be incremented with the pre-
and post-increment operators. The increment operations are required to be equality-preserving,
and the type is required to be \libconcept{equality_comparable}.
\begin{note}
This supersedes the ``not required to be equality-preserving'' comments
on the increment expressions
in the definition of \libconcept{weakly_incrementable}.
\end{note}

\begin{codeblock}
template<class I>
  concept @\deflibconcept{incrementable}@ =
    @\libconcept{regular}@<I> &&
    @\libconcept{weakly_incrementable}@<I> &&
    requires(I i) {
      { i++ } -> @\libconcept{same_as}@<I>;
    };
\end{codeblock}

\pnum
Let \tcode{a} and \tcode{b} be incrementable objects of type \tcode{I}.
\tcode{I} models \libconcept{incrementable} only if:
\begin{itemize}
\item If \tcode{bool(a == b)} then \tcode{bool(a++ == b)}.
\item If \tcode{bool(a == b)} then \tcode{bool(((void)a++, a) == ++b)}.
\end{itemize}

\pnum
\begin{note}
The requirement that
\tcode{a} equals \tcode{b}
implies
\tcode{++a} equals \tcode{++b}
(which is not true for weakly incrementable types)
allows the use of multi-pass one-directional
algorithms with types that model \libconcept{incrementable}.
\end{note}

\rSec3[iterator.concept.iterator]{Concept \cname{input_or_output_iterator}}

\pnum
The \libconcept{input_or_output_iterator} concept forms the basis
of the iterator concept taxonomy; every iterator models \libconcept{input_or_output_iterator}.
This concept specifies operations for dereferencing and incrementing
an iterator. Most algorithms will require additional operations
to compare iterators with sentinels\iref{iterator.concept.sentinel}, to
read\iref{iterator.concept.input} or write\iref{iterator.concept.output} values, or
to provide a richer set of iterator movements\iref{iterator.concept.forward,
iterator.concept.bidir,iterator.concept.random.access}.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{input_or_output_iterator}@ =
    requires(I i) {
      { *i } -> @\exposconcept{can-reference}@;
    } &&
    @\libconcept{weakly_incrementable}@<I>;
\end{codeblock}

\pnum
\begin{note}
Unlike the \oldconcept{Iterator} requirements,
the \libconcept{input_or_output_iterator} concept does not require copyability.
\end{note}

\rSec3[iterator.concept.sentinel]{Concept \cname{sentinel_for}}

\pnum
The \libconcept{sentinel_for} concept specifies the relationship
between an \libconcept{input_or_output_iterator} type and a \libconcept{semiregular} type
whose values denote a range.

\begin{itemdecl}
template<class S, class I>
  concept @\deflibconcept{sentinel_for}@ =
    @\libconcept{semiregular}@<S> &&
    !@\exposid{is-integer-like}@<S> &&
    @\libconcept{input_or_output_iterator}@<I> &&
    @\exposconcept{weakly-equality-comparable-with}@<S, I>;      // see \ref{concept.equalitycomparable}
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{s} and \tcode{i} be values of type \tcode{S} and
\tcode{I} such that \range{i}{s} denotes a range. Types
\tcode{S} and \tcode{I} model \tcode{\libconcept{sentinel_for}<S, I>} only if:
\begin{itemize}
\item \tcode{i == s} is well-defined.

\item If \tcode{bool(i != s)} then \tcode{i} is dereferenceable and
      \range{++i}{s} denotes a range.

\item \tcode{\libconcept{assignable_from}<I\&, S>} is either modeled or not satisfied.

\item If \tcode{I} and \tcode{S} are the same type, then
      \tcode{i == i} is \tcode{true}.
\end{itemize}
\end{itemdescr}

\pnum
The domain of \tcode{==} is not static.
Given an iterator \tcode{i} and sentinel \tcode{s} such that \range{i}{s}
denotes a range and \tcode{i != s}, \tcode{i} and \tcode{s} are not required to
continue to denote a range after incrementing any other iterator equal
to \tcode{i}. Consequently, \tcode{i == s} is no longer required to be
well-defined.

\rSec3[iterator.concept.sizedsentinel]{Concept \cname{sized_sentinel_for}}

\pnum
The \libconcept{sized_sentinel_for} concept specifies
requirements on an \libconcept{input_or_output_iterator} type \tcode{I} and
a corresponding \tcode{\libconcept{sentinel_for}<I>}
that allow the use of the \tcode{-} operator to compute the distance
between them in constant time.

\begin{itemdecl}
template<class S, class I>
  concept @\deflibconcept{sized_sentinel_for}@ =
    @\libconcept{sentinel_for}@<S, I> &&
    !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
      { s - i } -> @\libconcept{same_as}@<iter_difference_t<I>>;
      { i - s } -> @\libconcept{same_as}@<iter_difference_t<I>>;
    };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{i} be an iterator of type \tcode{I}, and \tcode{s}
a sentinel of type \tcode{S} such that \range{i}{s} denotes a range.
Let $N$ be the smallest number of applications of \tcode{++i}
necessary to make \tcode{bool(i == s)} be \tcode{true}.
\tcode{S} and \tcode{I} model \tcode{\libconcept{sized_sentinel_for}<S, I>} only if:
\begin{itemize}
\item If $N$ is representable by \tcode{iter_difference_t<I>},
      then \tcode{s - i} is well-defined and equals $N$.

\item If $-N$ is representable by \tcode{iter_difference_t<I>},
      then \tcode{i - s} is well-defined and equals $-N$.
\end{itemize}
\end{itemdescr}

\indexlibraryglobal{disable_sized_sentinel_for}%
\begin{itemdecl}
template<class S, class I>
  constexpr bool disable_sized_sentinel_for = false;
\end{itemdecl}

\begin{itemdescr}
\pnum
\remarks
Pursuant to \ref{namespace.std},
users may specialize \tcode{disable_sized_sentinel_for}
for cv-unqualified non-array object types \tcode{S} and \tcode{I}
if \tcode{S} and/or \tcode{I} is a program-defined type.
Such specializations shall
be usable in constant expressions\iref{expr.const.init} and
have type \tcode{const bool}.

\pnum
\begin{note}
\tcode{disable_sized_sentinel_for} allows use of sentinels and iterators with
the library that satisfy but do not in fact model \libconcept{sized_sentinel_for}.
\end{note}

\pnum
\begin{example}
The \libconcept{sized_sentinel_for} concept is modeled by pairs of
\libconcept{random_access_iterator}s\iref{iterator.concept.random.access} and by
counted iterators and their sentinels\iref{counted.iterator}.
\end{example}
\end{itemdescr}

\rSec3[iterator.concept.input]{Concept \cname{input_iterator}}

\pnum
The \libconcept{input_iterator} concept defines requirements for a type
whose referenced values can be read (from the requirement for
\libconcept{indirectly_readable}\iref{iterator.concept.readable})
and which can be both pre- and post-incremented.
\begin{note}
Unlike the \oldconcept{InputIterator} requirements\iref{input.iterators},
the \libconcept{input_iterator} concept does not need
equality comparison since iterators are typically compared to sentinels.
\end{note}

\begin{codeblock}
template<class I>
  concept @\deflibconcept{input_iterator}@ =
    @\libconcept{input_or_output_iterator}@<I> &&
    @\libconcept{indirectly_readable}@<I> &&
    requires { typename @\placeholdernc{ITER_CONCEPT}@(I); } &&
    @\libconcept{derived_from}@<@\placeholdernc{ITER_CONCEPT}@(I), input_iterator_tag>;
\end{codeblock}

\rSec3[iterator.concept.output]{Concept \cname{output_iterator}}

\pnum
The \libconcept{output_iterator} concept defines requirements for a type that
can be used to write values (from the requirement for
\libconcept{indirectly_writable}\iref{iterator.concept.writable})
and which can be both pre- and post-incremented.
\begin{note}
Output iterators are not required to model \libconcept{equality_comparable}.
\end{note}

\begin{codeblock}
template<class I, class T>
  concept @\deflibconcept{output_iterator}@ =
    @\libconcept{input_or_output_iterator}@<I> &&
    @\libconcept{indirectly_writable}@<I, T> &&
    requires(I i, T&& t) {
      *i++ = std::forward<T>(t);        // not required to be equality-preserving
    };
\end{codeblock}

\pnum
Let \tcode{E} be an expression such that \tcode{decltype((E))} is \tcode{T}, and let \tcode{i} be a
dereferenceable object of type \tcode{I}. \tcode{I} and \tcode{T} model \tcode{\libconcept{output_iterator}<I, T>} only if
\tcode{*i++ = E;} has effects equivalent to:
\begin{codeblock}
*i = E;
++i;
\end{codeblock}

\pnum
\recommended
The implementation of an algorithm on output iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single-pass algorithm.

\rSec3[iterator.concept.forward]{Concept \cname{forward_iterator}}

\pnum
The \libconcept{forward_iterator} concept adds
copyability, equality comparison, and
the multi-pass guarantee, specified below.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{forward_iterator}@ =
    @\libconcept{input_iterator}@<I> &&
    @\libconcept{derived_from}@<@\placeholdernc{ITER_CONCEPT}@(I), forward_iterator_tag> &&
    @\libconcept{incrementable}@<I> &&
    @\libconcept{sentinel_for}@<I, I>;
\end{codeblock}

\pnum
The domain of \tcode{==} for forward iterators is that of iterators over the same
underlying sequence. However, value-initialized iterators of the same type
may be compared and shall compare equal to other value-initialized iterators of the same type.
\begin{note}
Value-initialized iterators behave as if they refer past the end of the same
empty sequence.
\end{note}

\pnum
Pointers and references obtained from a forward iterator into a range \range{i}{s}
shall remain valid while \range{i}{s} continues to denote a range.

\pnum
Two dereferenceable iterators \tcode{a} and \tcode{b} of type \tcode{X}
offer the \defn{multi-pass guarantee} if
\begin{itemize}
\item \tcode{a == b} implies \tcode{++a == ++b} and
\item the expression
\tcode{((void)[](X x)\{++x;\}(a), *a)} is equivalent to the expression \tcode{*a}.
\end{itemize}

\pnum
\begin{note}
The requirement that
\tcode{a == b}
implies
\tcode{++a == ++b}
and the removal of the restrictions on the number of assignments through
a mutable iterator
(which applies to output iterators)
allow the use of multi-pass one-directional algorithms with forward iterators.
\end{note}

\rSec3[iterator.concept.bidir]{Concept \cname{bidirectional_iterator}}

\pnum
The \libconcept{bidirectional_iterator} concept adds the ability
to move an iterator backward as well as forward.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{bidirectional_iterator}@ =
    @\libconcept{forward_iterator}@<I> &&
    @\libconcept{derived_from}@<@\placeholdernc{ITER_CONCEPT}@(I), bidirectional_iterator_tag> &&
    requires(I i) {
      { --i } -> @\libconcept{same_as}@<I&>;
      { i-- } -> @\libconcept{same_as}@<I>;
    };
\end{codeblock}

\pnum
A bidirectional iterator \tcode{r} is decrementable if and only if there exists some \tcode{q} such that
\tcode{++q == r}. Decrementable iterators \tcode{r} shall be in the domain of the expressions
\tcode{--r} and \tcode{r--}.

\pnum
Let \tcode{a} and \tcode{b} be equal objects of type \tcode{I}.
\tcode{I} models \libconcept{bidirectional_iterator} only if:
\begin{itemize}
\item If \tcode{a} and \tcode{b} are decrementable,
  then all of the following are \tcode{true}:
  \begin{itemize}
  \item \tcode{addressof(--a) == addressof(a)}
  \item \tcode{bool(a-- == b)}
  \item after evaluating both \tcode{a--} and \tcode{--b},
    \tcode{bool(a == b)} is still \tcode{true}
  \item \tcode{bool(++(--a) == b)}
  \end{itemize}
  \item If \tcode{a} and \tcode{b} are incrementable, then
    \tcode{bool(--(++a) == b)}.
\end{itemize}

\rSec3[iterator.concept.random.access]{Concept \cname{random_access_iterator}}

\pnum
The \libconcept{random_access_iterator} concept adds support for
constant-time advancement with \tcode{+=}, \tcode{+}, \tcode{-=}, and \tcode{-},
as well as the computation of distance in constant time with \tcode{-}.
Random access iterators also support array notation via subscripting.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{random_access_iterator}@ =
    @\libconcept{bidirectional_iterator}@<I> &&
    @\libconcept{derived_from}@<@\placeholdernc{ITER_CONCEPT}@(I), random_access_iterator_tag> &&
    @\libconcept{totally_ordered}@<I> &&
    @\libconcept{sized_sentinel_for}@<I, I> &&
    requires(I i, const I j, const iter_difference_t<I> n) {
      { i += n } -> @\libconcept{same_as}@<I&>;
      { j +  n } -> @\libconcept{same_as}@<I>;
      { n +  j } -> @\libconcept{same_as}@<I>;
      { i -= n } -> @\libconcept{same_as}@<I&>;
      { j -  n } -> @\libconcept{same_as}@<I>;
      {  j[n]  } -> @\libconcept{same_as}@<iter_reference_t<I>>;
    };
\end{codeblock}

\pnum
Let \tcode{a} and \tcode{b} be valid iterators of type \tcode{I}
such that \tcode{b} is reachable from \tcode{a}
after \tcode{n} applications of \tcode{++a},
let \tcode{D} be \tcode{iter_difference_t<I>},
and let \tcode{n} denote a value of type \tcode{D}.
\tcode{I} models \libconcept{random_access_iterator} only if:
\begin{itemize}
\item \tcode{(a += n)} is equal to \tcode{b}.
\item \tcode{addressof(a += n)} is equal to \tcode{addressof(a)}.
\item \tcode{(a + n)} is equal to \tcode{(a += n)}.
\item For any two positive values
  \tcode{x} and \tcode{y} of type \tcode{D},
  if \tcode{(a + D(x + y))} is valid, then
  \tcode{(a + D(x + y))} is equal to \tcode{((a + x) + y)}.
\item \tcode{(a + D(0))} is equal to \tcode{a}.
\item If \tcode{(a + D(n - 1))} is valid, then
  \tcode{(a + n)} is equal to \tcode{[](I c)\{ return ++c; \}(a + D(n - 1))}.
\item \tcode{(b += D(-n))} is equal to \tcode{a}.
\item \tcode{(b -= n)} is equal to \tcode{a}.
\item \tcode{addressof(b -= n)} is equal to \tcode{addressof(b)}.
\item \tcode{(b - n)} is equal to \tcode{(b -= n)}.
\item If \tcode{b} is dereferenceable, then
  \tcode{a[n]} is valid and is equal to \tcode{*b}.
\item \tcode{bool(a <= b)} is \tcode{true}.
\end{itemize}

\rSec3[iterator.concept.contiguous]{Concept \cname{contiguous_iterator}}

\pnum
The \libconcept{contiguous_iterator} concept provides a guarantee that
the denoted elements are stored contiguously in memory.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{contiguous_iterator}@ =
    @\libconcept{random_access_iterator}@<I> &&
    @\libconcept{derived_from}@<@\placeholdernc{ITER_CONCEPT}@(I), contiguous_iterator_tag> &&
    is_lvalue_reference_v<iter_reference_t<I>> &&
    @\libconcept{same_as}@<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
    requires(const I& i) {
      { to_address(i) } -> @\libconcept{same_as}@<add_pointer_t<iter_reference_t<I>>>;
    };
\end{codeblock}

\pnum
Let \tcode{a} and \tcode{b} be dereferenceable iterators and
\tcode{c} be a non-dereferenceable iterator of type \tcode{I}
such that \tcode{b} is reachable from \tcode{a} and
\tcode{c} is reachable from \tcode{b},
and let \tcode{D} be \tcode{iter_difference_t<I>}.
The type \tcode{I} models \libconcept{contiguous_iterator} only if
\begin{itemize}
\item \tcode{to_address(a) == addressof(*a)},
\item \tcode{to_address(b) == to_address(a) + D(b - a)},
\item \tcode{to_address(c) == to_address(a) + D(c - a)},
\item \tcode{to_address(I\{\})} is well-defined,
\item \tcode{ranges::iter_move(a)} has
the same type, value category, and effects as \tcode{std::move(*a)}, and
\item if \tcode{ranges::iter_swap(a, b)} is well-formed,
it has effects equivalent to \tcode{ranges::swap(*a, *b)}.
\end{itemize}

\rSec2[iterator.cpp17]{\Cpp{}17 iterator requirements}

\rSec3[iterator.cpp17.general]{General}

\pnum
In the following sections,
\tcode{a}
and
\tcode{b}
denote values of type
\tcode{X} or \tcode{const X},
\tcode{difference_type} and \tcode{reference} refer to the
types \tcode{iterator_traits<X>::difference_type} and
\tcode{iterator_traits<X>::reference}, respectively,
\tcode{n}
denotes a value of
\tcode{difference_type},
\tcode{u},
\tcode{tmp},
and
\tcode{m}
denote identifiers,
\tcode{r}
denotes a value of
\tcode{X\&},
\tcode{t}
denotes a value of value type
\tcode{T},
\tcode{o}
denotes a value of some type that is writable to the output iterator.
\begin{note}
For an iterator type \tcode{X} there must be an instantiation
of \tcode{iterator_traits<X>}\iref{iterator.traits}.
\end{note}

\rSec3[iterator.iterators]{\oldconcept{Iterator}}

\pnum
The \oldconcept{Iterator} requirements form the basis of the iterator
taxonomy; every iterator meets the \oldconcept{\-Iterator} requirements. This
set of requirements specifies operations for dereferencing and incrementing
an iterator. Most algorithms will require additional operations to
read\iref{input.iterators} or write\iref{output.iterators} values, or
to provide a richer set of iterator movements\iref{forward.iterators,
bidirectional.iterators,random.access.iterators}.

\pnum
A type \tcode{X} meets the \defnoldconcept{Iterator} requirements if
\begin{itemize}
\item \tcode{X} meets the \oldconcept{CopyConstructible}, \oldconcept{CopyAssignable}, \oldconcept{Swappable}, and
\oldconcept{Destructible} requirements\iref{utility.arg.requirements,swappable.requirements}, and

\item \tcode{iterator_traits<X>::difference_type} is a signed integer type or \keyword{void}, and

\item the expressions in \tref{iterator} are valid and have
the indicated semantics.
\end{itemize}

\begin{libreqtab4b}[floattable]
{\oldconcept{Iterator} requirements}
{iterator}
\topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep

\tcode{*r}          &
  unspecified       &
                            &
  \expects \tcode{r} is dereferenceable.  \\ \rowsep

\tcode{++r}         &
  \tcode{X\&}       &
                            &
                    \\

\end{libreqtab4b}

\rSec3[input.iterators]{Input iterators}

\pnum
A class or pointer type
\tcode{X}
meets the requirements of an input iterator for the value type
\tcode{T}
if
\tcode{X} meets the \oldconcept{Iterator}\iref{iterator.iterators} and
\oldconcept{EqualityComparable} (\tref{cpp17.equalitycomparable}) requirements and
the expressions in \tref{inputiterator} are valid and have
the indicated semantics.

\pnum
In \tref{inputiterator}, the term
\term{the domain of \tcode{==}}
is used in the ordinary mathematical sense to denote
the set of values over which
\tcode{==} is (required to be) defined.
This set can change over time.
Each algorithm places additional requirements on the domain of
\tcode{==} for the iterator values it uses.
These requirements can be inferred from the uses that algorithm
makes of \tcode{==} and \tcode{!=}.
\begin{example}
The call \tcode{find(a,b,x)}
is defined only if the value of \tcode{a}
has the property \textit{p}
defined as follows:
\tcode{b} has property \textit{p}
and a value \tcode{i}
has property \textit{p}
if
(\tcode{*i==x})
or if
(\tcode{*i!=x}
and
\tcode{++i}
has property
\textit{p}).
\end{example}

\begin{libreqtab4b}
{\defnoldconcept{InputIterator} requirements (in addition to \oldconcept{Iterator})}
{inputiterator}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{a != b}                  &
 \tcode{decltype(a != b)} models \exposconceptx{boolean-test\-able}{boolean-testable}  &
 \tcode{!(a == b)}                              &
 \expects \orange{a}{b} is in the domain of \tcode{==}. \\ \rowsep

\tcode{*a}                      &
 \tcode{reference}, convertible to \tcode{T}       &
                                &
 \expects \tcode{a} is dereferenceable.\br
 The expression\br \tcode{(void)*a, *a} is equivalent to \tcode{*a}.\br
 If \tcode{a == b} and \orange{a}{b} is in the domain of \tcode{==}
 then \tcode{*a} is equivalent to \tcode{*b}.  \\ \rowsep
\tcode{a->m}                    &
                                &
 \tcode{(*a).m}                                &
 \expects \tcode{a} is dereferenceable. \\ \rowsep
\tcode{++r}                     &
 \tcode{X\&}                    &
                                &
 \expects \tcode{r} is dereferenceable.\br
 \ensures \tcode{r} is dereferenceable or \tcode{r} is past-the-end;\br
 any copies of the previous value of \tcode{r} are no longer
 required to be dereferenceable nor to be in the domain of \tcode{==}.    \\ \rowsep

\tcode{(void)r++}               &
                                &
                                &
 equivalent to \tcode{(void)++r}    \\ \rowsep

\tcode{*r++}                    &
 convertible to \tcode{T}       &
 \tcode{\{ T tmp = *r;}\br
 \tcode{++r;}\br
 \tcode{return tmp; \}} & \\
\end{libreqtab4b}

\pnum
\recommended
The implementation of an algorithm on input iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single pass algorithm.

\begin{note}
For input iterators, \tcode{a == b} does not imply \tcode{++a == ++b}.
(Equality does not guarantee the substitution property or referential transparency.)
Value type \tcode{T} is not required to be a \oldconcept{CopyAssignable} type (\tref{cpp17.copyassignable}).
Such an algorithm can be used with istreams as the source of the input data through the
\tcode{istream_iterator}
class template.
\end{note}

\rSec3[output.iterators]{Output iterators}

\pnum
A class or pointer type
\tcode{X}
meets the requirements of an output iterator
if \tcode{X} meets the \oldconcept{Iterator} requirements\iref{iterator.iterators}
and the expressions in \tref{outputiterator}
are valid and have the indicated semantics.

\begin{libreqtab4b}[floattable]
{\defnoldconcept{OutputIterator} requirements (in addition to \oldconcept{Iterator})}
{outputiterator}
\topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep

\tcode{*r = o}      &
 result is not used &
                    &
 \remarks After this operation \tcode{r} is not required to be dereferenceable.\br
 \ensures \tcode{r} is incrementable. \\ \rowsep

\tcode{++r}         &
 \tcode{X\&}        &
                    &
 \tcode{addressof(r) == addressof(++r)}.\br
 \remarks After this operation \tcode{r} is not required to be dereferenceable.\br
 \ensures \tcode{r} is incrementable. \\ \rowsep

\tcode{r++}         &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  ++r;}\br
 \tcode{  return tmp; \}}   &
 \remarks After this operation \tcode{r} is not required to be dereferenceable.\br
 \ensures \tcode{r} is incrementable. \\ \rowsep

\tcode{*r++ = o}    &
 result is not used &&
 \remarks After this operation \tcode{r} is not required to be dereferenceable.\br
 \ensures \tcode{r} is incrementable. \\
\end{libreqtab4b}

\pnum
\recommended
The implementation of an algorithm on output iterators
should never attempt to pass through the same iterator twice;
such an algorithm should be a single-pass algorithm.
\begin{note}
The only valid use of an \tcode{operator*}
is on the left side of the assignment statement.
Assignment through the same value of the iterator happens only once.
Equality and inequality are not necessarily defined.
\end{note}

\rSec3[forward.iterators]{Forward iterators}

\pnum
A class or pointer type
\tcode{X}
meets the \oldconcept{ForwardIterator} requirements if
\begin{itemize}
\item \tcode{X} meets the \oldconcept{InputIterator} requirements\iref{input.iterators},

\item \tcode{X} meets the \oldconcept{DefaultConstructible}
requirements\iref{utility.arg.requirements},

\item if \tcode{X} is a mutable iterator, \tcode{reference} is a reference to \tcode{T};
if \tcode{X} is a constant iterator, \tcode{reference} is a reference to \tcode{const T},

\item the expressions in \tref{forwarditerator}
are valid and have the indicated semantics, and

\item objects of type \tcode{X} offer the multi-pass guarantee, described below.
\end{itemize}

\pnum
The domain of \tcode{==} for forward iterators is that of iterators over the same
underlying sequence. However, value-initialized iterators may be compared and
shall compare equal to other value-initialized iterators of the same type.
\begin{note}
Value-initialized iterators behave as if they refer past the end of
the same empty sequence.
\end{note}

\pnum
Two dereferenceable iterators \tcode{a} and \tcode{b} of type \tcode{X} offer the
\defn{multi-pass guarantee} if
\begin{itemize}
\item \tcode{a == b} implies \tcode{++a == ++b} and
\item \tcode{X} is a pointer type or the expression
\tcode{(void)++X(a), *a} is equivalent to the expression \tcode{*a}.
\end{itemize}

\pnum
\begin{note}
The requirement that
\tcode{a == b}
implies
\tcode{++a == ++b}
(which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through
a mutable iterator
(which applies to output iterators)
allows the use of multi-pass one-directional algorithms with forward iterators.
\end{note}

\begin{libreqtab4b}[floattable]
{\defnoldconcept{ForwardIterator} requirements (in addition to \oldconcept{InputIterator})}
{forwarditerator}
\topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep

\tcode{r++}         &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  ++r;}\br
 \tcode{  return tmp; \}}&  \\ \rowsep

\tcode{*r++}        &
 \tcode{reference}     &&  \\
\end{libreqtab4b}

\pnum
If \tcode{a} and \tcode{b} are equal, then either \tcode{a} and \tcode{b}
are both dereferenceable
or else neither is dereferenceable.

\pnum
If \tcode{a} and \tcode{b} are both dereferenceable, then \tcode{a == b}
if and only if
\tcode{*a} and \tcode{*b} are bound to the same object.

\rSec3[bidirectional.iterators]{Bidirectional iterators}

\pnum
A class or pointer type
\tcode{X}
meets the requirements of a bidirectional iterator if,
in addition to meeting the \oldconcept{ForwardIterator} requirements,
the following expressions are valid as shown in \tref{bidirectionaliterator}.

\begin{libreqtab4b}[floattable]
{\defnoldconcept{BidirectionalIterator} requirements (in addition to \oldconcept{ForwardIterator})}
{bidirectionaliterator}
\topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep

\tcode{--r}      &
 \tcode{X\&}        &
                    &
 \expects there exists \tcode{s} such that \tcode{r == ++s}.\br
 \ensures \tcode{r} is dereferenceable.\br
 \tcode{--(++r) == r}.\br
 \tcode{--r == --s} implies \tcode{r == s}.\br
 \tcode{addressof(r) == addressof(--r)}.   \\ \hline

\tcode{r--}           &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  --r;}\br
 \tcode{  return tmp; \}}&  \\ \rowsep

\tcode{*r--}      &
 \tcode{reference}   &&  \\
\end{libreqtab4b}

\pnum
\begin{note}
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
\end{note}

\rSec3[random.access.iterators]{Random access iterators}

\pnum
A class or pointer type
\tcode{X}
meets the requirements of a random access iterator if,
in addition to meeting the \oldconcept{BidirectionalIterator} requirements,
the following expressions are valid as shown in \tref{randomaccessiterator}.

\begin{libreqtab4b}
{\defnoldconcept{RandomAccessIterator} requirements (in addition to \oldconcept{BidirectionalIterator})}
{randomaccessiterator}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{r += n}      &
 \tcode{X\&}        &
 \tcode{\{ difference_type m = n;}\br
 \tcode{  if (m >= 0)}\br
 \tcode{    while (m--)}\br
 \tcode{      ++r;}\br
 \tcode{  else}\br
 \tcode{    while (m++)}\br
 \tcode{      --r;}\br
 \tcode{  return r; \}}&    \\ \rowsep

\tcode{a + n}\br
\tcode{n + a}       &
 \tcode{X}          &
 \tcode{\{ X tmp = a;}\br
 \tcode{  return tmp += n; \}}  &
 \tcode{a + n == n + a}.        \\ \rowsep

\tcode{r -= n}      &
 \tcode{X\&}        &
 \tcode{return r += -n;}    &
 \expects the absolute value of \tcode{n} is in the range of
 representable values of \tcode{difference_type}.   \\ \rowsep

\tcode{a - n}       &
 \tcode{X}          &
 \tcode{\{ X tmp = a;}\br
 \tcode{  return tmp -= n; \}}  &   \\ \rowsep

\tcode{b - a}       &
 \tcode{difference_type}   &
 \tcode{return n;}   &
 \expects there exists a value \tcode{n} of type \tcode{difference_type} such that \tcode{a + n == b}.\br
 \tcode{b == a + (b - a)}.  \\ \rowsep

\tcode{a[n]}        &
 convertible to \tcode{reference}  &
 \tcode{*(a + n)}   &   \\ \rowsep

\tcode{a < b}       &
 \tcode{decltype(a < b)} models \exposconceptx{boolean-test\-able}{boolean-testable}    &
 \effects Equivalent to: \tcode{return b - a > 0;}  &
 \tcode{<} is a total ordering relation \\ \rowsep

\tcode{a > b}       &
 \tcode{decltype(a > b)} models \exposconceptx{boolean-test\-able}{boolean-testable}    &
 \tcode{b < a}      &
 \tcode{>} is a total ordering relation opposite to \tcode{<}.  \\ \rowsep

\tcode{a >= b}      &
 \tcode{decltype(a >= b)} models \exposconceptx{boolean-test\-able}{boolean-testable}    &
 \tcode{!(a < b)}   &   \\ \rowsep

\tcode{a <= b}      &
 \tcode{decltype(a <= b)} models \exposconceptx{boolean-test\-able}{boolean-testable}    &
 \tcode{!(a > b)}   &   \\
\end{libreqtab4b}

\rSec2[indirectcallable]{Indirect callable requirements}

\rSec3[indirectcallable.general]{General}

\pnum
There are several concepts that group requirements of algorithms that
take callable objects\iref{func.def} as arguments.

\rSec3[indirectcallable.traits]{Indirect callable traits}

\pnum
To implement algorithms taking projections,
it is necessary to determine the projected type of an iterator's value type.
For the exposition-only alias template \exposid{indirect-value-t},
\tcode{\exposid{indirect-value-t}<T>} denotes
\begin{itemize}
\item
\tcode{invoke_result_t<Proj\&, \exposid{indirect-value-t}<I>>}
if \tcode{T} names \tcode{projected<I, Proj>}, and
\item
\tcode{iter_value_t<T>\&} otherwise.
\end{itemize}

\rSec3[indirectcallable.indirectinvocable]{Indirect callables}

\pnum
The indirect callable concepts are used to constrain those algorithms
that accept callable objects\iref{func.def} as arguments.

\begin{codeblock}
namespace std {
  template<class F, class I>
    concept @\deflibconcept{indirectly_unary_invocable}@ =
      @\libconcept{indirectly_readable}@<I> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{invocable}@<F&, @\exposidnc{indirect-value-t}@<I>> &&
      @\libconcept{invocable}@<F&, iter_reference_t<I>> &&
      @\libconcept{common_reference_with}@<
        invoke_result_t<F&, @\exposidnc{indirect-value-t}@<I>>,
        invoke_result_t<F&, iter_reference_t<I>>>;

  template<class F, class I>
    concept @\deflibconcept{indirectly_regular_unary_invocable}@ =
      @\libconcept{indirectly_readable}@<I> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{regular_invocable}@<F&, @\exposidnc{indirect-value-t}@<I>> &&
      @\libconcept{regular_invocable}@<F&, iter_reference_t<I>> &&
      @\libconcept{common_reference_with}@<
        invoke_result_t<F&, @\exposidnc{indirect-value-t}@<I>>,
        invoke_result_t<F&, iter_reference_t<I>>>;

  template<class F, class I>
    concept @\deflibconcept{indirect_unary_predicate}@ =
      @\libconcept{indirectly_readable}@<I> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{predicate}@<F&, @\exposidnc{indirect-value-t}@<I>> &&
      @\libconcept{predicate}@<F&, iter_reference_t<I>>;

  template<class F, class I1, class I2>
    concept @\deflibconcept{indirect_binary_predicate}@ =
      @\libconcept{indirectly_readable}@<I1> && @\libconcept{indirectly_readable}@<I2> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{predicate}@<F&, @\exposidnc{indirect-value-t}@<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{predicate}@<F&, @\exposidnc{indirect-value-t}@<I1>, iter_reference_t<I2>> &&
      @\libconcept{predicate}@<F&, iter_reference_t<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{predicate}@<F&, iter_reference_t<I1>, iter_reference_t<I2>>;

  template<class F, class I1, class I2 = I1>
    concept @\deflibconcept{indirect_equivalence_relation}@ =
      @\libconcept{indirectly_readable}@<I1> && @\libconcept{indirectly_readable}@<I2> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{equivalence_relation}@<F&, @\exposidnc{indirect-value-t}@<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{equivalence_relation}@<F&, @\exposidnc{indirect-value-t}@<I1>, iter_reference_t<I2>> &&
      @\libconcept{equivalence_relation}@<F&, iter_reference_t<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{equivalence_relation}@<F&, iter_reference_t<I1>, iter_reference_t<I2>>;

  template<class F, class I1, class I2 = I1>
    concept @\deflibconcept{indirect_strict_weak_order}@ =
      @\libconcept{indirectly_readable}@<I1> && @\libconcept{indirectly_readable}@<I2> &&
      @\libconcept{copy_constructible}@<F> &&
      @\libconcept{strict_weak_order}@<F&, @\exposidnc{indirect-value-t}@<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{strict_weak_order}@<F&, @\exposidnc{indirect-value-t}@<I1>, iter_reference_t<I2>> &&
      @\libconcept{strict_weak_order}@<F&, iter_reference_t<I1>, @\exposidnc{indirect-value-t}@<I2>> &&
      @\libconcept{strict_weak_order}@<F&, iter_reference_t<I1>, iter_reference_t<I2>>;
}
\end{codeblock}

\rSec3[projected]{Alias template \tcode{projected}}

\pnum
Alias template \tcode{projected} is used to constrain algorithms
that accept callable objects and projections\iref{defns.projection}.
It combines an \libconcept{indirectly_readable} type \tcode{I} and
a callable object type \tcode{Proj} into a new \libconcept{indirectly_readable} type
whose \tcode{reference} type is the result of applying
\tcode{Proj} to the \tcode{iter_reference_t} of \tcode{I}.

\indexlibraryglobal{projected}%
\begin{codeblock}
namespace std {
  template<class I, class Proj>
  struct @\exposidnc{projected-impl}@ {                               // \expos
    struct @\exposidnc{type}@ {                                       // \expos
      using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
      using difference_type = iter_difference_t<I>;     // present only if \tcode{I}
                                                        // models \libconcept{weakly_incrementable}
      indirect_result_t<Proj&, I> operator*() const;    // \notdef
    };
  };

  template<@\libconcept{indirectly_readable}@ I, @\libconcept{indirectly_regular_unary_invocable}@<I> Proj>
    using projected = @\exposid{projected-impl}@<I, Proj>::@\exposid{type}@;
}
\end{codeblock}

\rSec2[alg.req]{Common algorithm requirements}

\rSec3[alg.req.general]{General}

\pnum
There are several additional iterator concepts that are commonly applied
to families of algorithms. These group together iterator requirements
of algorithm families.
There are three relational concepts that specify
how element values are transferred between
\libconcept{indirectly_readable} and \libconcept{indirectly_writable} types:
\libconcept{indirectly_movable},
\libconcept{indirectly_copyable}, and
\libconcept{indirectly_swappable}.
There are three relational concepts for rearrangements:
\libconcept{permutable},
\libconcept{mergeable}, and
\libconcept{sortable}.
There is one relational concept for comparing values from different sequences:
\libconcept{indirectly_comparable}.

\pnum
\begin{note}
The \tcode{ranges::less} function object type
used in the concepts below imposes constraints on the concepts' arguments
in addition to those that appear in the concepts' bodies\iref{range.cmp}.
\end{note}

\rSec3[alg.req.ind.move]{Concept \cname{indirectly_movable}}

\pnum
The \libconcept{indirectly_movable} concept specifies the relationship between
an \libconcept{indirectly_readable} type and an \libconcept{indirectly_writable} type
between which values may be moved.

\begin{codeblock}
template<class In, class Out>
  concept @\deflibconcept{indirectly_movable}@ =
    @\libconcept{indirectly_readable}@<In> &&
    @\libconcept{indirectly_writable}@<Out, iter_rvalue_reference_t<In>>;
\end{codeblock}

\pnum
The \libconcept{indirectly_movable_storable} concept augments
\libconcept{indirectly_movable} with additional requirements enabling
the transfer to be performed through an intermediate object of the
\libconcept{indirectly_readable} type's value type.

\begin{codeblock}
template<class In, class Out>
  concept @\deflibconcept{indirectly_movable_storable}@ =
    @\libconcept{indirectly_movable}@<In, Out> &&
    @\libconcept{indirectly_writable}@<Out, iter_value_t<In>> &&
    @\libconcept{movable}@<iter_value_t<In>> &&
    @\libconcept{constructible_from}@<iter_value_t<In>, iter_rvalue_reference_t<In>> &&
    @\libconcept{assignable_from}@<iter_value_t<In>&, iter_rvalue_reference_t<In>>;
\end{codeblock}

\pnum
Let \tcode{i} be a dereferenceable value of type \tcode{In}.
\tcode{In} and \tcode{Out} model \tcode{\libconcept{indirectly_movable_storable}<In, Out>}
only if after the initialization of the object \tcode{obj} in
\begin{codeblock}
iter_value_t<In> obj(ranges::iter_move(i));
\end{codeblock}
\tcode{obj} is equal to the value previously denoted by \tcode{*i}. If
\tcode{iter_rvalue_reference_t<In>} is an rvalue reference type,
the resulting state of the value denoted by \tcode{*i} is
valid but unspecified\iref{lib.types.movedfrom}.

\rSec3[alg.req.ind.copy]{Concept \cname{indirectly_copyable}}

\pnum
The \libconcept{indirectly_copyable} concept specifies the relationship between
an \libconcept{indirectly_readable} type and an \libconcept{indirectly_writable} type
between which values may be copied.

\begin{codeblock}
template<class In, class Out>
  concept @\deflibconcept{indirectly_copyable}@ =
    @\libconcept{indirectly_readable}@<In> &&
    @\libconcept{indirectly_writable}@<Out, iter_reference_t<In>>;
\end{codeblock}

\pnum
The \libconcept{indirectly_copyable_storable} concept augments
\libconcept{indirectly_copyable} with additional requirements enabling
the transfer to be performed through an intermediate object of the
\libconcept{indirectly_readable} type's value type. It also requires the capability
to make copies of values.

\begin{codeblock}
template<class In, class Out>
  concept @\deflibconcept{indirectly_copyable_storable}@ =
    @\libconcept{indirectly_copyable}@<In, Out> &&
    @\libconcept{indirectly_writable}@<Out, iter_value_t<In>&> &&
    @\libconcept{indirectly_writable}@<Out, const iter_value_t<In>&> &&
    @\libconcept{indirectly_writable}@<Out, iter_value_t<In>&&> &&
    @\libconcept{indirectly_writable}@<Out, const iter_value_t<In>&&> &&
    @\libconcept{copyable}@<iter_value_t<In>> &&
    @\libconcept{constructible_from}@<iter_value_t<In>, iter_reference_t<In>> &&
    @\libconcept{assignable_from}@<iter_value_t<In>&, iter_reference_t<In>>;
\end{codeblock}

\pnum
Let \tcode{i} be a dereferenceable value of type \tcode{In}.
\tcode{In} and \tcode{Out} model \tcode{\libconcept{indirectly_copyable_storable}<In, Out>}
only if after the initialization of the object \tcode{obj} in
\begin{codeblock}
iter_value_t<In> obj(*i);
\end{codeblock}
\tcode{obj} is equal to the value previously denoted by \tcode{*i}. If
\tcode{iter_reference_t<In>} is an rvalue reference type, the resulting state
of the value denoted by \tcode{*i} is
valid but unspecified\iref{lib.types.movedfrom}.

\rSec3[alg.req.ind.swap]{Concept \cname{indirectly_swappable}}

\pnum
The \libconcept{indirectly_swappable} concept specifies a swappable relationship
between the values referenced by two \libconcept{indirectly_readable} types.

\begin{codeblock}
template<class I1, class I2 = I1>
  concept @\deflibconcept{indirectly_swappable}@ =
    @\libconcept{indirectly_readable}@<I1> && @\libconcept{indirectly_readable}@<I2> &&
    requires(const I1 i1, const I2 i2) {
      ranges::iter_swap(i1, i1);
      ranges::iter_swap(i2, i2);
      ranges::iter_swap(i1, i2);
      ranges::iter_swap(i2, i1);
    };
\end{codeblock}

\rSec3[alg.req.ind.cmp]{Concept \cname{indirectly_comparable}}

\pnum
The \libconcept{indirectly_comparable} concept specifies
the common requirements of algorithms that
compare values from two different sequences.

\begin{codeblock}
template<class I1, class I2, class R, class P1 = identity,
         class P2 = identity>
  concept @\deflibconcept{indirectly_comparable}@ =
    @\libconcept{indirect_binary_predicate}@<R, projected<I1, P1>, projected<I2, P2>>;
\end{codeblock}

\rSec3[alg.req.permutable]{Concept \cname{permutable}}

\pnum
The \libconcept{permutable} concept specifies the common requirements
of algorithms that reorder elements in place by moving or swapping them.

\begin{codeblock}
template<class I>
  concept @\deflibconcept{permutable}@ =
    @\libconcept{forward_iterator}@<I> &&
    @\libconcept{indirectly_movable_storable}@<I, I> &&
    @\libconcept{indirectly_swappable}@<I, I>;
\end{codeblock}

\rSec3[alg.req.mergeable]{Concept \cname{mergeable}}

\pnum
The \libconcept{mergeable} concept specifies the requirements of algorithms
that merge sorted sequences into an output sequence by copying elements.

\begin{codeblock}
template<class I1, class I2, class Out, class R = ranges::less,
         class P1 = identity, class P2 = identity>
  concept @\deflibconcept{mergeable}@ =
    @\libconcept{input_iterator}@<I1> &&
    @\libconcept{input_iterator}@<I2> &&
    @\libconcept{weakly_incrementable}@<Out> &&
    @\libconcept{indirectly_copyable}@<I1, Out> &&
    @\libconcept{indirectly_copyable}@<I2, Out> &&
    @\libconcept{indirect_strict_weak_order}@<R, projected<I1, P1>, projected<I2, P2>>;
\end{codeblock}

\rSec3[alg.req.sortable]{Concept \cname{sortable}}

\pnum
The \libconcept{sortable} concept specifies the common requirements of
algorithms that permute sequences into ordered sequences (e.g., \tcode{sort}).

\begin{codeblock}
template<class I, class R = ranges::less, class P = identity>
  concept @\deflibconcept{sortable}@ =
    @\libconcept{permutable}@<I> &&
    @\libconcept{indirect_strict_weak_order}@<R, projected<I, P>>;
\end{codeblock}

\rSec1[iterator.primitives]{Iterator primitives}

\rSec2[iterator.primitives.general]{General}

\pnum
To simplify the use of iterators, the library provides
several classes and functions.

\rSec2[std.iterator.tags]{Standard iterator tags}

\pnum
\indexlibraryglobal{output_iterator_tag}%
\indexlibraryglobal{input_iterator_tag}%
\indexlibraryglobal{forward_iterator_tag}%
\indexlibraryglobal{bidirectional_iterator_tag}%
\indexlibraryglobal{random_access_iterator_tag}%
\indexlibraryglobal{contiguous_iterator_tag}%
It is often desirable for a
function template specialization
to find out what is the most specific category of its iterator
argument, so that the function can select the most efficient algorithm at compile time.
To facilitate this, the
library introduces
\defn{category tag}
classes which are used as compile time tags for algorithm selection.
They are:
\tcode{output_iterator_tag},
\tcode{input_iterator_tag},
\tcode{forward_iterator_tag},
\tcode{bidirectional_iterator_tag},
\tcode{random_access_iterator_tag},
and
\tcode{contiguous_iterator_tag}.
For every iterator of type
\tcode{I},
\tcode{iterator_traits<I>::it\-er\-a\-tor_ca\-te\-go\-ry}
shall be declared to be a category tag that describes the
iterator's behavior.
Additionally,
\tcode{iterator_traits<I>::it\-er\-a\-tor_con\-cept}
may be used to indicate conformance to
the iterator concepts\iref{iterator.concepts}.

\begin{codeblock}
namespace std {
  struct output_iterator_tag { };
  struct input_iterator_tag { };
  struct forward_iterator_tag: public input_iterator_tag { };
  struct bidirectional_iterator_tag: public forward_iterator_tag { };
  struct random_access_iterator_tag: public bidirectional_iterator_tag { };
  struct contiguous_iterator_tag: public random_access_iterator_tag { };
}
\end{codeblock}

\pnum
\begin{example}
A program-defined iterator \tcode{BinaryTreeIterator}
can be included into the bidirectional iterator category by
specializing the \tcode{iterator_traits} template:

\begin{codeblock}
template<class T> struct iterator_traits<BinaryTreeIterator<T>> {
  using iterator_category = bidirectional_iterator_tag;
  using difference_type   = ptrdiff_t;
  using value_type        = T;
  using pointer           = T*;
  using reference         = T&;
};
\end{codeblock}
\end{example}

\pnum
\begin{example}
If
\tcode{evolve()}
is well-defined for bidirectional iterators, but can be implemented more
efficiently for random access iterators, then the implementation is as follows:

\begin{codeblock}
template<class BidirectionalIterator>
inline void
evolve(BidirectionalIterator first, BidirectionalIterator last) {
  evolve(first, last,
    typename iterator_traits<BidirectionalIterator>::iterator_category());
}

template<class BidirectionalIterator>
void evolve(BidirectionalIterator first, BidirectionalIterator last,
  bidirectional_iterator_tag) {
  // more generic, but less efficient algorithm
}

template<class RandomAccessIterator>
void evolve(RandomAccessIterator first, RandomAccessIterator last,
  random_access_iterator_tag) {
  // more efficient, but less generic algorithm
}
\end{codeblock}
\end{example}

\rSec2[iterator.operations]{Iterator operations}

\pnum
Since only random access iterators provide
\tcode{+}
and
\tcode{-}
operators, the library provides two
function templates
\tcode{advance}
and
\tcode{distance}.
These
function templates
use
\tcode{+}
and
\tcode{-}
for random access iterators (and are, therefore, constant
time for them); for input, forward and bidirectional iterators they use
\tcode{++}
to provide linear time
implementations.

\indexlibraryglobal{advance}%
\begin{itemdecl}
template<class InputIterator, class Distance>
  constexpr void advance(InputIterator& i, Distance n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{n}
is negative only for bidirectional iterators.

\pnum
\effects
Increments \tcode{i} by \tcode{n} if \tcode{n} is non-negative, and
decrements \tcode{i} by \tcode{-n} otherwise.
\end{itemdescr}

\indexlibraryglobal{distance}%
\begin{itemdecl}
template<class InputIterator>
  constexpr typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{last} is reachable from \tcode{first}, or
\tcode{InputIterator} meets
the \oldconcept{RandomAccessIterator} requirements and
\tcode{first} is reachable from \tcode{last}.

\pnum
\effects
If \tcode{InputIterator} meets the \oldconcept{RandomAccessIterator} requirements,
returns \tcode{(last - first)}; otherwise, increments
\tcode{first} until \tcode{last} is reached and returns
the number of increments.
\end{itemdescr}

\indexlibraryglobal{next}%
\begin{itemdecl}
template<class InputIterator>
  constexpr InputIterator next(InputIterator x,
    typename iterator_traits<InputIterator>::difference_type n = 1);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{advance(x, n); return x;}
\end{itemdescr}

\indexlibraryglobal{prev}%
\begin{itemdecl}
template<class BidirectionalIterator>
  constexpr BidirectionalIterator prev(BidirectionalIterator x,
    typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{advance(x, -n); return x;}
\end{itemdescr}

\rSec2[range.iter.ops]{Range iterator operations}

\rSec3[range.iter.ops.general]{General}

\pnum
The library includes the function templates
\tcode{ranges::advance}, \tcode{ranges::distance},
\tcode{ranges::next}, and \tcode{ranges::prev}
to manipulate iterators. These operations adapt to the set of operators
provided by each iterator category to provide the most efficient implementation
possible for a concrete iterator type.
\begin{example}
\tcode{ranges::advance} uses the \tcode{+} operator to move a
\libconcept{random_access_iterator} forward \tcode{n} steps in constant time.
For an iterator type that does not model \libconcept{random_access_iterator},
\tcode{ranges::advance} instead performs \tcode{n} individual increments with
the \tcode{++} operator.
\end{example}

\pnum
The entities defined in \ref{range.iter.ops} are
algorithm function objects\iref{alg.func.obj}.

\rSec3[range.iter.op.advance]{\tcode{ranges::advance}}

\indexlibraryglobal{advance}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I>
  constexpr void ranges::advance(I& i, iter_difference_t<I> n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
If \tcode{I} does not model \libconcept{bidirectional_iterator},
\tcode{n} is not negative.

\pnum
\effects
\begin{itemize}
\item If \tcode{I} models \libconcept{random_access_iterator},
  equivalent to \tcode{i += n}.
\item Otherwise, if \tcode{n} is non-negative, increments
  \tcode{i} by \tcode{n}.
\item Otherwise, decrements \tcode{i} by \tcode{-n}.
\end{itemize}
\end{itemdescr}

\indexlibraryglobal{advance}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
  constexpr void ranges::advance(I& i, S bound);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
Either \tcode{\libconcept{assignable_from}<I\&, S> || \libconcept{sized_sentinel_for}<S, I>} is modeled, or
\range{i}{bound} denotes a range.

\pnum
\effects
\begin{itemize}
\item If \tcode{I} and \tcode{S} model \tcode{\libconcept{assignable_from}<I\&, S>},
  equivalent to \tcode{i = std::move(bound)}.
\item Otherwise, if \tcode{S} and \tcode{I} model \tcode{\libconcept{sized_sentinel_for}<S, I>},
  equivalent to \tcode{ranges::advance(i, bound - i)}.
\item Otherwise, while \tcode{bool(i != bound)} is \tcode{true},
  increments \tcode{i}.
\end{itemize}
\end{itemdescr}

\indexlibraryglobal{advance}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
  constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
If \tcode{n > 0}, \range{i}{bound} denotes a range.
If \tcode{n == 0}, \range{i}{bound} or \range{bound}{i} denotes a range.
If \tcode{n < 0}, \range{bound}{i} denotes a range,
\tcode{I} models \libconcept{bidirectional_iterator}, and
\tcode{I} and \tcode{S} model \tcode{\libconcept{same_as}<I, S>}.

\pnum
\effects
\begin{itemize}
\item If \tcode{S} and \tcode{I} model \tcode{\libconcept{sized_sentinel_for}<S, I>}:
  \begin{itemize}
  \item If \brk{}$|\tcode{n}| \ge |\tcode{bound - i}|$,
    equivalent to \tcode{ranges::advance(i, bound)}.
  \item Otherwise, equivalent to \tcode{ranges::advance(i, n)}.
  \end{itemize}
\item Otherwise,
  \begin{itemize}
  \item if \tcode{n} is non-negative,
    while \tcode{bool(i != bound)} is \tcode{true},
    increments \tcode{i} but at most \tcode{n} times.
  \item Otherwise,
    while \tcode{bool(i != bound)} is \tcode{true},
    decrements \tcode{i} but at most \tcode{-n} times.
  \end{itemize}
\end{itemize}

\pnum
\returns
\tcode{n - $M$}, where $M$ is the difference between
the ending and starting positions of \tcode{i}.
\end{itemdescr}

\rSec3[range.iter.op.distance]{\tcode{ranges::distance}}
\indexlibraryglobal{distance}%
\begin{itemdecl}
template<class I, @\libconcept{sentinel_for}@<I> S>
  requires (!@\libconcept{sized_sentinel_for}@<S, I>)
  constexpr iter_difference_t<I> ranges::distance(I first, S last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\range{first}{last} denotes a range.

\pnum
\effects
Increments \tcode{first} until \tcode{last} is reached and
returns the number of increments.
\end{itemdescr}

\indexlibraryglobal{distance}%
\begin{itemdecl}
template<class I, @\libconcept{sized_sentinel_for}@<decay_t<I>> S>
  constexpr iter_difference_t<decay_t<I>> ranges::distance(I&& first, S last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
if constexpr (!is_array_v<remove_reference_t<I>>)
  return last - first;
else
  return last - static_cast<decay_t<I>>(first);
\end{codeblock}
\end{itemdescr}

\indexlibraryglobal{distance}%
\begin{itemdecl}
template<@\libconcept{range}@ R>
  constexpr range_difference_t<R> ranges::distance(R&& r);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
If \tcode{R} models \libconcept{sized_range}, equivalent to:
\begin{codeblock}
return static_cast<range_difference_t<R>>(ranges::size(r));     // \ref{range.prim.size}
\end{codeblock}
Otherwise, equivalent to:
\begin{codeblock}
return ranges::distance(ranges::begin(r), ranges::end(r));      // \ref{range.access}
\end{codeblock}
\end{itemdescr}

\rSec3[range.iter.op.next]{\tcode{ranges::next}}

\indexlibraryglobal{next}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I>
  constexpr I ranges::next(I x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{++x; return x;}
\end{itemdescr}

\indexlibraryglobal{next}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I>
  constexpr I ranges::next(I x, iter_difference_t<I> n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::advance(x, n); return x;}
\end{itemdescr}

\indexlibraryglobal{next}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
  constexpr I ranges::next(I x, S bound);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::advance(x, bound); return x;}
\end{itemdescr}

\indexlibraryglobal{next}%
\begin{itemdecl}
template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
  constexpr I ranges::next(I x, iter_difference_t<I> n, S bound);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::advance(x, n, bound); return x;}
\end{itemdescr}

\rSec3[range.iter.op.prev]{\tcode{ranges::prev}}
\indexlibraryglobal{prev}%
\begin{itemdecl}
template<@\libconcept{bidirectional_iterator}@ I>
  constexpr I ranges::prev(I x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{--x; return x;}
\end{itemdescr}

\indexlibraryglobal{prev}%
\begin{itemdecl}
template<@\libconcept{bidirectional_iterator}@ I>
  constexpr I ranges::prev(I x, iter_difference_t<I> n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::advance(x, -n); return x;}
\end{itemdescr}

\indexlibraryglobal{prev}%
\begin{itemdecl}
template<@\libconcept{bidirectional_iterator}@ I>
  constexpr I ranges::prev(I x, iter_difference_t<I> n, I bound);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::advance(x, -n, bound); return x;}
\end{itemdescr}

\rSec1[predef.iterators]{Iterator adaptors}

\rSec2[reverse.iterators]{Reverse iterators}

\rSec3[reverse.iterators.general]{General}

\pnum
Class template \tcode{reverse_iterator} is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence.

\rSec3[reverse.iterator]{Class template \tcode{reverse_iterator}}

\indexlibraryglobal{reverse_iterator}%
\begin{codeblock}
namespace std {
  template<class Iterator>
  class reverse_iterator {
  public:
    using iterator_type     = Iterator;
    using iterator_concept  = @\seebelow@;
    using iterator_category = @\seebelow@;
    using value_type        = iter_value_t<Iterator>;
    using difference_type   = iter_difference_t<Iterator>;
    using pointer           = iterator_traits<Iterator>::pointer;
    using reference         = iter_reference_t<Iterator>;

    constexpr reverse_iterator();
    constexpr explicit reverse_iterator(Iterator x);
    template<class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
    template<class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u);

    constexpr Iterator base() const;
    constexpr reference operator*() const;
    constexpr pointer   operator->() const requires @\seebelow@;

    constexpr reverse_iterator& operator++();
    constexpr reverse_iterator  operator++(int);
    constexpr reverse_iterator& operator--();
    constexpr reverse_iterator  operator--(int);

    constexpr reverse_iterator  operator+ (difference_type n) const;
    constexpr reverse_iterator& operator+=(difference_type n);
    constexpr reverse_iterator  operator- (difference_type n) const;
    constexpr reverse_iterator& operator-=(difference_type n);
    constexpr @\unspec@ operator[](difference_type n) const;

    friend constexpr iter_rvalue_reference_t<Iterator>
      iter_move(const reverse_iterator& i) noexcept(@\seebelow@);
    template<@\libconcept{indirectly_swappable}@<Iterator> Iterator2>
      friend constexpr void
        iter_swap(const reverse_iterator& x,
                  const reverse_iterator<Iterator2>& y) noexcept(@\seebelow@);

  protected:
    Iterator current;
  };
}
\end{codeblock}

\pnum
The member \grammarterm{typedef-name} \tcode{iterator_concept} denotes
\begin{itemize}
\item
\tcode{random_access_iterator_tag} if \tcode{Iterator} models
\libconcept{random_access_iterator}, and
\item
\tcode{bidirectional_iterator_tag} otherwise.
\end{itemize}

\pnum
The member \grammarterm{typedef-name} \tcode{iterator_category} denotes
\begin{itemize}
\item
\tcode{random_access_iterator_tag} if
the type
\tcode{iterator_traits<\brk{}Iterator>::iterator_category} models
\tcode{\libconcept{derived_from}<random_access_iterator_tag>}, and
\item
\tcode{iterator_traits<\brk{}Iterator>::iterator_category} otherwise.
\end{itemize}

\rSec3[reverse.iter.requirements]{Requirements}

\pnum
The template parameter
\tcode{Iterator}
shall either meet the requirements of a
\oldconcept{BidirectionalIterator}\iref{bidirectional.iterators}
or model
\libconcept{bidirectional_iterator}\iref{iterator.concept.bidir}.

\pnum
Additionally,
\tcode{Iterator}
shall either meet the requirements of a
\oldconcept{RandomAccessIterator}\iref{random.access.iterators}
or model
\libconcept{random_access_iterator}\iref{iterator.concept.random.access}
if the definitions of any of the members
\begin{itemize}
\item
\tcode{operator+},
\tcode{operator-},
\tcode{operator+=},
\tcode{operator-=}\iref{reverse.iter.nav}, or
\item
\tcode{operator[]}\iref{reverse.iter.elem},
\end{itemize}
or the non-member operators\iref{reverse.iter.cmp}
\begin{itemize}
\item
\tcode{operator<},
\tcode{operator>},
\tcode{operator<=},
\tcode{operator>=},
\tcode{operator-},
or
\tcode{operator+}\iref{reverse.iter.nonmember}
\end{itemize}
are instantiated\iref{temp.inst}.

\rSec3[reverse.iter.cons]{Construction and assignment}

\indexlibraryctor{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Value-initializes
\tcode{current}.
\end{itemdescr}

\indexlibraryctor{reverse_iterator}%
\begin{itemdecl}
constexpr explicit reverse_iterator(Iterator x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{current}
with \tcode{x}.
\end{itemdescr}

\indexlibraryctor{reverse_iterator}%
\begin{itemdecl}
template<class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{is_same_v<U, Iterator>} is \tcode{false} and
\tcode{const U\&} models \tcode{\libconcept{convertible_to}<Iterator>}.

\pnum
\effects
Initializes
\tcode{current}
with
\tcode{u.current}.
\end{itemdescr}

\indexlibrarymember{operator=}{reverse_iterator}%
\begin{itemdecl}
template<class U>
  constexpr reverse_iterator&
    operator=(const reverse_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{is_same_v<U, Iterator>} is \tcode{false},
\tcode{const U\&} models \tcode{\libconcept{convertible_to}<Iterator>}, and
\tcode{\libconcept{assignable_from}<Iterator\&, const U\&>} is modeled.

\pnum
\effects
Assigns \tcode{u.current} to \tcode{current}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[reverse.iter.conv]{Conversion}

\indexlibrarymember{base}{reverse_iterator}%
\begin{itemdecl}
constexpr Iterator base() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{current}.
\end{itemdescr}

\rSec3[reverse.iter.elem]{Element access}

\indexlibrarymember{operator*}{reverse_iterator}%
\begin{itemdecl}
constexpr reference operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
Iterator tmp = current;
return *--tmp;
\end{codeblock}

\end{itemdescr}

\indexlibrarymember{operator->}{reverse_iterator}%
\begin{itemdecl}
constexpr pointer operator->() const
  requires (is_pointer_v<Iterator> ||
            requires(const Iterator i) { i.operator->(); });
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{itemize}
\item If \tcode{Iterator} is a pointer type, equivalent to:
\tcode{return prev(current);}

\item Otherwise, equivalent to:
\tcode{return prev(current).operator->();}
\end{itemize}
\end{itemdescr}

\indexlibrarymember{operator[]}{reverse_iterator}%
\begin{itemdecl}
constexpr @\unspec@ operator[](difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{current[-n - 1]}.
\end{itemdescr}

\rSec3[reverse.iter.nav]{Navigation}

\indexlibrarymember{operator+}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator operator+(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator(current - n)}.
\end{itemdescr}

\indexlibrarymember{operator-}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator operator-(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator(current + n)}.
\end{itemdescr}

\indexlibrarymember{operator++}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{--current;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
reverse_iterator tmp = *this;
--current;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator--}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator& operator--();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by \tcode{++current}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator--}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator operator--(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
reverse_iterator tmp = *this;
++current;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator+=}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator& operator+=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{current -= n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator-=}{reverse_iterator}%
\begin{itemdecl}
constexpr reverse_iterator& operator-=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{current += n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[reverse.iter.cmp]{Comparisons}

\indexlibrarymember{operator==}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator==(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() == y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() == y.base()}.
\end{itemdescr}

\indexlibrarymember{operator"!=}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator!=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() != y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() != y.base()}.
\end{itemdescr}

\indexlibrarymember{operator<}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator<(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() > y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() > y.base()}.
\end{itemdescr}

\indexlibrarymember{operator>}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator>(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() < y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() < y.base()}.
\end{itemdescr}

\indexlibrarymember{operator<=}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator<=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() >= y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() >= y.base()}.
\end{itemdescr}

\indexlibrarymember{operator>=}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator>=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() <= y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() <= y.base()}.
\end{itemdescr}

\indexlibrarymember{operator<=>}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, @\libconcept{three_way_comparable_with}@<Iterator1> Iterator2>
  constexpr compare_three_way_result_t<Iterator1, Iterator2>
    operator<=>(const reverse_iterator<Iterator1>& x,
                const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{y.base() <=> x.base()}.

\pnum
\begin{note}
The argument order in the \returns element is reversed
because this is a reverse iterator.
\end{note}
\end{itemdescr}

\rSec3[reverse.iter.nonmember]{Non-member functions}

\indexlibrarymember{operator-}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr auto operator-(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{y.base() - x.base()}.
\end{itemdescr}

\indexlibrarymember{operator+}{reverse_iterator}%
\begin{itemdecl}
template<class Iterator>
  constexpr reverse_iterator<Iterator> operator+(
    iter_difference_t<Iterator> n,
    const reverse_iterator<Iterator>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<Iterator>(x.base() - n)}.
\end{itemdescr}

\indexlibrarymember{iter_move}{reverse_iterator}%
\begin{itemdecl}
friend constexpr iter_rvalue_reference_t<Iterator>
  iter_move(const reverse_iterator& i) noexcept(@\seebelow@);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
auto tmp = i.base();
return ranges::iter_move(--tmp);
\end{codeblock}

\pnum
\remarks
The exception specification is equivalent to:
\begin{codeblock}
is_nothrow_copy_constructible_v<Iterator> &&
noexcept(ranges::iter_move(--declval<Iterator&>()))
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{iter_swap}{reverse_iterator}%
\begin{itemdecl}
template<@\libconcept{indirectly_swappable}@<Iterator> Iterator2>
  friend constexpr void
    iter_swap(const reverse_iterator& x,
              const reverse_iterator<Iterator2>& y) noexcept(@\seebelow@);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
auto xtmp = x.base();
auto ytmp = y.base();
ranges::iter_swap(--xtmp, --ytmp);
\end{codeblock}

\pnum
\remarks
The exception specification is equivalent to:
\begin{codeblock}
is_nothrow_copy_constructible_v<Iterator> &&
is_nothrow_copy_constructible_v<Iterator2> &&
noexcept(ranges::iter_swap(--declval<Iterator&>(), --declval<Iterator2&>()))
\end{codeblock}
\end{itemdescr}

\indexlibrary{\idxcode{reverse_iterator}!\idxcode{make_reverse_iterator} non-member function}%
\indexlibraryglobal{make_reverse_iterator}%
\begin{itemdecl}
template<class Iterator>
  constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<Iterator>(i)}.
\end{itemdescr}

\rSec2[insert.iterators]{Insert iterators}

\rSec3[insert.iterators.general]{General}

\pnum
To make it possible to deal with insertion in the same way as writing into an array, a special kind of iterator
adaptors, called
\term{insert iterators},
are provided in the library.
With regular iterator classes,
\begin{codeblock}
while (first != last) *result++ = *first++;
\end{codeblock}
causes a range \range{first}{last}
to be copied into a range starting with result.
The same code with
\tcode{result}
being an insert iterator will insert corresponding elements into the container.
This device allows all of the
copying algorithms in the library to work in the
\term{insert mode}
instead of the \term{regular overwrite} mode.

\pnum
An insert iterator is constructed from a container and possibly one of its iterators pointing to where
insertion takes place if it is neither at the beginning nor at the end of the container.
Insert iterators meet the requirements of output iterators.
\tcode{operator*}
returns the insert iterator itself.
The assignment
\tcode{operator=(const T\& x)}
is defined on insert iterators to allow writing into them, it inserts
\tcode{x}
right before where the insert iterator is pointing.
In other words, an insert iterator is like a cursor pointing into the
container where the insertion takes place.
\tcode{back_insert_iterator}
inserts elements at the end of a container,
\tcode{front_insert_iterator}
inserts elements at the beginning of a container, and
\tcode{insert_iterator}
inserts elements where the iterator points to in a container.
\tcode{back_inserter},
\tcode{front_inserter},
and
\tcode{inserter}
are three
functions making the insert iterators out of a container.

\rSec3[back.insert.iterator]{Class template \tcode{back_insert_iterator}}

\rSec4[back.insert.iter.general]{General}

\indexlibraryglobal{back_insert_iterator}%
\begin{codeblock}
namespace std {
  template<class Container>
  class back_insert_iterator {
  protected:
    Container* container;

  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

    constexpr explicit back_insert_iterator(Container& x);
    constexpr back_insert_iterator& operator=(const typename Container::value_type& value);
    constexpr back_insert_iterator& operator=(typename Container::value_type&& value);

    constexpr back_insert_iterator& operator*();
    constexpr back_insert_iterator& operator++();
    constexpr back_insert_iterator  operator++(int);
  };
}
\end{codeblock}

\rSec4[back.insert.iter.ops]{Operations}

\indexlibraryctor{back_insert_iterator}%
\begin{itemdecl}
constexpr explicit back_insert_iterator(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{addressof(x)}.
\end{itemdescr}

\indexlibrarymember{operator=}{back_insert_iterator}%
\begin{itemdecl}
constexpr back_insert_iterator& operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{container->push_back(value);}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator=}{back_insert_iterator}%
\begin{itemdecl}
constexpr back_insert_iterator& operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{container->push_back(std::move(value));}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator*}{back_insert_iterator}%
\begin{itemdecl}
constexpr back_insert_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{back_insert_iterator}%
\begin{itemdecl}
constexpr back_insert_iterator& operator++();
constexpr back_insert_iterator  operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[back.inserter]{ \tcode{back_inserter}}

\indexlibraryglobal{back_inserter}%
\begin{itemdecl}
template<class Container>
  constexpr back_insert_iterator<Container> back_inserter(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{back_insert_iterator<Container>(x)}.
\end{itemdescr}

\rSec3[front.insert.iterator]{Class template \tcode{front_insert_iterator}}

\rSec4[front.insert.iter.general]{General}

\indexlibraryglobal{front_insert_iterator}%
\begin{codeblock}
namespace std {
  template<class Container>
  class front_insert_iterator {
  protected:
    Container* container;

  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

    constexpr explicit front_insert_iterator(Container& x);
    constexpr front_insert_iterator& operator=(const typename Container::value_type& value);
    constexpr front_insert_iterator& operator=(typename Container::value_type&& value);

    constexpr front_insert_iterator& operator*();
    constexpr front_insert_iterator& operator++();
    constexpr front_insert_iterator  operator++(int);
  };
}
\end{codeblock}

\rSec4[front.insert.iter.ops]{Operations}

\indexlibraryctor{front_insert_iterator}%
\begin{itemdecl}
constexpr explicit front_insert_iterator(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{addressof(x)}.
\end{itemdescr}

\indexlibrarymember{operator=}{front_insert_iterator}%
\begin{itemdecl}
constexpr front_insert_iterator& operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{container->push_front(value);}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator=}{front_insert_iterator}%
\begin{itemdecl}
constexpr front_insert_iterator& operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{container->push_front(std::move(value));}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator*}{front_insert_iterator}%
\begin{itemdecl}
constexpr front_insert_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{front_insert_iterator}%
\begin{itemdecl}
constexpr front_insert_iterator& operator++();
constexpr front_insert_iterator  operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[front.inserter]{\tcode{front_inserter}}

\indexlibraryglobal{front_inserter}%
\begin{itemdecl}
template<class Container>
  constexpr front_insert_iterator<Container> front_inserter(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{front_insert_iterator<Container>(x)}.
\end{itemdescr}

\rSec3[insert.iterator]{Class template \tcode{insert_iterator}}

\rSec4[insert.iter.general]{General}

\indexlibraryglobal{insert_iterator}%
\begin{codeblock}
namespace std {
  template<class Container>
  class insert_iterator {
  protected:
    Container* container;
    ranges::iterator_t<Container> iter;

  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

    constexpr insert_iterator(Container& x, ranges::iterator_t<Container> i);
    constexpr insert_iterator& operator=(const typename Container::value_type& value);
    constexpr insert_iterator& operator=(typename Container::value_type&& value);

    constexpr insert_iterator& operator*();
    constexpr insert_iterator& operator++();
    constexpr insert_iterator& operator++(int);
  };
}
\end{codeblock}

\rSec4[insert.iter.ops]{Operations}

\indexlibraryctor{insert_iterator}%
\begin{itemdecl}
constexpr insert_iterator(Container& x, ranges::iterator_t<Container> i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{addressof(x)} and
\tcode{iter}
with \tcode{i}.
\end{itemdescr}

\indexlibrarymember{operator=}{insert_iterator}%
\begin{itemdecl}
constexpr insert_iterator& operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
iter = container->insert(iter, value);
++iter;
\end{codeblock}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator=}{insert_iterator}%
\begin{itemdecl}
constexpr insert_iterator& operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
iter = container->insert(iter, std::move(value));
++iter;
\end{codeblock}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator*}{insert_iterator}%
\begin{itemdecl}
constexpr insert_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{insert_iterator}%
\begin{itemdecl}
constexpr insert_iterator& operator++();
constexpr insert_iterator& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[inserter]{\tcode{inserter}}

\indexlibraryglobal{inserter}%
\begin{itemdecl}
template<class Container>
  constexpr insert_iterator<Container>
    inserter(Container& x, ranges::iterator_t<Container> i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{insert_iterator<Container>(x, i)}.
\end{itemdescr}

\rSec2[const.iterators]{Constant iterators and sentinels}

\rSec3[const.iterators.general]{General}

\pnum
Class template \tcode{basic_const_iterator} is an iterator adaptor
with the same behavior as the underlying iterator
except that its indirection operator implicitly converts
the value returned by the underlying iterator's indirection operator
to a type such that the adapted iterator is
a constant iterator\iref{iterator.requirements}.
Some generic algorithms can be called with constant iterators to avoid mutation.

\pnum
Specializations of \tcode{basic_const_iterator} are constant iterators.

\rSec3[const.iterators.alias]{Alias templates}

\begin{itemdecl}
template<@\libconcept{indirectly_readable}@ It>
  using @\libglobal{iter_const_reference_t}@ =
    common_reference_t<const iter_value_t<It>&&, iter_reference_t<It>>;

template<class It>
  concept @\defexposconcept{constant-iterator}@ =                                                   // \expos
    @\libconcept{input_iterator}@<It> && @\libconcept{same_as}@<iter_const_reference_t<It>, iter_reference_t<It>>;

template<@\libconcept{input_iterator}@ I>
  using @\libglobal{const_iterator}@ = @\seebelow@;
\end{itemdecl}

\begin{itemdescr}
\pnum
\result
If \tcode{I} models \exposconcept{constant-iterator}, \tcode{I}.
Otherwise, \tcode{basic_const_iterator<I>}.
\end{itemdescr}

\begin{itemdecl}
template<@\libconcept{semiregular}@ S>
  using @\libglobal{const_sentinel}@ = @\seebelow@;
\end{itemdecl}

\begin{itemdescr}
\pnum
\result
If \tcode{S} models \libconcept{input_iterator}, \tcode{const_iterator<S>}.
Otherwise, \tcode{S}.
\end{itemdescr}

\rSec3[const.iterators.iterator]{Class template \tcode{basic_const_iterator}}

\begin{codeblock}
namespace std {
  template<class I>
    concept @\exposconcept{not-a-const-iterator}@ = @\seebelow@;                   // \expos

  template<@\libconcept{indirectly_readable}@ I>
    using @\exposidnc{iter-const-rvalue-reference-t}@ =                       // \expos
      common_reference_t<const iter_value_t<I>&&, iter_rvalue_reference_t<I>>;

  template<@\libconcept{input_iterator}@ Iterator>
  class @\libglobal{basic_const_iterator}@ {
    Iterator @\exposidnc{current_}@ = Iterator();                             // \expos
    using @\exposidnc{reference}@ = iter_const_reference_t<Iterator>;         // \expos
    using @\exposidnc{rvalue-reference}@ =                                    // \expos
      @\exposid{iter-const-rvalue-reference-t}@<Iterator>;

  public:
    using iterator_type = Iterator;
    using iterator_concept = @\seebelow@;
    using iterator_category = @\seebelow@;  // not always present
    using value_type = iter_value_t<Iterator>;
    using difference_type = iter_difference_t<Iterator>;

    basic_const_iterator() requires @\libconcept{default_initializable}@<Iterator> = default;
    constexpr basic_const_iterator(Iterator current);
    template<@\libconcept{convertible_to}@<Iterator> U>
      constexpr basic_const_iterator(basic_const_iterator<U> current);
    template<@\exposconcept{different-from}@<basic_const_iterator> T>
      requires @\libconcept{convertible_to}@<T, Iterator>
      constexpr basic_const_iterator(T&& current);

    constexpr const Iterator& base() const & noexcept;
    constexpr Iterator base() &&;

    constexpr @\exposid{reference}@ operator*() const;
    constexpr const auto* operator->() const
      requires is_lvalue_reference_v<iter_reference_t<Iterator>> &&
               @\libconcept{same_as}@<remove_cvref_t<iter_reference_t<Iterator>>, value_type>;

    constexpr basic_const_iterator& operator++();
    constexpr void operator++(int);
    constexpr basic_const_iterator operator++(int) requires @\libconcept{forward_iterator}@<Iterator>;

    constexpr basic_const_iterator& operator--() requires @\libconcept{bidirectional_iterator}@<Iterator>;
    constexpr basic_const_iterator operator--(int) requires @\libconcept{bidirectional_iterator}@<Iterator>;

    constexpr basic_const_iterator& operator+=(difference_type n)
      requires @\libconcept{random_access_iterator}@<Iterator>;
    constexpr basic_const_iterator& operator-=(difference_type n)
      requires @\libconcept{random_access_iterator}@<Iterator>;

    constexpr @\exposid{reference}@ operator[](difference_type n) const
      requires @\libconcept{random_access_iterator}@<Iterator>;

    template<@\libconcept{sentinel_for}@<Iterator> S>
      constexpr bool operator==(const S& s) const;

    template<@\exposconcept{not-a-const-iterator}@ CI>
      requires @\exposconcept{constant-iterator}@<CI> && @\libconcept{convertible_to}@<Iterator const&, CI>
    constexpr operator CI() const &;
    template<@\exposconcept{not-a-const-iterator}@ CI>
      requires @\exposconcept{constant-iterator}@<CI> && @\libconcept{convertible_to}@<Iterator, CI>
    constexpr operator CI() &&;

    constexpr bool operator<(const basic_const_iterator& y) const
      requires @\libconcept{random_access_iterator}@<Iterator>;
    constexpr bool operator>(const basic_const_iterator& y) const
      requires @\libconcept{random_access_iterator}@<Iterator>;
    constexpr bool operator<=(const basic_const_iterator& y) const
      requires @\libconcept{random_access_iterator}@<Iterator>;
    constexpr bool operator>=(const basic_const_iterator& y) const
      requires @\libconcept{random_access_iterator}@<Iterator>;
    constexpr auto operator<=>(const basic_const_iterator& y) const
      requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{three_way_comparable}@<Iterator>;

    template<@\exposconcept{different-from}@<basic_const_iterator> I>
      constexpr bool operator<(const I& y) const
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{different-from}@<basic_const_iterator> I>
      constexpr bool operator>(const I& y) const
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{different-from}@<basic_const_iterator> I>
      constexpr bool operator<=(const I& y) const
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{different-from}@<basic_const_iterator> I>
      constexpr bool operator>=(const I& y) const
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{different-from}@<basic_const_iterator> I>
      constexpr auto operator<=>(const I& y) const
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I> &&
                 @\libconcept{three_way_comparable_with}@<Iterator, I>;
    template<@\exposconcept{not-a-const-iterator}@ I>
      friend constexpr bool operator<(const I& x, const basic_const_iterator& y)
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{not-a-const-iterator}@ I>
      friend constexpr bool operator>(const I& x, const basic_const_iterator& y)
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{not-a-const-iterator}@ I>
      friend constexpr bool operator<=(const I& x, const basic_const_iterator& y)
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
    template<@\exposconcept{not-a-const-iterator}@ I>
      friend constexpr bool operator>=(const I& x, const basic_const_iterator& y)
        requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;

    friend constexpr basic_const_iterator operator+(const basic_const_iterator& i,
                                                    difference_type n)
      requires @\libconcept{random_access_iterator}@<Iterator>;
    friend constexpr basic_const_iterator operator+(difference_type n,
                                                    const basic_const_iterator& i)
      requires @\libconcept{random_access_iterator}@<Iterator>;
    friend constexpr basic_const_iterator operator-(const basic_const_iterator& i,
                                                    difference_type n)
      requires @\libconcept{random_access_iterator}@<Iterator>;
    template<@\libconcept{sized_sentinel_for}@<Iterator> S>
      constexpr difference_type operator-(const S& y) const;
    template<@\exposconcept{not-a-const-iterator}@ S>
      requires @\libconcept{sized_sentinel_for}@<S, Iterator>
      friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);
    friend constexpr @\exposid{rvalue-reference}@ iter_move(const basic_const_iterator& i)
      noexcept(noexcept(static_cast<@\exposid{rvalue-reference}@>(ranges::iter_move(i.@\exposid{current_}@))))
      {
        return static_cast<@\exposid{rvalue-reference}@>(ranges::iter_move(i.@\exposid{current_}@));
      }
  };
}
\end{codeblock}

\pnum
Given some type \tcode{I},
the concept \defexposconcept{not-a-const-iterator} is defined as \tcode{false}
if \tcode{I} is a specialization of \tcode{basic_const_iterator} and
\tcode{true} otherwise.

\rSec3[const.iterators.types]{Member types}

\pnum
\tcode{basic_const_iterator<Iterator>::iterator_concept} is defined as follows:
\begin{itemize}
\item
If \tcode{Iterator} models \libconcept{contiguous_iterator},
then \tcode{iterator_concept} denotes \tcode{contiguous_iterator_tag}.
\item
Otherwise, if \tcode{Iterator} models \libconcept{random_access_iterator},
then \tcode{iterator_concept} denotes \tcode{random_access_iterator_tag}.
\item
Otherwise, if \tcode{Iterator} models \libconcept{bidirectional_iterator},
then \tcode{iterator_concept} denotes \tcode{bidirec\-tional_iterator_tag}.
\item
Otherwise, if \tcode{Iterator} models \libconcept{forward_iterator},
then \tcode{iterator_concept} denotes \tcode{forward_itera\-tor_tag}.
\item
Otherwise, \tcode{iterator_concept} denotes \tcode{input_iterator_tag}.
\end{itemize}

\pnum
The member \grammarterm{typedef-name} \tcode{iterator_category} is declared
if and only if \tcode{Iterator} models \libconcept{forward_iterator}.
In that case,
\tcode{basic_const_iterator<Iterator>::iterator_category} denotes
the type \tcode{iterator_traits<\brk{}Iterator>::iterator_category}.

\rSec3[const.iterators.ops]{Operations}

\indexlibraryctor{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator(Iterator current);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \exposid{current_} with \tcode{std::move(current)}.
\end{itemdescr}

\indexlibraryctor{basic_const_iterator}%
\begin{itemdecl}
template<@\libconcept{convertible_to}@<Iterator> U>
  constexpr basic_const_iterator(basic_const_iterator<U> current);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \exposid{current_}
with \tcode{std::move(current.\exposid{current_})}.
\end{itemdescr}

\indexlibraryctor{basic_const_iterator}%
\begin{itemdecl}
template<@\exposconcept{different-from}@<basic_const_iterator> T>
  requires @\libconcept{convertible_to}@<T, Iterator>
  constexpr basic_const_iterator(T&& current);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \exposid{current_} with \tcode{std::forward<T>(current)}.
\end{itemdescr}

\indexlibrarymember{base}{basic_const_iterator}%
\begin{itemdecl}
constexpr const Iterator& base() const & noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return \exposid{current_};}
\end{itemdescr}

\indexlibrarymember{base}{basic_const_iterator}%
\begin{itemdecl}
constexpr Iterator base() &&;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return std::move(\exposid{current_});}
\end{itemdescr}

\indexlibrarymember{operator*}{basic_const_iterator}%
\begin{itemdecl}
constexpr @\exposid{reference}@ operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return static_cast<\exposid{reference}>(*\exposid{current_});}
\end{itemdescr}

\indexlibrarymember{operator->}{basic_const_iterator}%
\begin{itemdecl}
constexpr const auto* operator->() const
  requires is_lvalue_reference_v<iter_reference_t<Iterator>> &&
           @\libconcept{same_as}@<remove_cvref_t<iter_reference_t<Iterator>>, value_type>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
If \tcode{Iterator} models \libconcept{contiguous_iterator},
\tcode{to_address(\exposid{current_})};
otherwise, \tcode{address\-of(*\exposid{current_})}.
\end{itemdescr}

\indexlibrarymember{operator++}{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
++@\exposid{current_}@;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator++}{basic_const_iterator}%
\begin{itemdecl}
constexpr void operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{++\exposid{current_};}
\end{itemdescr}

\indexlibrarymember{operator++}{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator operator++(int) requires @\libconcept{forward_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
auto tmp = *this;
++*this;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator--}{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator& operator--() requires @\libconcept{bidirectional_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
--@\exposid{current_}@;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator--}{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator operator--(int) requires @\libconcept{bidirectional_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
auto tmp = *this;
--*this;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator+=}{basic_const_iterator}%
\indexlibrarymember{operator-=}{basic_const_iterator}%
\begin{itemdecl}
constexpr basic_const_iterator& operator+=(difference_type n)
  requires @\libconcept{random_access_iterator}@<Iterator>;
constexpr basic_const_iterator& operator-=(difference_type n)
  requires @\libconcept{random_access_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{\placeholder{op}} be the operator.

\pnum
\effects
Equivalent to:
\begin{codeblock}
@\exposid{current_}@ @\placeholder{op}@ n;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator[]}{basic_const_iterator}%
\begin{itemdecl}
constexpr @\exposid{reference}@ operator[](difference_type n) const requires @\libconcept{random_access_iterator}@<Iterator>
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return static_cast<\exposid{reference}>(\exposid{current_}[n]);}
\end{itemdescr}

\indexlibrarymember{operator==}{basic_const_iterator}%
\begin{itemdecl}
template<@\libconcept{sentinel_for}@<Iterator> S>
  constexpr bool operator==(const S& s) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return \exposid{current_} == s;}
\end{itemdescr}

\begin{itemdecl}
template<@\exposconcept{not-a-const-iterator}@ CI>
  requires @\exposconcept{constant-iterator}@<CI> && @\libconcept{convertible_to}@<Iterator const&, CI>
constexpr operator CI() const &;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\exposid{current_}.
\end{itemdescr}

\begin{itemdecl}
template<@\exposconcept{not-a-const-iterator}@ CI>
  requires @\exposconcept{constant-iterator}@<CI> && @\libconcept{convertible_to}@<Iterator, CI>
constexpr operator CI() &&;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{std::move(\exposid{current_})}.
\end{itemdescr}

\indexlibrarymember{operator<}{basic_const_iterator}%
\indexlibrarymember{operator>}{basic_const_iterator}%
\indexlibrarymember{operator<=}{basic_const_iterator}%
\indexlibrarymember{operator>=}{basic_const_iterator}%
\indexlibrarymember{operator<=>}{basic_const_iterator}%
\begin{itemdecl}
constexpr bool operator<(const basic_const_iterator& y) const
  requires @\libconcept{random_access_iterator}@<Iterator>;
constexpr bool operator>(const basic_const_iterator& y) const
  requires @\libconcept{random_access_iterator}@<Iterator>;
constexpr bool operator<=(const basic_const_iterator& y) const
  requires @\libconcept{random_access_iterator}@<Iterator>;
constexpr bool operator>=(const basic_const_iterator& y) const
  requires @\libconcept{random_access_iterator}@<Iterator>;
constexpr auto operator<=>(const basic_const_iterator& y) const
  requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{three_way_comparable}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{\placeholder{op}} be the operator.

\pnum
\effects
Equivalent to:
\tcode{return \exposid{current_} \placeholder{op} \exposid{y.current_};}
\end{itemdescr}

\indexlibrarymember{operator<}{basic_const_iterator}%
\indexlibrarymember{operator>}{basic_const_iterator}%
\indexlibrarymember{operator<=}{basic_const_iterator}%
\indexlibrarymember{operator>=}{basic_const_iterator}%
\indexlibrarymember{operator<=>}{basic_const_iterator}%
\begin{itemdecl}
template<@\exposconcept{different-from}@<basic_const_iterator> I>
  constexpr bool operator<(const I& y) const
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{different-from}@<basic_const_iterator> I>
  constexpr bool operator>(const I& y) const
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{different-from}@<basic_const_iterator> I>
  constexpr bool operator<=(const I& y) const
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{different-from}@<basic_const_iterator> I>
  constexpr bool operator>=(const I& y) const
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{different-from}@<basic_const_iterator> I>
  constexpr auto operator<=>(const I& y) const
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I> &&
             @\libconcept{three_way_comparable_with}@<Iterator, I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{\placeholder{op}} be the operator.

\pnum
\effects
Equivalent to: \tcode{return \exposid{current_} \placeholder{op} y;}
\end{itemdescr}

\indexlibrarymember{operator<}{basic_const_iterator}%
\indexlibrarymember{operator>}{basic_const_iterator}%
\indexlibrarymember{operator<=}{basic_const_iterator}%
\indexlibrarymember{operator>=}{basic_const_iterator}%
\begin{itemdecl}
template<@\exposconcept{not-a-const-iterator}@ I>
  friend constexpr bool operator<(const I& x, const basic_const_iterator& y)
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{not-a-const-iterator}@ I>
  friend constexpr bool operator>(const I& x, const basic_const_iterator& y)
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{not-a-const-iterator}@ I>
  friend constexpr bool operator<=(const I& x, const basic_const_iterator& y)
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
template<@\exposconcept{not-a-const-iterator}@ I>
  friend constexpr bool operator>=(const I& x, const basic_const_iterator& y)
    requires @\libconcept{random_access_iterator}@<Iterator> && @\libconcept{totally_ordered_with}@<Iterator, I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{\placeholder{op}} be the operator.

\pnum
\effects
Equivalent to: \tcode{return x \placeholder{op} y.\exposid{current_};}
\end{itemdescr}

\indexlibrarymember{operator+}{basic_const_iterator}%
\begin{itemdecl}
friend constexpr basic_const_iterator operator+(const basic_const_iterator& i, difference_type n)
  requires @\libconcept{random_access_iterator}@<Iterator>;
friend constexpr basic_const_iterator operator+(difference_type n, const basic_const_iterator& i)
  requires @\libconcept{random_access_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return basic_const_iterator(i.\exposid{current_} + n);}
\end{itemdescr}

\indexlibrarymember{operator-}{basic_const_iterator}%
\begin{itemdecl}
friend constexpr basic_const_iterator operator-(const basic_const_iterator& i, difference_type n)
  requires @\libconcept{random_access_iterator}@<Iterator>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return basic_const_iterator(i.\exposid{current_} - n);}
\end{itemdescr}

\indexlibrarymember{operator-}{basic_const_iterator}%
\begin{itemdecl}
template<@\libconcept{sized_sentinel_for}@<Iterator> S>
  constexpr difference_type operator-(const S& y) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return \exposid{current_} - y;}
\end{itemdescr}

\indexlibrarymember{operator-}{basic_const_iterator}%
\begin{itemdecl}
template<@\exposconcept{not-a-const-iterator}@ S>
  requires @\libconcept{sized_sentinel_for}@<S, Iterator>
  friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return x - y.\exposid{current_};}
\end{itemdescr}

\rSec2[move.iterators]{Move iterators and sentinels}

\rSec3[move.iterators.general]{General}

\pnum
Class template \tcode{move_iterator} is an iterator adaptor
with the same behavior as the underlying iterator except that its
indirection operator implicitly converts the value returned by the
underlying iterator's indirection operator to an rvalue.
Some generic algorithms can be called with move iterators to replace
copying with moving.

\pnum
\begin{example}
\begin{codeblock}
list<string> s;
// populate the list \tcode{s}
vector<string> v1(s.begin(), s.end());          // copies strings into \tcode{v1}
vector<string> v2(make_move_iterator(s.begin()),
                  make_move_iterator(s.end())); // moves strings into \tcode{v2}
\end{codeblock}

\end{example}

\rSec3[move.iterator]{Class template \tcode{move_iterator}}

\indexlibraryglobal{move_iterator}%
\begin{codeblock}
namespace std {
  template<class Iterator>
  class move_iterator {
  public:
    using iterator_type     = Iterator;
    using iterator_concept  = @\seebelow@;
    using iterator_category = @\seebelow@;                      // not always present
    using value_type        = iter_value_t<Iterator>;
    using difference_type   = iter_difference_t<Iterator>;
    using pointer           = Iterator;
    using reference         = iter_rvalue_reference_t<Iterator>;

    constexpr move_iterator();
    constexpr explicit move_iterator(Iterator i);
    template<class U> constexpr move_iterator(const move_iterator<U>& u);
    template<class U> constexpr move_iterator& operator=(const move_iterator<U>& u);

    constexpr const Iterator& base() const & noexcept;
    constexpr Iterator base() &&;
    constexpr reference operator*() const;

    constexpr move_iterator& operator++();
    constexpr auto operator++(int);
    constexpr move_iterator& operator--();
    constexpr move_iterator operator--(int);

    constexpr move_iterator operator+(difference_type n) const;
    constexpr move_iterator& operator+=(difference_type n);
    constexpr move_iterator operator-(difference_type n) const;
    constexpr move_iterator& operator-=(difference_type n);
    constexpr reference operator[](difference_type n) const;

    template<@\libconcept{sentinel_for}@<Iterator> S>
      friend constexpr bool
        operator==(const move_iterator& x, const move_sentinel<S>& y);
    template<@\libconcept{sized_sentinel_for}@<Iterator> S>
      friend constexpr iter_difference_t<Iterator>
        operator-(const move_sentinel<S>& x, const move_iterator& y);
    template<@\libconcept{sized_sentinel_for}@<Iterator> S>
      friend constexpr iter_difference_t<Iterator>
        operator-(const move_iterator& x, const move_sentinel<S>& y);
    friend constexpr iter_rvalue_reference_t<Iterator>
      iter_move(const move_iterator& i)
        noexcept(noexcept(ranges::iter_move(i.current)));
    template<@\libconcept{indirectly_swappable}@<Iterator> Iterator2>
      friend constexpr void
        iter_swap(const move_iterator& x, const move_iterator<Iterator2>& y)
          noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

  private:
    Iterator current;   // \expos
  };
}
\end{codeblock}

\pnum
The member \grammarterm{typedef-name} \tcode{iterator_concept} is defined
as follows:
\begin{itemize}
\item
If \tcode{Iterator} models \libconcept{random_access_iterator},
then \tcode{iterator_concept} denotes \tcode{random_access_iterator_tag}.
\item
Otherwise, if \tcode{Iterator} models \libconcept{bidirectional_iterator},
then \tcode{iterator_concept} denotes \tcode{bidirec\-tional_iterator_tag}.
\item
Otherwise, if \tcode{Iterator} models \libconcept{forward_iterator},
then \tcode{iterator_concept} denotes \tcode{forward_itera\-tor_tag}.
\item
Otherwise, \tcode{iterator_concept} denotes \tcode{input_iterator_tag}.
\end{itemize}

\pnum
The member \grammarterm{typedef-name} \tcode{iterator_category} is declared
if and only if the \grammarterm{qualified-id}
\tcode{iterator_traits<It\-erator>::iterator_category}
is valid and denotes a type.
In that case, \tcode{iterator_category} denotes
\begin{itemize}
\item
\tcode{random_access_iterator_tag} if
the type
\tcode{iterator_traits<\brk{}Iterator>::iterator_category} models
\tcode{\libconcept{derived_from}<random_access_iterator_tag>}, and
\item
\tcode{iterator_traits<\brk{}Iterator>::iterator_category} otherwise.
\end{itemize}

\rSec3[move.iter.requirements]{Requirements}

\pnum
The template parameter \tcode{Iterator} shall either
meet the \oldconcept{InputIterator} requirements\iref{input.iterators}
or model \libconcept{input_iterator}\iref{iterator.concept.input}.
Additionally, if any of the bidirectional traversal
functions are instantiated, the template parameter shall either
meet the \oldconcept{BidirectionalIterator} requirements\iref{bidirectional.iterators}
or model \libconcept{bidirectional_iterator}\iref{iterator.concept.bidir}.
If any of the random access traversal functions are instantiated, the
template parameter shall either
meet the \oldconcept{RandomAccessIterator} requirements\iref{random.access.iterators}
or model
\libconcept{random_access_iterator}\iref{iterator.concept.random.access}.

\rSec3[move.iter.cons]{Construction and assignment}

\indexlibraryctor{move_iterator}%
\begin{itemdecl}
constexpr move_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Value-initializes \tcode{current}.
\end{itemdescr}


\indexlibraryctor{move_iterator}%
\begin{itemdecl}
constexpr explicit move_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{current} with \tcode{std::move(i)}.
\end{itemdescr}


\indexlibraryctor{move_iterator}%
\begin{itemdecl}
template<class U> constexpr move_iterator(const move_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{is_same_v<U, Iterator>} is \tcode{false} and
\tcode{const U\&} models \tcode{\libconcept{convertible_to}<Iterator>}.

\pnum
\effects
Initializes \tcode{current} with \tcode{u.current}.
\end{itemdescr}

\indexlibrarymember{operator=}{move_iterator}%
\begin{itemdecl}
template<class U> constexpr move_iterator& operator=(const move_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{is_same_v<U, Iterator>} is \tcode{false},
\tcode{const U\&} models \tcode{\libconcept{convertible_to}<Iterator>}, and
\tcode{\libconcept{assignable_from}<Iterator\&, const U\&>} is modeled.

\pnum
\effects
Assigns \tcode{u.current} to
\tcode{current}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[move.iter.op.conv]{Conversion}

\indexlibrarymember{base}{move_iterator}%
\begin{itemdecl}
constexpr const Iterator& base() const & noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{current}.
\end{itemdescr}

\indexlibrarymember{base}{move_iterator}%
\begin{itemdecl}
constexpr Iterator base() &&;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{std::move(current)}.
\end{itemdescr}

\rSec3[move.iter.elem]{Element access}

\indexlibrarymember{operator*}{move_iterator}%
\begin{itemdecl}
constexpr reference operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return ranges::iter_move(current);}
\end{itemdescr}

\indexlibrarymember{operator[]}{move_iterator}%
\begin{itemdecl}
constexpr reference operator[](difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return ranges::iter_move(current + n);}
\end{itemdescr}

\rSec3[move.iter.nav]{Navigation}

\indexlibrarymember{operator++}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by \tcode{++current}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{move_iterator}%
\begin{itemdecl}
constexpr auto operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
If \tcode{Iterator} models \libconcept{forward_iterator}, equivalent to:
\begin{codeblock}
move_iterator tmp = *this;
++current;
return tmp;
\end{codeblock}
Otherwise, equivalent to \tcode{++current}.
\end{itemdescr}

\indexlibrarymember{operator--}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator& operator--();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by \tcode{--current}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator--}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator operator--(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
move_iterator tmp = *this;
--current;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator+}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator operator+(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{move_iterator(current + n)}.
\end{itemdescr}

\indexlibrarymember{operator+=}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator& operator+=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{current += n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator-}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator operator-(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{move_iterator(current - n)}.
\end{itemdescr}

\indexlibrarymember{operator-=}{move_iterator}%
\begin{itemdecl}
constexpr move_iterator& operator-=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by: \tcode{current -= n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[move.iter.op.comp]{Comparisons}

\indexlibrarymember{operator==}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr bool operator==(const move_iterator<Iterator1>& x,
                            const move_iterator<Iterator2>& y);
template<@\libconcept{sentinel_for}@<Iterator> S>
  friend constexpr bool operator==(const move_iterator& x,
                                   const move_sentinel<S>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() == y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() == y.base()}.
\end{itemdescr}

\indexlibrarymember{operator<}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
constexpr bool operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() < y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{x.base() < y.base()}.
\end{itemdescr}

\indexlibrarymember{operator>}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
constexpr bool operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{y.base() < x.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{y < x}.
\end{itemdescr}

\indexlibrarymember{operator<=}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
constexpr bool operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{y.base() < x.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{!(y < x)}.
\end{itemdescr}

\indexlibrarymember{operator>=}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
constexpr bool operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() < y.base()} is well-formed and
convertible to \tcode{bool}.

\pnum
\returns
\tcode{!(x < y)}.
\end{itemdescr}

\indexlibrarymember{operator<=>}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, @\libconcept{three_way_comparable_with}@<Iterator1> Iterator2>
  constexpr compare_three_way_result_t<Iterator1, Iterator2>
    operator<=>(const move_iterator<Iterator1>& x,
                const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.base() <=> y.base()}.
\end{itemdescr}

\rSec3[move.iter.nonmember]{Non-member functions}

\indexlibrarymember{operator-}{move_iterator}%
\begin{itemdecl}
template<class Iterator1, class Iterator2>
  constexpr auto operator-(
    const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y)
      -> decltype(x.base() - y.base());
template<@\libconcept{sized_sentinel_for}@<Iterator> S>
  friend constexpr iter_difference_t<Iterator>
    operator-(const move_sentinel<S>& x, const move_iterator& y);
template<@\libconcept{sized_sentinel_for}@<Iterator> S>
  friend constexpr iter_difference_t<Iterator>
    operator-(const move_iterator& x, const move_sentinel<S>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.base() - y.base()}.
\end{itemdescr}

\indexlibrarymember{operator+}{move_iterator}%
\begin{itemdecl}
template<class Iterator>
  constexpr move_iterator<Iterator>
    operator+(iter_difference_t<Iterator> n, const move_iterator<Iterator>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\constraints
\tcode{x.base() + n} is well-formed and has type \tcode{Iterator}.

\pnum
\returns
\tcode{x + n}.
\end{itemdescr}

\indexlibrarymember{iter_move}{move_iterator}%
\begin{itemdecl}
friend constexpr iter_rvalue_reference_t<Iterator>
  iter_move(const move_iterator& i)
    noexcept(noexcept(ranges::iter_move(i.current)));
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return ranges::iter_move(i.current);}
\end{itemdescr}

\indexlibrarymember{iter_swap}{move_iterator}%
\begin{itemdecl}
template<@\libconcept{indirectly_swappable}@<Iterator> Iterator2>
  friend constexpr void
    iter_swap(const move_iterator& x, const move_iterator<Iterator2>& y)
      noexcept(noexcept(ranges::iter_swap(x.current, y.current)));
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{ranges::iter_swap(x.current, y.current)}.
\end{itemdescr}

\indexlibraryglobal{make_move_iterator}%
\begin{itemdecl}
template<class Iterator>
  constexpr move_iterator<Iterator> make_move_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{move_iterator<Iterator>(std::move(i))}.
\end{itemdescr}

\rSec3[move.sentinel]{Class template \tcode{move_sentinel}}

\pnum
Class template \tcode{move_sentinel} is a sentinel adaptor useful for denoting
ranges together with \tcode{move_iterator}. When an input iterator type
\tcode{I} and sentinel type \tcode{S} model \tcode{\libconcept{sentinel_for}<S, I>},
\tcode{move_sentinel<S>} and \tcode{move_iterator<I>} model
\tcode{\libconcept{sentinel_for}<move_sentinel<S>, move_iterator<I>>} as well.

\pnum
\begin{example}
A \tcode{move_if} algorithm is easily implemented with
\tcode{copy_if} using \tcode{move_iterator} and \tcode{move_sentinel}:
\begin{codeblock}
template<@\libconcept{input_iterator}@ I, @\libconcept{sentinel_for}@<I> S, @\libconcept{weakly_incrementable}@ O,
         @\libconcept{indirect_unary_predicate}@<I> Pred>
  requires @\libconcept{indirectly_movable}@<I, O>
void move_if(I first, S last, O out, Pred pred) {
  ranges::copy_if(move_iterator<I>{std::move(first)}, move_sentinel<S>{last},
                  std::move(out), pred);
}
\end{codeblock}
\end{example}

\indexlibraryglobal{move_sentinel}%
\begin{codeblock}
namespace std {
  template<@\libconcept{semiregular}@ S>
  class move_sentinel {
  public:
    constexpr move_sentinel();
    constexpr explicit move_sentinel(S s);
    template<class S2>
      requires @\libconcept{convertible_to}@<const S2&, S>
        constexpr move_sentinel(const move_sentinel<S2>& s);
    template<class S2>
      requires @\libconcept{assignable_from}@<S&, const S2&>
        constexpr move_sentinel& operator=(const move_sentinel<S2>& s);

    constexpr S base() const;

  private:
    S last;     // \expos
  };
}
\end{codeblock}

\rSec3[move.sent.ops]{Operations}

\indexlibraryctor{move_sentinel}%
\begin{itemdecl}
constexpr move_sentinel();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Value-initializes \tcode{last}.
If \tcode{is_trivially_default_constructible_v<S>} is \tcode{true},
then this constructor is a \keyword{constexpr} constructor.
\end{itemdescr}

\indexlibraryctor{move_sentinel}%
\begin{itemdecl}
constexpr explicit move_sentinel(S s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{last} with \tcode{std::move(s)}.
\end{itemdescr}

\indexlibraryctor{move_sentinel}%
\begin{itemdecl}
template<class S2>
  requires @\libconcept{convertible_to}@<const S2&, S>
    constexpr move_sentinel(const move_sentinel<S2>& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{last} with \tcode{s.last}.
\end{itemdescr}

\indexlibrarymember{operator=}{move_sentinel}%
\indexlibrarymember{move_sentinel}{operator=}%
\begin{itemdecl}
template<class S2>
  requires @\libconcept{assignable_from}@<S&, const S2&>
    constexpr move_sentinel& operator=(const move_sentinel<S2>& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{last = s.last; return *this;}
\end{itemdescr}

\indexlibrarymember{base}{move_sentinel}%
\begin{itemdecl}
constexpr S base() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{last}.
\end{itemdescr}

\rSec2[iterators.common]{Common iterators}

\rSec3[common.iterator]{Class template \tcode{common_iterator}}

\pnum
Class template \tcode{common_iterator} is an iterator/sentinel adaptor that is
capable of representing a non-common range of elements (where the types of the
iterator and sentinel differ) as a common range (where they are the same). It
does this by holding either an iterator or a sentinel, and implementing the
equality comparison operators appropriately.

\pnum
\begin{note}
The \tcode{common_iterator} type is useful for interfacing with legacy
code that expects the begin and end of a range to have the same type.
\end{note}

\pnum
\begin{example}
\begin{codeblock}
template<class ForwardIterator>
void fun(ForwardIterator begin, ForwardIterator end);

list<int> s;
// populate the list \tcode{s}
using CI = common_iterator<counted_iterator<list<int>::iterator>, default_sentinel_t>;
// call \tcode{fun} on a range of 10 ints
fun(CI(counted_iterator(s.begin(), 10)), CI(default_sentinel));
\end{codeblock}
\end{example}

\indexlibraryglobal{common_iterator}%
\begin{codeblock}
namespace std {
  template<@\libconcept{input_or_output_iterator}@ I, @\libconcept{sentinel_for}@<I> S>
    requires (!@\libconcept{same_as}@<I, S> && @\libconcept{copyable}@<I>)
  class common_iterator {
  public:
    constexpr common_iterator() requires @\libconcept{default_initializable}@<I> = default;
    constexpr common_iterator(I i);
    constexpr common_iterator(S s);
    template<class I2, class S2>
      requires @\libconcept{convertible_to}@<const I2&, I> && @\libconcept{convertible_to}@<const S2&, S>
        constexpr common_iterator(const common_iterator<I2, S2>& x);

    template<class I2, class S2>
      requires @\libconcept{convertible_to}@<const I2&, I> && @\libconcept{convertible_to}@<const S2&, S> &&
               @\libconcept{assignable_from}@<I&, const I2&> && @\libconcept{assignable_from}@<S&, const S2&>
        constexpr common_iterator& operator=(const common_iterator<I2, S2>& x);

    constexpr decltype(auto) operator*();
    constexpr decltype(auto) operator*() const
      requires @\exposconcept{dereferenceable}@<const I>;
    constexpr auto operator->() const
      requires @\seebelow@;

    constexpr common_iterator& operator++();
    constexpr decltype(auto) operator++(int);

    template<class I2, @\libconcept{sentinel_for}@<I> S2>
      requires @\libconcept{sentinel_for}@<S, I2>
    friend constexpr bool operator==(
      const common_iterator& x, const common_iterator<I2, S2>& y);
    template<class I2, @\libconcept{sentinel_for}@<I> S2>
      requires @\libconcept{sentinel_for}@<S, I2> && @\libconcept{equality_comparable_with}@<I, I2>
    friend constexpr bool operator==(
      const common_iterator& x, const common_iterator<I2, S2>& y);

    template<@\libconcept{sized_sentinel_for}@<I> I2, @\libconcept{sized_sentinel_for}@<I> S2>
      requires @\libconcept{sized_sentinel_for}@<S, I2>
    friend constexpr iter_difference_t<I2> operator-(
      const common_iterator& x, const common_iterator<I2, S2>& y);

    friend constexpr decltype(auto) iter_move(const common_iterator& i)
      noexcept(noexcept(ranges::iter_move(declval<const I&>())))
        requires @\libconcept{input_iterator}@<I>;
    template<@\libconcept{indirectly_swappable}@<I> I2, class S2>
      friend constexpr void iter_swap(const common_iterator& x, const common_iterator<I2, S2>& y)
        noexcept(noexcept(ranges::iter_swap(declval<const I&>(), declval<const I2&>())));

  private:
    variant<I, S> v_;   // \expos
  };

  template<class I, class S>
  struct incrementable_traits<common_iterator<I, S>> {
    using difference_type = iter_difference_t<I>;
  };

  template<@\libconcept{input_iterator}@ I, class S>
  struct iterator_traits<common_iterator<I, S>> {
    using iterator_concept = @\seebelow@;
    using iterator_category = @\seebelow@;  // not always present
    using value_type = iter_value_t<I>;
    using difference_type = iter_difference_t<I>;
    using pointer = @\seebelow@;
    using reference = iter_reference_t<I>;
  };
}
\end{codeblock}

\rSec3[common.iter.types]{Associated types}

\pnum
The nested \grammarterm{typedef-name} \tcode{iterator_category} of
the specialization of \tcode{iterator_traits} for \tcode{common_iterator<I, S>}
is declared if and only if \tcode{iter_difference_t<I>} is an integral type.
In that case,
\tcode{iterator_category} denotes \tcode{forward_iterator_tag} if
the \grammarterm{qualified-id} \tcode{iterator_traits<I>::iterator_category}
is valid and denotes a type that
models \tcode{\libconcept{derived_from}<forward_iterator_tag>};
otherwise it denotes \tcode{input_iterator_tag}.

\pnum
The remaining nested \grammarterm{typedef-name}s of the specialization of
\tcode{iterator_traits} for \tcode{common_iterator<I, S>} are defined as follows:
\begin{itemize}
\item
\tcode{iterator_concept} denotes \tcode{forward_iterator_tag}
if \tcode{I} models \libconcept{forward_iterator};
otherwise it denotes \tcode{input_iterator_tag}.

\item
Let \tcode{a} denote an lvalue of type \tcode{const common_iterator<I, S>}.
If the expression \tcode{a.operator->()} is well-formed,
then \tcode{pointer} denotes \tcode{decltype(a.operator->())}.
Otherwise, \tcode{pointer} denotes \keyword{void}.
\end{itemize}

\rSec3[common.iter.const]{Constructors and conversions}

\indexlibraryctor{common_iterator}%
\begin{itemdecl}
constexpr common_iterator(I i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{v_} as if by \tcode{v_\{in_place_type<I>, std::move(i)\}}.
\end{itemdescr}

\indexlibraryctor{common_iterator}%
\begin{itemdecl}
constexpr common_iterator(S s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{v_} as if by
\tcode{v_\{in_place_type<S>, std::move(s)\}}.
\end{itemdescr}

\indexlibraryctor{common_iterator}%
\begin{itemdecl}
template<class I2, class S2>
  requires @\libconcept{convertible_to}@<const I2&, I> && @\libconcept{convertible_to}@<const S2&, S>
    constexpr common_iterator(const common_iterator<I2, S2>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{x.v_.valueless_by_exception()} is \tcode{false}.

\pnum
\effects
Initializes \tcode{v_} as if by
\tcode{v_\{in_place_index<$i$>, get<$i$>(x.v_)\}},
where $i$ is \tcode{x.v_.index()}.
\end{itemdescr}

\indexlibrarymember{operator=}{common_iterator}%
\begin{itemdecl}
template<class I2, class S2>
  requires @\libconcept{convertible_to}@<const I2&, I> && @\libconcept{convertible_to}@<const S2&, S> &&
           @\libconcept{assignable_from}@<I&, const I2&> && @\libconcept{assignable_from}@<S&, const S2&>
    constexpr common_iterator& operator=(const common_iterator<I2, S2>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{x.v_.valueless_by_exception()} is \tcode{false}.

\pnum
\effects
Equivalent to:
\begin{itemize}
\item If \tcode{v_.index() == x.v_.index()}, then
\tcode{get<$i$>(v_) = get<$i$>(x.v_)}.

\item Otherwise, \tcode{v_.emplace<$i$>(get<$i$>(x.v_))}.
\end{itemize}
where $i$ is \tcode{x.v_.index()}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[common.iter.access]{Accessors}

\indexlibrarymember{operator*}{common_iterator}%
\begin{itemdecl}
constexpr decltype(auto) operator*();
constexpr decltype(auto) operator*() const
  requires @\exposconcept{dereferenceable}@<const I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{holds_alternative<I>(v_)} is \tcode{true}.

\pnum
\effects
Equivalent to: \tcode{return *get<I>(v_);}
\end{itemdescr}

\indexlibrarymember{operator->}{common_iterator}%
\begin{itemdecl}
constexpr auto operator->() const
  requires @\seebelow@;
\end{itemdecl}

\begin{itemdescr}
\pnum
The expression in the \grammarterm{requires-clause} is equivalent to:
\begin{codeblock}
@\libconcept{indirectly_readable}@<const I> &&
(requires(const I& i) { i.operator->(); } ||
 is_reference_v<iter_reference_t<I>> ||
 @\libconcept{constructible_from}@<iter_value_t<I>, iter_reference_t<I>>)
\end{codeblock}

\pnum
\hardexpects
\tcode{holds_alternative<I>(v_)} is \tcode{true}.

\pnum
\effects
\begin{itemize}
\item
If \tcode{I} is a pointer type or if the expression
\tcode{get<I>(v_).operator->()} is
well-formed, equivalent to: \tcode{return get<I>(v_);}

\item
Otherwise, if \tcode{iter_reference_t<I>} is a reference type, equivalent to:
\begin{codeblock}
auto&& tmp = *get<I>(v_);
return addressof(tmp);
\end{codeblock}

\item
Otherwise, equivalent to:
\tcode{return \exposid{proxy}(*get<I>(v_));} where
\exposid{proxy} is the exposition-only class:
\begin{codeblock}
class @\exposid{proxy}@ {
  iter_value_t<I> keep_;
  constexpr @\exposid{proxy}@(iter_reference_t<I>&& x)
    : keep_(std::move(x)) {}
public:
  constexpr const iter_value_t<I>* operator->() const noexcept {
    return addressof(keep_);
  }
};
\end{codeblock}
\end{itemize}
\end{itemdescr}

\rSec3[common.iter.nav]{Navigation}

\indexlibrarymember{operator++}{common_iterator}%
\begin{itemdecl}
constexpr common_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{holds_alternative<I>(v_)} is \tcode{true}.

\pnum
\effects
Equivalent to \tcode{++get<I>(v_)}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{common_iterator}%
\begin{itemdecl}
constexpr decltype(auto) operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{holds_alternative<I>(v_)} is \tcode{true}.

\pnum
\effects
If \tcode{I} models \libconcept{forward_iterator}, equivalent to:
\begin{codeblock}
common_iterator tmp = *this;
++*this;
return tmp;
\end{codeblock}
Otherwise, if
\tcode{requires(I\& i) \{ \{ *i++ \} -> \exposconceptnc{can-reference}; \}}
is \tcode{true} or
\begin{codeblock}
@\libconcept{indirectly_readable}@<I> && @\libconcept{constructible_from}@<iter_value_t<I>, iter_reference_t<I>> &&
@\libconcept{move_constructible}@<iter_value_t<I>>
\end{codeblock}
is \tcode{false},
equivalent to:
\begin{codeblock}
return get<I>(v_)++;
\end{codeblock}
Otherwise, equivalent to:
\begin{codeblock}
@\exposid{postfix-proxy}@ p(**this);
++*this;
return p;
\end{codeblock}
where \exposid{postfix-proxy} is the exposition-only class:
\begin{codeblock}
class @\exposid{postfix-proxy}@ {
  iter_value_t<I> keep_;
  constexpr @\exposid{postfix-proxy}@(iter_reference_t<I>&& x)
    : keep_(std::forward<iter_reference_t<I>>(x)) {}
public:
  constexpr const iter_value_t<I>& operator*() const noexcept {
    return keep_;
  }
};
\end{codeblock}
\end{itemdescr}

\rSec3[common.iter.cmp]{Comparisons}

\indexlibrarymember{operator==}{common_iterator}%
\begin{itemdecl}
template<class I2, @\libconcept{sentinel_for}@<I> S2>
  requires @\libconcept{sentinel_for}@<S, I2>
friend constexpr bool operator==(
  const common_iterator& x, const common_iterator<I2, S2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{x.v_.valueless_by_exception()} and \tcode{y.v_.valueless_by_exception()}
are each \tcode{false}.

\pnum
\returns
\tcode{true} if \tcode{$i$ == $j$},
and otherwise \tcode{get<$i$>(x.v_) == get<$j$>(y.v_)},
where $i$ is \tcode{x.v_.index()} and $j$ is \tcode{y.v_.index()}.
\end{itemdescr}

\indexlibrarymember{operator==}{common_iterator}%
\begin{itemdecl}
template<class I2, @\libconcept{sentinel_for}@<I> S2>
  requires @\libconcept{sentinel_for}@<S, I2> && @\libconcept{equality_comparable_with}@<I, I2>
friend constexpr bool operator==(
  const common_iterator& x, const common_iterator<I2, S2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{x.v_.valueless_by_exception()} and \tcode{y.v_.valueless_by_exception()}
are each \tcode{false}.

\pnum
\returns
\tcode{true} if $i$ and $j$ are each \tcode{1}, and otherwise
\tcode{get<$i$>(x.v_) == get<$j$>(y.v_)}, where
$i$ is \tcode{x.v_.index()} and $j$ is \tcode{y.v_.index()}.
\end{itemdescr}

\indexlibrarymember{operator-}{common_iterator}%
\begin{itemdecl}
template<@\libconcept{sized_sentinel_for}@<I> I2, @\libconcept{sized_sentinel_for}@<I> S2>
  requires @\libconcept{sized_sentinel_for}@<S, I2>
friend constexpr iter_difference_t<I2> operator-(
  const common_iterator& x, const common_iterator<I2, S2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{x.v_.valueless_by_exception()} and \tcode{y.v_.valueless_by_exception()}
are each \tcode{false}.

\pnum
\returns
\tcode{0} if $i$ and $j$ are each \tcode{1}, and otherwise
\tcode{get<$i$>(x.v_) - get<$j$>(y.v_)}, where
$i$ is \tcode{x.v_.index()} and $j$ is \tcode{y.v_.index()}.
\end{itemdescr}

\rSec3[common.iter.cust]{Customizations}

\indexlibrarymember{iter_move}{common_iterator}%
\begin{itemdecl}
friend constexpr decltype(auto) iter_move(const common_iterator& i)
  noexcept(noexcept(ranges::iter_move(declval<const I&>())))
    requires @\libconcept{input_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{holds_alternative<I>(i.v_)} is \tcode{true}.

\pnum
\effects
Equivalent to: \tcode{return ranges::iter_move(get<I>(i.v_));}
\end{itemdescr}

\indexlibrarymember{iter_swap}{common_iterator}%
\begin{itemdecl}
template<@\libconcept{indirectly_swappable}@<I> I2, class S2>
  friend constexpr void iter_swap(const common_iterator& x, const common_iterator<I2, S2>& y)
    noexcept(noexcept(ranges::iter_swap(declval<const I&>(), declval<const I2&>())));
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{holds_alternative<I>(x.v_)} and \tcode{holds_alternative<I2>(y.v_)}
are each \tcode{true}.

\pnum
\effects
Equivalent to \tcode{ranges::iter_swap(get<I>(x.v_), get<I2>(y.v_))}.
\end{itemdescr}

\rSec2[default.sentinel]{Default sentinel}

\indexlibraryglobal{default_sentinel_t}%
\begin{itemdecl}
namespace std {
  struct default_sentinel_t { };
}
\end{itemdecl}

\pnum
Class \tcode{default_sentinel_t} is an empty type used to denote the end of a
range. It can be used together with iterator types that know the bound
of their range (e.g., \tcode{counted_iterator}\iref{counted.iterator}).

\rSec2[iterators.counted]{Counted iterators}

\rSec3[counted.iterator]{Class template \tcode{counted_iterator}}

\pnum
Class template \tcode{counted_iterator} is an iterator adaptor
with the same behavior as the underlying iterator except that
it keeps track of the distance to the end of its range.
It can be used together with \tcode{default_sentinel}
in calls to generic algorithms to operate on
a range of $N$ elements starting at a given position
without needing to know the end position a priori.

\pnum
\begin{example}
\begin{codeblock}
list<string> s;
// populate the list \tcode{s} with at least 10 strings
vector<string> v;
// copies 10 strings into \tcode{v}:
ranges::copy(counted_iterator(s.begin(), 10), default_sentinel, back_inserter(v));
\end{codeblock}
\end{example}

\pnum
Two values \tcode{i1} and \tcode{i2} of types
\tcode{counted_iterator<I1>}
and
\tcode{counted_iterator<I2>}
refer to elements of the same sequence if and only if
there exists some integer $n$ such that
\tcode{next(i1.base(), i1.count() + $n$)}
and
\tcode{next(i2.base(), i2.count() + $n$)}
refer to the same (possibly past-the-end) element.

\indexlibraryglobal{counted_iterator}%
\begin{codeblock}
namespace std {
  template<@\libconcept{input_or_output_iterator}@ I>
  class counted_iterator {
  public:
    using iterator_type = I;
    using value_type = iter_value_t<I>;                         // present only
                        // if \tcode{I} models \libconcept{indirectly_readable}
    using difference_type = iter_difference_t<I>;
    using iterator_concept = I::iterator_concept;               // present only
                        // if the \grammarterm{qualified-id} \tcode{I::iterator_concept} is valid and denotes a type
    using iterator_category = I::iterator_category;             // present only
                        // if the \grammarterm{qualified-id} \tcode{I::iterator_category} is valid and denotes a type
    constexpr counted_iterator() requires @\libconcept{default_initializable}@<I> = default;
    constexpr counted_iterator(I x, iter_difference_t<I> n);
    template<class I2>
      requires @\libconcept{convertible_to}@<const I2&, I>
        constexpr counted_iterator(const counted_iterator<I2>& x);

    template<class I2>
      requires @\libconcept{assignable_from}@<I&, const I2&>
        constexpr counted_iterator& operator=(const counted_iterator<I2>& x);

    constexpr const I& base() const & noexcept;
    constexpr I base() &&;
    constexpr iter_difference_t<I> count() const noexcept;
    constexpr decltype(auto) operator*();
    constexpr decltype(auto) operator*() const
      requires @\exposconcept{dereferenceable}@<const I>;

    constexpr auto operator->() const noexcept
      requires @\libconcept{contiguous_iterator}@<I>;

    constexpr counted_iterator& operator++();
    constexpr decltype(auto) operator++(int);
    constexpr counted_iterator operator++(int)
      requires @\libconcept{forward_iterator}@<I>;
    constexpr counted_iterator& operator--()
      requires @\libconcept{bidirectional_iterator}@<I>;
    constexpr counted_iterator operator--(int)
      requires @\libconcept{bidirectional_iterator}@<I>;

    constexpr counted_iterator operator+(iter_difference_t<I> n) const
      requires @\libconcept{random_access_iterator}@<I>;
    friend constexpr counted_iterator operator+(
      iter_difference_t<I> n, const counted_iterator& x)
        requires @\libconcept{random_access_iterator}@<I>;
    constexpr counted_iterator& operator+=(iter_difference_t<I> n)
      requires @\libconcept{random_access_iterator}@<I>;

    constexpr counted_iterator operator-(iter_difference_t<I> n) const
      requires @\libconcept{random_access_iterator}@<I>;
    template<@\libconcept{common_with}@<I> I2>
      friend constexpr iter_difference_t<I2> operator-(
        const counted_iterator& x, const counted_iterator<I2>& y);
    friend constexpr iter_difference_t<I> operator-(
      const counted_iterator& x, default_sentinel_t) noexcept;
    friend constexpr iter_difference_t<I> operator-(
      default_sentinel_t, const counted_iterator& y) noexcept;
    constexpr counted_iterator& operator-=(iter_difference_t<I> n)
      requires @\libconcept{random_access_iterator}@<I>;

    constexpr decltype(auto) operator[](iter_difference_t<I> n) const
      requires @\libconcept{random_access_iterator}@<I>;

    template<@\libconcept{common_with}@<I> I2>
      friend constexpr bool operator==(
        const counted_iterator& x, const counted_iterator<I2>& y);
    friend constexpr bool operator==(
      const counted_iterator& x, default_sentinel_t) noexcept;

    template<@\libconcept{common_with}@<I> I2>
      friend constexpr strong_ordering operator<=>(
        const counted_iterator& x, const counted_iterator<I2>& y);

    friend constexpr decltype(auto) iter_move(const counted_iterator& i)
      noexcept(noexcept(ranges::iter_move(i.current)))
        requires @\libconcept{input_iterator}@<I>;
    template<@\libconcept{indirectly_swappable}@<I> I2>
      friend constexpr void iter_swap(const counted_iterator& x, const counted_iterator<I2>& y)
        noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

  private:
    I current = I();                    // \expos
    iter_difference_t<I> length = 0;    // \expos
  };

  template<@\libconcept{input_iterator}@ I>
    requires @\libconcept{same_as}@<@\exposid{ITER_TRAITS}@(I), iterator_traits<I>>   // see \ref{iterator.concepts.general}
  struct iterator_traits<counted_iterator<I>> : iterator_traits<I> {
    using pointer = conditional_t<@\libconcept{contiguous_iterator}@<I>,
                                  add_pointer_t<iter_reference_t<I>>, void>;
  };
}
\end{codeblock}

\rSec3[counted.iter.const]{Constructors and conversions}

\indexlibraryctor{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator(I i, iter_difference_t<I> n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{n >= 0} is \tcode{true}.

\pnum
\effects
Initializes \tcode{current} with \tcode{std::move(i)} and
\tcode{length} with \tcode{n}.
\end{itemdescr}

\indexlibraryctor{counted_iterator}%
\begin{itemdecl}
template<class I2>
  requires @\libconcept{convertible_to}@<const I2&, I>
    constexpr counted_iterator(const counted_iterator<I2>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{current} with \tcode{x.current} and
\tcode{length} with \tcode{x.length}.
\end{itemdescr}

\indexlibrarymember{operator=}{counted_iterator}%
\begin{itemdecl}
template<class I2>
  requires @\libconcept{assignable_from}@<I&, const I2&>
    constexpr counted_iterator& operator=(const counted_iterator<I2>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Assigns \tcode{x.current} to \tcode{current} and
\tcode{x.length} to \tcode{length}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec3[counted.iter.access]{Accessors}

\indexlibrarymember{base}{counted_iterator}%
\begin{itemdecl}
constexpr const I& base() const & noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return current;}
\end{itemdescr}

\indexlibrarymember{base}{counted_iterator}%
\begin{itemdecl}
constexpr I base() &&;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{std::move(current)}.
\end{itemdescr}

\indexlibrarymember{count}{counted_iterator}%
\begin{itemdecl}
constexpr iter_difference_t<I> count() const noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return length;}
\end{itemdescr}

\rSec3[counted.iter.elem]{Element access}

\indexlibrarymember{operator*}{counted_iterator}%
\begin{itemdecl}
constexpr decltype(auto) operator*();
constexpr decltype(auto) operator*() const
  requires @\exposconcept{dereferenceable}@<const I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{length > 0} is \tcode{true}.

\pnum
\effects
Equivalent to: \tcode{return *current;}
\end{itemdescr}

\indexlibrarymember{operator->}{counted_iterator}%
\begin{itemdecl}
constexpr auto operator->() const noexcept
  requires @\libconcept{contiguous_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return to_address(current);}
\end{itemdescr}

\indexlibrarymember{operator[]}{counted_iterator}%
\begin{itemdecl}
constexpr decltype(auto) operator[](iter_difference_t<I> n) const
  requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{n < length} is \tcode{true}.

\pnum
\effects
Equivalent to: \tcode{return current[n];}
\end{itemdescr}

\rSec3[counted.iter.nav]{Navigation}

\indexlibrarymember{operator++}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{length > 0} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
++current;
--length;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator++}{counted_iterator}%
\begin{itemdecl}
constexpr decltype(auto) operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{length > 0} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
--length;
try { return current++; }
catch(...) { ++length; throw; }
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator++}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator operator++(int)
  requires @\libconcept{forward_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
counted_iterator tmp = *this;
++*this;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator--}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator& operator--()
  requires @\libconcept{bidirectional_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
--current;
++length;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator--}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator operator--(int)
  requires @\libconcept{bidirectional_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
counted_iterator tmp = *this;
--*this;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator+}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator operator+(iter_difference_t<I> n) const
  requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return counted_iterator(current + n, length - n);}
\end{itemdescr}

\indexlibrarymember{operator+}{counted_iterator}%
\begin{itemdecl}
friend constexpr counted_iterator operator+(
  iter_difference_t<I> n, const counted_iterator& x)
    requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return x + n;}
\end{itemdescr}

\indexlibrarymember{operator+=}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator& operator+=(iter_difference_t<I> n)
  requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{n <= length} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
current += n;
length -= n;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator-}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator operator-(iter_difference_t<I> n) const
  requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return counted_iterator(current - n, length + n);}
\end{itemdescr}

\indexlibrarymember{operator-}{counted_iterator}%
\begin{itemdecl}
template<@\libconcept{common_with}@<I> I2>
  friend constexpr iter_difference_t<I2> operator-(
    const counted_iterator& x, const counted_iterator<I2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{x} and \tcode{y} refer to elements of the same
sequence\iref{counted.iterator}.

\pnum
\effects
Equivalent to: \tcode{return y.length - x.length;}
\end{itemdescr}

\indexlibrarymember{operator-}{counted_iterator}%
\begin{itemdecl}
friend constexpr iter_difference_t<I> operator-(
  const counted_iterator& x, default_sentinel_t) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to:
\tcode{return -x.length;}
\end{itemdescr}

\indexlibrarymember{operator-}{counted_iterator}%
\begin{itemdecl}
friend constexpr iter_difference_t<I> operator-(
  default_sentinel_t, const counted_iterator& y) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return y.length;}
\end{itemdescr}

\indexlibrarymember{operator-=}{counted_iterator}%
\begin{itemdecl}
constexpr counted_iterator& operator-=(iter_difference_t<I> n)
  requires @\libconcept{random_access_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{-n <= length} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
current -= n;
length += n;
return *this;
\end{codeblock}
\end{itemdescr}

\rSec3[counted.iter.cmp]{Comparisons}

\indexlibrarymember{operator==}{counted_iterator}%
\begin{itemdecl}
template<@\libconcept{common_with}@<I> I2>
  friend constexpr bool operator==(
    const counted_iterator& x, const counted_iterator<I2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{x} and \tcode{y} refer to
elements of the same sequence\iref{counted.iterator}.

\pnum
\effects
Equivalent to: \tcode{return x.length == y.length;}
\end{itemdescr}

\indexlibrarymember{operator==}{counted_iterator}%
\begin{itemdecl}
friend constexpr bool operator==(
  const counted_iterator& x, default_sentinel_t) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Equivalent to: \tcode{return x.length == 0;}
\end{itemdescr}

\indexlibrarymember{operator<=>}{counted_iterator}%
\begin{itemdecl}
template<@\libconcept{common_with}@<I> I2>
  friend constexpr strong_ordering operator<=>(
    const counted_iterator& x, const counted_iterator<I2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{x} and \tcode{y} refer to
elements of the same sequence\iref{counted.iterator}.

\pnum
\effects
Equivalent to: \tcode{return y.length <=> x.length;}

\pnum
\begin{note}
The argument order in the \effects element is reversed
because \tcode{length} counts down, not up.
\end{note}
\end{itemdescr}

\rSec3[counted.iter.cust]{Customizations}

\indexlibrarymember{iter_move}{counted_iterator}%
\begin{itemdecl}
friend constexpr decltype(auto)
  iter_move(const counted_iterator& i)
    noexcept(noexcept(ranges::iter_move(i.current)))
    requires @\libconcept{input_iterator}@<I>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
\tcode{i.length > 0} is \tcode{true}.

\pnum
\effects
Equivalent to: \tcode{return ranges::iter_move(i.current);}
\end{itemdescr}

\indexlibrarymember{iter_swap}{counted_iterator}%
\begin{itemdecl}
template<@\libconcept{indirectly_swappable}@<I> I2>
  friend constexpr void
    iter_swap(const counted_iterator& x, const counted_iterator<I2>& y)
      noexcept(noexcept(ranges::iter_swap(x.current, y.current)));
\end{itemdecl}

\begin{itemdescr}
\pnum
\hardexpects
Both \tcode{x.length > 0} and \tcode{y.length > 0} are \tcode{true}.

\pnum
\effects
Equivalent to \tcode{ranges::iter_swap(x.current, y.current)}.
\end{itemdescr}

\rSec2[unreachable.sentinel]{Unreachable sentinel}

\indexlibraryglobal{unreachable_sentinel_t}%
\pnum
Class \tcode{unreachable_sentinel_t} can be used with
any \libconcept{weakly_incrementable} type
to denote the ``upper bound'' of an unbounded interval.

\pnum
\begin{example}
\begin{codeblock}
char* p;
// set \tcode{p} to point to a character buffer containing newlines
char* nl = find(p, unreachable_sentinel, '\n');
\end{codeblock}

Provided a newline character really exists in the buffer, the use of
\tcode{unreachable_sentinel} above potentially makes the call to \tcode{find} more
efficient since the loop test against the sentinel does not require a
conditional branch.
\end{example}

\indexlibrarymember{operator==}{unreachable_sentinel_t}%
\begin{codeblock}
namespace std {
  struct unreachable_sentinel_t {
    template<@\libconcept{weakly_incrementable}@ I>
      friend constexpr bool operator==(unreachable_sentinel_t, const I&) noexcept
      { return false; }
  };
}
\end{codeblock}

\rSec1[stream.iterators]{Stream iterators}

\rSec2[stream.iterators.general]{General}

\pnum
To make it possible for algorithmic templates to work directly with input/output streams, appropriate
iterator-like
class templates
are provided.

\begin{example}
\begin{codeblock}
partial_sum(istream_iterator<double, char>(cin),
  istream_iterator<double, char>(),
  ostream_iterator<double, char>(cout, "@\textbackslash@n"));
\end{codeblock}

reads a file containing floating-point numbers from
\tcode{cin},
and prints the partial sums onto
\tcode{cout}.
\end{example}

\rSec2[istream.iterator]{Class template \tcode{istream_iterator}}

\rSec3[istream.iterator.general]{General}

\pnum
\indexlibraryglobal{istream_iterator}%
The class template \tcode{istream_iterator}
is an input iterator\iref{input.iterators} that reads successive elements
from the input stream for which it was constructed.

\begin{codeblock}
namespace std {
  template<class T, class charT = char, class traits = char_traits<charT>,
           class Distance = ptrdiff_t>
  class istream_iterator {
  public:
    using iterator_category = input_iterator_tag;
    using value_type        = T;
    using difference_type   = Distance;
    using pointer           = const T*;
    using reference         = const T&;
    using char_type         = charT;
    using traits_type       = traits;
    using istream_type      = basic_istream<charT,traits>;

    constexpr istream_iterator();
    constexpr istream_iterator(default_sentinel_t);
    istream_iterator(istream_type& s);
    constexpr istream_iterator(const istream_iterator& x) noexcept(@\seebelow@);
    ~istream_iterator() = default;
    istream_iterator& operator=(const istream_iterator&) = default;

    const T& operator*() const;
    const T* operator->() const;
    istream_iterator& operator++();
    istream_iterator  operator++(int);

    friend bool operator==(const istream_iterator& i, default_sentinel_t);

  private:
    basic_istream<charT,traits>* in_stream; // \expos
    T value;                                // \expos
  };
}
\end{codeblock}

\pnum
The type \tcode{T} shall meet the \oldconcept{DefaultConstructible},
\oldconcept{CopyConstructible}, and \oldconcept{CopyAssignable} requirements.

\rSec3[istream.iterator.cons]{Constructors and destructor}

\indexlibraryctor{istream_iterator}%
\begin{itemdecl}
constexpr istream_iterator();
constexpr istream_iterator(default_sentinel_t);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs the end-of-stream iterator, value-initializing \tcode{value}.

\pnum
\ensures
\tcode{in_stream == nullptr} is \tcode{true}.

\pnum
\remarks
If the initializer \tcode{T()} in the declaration \tcode{auto x = T();}
is a constant initializer\iref{expr.const.init},
then these constructors are \keyword{constexpr} constructors.
\end{itemdescr}


\indexlibraryctor{istream_iterator}%
\begin{itemdecl}
istream_iterator(istream_type& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{in_stream} with \tcode{addressof(s)},
value-initializes \tcode{value},
and then calls \tcode{operator++()}.
\end{itemdescr}


\indexlibraryctor{istream_iterator}%
\begin{itemdecl}
constexpr istream_iterator(const istream_iterator& x) noexcept(@\seebelow@);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{in_stream} with \tcode{x.in_stream} and
initializes \tcode{value} with \tcode{x.value}.

\pnum
\remarks
An invocation of this constructor may be used in a core constant expression
if and only if the initialization of \tcode{value} from \tcode{x.value}
is a constant subexpression\iref{defns.const.subexpr}.
The exception specification is equivalent to
\tcode{is_nothrow_copy_constructible_v<T>}.
\end{itemdescr}

\indexlibrarydtor{istream_iterator}%
\begin{itemdecl}
~istream_iterator() = default;
\end{itemdecl}

\begin{itemdescr}
\pnum
\remarks
If \tcode{is_trivially_destructible_v<T>} is \tcode{true},
then this destructor is trivial.
\end{itemdescr}

\rSec3[istream.iterator.ops]{Operations}

\indexlibrarymember{operator*}{istream_iterator}%
\begin{itemdecl}
const T& operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{in_stream != nullptr} is \tcode{true}.

\pnum
\returns
\tcode{value}.
\end{itemdescr}

\indexlibrarymember{operator->}{istream_iterator}%
\begin{itemdecl}
const T* operator->() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{in_stream != nullptr} is \tcode{true}.

\pnum
\returns
\tcode{addressof(value)}.
\end{itemdescr}

\indexlibrarymember{operator++}{istream_iterator}%
\begin{itemdecl}
istream_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{in_stream != nullptr} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
if (!(*in_stream >> value))
  in_stream = nullptr;
\end{codeblock}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{istream_iterator}%
\begin{itemdecl}
istream_iterator operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{in_stream != nullptr} is \tcode{true}.

\pnum
\effects
Equivalent to:
\begin{codeblock}
istream_iterator tmp = *this;
++*this;
return tmp;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator==}{istream_iterator}%
\begin{itemdecl}
template<class T, class charT, class traits, class Distance>
  bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
                  const istream_iterator<T,charT,traits,Distance>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.in_stream == y.in_stream}.
\end{itemdescr}

\indexlibrarymember{operator==}{istream_iterator}%
\begin{itemdecl}
friend bool operator==(const istream_iterator& i, default_sentinel_t);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{!i.in_stream}.
\end{itemdescr}

\rSec2[ostream.iterator]{Class template \tcode{ostream_iterator}}

\rSec3[ostream.iterator.general]{General}

\pnum
\indexlibraryglobal{ostream_iterator}%
\tcode{ostream_iterator}
writes (using
\tcode{operator<<})
successive elements onto the output stream from which it was constructed.
If it was constructed with
\tcode{charT*}
as a constructor argument, this string, called a
\term{delimiter string},
is written to the stream after every
\tcode{T}
is written.

\begin{codeblock}
namespace std {
  template<class T, class charT = char, class traits = char_traits<charT>>
  class ostream_iterator {
  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using char_type         = charT;
    using traits_type       = traits;
    using ostream_type      = basic_ostream<charT,traits>;

    ostream_iterator(ostream_type& s);
    ostream_iterator(ostream_type& s, const charT* delimiter);
    ostream_iterator(const ostream_iterator& x);
    ~ostream_iterator();
    ostream_iterator& operator=(const ostream_iterator&) = default;
    ostream_iterator& operator=(const T& value);

    ostream_iterator& operator*();
    ostream_iterator& operator++();
    ostream_iterator& operator++(int);

  private:
    basic_ostream<charT,traits>* out_stream;            // \expos
    const charT* delim;                                 // \expos
  };
}
\end{codeblock}

\rSec3[ostream.iterator.cons.des]{Constructors and destructor}

\indexlibraryctor{ostream_iterator}%
\begin{itemdecl}
ostream_iterator(ostream_type& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{out_stream} with \tcode{addressof(s)} and
\tcode{delim} with \keyword{nullptr}.
\end{itemdescr}


\indexlibraryctor{ostream_iterator}%
\begin{itemdecl}
ostream_iterator(ostream_type& s, const charT* delimiter);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{out_stream} with \tcode{addressof(s)} and
\tcode{delim} with \tcode{delimiter}.
\end{itemdescr}

\rSec3[ostream.iterator.ops]{Operations}

\indexlibrarymember{operator=}{ostream_iterator}%
\begin{itemdecl}
ostream_iterator& operator=(const T& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by:
\begin{codeblock}
*out_stream << value;
if (delim)
  *out_stream << delim;
return *this;
\end{codeblock}
\end{itemdescr}

\indexlibrarymember{operator*}{ostream_iterator}%
\begin{itemdecl}
ostream_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{ostream_iterator}%
\begin{itemdecl}
ostream_iterator& operator++();
ostream_iterator& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec2[istreambuf.iterator]{Class template \tcode{istreambuf_iterator}}

\rSec3[istreambuf.iterator.general]{General}

\pnum
The
class template
\tcode{istreambuf_iterator}
defines an input iterator\iref{input.iterators} that
reads successive
\textit{characters}
from the streambuf for which it was constructed.
\tcode{operator*}
provides access to the current input character, if any.
Each time
\tcode{operator++}
is evaluated, the iterator advances to the next input character.
If the end of stream is reached (\tcode{streambuf_type::sgetc()} returns
\tcode{traits::eof()}),
the iterator becomes equal to the
\term{end-of-stream}
iterator value.
The default constructor
\tcode{istreambuf_iterator()}
and the constructor
\tcode{istreambuf_iterator(nullptr)}
both construct an end-of-stream iterator object suitable for use
as an end-of-range.
All specializations of \tcode{istreambuf_iterator} shall have a trivial copy
constructor, a \keyword{constexpr} default constructor, and a trivial destructor.

\pnum
The result of
\tcode{operator*()}
on an end-of-stream iterator is undefined.
\indextext{behavior!undefined}%
For any other iterator value a
\tcode{char_type}
value is returned.
It is impossible to assign a character via an input iterator.

\indexlibraryglobal{istreambuf_iterator}%
\begin{codeblock}
namespace std {
  template<class charT, class traits = char_traits<charT>>
  class istreambuf_iterator {
  public:
    using iterator_category = input_iterator_tag;
    using value_type        = charT;
    using difference_type   = traits::off_type;
    using pointer           = @\unspec@;
    using reference         = charT;
    using char_type         = charT;
    using traits_type       = traits;
    using int_type          = traits::int_type;
    using streambuf_type    = basic_streambuf<charT,traits>;
    using istream_type      = basic_istream<charT,traits>;

    // \ref{istreambuf.iterator.proxy}, class \tcode{istreambuf_iterator::\exposid{proxy}}
    class @\placeholder{proxy}@;                          // \expos

    constexpr istreambuf_iterator() noexcept;
    constexpr istreambuf_iterator(default_sentinel_t) noexcept;
    istreambuf_iterator(const istreambuf_iterator&) noexcept = default;
    ~istreambuf_iterator() = default;
    istreambuf_iterator(istream_type& s) noexcept;
    istreambuf_iterator(streambuf_type* s) noexcept;
    istreambuf_iterator(const @\placeholder{proxy}@& p) noexcept;
    istreambuf_iterator& operator=(const istreambuf_iterator&) noexcept = default;
    charT operator*() const;
    istreambuf_iterator& operator++();
    @\placeholder{proxy}@ operator++(int);
    bool equal(const istreambuf_iterator& b) const;

    friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s);

  private:
    streambuf_type* sbuf_;              // \expos
  };
}
\end{codeblock}

\rSec3[istreambuf.iterator.proxy]{Class \tcode{istreambuf_iterator::\placeholder{proxy}}}

\pnum
Class
\tcode{istreambuf_iterator<charT,traits>::\placeholder{proxy}}
is for exposition only.
An implementation is permitted to provide equivalent functionality without
providing a class with this name.
Class
\tcode{istreambuf_iterator<charT, traits>::\placeholder{proxy}}
provides a temporary
placeholder as the return value of the post-increment operator
(\tcode{operator++}).
It keeps the character pointed to by the previous value
of the iterator for some possible future access to get the character.

\indexlibrarymember{proxy}{istreambuf_iterator}%
\begin{codeblock}
namespace std {
  template<class charT, class traits>
  class istreambuf_iterator<charT, traits>::@\placeholder{proxy}@ { // \expos
    charT keep_;
    basic_streambuf<charT,traits>* sbuf_;
    @\placeholder{proxy}@(charT c, basic_streambuf<charT,traits>* sbuf)
      : keep_(c), sbuf_(sbuf) { }
  public:
    charT operator*() { return keep_; }
  };
}
\end{codeblock}

\rSec3[istreambuf.iterator.cons]{Constructors}

\pnum
For each \tcode{istreambuf_iterator} constructor in this subclause,
an end-of-stream iterator is constructed if and only if
the exposition-only member \tcode{sbuf_} is initialized with a null pointer value.


\indexlibraryctor{istreambuf_iterator}%
\begin{itemdecl}
constexpr istreambuf_iterator() noexcept;
constexpr istreambuf_iterator(default_sentinel_t) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{sbuf_} with \keyword{nullptr}.
\end{itemdescr}


\indexlibraryctor{istreambuf_iterator}%
\begin{itemdecl}
istreambuf_iterator(istream_type& s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s.rdbuf()}.
\end{itemdescr}


\indexlibraryctor{istreambuf_iterator}%
\begin{itemdecl}
istreambuf_iterator(streambuf_type* s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s}.
\end{itemdescr}


\indexlibraryctor{istreambuf_iterator}%
\begin{itemdecl}
istreambuf_iterator(const @\placeholder{proxy}@& p) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{p.sbuf_}.
\end{itemdescr}

\rSec3[istreambuf.iterator.ops]{Operations}

\indexlibrarymember{operator*}{istreambuf_iterator}%
\begin{itemdecl}
charT operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The character obtained via the
\tcode{streambuf}
member
\tcode{sbuf_->sgetc()}.
\end{itemdescr}

\indexlibrarymember{operator++}{istreambuf_iterator}%
\begin{itemdecl}
istreambuf_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
As if by \tcode{sbuf_->sbumpc()}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{istreambuf_iterator}%
\begin{itemdecl}
@\exposid{proxy}@ operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{\exposid{proxy}(sbuf_->sbumpc(), sbuf_)}.
\end{itemdescr}

\indexlibrarymember{equal}{istreambuf_iterator}%
\begin{itemdecl}
bool equal(const istreambuf_iterator& b) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if and only if both iterators are at end-of-stream,
or neither is at end-of-stream, regardless of what
\tcode{streambuf}
object they use.
\end{itemdescr}

\indexlibrarymember{operator==}{istreambuf_iterator}%
\begin{itemdecl}
template<class charT, class traits>
  bool operator==(const istreambuf_iterator<charT,traits>& a,
                  const istreambuf_iterator<charT,traits>& b);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{a.equal(b)}.
\end{itemdescr}

\indexlibrarymember{operator==}{istreambuf_iterator}%
\begin{itemdecl}
friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{i.equal(s)}.
\end{itemdescr}

\rSec2[ostreambuf.iterator]{Class template \tcode{ostreambuf_iterator}}

\rSec3[ostreambuf.iterator.general]{General}

\pnum
The class template \tcode{ostreambuf_iterator}
writes successive \textit{characters} onto the output stream
from which it was constructed.

\indexlibraryglobal{ostreambuf_iterator}%
\begin{codeblock}
namespace std {
  template<class charT, class traits = char_traits<charT>>
  class ostreambuf_iterator {
  public:
    using iterator_category = output_iterator_tag;
    using value_type        = void;
    using difference_type   = ptrdiff_t;
    using pointer           = void;
    using reference         = void;
    using char_type         = charT;
    using traits_type       = traits;
    using streambuf_type    = basic_streambuf<charT,traits>;
    using ostream_type      = basic_ostream<charT,traits>;

    ostreambuf_iterator(ostream_type& s) noexcept;
    ostreambuf_iterator(streambuf_type* s) noexcept;
    ostreambuf_iterator& operator=(charT c);

    ostreambuf_iterator& operator*();
    ostreambuf_iterator& operator++();
    ostreambuf_iterator& operator++(int);
    bool failed() const noexcept;

  private:
    streambuf_type* sbuf_;              // \expos
  };
}
\end{codeblock}

\rSec3[ostreambuf.iter.cons]{Constructors}

\indexlibraryctor{ostreambuf_iterator}%
\begin{itemdecl}
ostreambuf_iterator(ostream_type& s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{s.rdbuf()}
is not a null pointer.

\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s.rdbuf()}.
\end{itemdescr}


\indexlibraryctor{ostreambuf_iterator}%
\begin{itemdecl}
ostreambuf_iterator(streambuf_type* s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\expects
\tcode{s}
is not a null pointer.

\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s}.
\end{itemdescr}

\rSec3[ostreambuf.iter.ops]{Operations}

\indexlibrarymember{operator=}{ostreambuf_iterator}%
\begin{itemdecl}
ostreambuf_iterator& operator=(charT c);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
If
\tcode{failed()}
yields
\tcode{false},
calls
\tcode{sbuf_->sputc(c)};
otherwise has no effect.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator*}{ostreambuf_iterator}%
\begin{itemdecl}
ostreambuf_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{operator++}{ostreambuf_iterator}%
\begin{itemdecl}
ostreambuf_iterator& operator++();
ostreambuf_iterator& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrarymember{failed}{ostreambuf_iterator}%
\begin{itemdecl}
bool failed() const noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if in any prior use of member
\tcode{operator=},
the call to
\tcode{sbuf_->sputc()}
returned
\tcode{traits::eof()};
or
\tcode{false}
otherwise.
\end{itemdescr}

\rSec1[iterator.range]{Range access}

\pnum
In addition to being available via inclusion of the \libheader{iterator} header,
the function templates in \ref{iterator.range} are available when any of the following
headers are included:
\begin{itemize}
\item \libheaderref{array}
\item \libheaderref{deque}
\item \libheaderrefx{flat_map}{flat.map.syn}
\item \libheaderrefx{flat_set}{flat.set.syn}
\item \libheaderrefx{forward_list}{forward.list.syn}
\item \libheaderref{hive}
\item \libheaderrefx{inplace_vector}{inplace.vector.syn}
\item \libheaderref{list}
\item \libheaderrefx{map}{associative.map.syn}
\item \libheaderref{optional}
\item \libheaderrefx{regex}{re.syn}
\item \libheaderrefx{set}{associative.set.syn}
\item \libheaderref{span}
\item \libheaderref{stacktrace}
\item \libheaderref{string}
\item \libheaderrefx{string_view}{string.view.synop}
\item \libheaderrefx{unordered_map}{unord.map.syn}
\item \libheaderrefx{unordered_set}{unord.set.syn}
\item \libheaderref{valarray}
\item \libheaderref{vector}
\end{itemize}

\indexlibrary{\idxcode{begin(C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto begin(C& c) noexcept(noexcept(c.begin()))
  -> decltype(c.begin());
template<class C> constexpr auto begin(const C& c) noexcept(noexcept(c.begin()))
  -> decltype(c.begin());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{c.begin()}.
\end{itemdescr}

\indexlibrary{\idxcode{end(C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto end(C& c) noexcept(noexcept(c.end())) -> decltype(c.end());
template<class C> constexpr auto end(const C& c) noexcept(noexcept(c.end())) -> decltype(c.end());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{c.end()}.
\end{itemdescr}

\indexlibrary{\idxcode{begin(T (\&)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{array}.
\end{itemdescr}

\indexlibrary{\idxcode{end(T (\&)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{array + N}.
\end{itemdescr}

\indexlibrary{\idxcode{cbegin(const C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto cbegin(const C& c) noexcept(noexcept(std::begin(c)))
  -> decltype(std::begin(c));
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{std::begin(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{cend(const C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto cend(const C& c) noexcept(noexcept(std::end(c)))
  -> decltype(std::end(c));
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{std::end(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto rbegin(C& c) noexcept(noexcept(c.rbegin()))
  -> decltype(c.rbegin());
template<class C> constexpr auto rbegin(const C& c) noexcept(noexcept(c.rbegin()))
  -> decltype(c.rbegin());
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{c.rbegin()}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(C\&)}}%
\begin{itemdecl}
template<class C> constexpr auto rend(C& c) noexcept(noexcept(c.rend())) -> decltype(c.rend());
template<class C> constexpr auto rend(const C& c) noexcept(noexcept(c.rend()))
  -> decltype(c.rend());
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{c.rend()}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr reverse_iterator<T*> rbegin(T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<T*>(array + N)}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr reverse_iterator<T*> rend(T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<T*>(array)}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(initializer_list<E>)}}%
\begin{itemdecl}
template<class E> constexpr reverse_iterator<const E*> rbegin(initializer_list<E> il) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<const E*>(il.end())}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(initializer_list<E>)}}%
\begin{itemdecl}
template<class E> constexpr reverse_iterator<const E*> rend(initializer_list<E> il) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<const E*>(il.begin())}.
\end{itemdescr}

\indexlibrary{\idxcode{crbegin(const C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto crbegin(const C& c) noexcept(noexcept(std::rbegin(c)))
  -> decltype(std::rbegin(c));
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{std::rbegin(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{crend(const C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto crend(const C& c) noexcept(noexcept(c.crend()))
  -> decltype(std::rend(c));
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{std::rend(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{size(C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto size(const C& c) noexcept(noexcept(c.size()))
  -> decltype(c.size());
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{c.size()}.
\end{itemdescr}

\indexlibrary{\idxcode{size(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{N}.
\end{itemdescr}

\indexlibrary{\idxcode{ssize(C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto ssize(const C& c) noexcept(noexcept(c.size()))
  -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>;
\end{itemdecl}
\begin{itemdescr}
\pnum
\effects
Equivalent to:
\begin{codeblock}
return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>>(c.size());
\end{codeblock}
\end{itemdescr}

\indexlibrary{\idxcode{ssize(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, ptrdiff_t N> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{N}.
\end{itemdescr}

\indexlibrary{\idxcode{empty(C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto empty(const C& c) noexcept(noexcept(c.empty()))
  -> decltype(c.empty());
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{c.empty()}.
\end{itemdescr}

\indexlibrary{\idxcode{empty(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{false}.
\end{itemdescr}

\indexlibrary{\idxcode{data(C\& c)}}%
\begin{itemdecl}
template<class C> constexpr auto data(C& c) noexcept(noexcept(c.data())) -> decltype(c.data());
template<class C> constexpr auto data(const C& c) noexcept(noexcept(c.data()))
  -> decltype(c.data());
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{c.data()}.
\end{itemdescr}

\indexlibrary{\idxcode{data(T (\&array)[N])}}%
\begin{itemdecl}
template<class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;
\end{itemdecl}
\begin{itemdescr}
\pnum
\returns
\tcode{array}.
\end{itemdescr}