%!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}@ =