27 Iterators library [iterators]

27.1 General [iterators.general]

1
#
This Clause describes components that C++ programs may use to perform iterations over containers (Clause [containers]), streams ([iostream.format]), and stream buffers ([stream.buffers]).
2
#
The following subclauses describe iterator requirements, and components for iterator primitives, predefined iterators, and stream iterators, as summarized in Table 87.
Table 87 — Iterators library summary
Subclause
Header(s)
Requirements
Iterator primitives
<iterator>
Predefined iterators
Stream iterators

27.2 Iterator requirements [iterator.requirements]

27.2.1 In general [iterator.requirements.general]

1
#
Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) 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 i supports the expression *i, resulting in a value of some object type T, called the value type of the iterator.
An output iterator i has a non-empty set of types that are writable to the iterator; for each such type T, the expression *i = o is valid where o is a value of type T.
An iterator i for which the expression (*i).m is well-defined supports the expression i->m with the same semantics as (*i).m.
For every iterator type X for which equality is defined, there is a corresponding signed integer type called the difference type of the iterator.
2
#
Since iterators are an abstraction of pointers, their semantics is a generalization of most of the semantics of pointers in C++.
This ensures that every function template that takes iterators works as well with regular pointers.
This International Standard defines five categories of iterators, according to the operations defined on them: input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators, as shown in Table 88.
Table 88 — Relations among iterator categories
Random Access
→ Bidirectional
→ Forward
→ Input
→ Output
3
#
Forward iterators satisfy all the requirements of input iterators and can be used whenever an input iterator is specified; Bidirectional iterators also satisfy all the requirements of forward iterators and can be used whenever a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.
4
#
Iterators that further satisfy the requirements of output iterators are called mutable iterators.
Nonmutable iterators are referred to as constant iterators.
5
#
In addition to the requirements in this subclause, the nested typedef-names specified in [iterator.traits] shall be provided for the iterator type.
[ Note
:
Either the iterator type must provide the typedef-names directly (in which case iterator_­traits pick them up automatically), or an iterator_­traits specialization must provide them.
— end note
 ]
6
#
Iterators that further satisfy the requirement that, for integral values n and dereferenceable iterator values a and (a + n), *(a + n) is equivalent to *(addressof(*a) + n), are called contiguous iterators.
[ Note
:
For example, the type “pointer to int” is a contiguous iterator, but reverse_­iterator<int *> is not.
For a valid iterator range [ab) with dereferenceable a, the corresponding range denoted by pointers is [addressof(*a)addressof(*a) + (b - a)); b might not be dereferenceable.
— end note
 ]
7
#
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.
These values are called past-the-end values.
Values of an iterator i for which the expression *i is defined are called 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.
[ Example
:
After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer.
— end example
 ]
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 satisfy the DefaultConstructible requirements, using a value-initialized iterator as the source of a copy or move operation.
[ 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.
8
#
An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j.
If j is reachable from i, they refer to elements of the same sequence.
9
#
Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges.
A range is a pair of iterators that designate the beginning and end of the computation.
A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element pointed to by j.
Range [i, j) is valid if and only if j is reachable from i.
The result of the application of functions in the library to invalid ranges is undefined.
10
#
All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).
Therefore, requirement tables for the iterators do not have a complexity column.
11
#
Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.
12
#
An invalid iterator is an iterator that may be singular.261
13
#
In the following sections, a and b denote values of type X or const X, difference_­type and reference refer to the types iterator_­traits<X>​::​difference_­type and iterator_­traits<X>​::​reference, respectively, n denotes a value of difference_­type, u, tmp, and m denote identifiers, r denotes a value of X&, t denotes a value of value type T, o denotes a value of some type that is writable to the output iterator.
[ Note
:
For an iterator type X there must be an instantiation of iterator_­traits<X> ([iterator.traits]).
— end note
 ]
261)
This definition applies to pointers, since pointers are iterators.
The effect of dereferencing an iterator that has been invalidated is undefined.

27.2.2 Iterator [iterator.iterators]

1
#
The Iterator requirements form the basis of the iterator concept taxonomy; every iterator satisfies the Iterator requirements.
This set of requirements specifies operations for dereferencing and incrementing an iterator.
Most algorithms will require additional operations to read ([input.iterators]) or write ([output.iterators]) values, or to provide a richer set of iterator movements ([forward.iterators], [bidirectional.iterators], [random.access.iterators]).
2
#
A type X satisfies the Iterator requirements if:
Table 89 — Iterator requirements
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r
unspecified
Requires: r is dereferenceable.
++r
X&

27.2.3 Input iterators [input.iterators]

1
#
A class or pointer type X satisfies the requirements of an input iterator for the value type T if X satisfies the Iterator ([iterator.iterators]) and EqualityComparable (Table 20) requirements and the expressions in Table 90 are valid and have the indicated semantics.
2
#
In Table 90, the term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined.
This set can change over time.
Each algorithm places additional requirements on the domain of == for the iterator values it uses.
These requirements can be inferred from the uses that algorithm makes of == and !=.
[ Example
:
The call find(a,b,x) is defined only if the value of a has the property p defined as follows: b has property p and a value i has property p if (*i==x) or if (*i!=x and ++i has property p).
— end example
 ]
Table 90 — Input iterator requirements (in addition to Iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
a != b
contextually convertible to bool
!(a == b)
Requires: (a, b) is in the domain of ==.
*a
reference, convertible to T
Requires: a is dereferenceable.

The expression
(void)*a, *a is equivalent to *a.

If a == b and (a, b) is in the domain of == then *a is equivalent to *b.
a->m
(*a).m
Requires: a is dereferenceable.
++r
X&
Requires: r is dereferenceable.

Postconditions: r is dereferenceable or r is past-the-end;
any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==.
(void)r++
equivalent to (void)++r
*r++
convertible to T
{ T tmp = *r;
++r;
return tmp; }
3
#
[ Note
:
For input iterators, a == b does not imply ++a == ++b.
(Equality does not guarantee the substitution property or referential transparency.)
Algorithms on input iterators should never attempt to pass through the same iterator twice.
They should be single pass algorithms.
Value type T is not required to be a CopyAssignable type (Table 26).
These algorithms can be used with istreams as the source of the input data through the istream_­iterator class template.
— end note
 ]

27.2.4 Output iterators [output.iterators]

1
#
A class or pointer type X satisfies the requirements of an output iterator if X satisfies the Iterator requirements ([iterator.iterators]) and the expressions in Table 91 are valid and have the indicated semantics.
Table 91 — Output iterator requirements (in addition to Iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
*r = o
result is not used
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
++r
X&
&r == &++r.

Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
r++
convertible to const X&
{ X tmp = r;
++r;
return tmp; }
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
*r++ = o
result is not used
Remarks: After this operation r is not required to be dereferenceable.

Postconditions: r is incrementable.
2
#
[ Note
:
The only valid use of an operator* is on the left side of the assignment statement.
Assignment through the same value of the iterator happens only once. Algorithms on output iterators should never attempt to pass through the same iterator twice.
They should be single pass algorithms.
Equality and inequality might not be defined.
Algorithms that take output iterators can be used with ostreams as the destination for placing data through the ostream_­iterator class as well as with insert iterators and insert pointers.
— end note
 ]

27.2.5 Forward iterators [forward.iterators]

1
#
A class or pointer type X satisfies the requirements of a forward iterator if
  • (1.1)
    X satisfies the requirements of an input iterator ([input.iterators]),
  • (1.2)
    X satisfies the DefaultConstructible requirements ([utility.arg.requirements]),
  • (1.3)
    if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,
  • (1.4)
    the expressions in Table 92 are valid and have the indicated semantics, and
  • (1.5)
    objects of type X offer the multi-pass guarantee, described below.
2
#
The domain of == 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.
[ Note
:
Value-initialized iterators behave as if they refer past the end of the same empty sequence.
— end note
 ]
3
#
Two dereferenceable iterators a and b of type X offer the multi-pass guarantee if:
  • (3.1)
    a == b implies ++a == ++b and
  • (3.2)
    X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.
4
#
[ Note
:
The requirement that a == b implies ++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
 ]
Table 92 — Forward iterator requirements (in addition to input iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r++
convertible to const X&
{ X tmp = r;
++r;
return tmp; }
*r++
reference
5
#
If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.
6
#
If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

27.2.6 Bidirectional iterators [bidirectional.iterators]

1
#
A class or pointer type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the requirements for forward iterators, the following expressions are valid as shown in Table 93.
Table 93 — Bidirectional iterator requirements (in addition to forward iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
--r
X&
Requires: there exists s such that r == ++s.

Postconditions: r is dereferenceable.

--(++r) == r.

--r == --s implies r == s.

&r == &--r.
r--
convertible to const X&
{ X tmp = r;
--r;
return tmp; }
*r--
reference
2
#
[ Note
:
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
— end note
 ]

27.2.7 Random access iterators [random.access.iterators]

1
#
A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, the following expressions are valid as shown in Table 94.
Table 94 — Random access iterator requirements (in addition to bidirectional iterator)
Expression
Return type
Operational
Assertion/note
semantics
pre-/post-condition
r += n
X&
{ difference_­type m = n;
if (m >= 0)
while (m--)
++r;
else
while (m++)
--r;
return r; }
a + n
n + a
X
{ X tmp = a;
return tmp += n; }
a + n == n + a.
r -= n
X&
return r += -n;
Requires: the absolute value of n is in the range of representable values of difference_­type.
a - n
X
{ X tmp = a;
return tmp -= n; }
b - a
difference_­type
return n
Requires: there exists a value n of type difference_­type such that a + n == b.

b == a + (b - a).
a[n]
convertible to reference
*(a + n)
a < b
contextually convertible to bool
b - a > 0
< is a total ordering relation
a > b
contextually convertible to bool
b < a
> is a total ordering relation opposite to <.
a >= b
contextually convertible to bool
!(a < b)
a <= b
contextually convertible to bool.
!(a > b)

27.3 Header <iterator> synopsis [iterator.synopsis]

namespace std {
  // [iterator.primitives], primitives
  template<class Iterator> struct iterator_traits;
  template<class T> struct iterator_traits<T*>;
  template<class T> struct iterator_traits<const T*>;

  struct input_iterator_tag { };
  struct output_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 { };

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

  // [predef.iterators], predefined iterators
  template <class Iterator> class reverse_iterator;

  template <class Iterator1, class Iterator2>
    constexpr bool operator==(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator!=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);

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

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

  template <class Container> class back_insert_iterator;
  template <class Container>
    back_insert_iterator<Container> back_inserter(Container& x);

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

  template <class Container> class insert_iterator;
  template <class Container>
    insert_iterator<Container> inserter(Container& x, typename Container::iterator i);

  template <class Iterator> class move_iterator;
  template <class Iterator1, class Iterator2>
    constexpr bool operator==(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator!=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

  template <class Iterator1, class Iterator2>
    constexpr auto operator-(
    const move_iterator<Iterator1>& x,
    const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
  template <class Iterator>
    constexpr move_iterator<Iterator> operator+(
      typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
  template <class Iterator>
    constexpr move_iterator<Iterator> make_move_iterator(Iterator i);

  // [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, 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>
    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;

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

  // [iterator.container], container access
  template <class C> constexpr auto size(const C& c) -> decltype(c.size());
  template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;
  template <class C> constexpr auto empty(const C& c) -> decltype(c.empty());
  template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;
  template <class E> constexpr bool empty(initializer_list<E> il) noexcept;
  template <class C> constexpr auto data(C& c) -> decltype(c.data());
  template <class C> constexpr auto data(const C& c) -> decltype(c.data());
  template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;
  template <class E> constexpr const E* data(initializer_list<E> il) noexcept;
}

27.4 Iterator primitives [iterator.primitives]

1
#
To simplify the task of defining iterators, the library provides several classes and functions:

27.4.1 Iterator traits [iterator.traits]

1
#
To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type.
Accordingly, it is required that if Iterator is the type of an iterator, the types
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
be defined as the iterator's difference type, value type and iterator category, respectively.
In addition, the types 
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
shall be defined as the iterator's reference and pointer types, that is, for an iterator object a, the same type as the type of *a and a->, respectively.
In the case of an output iterator, the types
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
may be defined as void.
2
#
If Iterator has valid ([temp.deduct]) member types difference_­type, value_­type, pointer, reference, and iterator_­category, iterator_­traits<Iterator> shall have the following as publicly accessible members: 
  using difference_type   = typename Iterator::difference_type;
  using value_type        = typename Iterator::value_type;
  using pointer           = typename Iterator::pointer;
  using reference         = typename Iterator::reference;
  using iterator_category = typename Iterator::iterator_category;
Otherwise, iterator_­traits<Iterator> shall have no members by any of the above names.
3
#
It is specialized for pointers as
namespace std {
  template<class T> struct iterator_traits<T*> {
    using difference_type   = ptrdiff_t;
    using value_type        = T;
    using pointer           = T*;
    using reference         = T&;
    using iterator_category = random_access_iterator_tag;
  };
}
and for pointers to const as 
namespace std {
  template<class T> struct iterator_traits<const T*> {
    using difference_type   = ptrdiff_t;
    using value_type        = T;
    using pointer           = const T*;
    using reference         = const T&;
    using iterator_category = random_access_iterator_tag;
  };
}
4
#
[ Example
:
To implement a generic reverse function, a C++ program can do the following:
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  typename iterator_traits<BidirectionalIterator>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BidirectionalIterator>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}
— end example
 ]

27.4.2 Standard iterator tags [std.iterator.tags]

1
#
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 category tag classes which are used as compile time tags for algorithm selection.
They are: input_­iterator_­tag, output_­iterator_­tag, forward_­iterator_­tag, bidirectional_­iterator_­tag and random_­access_­iterator_­tag.
For every iterator of type Iterator, iterator_­traits<Iterator>​::​iterator_­category shall be defined to be the most specific category tag that describes the iterator's behavior.
namespace std {
  struct input_iterator_tag { };
  struct output_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 { };
}
2
#
[ Example
:
For a program-defined iterator BinaryTreeIterator, it could be included into the bidirectional iterator category by specializing the iterator_­traits template:
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 example
 ]
3
#
[ Example
:
If evolve() is well defined for bidirectional iterators, but can be implemented more efficiently for random access iterators, then the implementation is as follows:
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 example
 ]

27.4.3 Iterator operations [iterator.operations]

1
#
Since only random access iterators provide + and - operators, the library provides two function templates advance and distance.
These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.
template <class InputIterator, class Distance> constexpr void advance(InputIterator& i, Distance n);
2
#
Requires: n shall be negative only for bidirectional and random access iterators.
3
#
Effects: Increments (or decrements for negative n) iterator reference i by n.
template <class InputIterator> constexpr typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);
4
#
Effects: If InputIterator meets the requirements of random access iterator, returns (last - first); otherwise, returns the number of increments needed to get from first to last.
5
#
Requires: If InputIterator meets the requirements of random access iterator, last shall be reachable from first or first shall be reachable from last; otherwise, last shall be reachable from first.
template <class InputIterator> constexpr InputIterator next(InputIterator x, typename iterator_traits<InputIterator>::difference_type n = 1);
6
#
Effects: Equivalent to: advance(x, n); return x;
template <class BidirectionalIterator> constexpr BidirectionalIterator prev(BidirectionalIterator x, typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
7
#
Effects: Equivalent to: advance(x, -n); return x;

27.5 Iterator adaptors [predef.iterators]

27.5.1 Reverse iterators [reverse.iterators]

1
#
Class template 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.
The fundamental relation between a reverse iterator and its corresponding iterator i is established by the identity: &*(reverse_­iterator(i)) == &*(i - 1).

27.5.1.1 Class template reverse_­iterator [reverse.iterator]

namespace std {
  template <class Iterator>
  class reverse_iterator {
  public:
    using iterator_type     = Iterator;
    using iterator_category = typename iterator_traits<Iterator>::iterator_category;
    using value_type        = typename iterator_traits<Iterator>::value_type;
    using difference_type   = typename iterator_traits<Iterator>::difference_type;
    using pointer           = typename iterator_traits<Iterator>::pointer;
    using reference         = typename iterator_traits<Iterator>::reference;

    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;      // explicit
    constexpr reference operator*() const;
    constexpr pointer   operator->() const;

    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 unspecified operator[](difference_type n) const;
  protected:
    Iterator current;
  };

  template <class Iterator1, class Iterator2>
    constexpr bool operator==(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator!=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr auto operator-(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
  template <class Iterator>
    constexpr reverse_iterator<Iterator> operator+(
      typename reverse_iterator<Iterator>::difference_type n,
      const reverse_iterator<Iterator>& x);

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

27.5.1.2 reverse_­iterator requirements [reverse.iter.requirements]

1
#
The template parameter Iterator shall meet all the requirements of a Bidirectional Iterator ([bidirectional.iterators]).
2
#
Additionally, Iterator shall meet the requirements of a random access iterator ([random.access.iterators]) if any of the members operator+ ([reverse.iter.op+]), operator- ([reverse.iter.op-]), operator+= ([reverse.iter.op+=]), operator-= ([reverse.iter.op-=]), operator[] ([reverse.iter.opindex]), or the non-member operators operator< ([reverse.iter.op<]), operator> ([reverse.iter.op>]),
operator<= ([reverse.iter.op<=]), operator>= ([reverse.iter.op>=]), operator- ([reverse.iter.opdiff]) or operator+ ([reverse.iter.opsum]) are referenced in a way that requires instantiation ([temp.inst]).

27.5.1.3 reverse_­iterator operations [reverse.iter.ops]

27.5.1.3.1 reverse_­iterator constructor [reverse.iter.cons]

constexpr reverse_iterator();
1
#
Effects: Value-initializes current.
Iterator operations applied to the resulting iterator have defined behavior if and only if the corresponding operations are defined on a value-initialized iterator of type Iterator.
constexpr explicit reverse_iterator(Iterator x);
2
#
Effects: Initializes current with x.
template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
3
#
Effects: Initializes current with u.current.

27.5.1.3.2 reverse_­iterator​::​operator= [reverse.iter.op=]

template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u);
1
#
Effects: Assigns u.base() to current.
2
#
Returns: *this.

27.5.1.3.3 Conversion [reverse.iter.conv]

constexpr Iterator base() const; // explicit
1
#
Returns: current.

27.5.1.3.4 operator* [reverse.iter.op.star]

constexpr reference operator*() const;
1
#
Effects: As if by: 
Iterator tmp = current;
return *--tmp;

27.5.1.3.5 operator-> [reverse.iter.opref]

constexpr pointer operator->() const;
1
#
Returns: addressof(operator*()).

27.5.1.3.6 operator++ [reverse.iter.op++]

constexpr reverse_iterator& operator++();
1
#
Effects: As if by: --current;
2
#
Returns: *this.
constexpr reverse_iterator operator++(int);
3
#
Effects: As if by: 
reverse_iterator tmp = *this;
--current;
return tmp;

27.5.1.3.7 operator-- [reverse.iter.op--]

constexpr reverse_iterator& operator--();
1
#
Effects: As if by ++current.
2
#
Returns: *this.
constexpr reverse_iterator operator--(int);
3
#
Effects: As if by: 
reverse_iterator tmp = *this;
++current;
return tmp;

27.5.1.3.8 operator+ [reverse.iter.op+]

constexpr reverse_iterator operator+(difference_type n) const;
1
#
Returns: reverse_­iterator(current-n).

27.5.1.3.9 operator+= [reverse.iter.op+=]

constexpr reverse_iterator& operator+=(difference_type n);
1
#
Effects: As if by: current -= n;
2
#
Returns: *this.

27.5.1.3.10 operator- [reverse.iter.op-]

constexpr reverse_iterator operator-(difference_type n) const;
1
#
Returns: reverse_­iterator(current+n).

27.5.1.3.11 operator-= [reverse.iter.op-=]

constexpr reverse_iterator& operator-=(difference_type n);
1
#
Effects: As if by: current += n;
2
#
Returns: *this.

27.5.1.3.12 operator[] [reverse.iter.opindex]

constexpr unspecified operator[](difference_type n) const;
1
#
Returns: current[-n-1].

27.5.1.3.13 operator== [reverse.iter.op==]

template <class Iterator1, class Iterator2> constexpr bool operator==( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current == y.current.

27.5.1.3.14 operator< [reverse.iter.op<]

template <class Iterator1, class Iterator2> constexpr bool operator<( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current > y.current.

27.5.1.3.15 operator!= [reverse.iter.op!=]

template <class Iterator1, class Iterator2> constexpr bool operator!=( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current != y.current.

27.5.1.3.16 operator> [reverse.iter.op>]

template <class Iterator1, class Iterator2> constexpr bool operator>( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current < y.current.

27.5.1.3.17 operator>= [reverse.iter.op>=]

template <class Iterator1, class Iterator2> constexpr bool operator>=( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current <= y.current.

27.5.1.3.18 operator<= [reverse.iter.op<=]

template <class Iterator1, class Iterator2> constexpr bool operator<=( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
1
#
Returns: x.current >= y.current.

27.5.1.3.19 operator- [reverse.iter.opdiff]

template <class Iterator1, class Iterator2> constexpr auto operator-( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
1
#
Returns: y.current - x.current.

27.5.1.3.20 operator+ [reverse.iter.opsum]

template <class Iterator> constexpr reverse_iterator<Iterator> operator+( typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);
1
#
Returns: reverse_­iterator<Iterator> (x.current - n).

27.5.1.3.21 Non-member function make_­reverse_­iterator() [reverse.iter.make]

template <class Iterator> constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i);
1
#
Returns: reverse_­iterator<Iterator>(i).

27.5.2 Insert iterators [insert.iterators]

1
#
To make it possible to deal with insertion in the same way as writing into an array, a special kind of iterator adaptors, called insert iterators, are provided in the library.
With regular iterator classes,
while (first != last) *result++ = *first++;
causes a range [first, last) to be copied into a range starting with result.
The same code with 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 insert mode instead of the regular overwrite mode.
2
#
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 satisfy the requirements of output iterators.
operator* returns the insert iterator itself.
The assignment operator=(const T& x) is defined on insert iterators to allow writing into them, it inserts 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.
back_­insert_­iterator inserts elements at the end of a container, front_­insert_­iterator inserts elements at the beginning of a container, and insert_­iterator inserts elements where the iterator points to in a container.
back_­inserter, front_­inserter, and inserter are three functions making the insert iterators out of a container.

27.5.2.1 Class template back_­insert_­iterator [back.insert.iterator]

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   = void;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

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

    back_insert_iterator& operator*();
    back_insert_iterator& operator++();
    back_insert_iterator  operator++(int);
  };

  template <class Container>
    back_insert_iterator<Container> back_inserter(Container& x);
}

27.5.2.2 back_­insert_­iterator operations [back.insert.iter.ops]

27.5.2.2.1 back_­insert_­iterator constructor [back.insert.iter.cons]

explicit back_insert_iterator(Container& x);
1
#
Effects: Initializes container with addressof(x).

27.5.2.2.2 back_­insert_­iterator​::​operator= [back.insert.iter.op=]

back_insert_iterator& operator=(const typename Container::value_type& value);
1
#
Effects: As if by: container->push_­back(value);
2
#
Returns: *this.
back_insert_iterator& operator=(typename Container::value_type&& value);
3
#
Effects: As if by: container->push_­back(std​::​move(value));
4
#
Returns: *this.

27.5.2.2.3 back_­insert_­iterator​::​operator* [back.insert.iter.op*]

back_insert_iterator& operator*();
1
#
Returns: *this.

27.5.2.2.4 back_­insert_­iterator​::​operator++ [back.insert.iter.op++]

back_insert_iterator& operator++(); back_insert_iterator operator++(int);
1
#
Returns: *this.

27.5.2.2.5 back_­inserter [back.inserter]

template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
1
#
Returns: back_­insert_­iterator<Container>(x).

27.5.2.3 Class template front_­insert_­iterator [front.insert.iterator]

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   = void;
    using pointer           = void;
    using reference         = void;
    using container_type    = Container;

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

    front_insert_iterator& operator*();
    front_insert_iterator& operator++();
    front_insert_iterator  operator++(int);
  };

  template <class Container>
    front_insert_iterator<Container> front_inserter(Container& x);
}

27.5.2.4 front_­insert_­iterator operations [front.insert.iter.ops]

27.5.2.4.1 front_­insert_­iterator constructor [front.insert.iter.cons]

explicit front_insert_iterator(Container& x);
1
#
Effects: Initializes container with addressof(x).

27.5.2.4.2 front_­insert_­iterator​::​operator= [front.insert.iter.op=]

front_insert_iterator& operator=(const typename Container::value_type& value);
1
#
Effects: As if by: container->push_­front(value);
2
#
Returns: *this.
front_insert_iterator& operator=(typename Container::value_type&& value);
3
#
Effects: As if by: container->push_­front(std​::​move(value));
4
#
Returns: *this.

27.5.2.4.3 front_­insert_­iterator​::​operator* [front.insert.iter.op*]

front_insert_iterator& operator*();
1
#
Returns: *this.

27.5.2.4.4 front_­insert_­iterator​::​operator++ [front.insert.iter.op++]

front_insert_iterator& operator++(); front_insert_iterator operator++(int);
1
#
Returns: *this.

27.5.2.4.5 front_­inserter [front.inserter]

template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
1
#
Returns: front_­insert_­iterator<Container>(x).

27.5.2.5 Class template insert_­iterator [insert.iterator]

namespace std {
  template <class Container>
  class insert_iterator {
  protected:
    Container* container;
    typename Container::iterator iter;

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

    insert_iterator(Container& x, typename Container::iterator i);
    insert_iterator& operator=(const typename Container::value_type& value);
    insert_iterator& operator=(typename Container::value_type&& value);

    insert_iterator& operator*();
    insert_iterator& operator++();
    insert_iterator& operator++(int);
  };

  template <class Container>
    insert_iterator<Container> inserter(Container& x, typename Container::iterator i);
}

27.5.2.6 insert_­iterator operations [insert.iter.ops]

27.5.2.6.1 insert_­iterator constructor [insert.iter.cons]

insert_iterator(Container& x, typename Container::iterator i);
1
#
Effects: Initializes container with addressof(x) and iter with i.

27.5.2.6.2 insert_­iterator​::​operator= [insert.iter.op=]

insert_iterator& operator=(const typename Container::value_type& value);
1
#
Effects: As if by: 
iter = container->insert(iter, value);
++iter;
2
#
Returns: *this.
insert_iterator& operator=(typename Container::value_type&& value);
3
#
Effects: As if by: 
iter = container->insert(iter, std::move(value));
++iter;
4
#
Returns: *this.

27.5.2.6.3 insert_­iterator​::​operator* [insert.iter.op*]

insert_iterator& operator*();
1
#
Returns: *this.

27.5.2.6.4 insert_­iterator​::​operator++ [insert.iter.op++]

insert_iterator& operator++(); insert_iterator& operator++(int);
1
#
Returns: *this.

27.5.2.6.5 inserter [inserter]

template <class Container> insert_iterator<Container> inserter(Container& x, typename Container::iterator i);
1
#
Returns: insert_­iterator<Container>(x, i).

27.5.3 Move iterators [move.iterators]

1
#
Class template 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.
2
#
[ Example
: 
list<string> s;
// populate the list s
vector<string> v1(s.begin(), s.end());          // copies strings into v1
vector<string> v2(make_move_iterator(s.begin()),
                  make_move_iterator(s.end())); // moves strings into v2
— end example
 ]

27.5.3.1 Class template move_­iterator [move.iterator]

namespace std {
  template <class Iterator>
  class move_iterator {
  public:
    using iterator_type     = Iterator;
    using iterator_category = typename iterator_traits<Iterator>::iterator_category;
    using value_type        = typename iterator_traits<Iterator>::value_type;
    using difference_type   = typename iterator_traits<Iterator>::difference_type;
    using pointer           = Iterator;
    using reference         = see below;

    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 iterator_type base() const;
    constexpr reference operator*() const;
    constexpr pointer operator->() const;

    constexpr move_iterator& operator++();
    constexpr move_iterator 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 unspecified operator[](difference_type n) const;

  private:
    Iterator current;   // exposition only
  };

  template <class Iterator1, class Iterator2>
    constexpr bool operator==(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator!=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator<=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    constexpr bool operator>=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

  template <class Iterator1, class Iterator2>
    constexpr auto operator-(
      const move_iterator<Iterator1>& x,
      const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
  template <class Iterator>
    constexpr move_iterator<Iterator> operator+(
      typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
  template <class Iterator>
    constexpr move_iterator<Iterator> make_move_iterator(Iterator i);
}
1
#
Let R denote iterator_­traits<Iterator>​::​reference.
If is_­reference_­v<R> is true, the template specialization move_­iterator<Iterator> shall define the nested type named reference as a synonym for remove_­reference_­t<R>&&, otherwise as a synonym for R.

27.5.3.2 move_­iterator requirements [move.iter.requirements]

1
#
The template parameter Iterator shall meet the requirements of an input iterator ([input.iterators]).
Additionally, if any of the bidirectional or random access traversal functions are instantiated, the template parameter shall meet the requirements for a Bidirectional Iterator ([bidirectional.iterators]) or a Random Access Iterator ([random.access.iterators]), respectively.

27.5.3.3 move_­iterator operations [move.iter.ops]

27.5.3.3.1 move_­iterator constructors [move.iter.op.const]

constexpr move_iterator();
1
#
Effects: Constructs a move_­iterator, value-initializing current.
Iterator operations applied to the resulting iterator have defined behavior if and only if the corresponding operations are defined on a value-initialized iterator of type Iterator.
constexpr explicit move_iterator(Iterator i);
2
#
Effects: Constructs a move_­iterator, initializing current with i.
template <class U> constexpr move_iterator(const move_iterator<U>& u);
3
#
Effects: Constructs a move_­iterator, initializing current with u.base().
4
#
Requires: U shall be convertible to Iterator.

27.5.3.3.2 move_­iterator​::​operator= [move.iter.op=]

template <class U> constexpr move_iterator& operator=(const move_iterator<U>& u);
1
#
Effects: Assigns u.base() to current.
2
#
Requires: U shall be convertible to Iterator.

27.5.3.3.3 move_­iterator conversion [move.iter.op.conv]

constexpr Iterator base() const;
1
#
Returns: current.

27.5.3.3.4 move_­iterator​::​operator* [move.iter.op.star]

constexpr reference operator*() const;
1
#
Returns: static_­cast<reference>(*current).

27.5.3.3.5 move_­iterator​::​operator-> [move.iter.op.ref]

constexpr pointer operator->() const;
1
#
Returns: current.

27.5.3.3.6 move_­iterator​::​operator++ [move.iter.op.incr]

constexpr move_iterator& operator++();
1
#
Effects: As if by ++current.
2
#
Returns: *this.
constexpr move_iterator operator++(int);
3
#
Effects: As if by: 
move_iterator tmp = *this;
++current;
return tmp;

27.5.3.3.7 move_­iterator​::​operator-- [move.iter.op.decr]

constexpr move_iterator& operator--();
1
#
Effects: As if by --current.
2
#
Returns: *this.
constexpr move_iterator operator--(int);
3
#
Effects: As if by: 
move_iterator tmp = *this;
--current;
return tmp;

27.5.3.3.8 move_­iterator​::​operator+ [move.iter.op.+]

constexpr move_iterator operator+(difference_type n) const;
1
#
Returns: move_­iterator(current + n).

27.5.3.3.9 move_­iterator​::​operator+= [move.iter.op.+=]

constexpr move_iterator& operator+=(difference_type n);
1
#
Effects: As if by: current += n;
2
#
Returns: *this.

27.5.3.3.10 move_­iterator​::​operator- [move.iter.op.-]

constexpr move_iterator operator-(difference_type n) const;
1
#
Returns: move_­iterator(current - n).

27.5.3.3.11 move_­iterator​::​operator-= [move.iter.op.-=]

constexpr move_iterator& operator-=(difference_type n);
1
#
Effects: As if by: current -= n;
2
#
Returns: *this.

27.5.3.3.12 move_­iterator​::​operator[] [move.iter.op.index]

constexpr unspecified operator[](difference_type n) const;
1
#
Returns: std​::​move(current[n]).

27.5.3.3.13 move_­iterator comparisons [move.iter.op.comp]

template <class Iterator1, class Iterator2> constexpr bool operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
1
#
Returns: x.base() == y.base().
template <class Iterator1, class Iterator2> constexpr bool operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
2
#
Returns: !(x == y).
template <class Iterator1, class Iterator2> constexpr bool operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
3
#
Returns: x.base() < y.base().
template <class Iterator1, class Iterator2> constexpr bool operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
4
#
Returns: !(y < x).
template <class Iterator1, class Iterator2> constexpr bool operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
5
#
Returns: y < x.
template <class Iterator1, class Iterator2> constexpr bool operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
6
#
Returns: !(x < y).

27.5.3.3.14 move_­iterator non-member functions [move.iter.nonmember]

template <class Iterator1, class Iterator2> constexpr auto operator-( const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
1
#
Returns: x.base() - y.base().
template <class Iterator> constexpr move_iterator<Iterator> operator+( typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
2
#
Returns: x + n.
template <class Iterator> constexpr move_iterator<Iterator> make_move_iterator(Iterator i);
3
#
Returns: move_­iterator<Iterator>(i).

27.6 Stream iterators [stream.iterators]

1
#
To make it possible for algorithmic templates to work directly with input/output streams, appropriate iterator-like class templates are provided.
[ Example
: 
partial_sum(istream_iterator<double, char>(cin),
  istream_iterator<double, char>(),
  ostream_iterator<double, char>(cout, "\n"));
reads a file containing floating-point numbers from cin, and prints the partial sums onto cout.
— end example
 ]

27.6.1 Class template istream_­iterator [istream.iterator]

1
#
The class template istream_­iterator is an input iterator ([input.iterators]) that reads (using operator>>) successive elements from the input stream for which it was constructed.
After it is constructed, and every time ++ is used, the iterator reads and stores a value of T.
If the iterator fails to read and store a value of T (fail() on the stream returns true), the iterator becomes equal to the end-of-stream iterator value.
The constructor with no arguments istream_­iterator() always constructs an end-of-stream input iterator object, which is the only legitimate iterator to be used for the end condition.
The result of operator* on an end-of-stream iterator is not defined.
For any other iterator value a const T& is returned.
The result of operator-> on an end-of-stream iterator is not defined.
For any other iterator value a const T* is returned.
The behavior of a program that applies operator++() to an end-of-stream iterator is undefined.
It is impossible to store things into istream iterators.
The type T shall meet the DefaultConstructible, CopyConstructible, and CopyAssignable requirements.
2
#
Two end-of-stream iterators are always equal.
An end-of-stream iterator is not equal to a non-end-of-stream iterator.
Two non-end-of-stream iterators are equal when they are constructed from the same stream.
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();
    istream_iterator(istream_type& s);
    istream_iterator(const istream_iterator& x) = default;
    ~istream_iterator() = default;

    const T& operator*() const;
    const T* operator->() const;
    istream_iterator& operator++();
    istream_iterator  operator++(int);
  private:
    basic_istream<charT,traits>* in_stream; // exposition only
    T value;                                // exposition only
  };

  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, class traits, class Distance>
    bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
            const istream_iterator<T,charT,traits,Distance>& y);
}

27.6.1.1 istream_­iterator constructors and destructor [istream.iterator.cons]

constexpr istream_iterator();
1
#
Effects: Constructs the end-of-stream iterator.
If is_­trivially_­default_­constructible_­v<T> is true, then this constructor is a constexpr constructor.
2
#
Postconditions: in_­stream == 0.
istream_iterator(istream_type& s);
3
#
Effects: Initializes in_­stream with addressof(s).
value may be initialized during construction or the first time it is referenced.
4
#
Postconditions: in_­stream == addressof(s).
istream_iterator(const istream_iterator& x) = default;
5
#
Effects: Constructs a copy of x.
If is_­trivially_­copy_­constructible_­v<T> is true, then this constructor is a trivial copy constructor.
6
#
Postconditions: in_­stream == x.in_­stream.
~istream_iterator() = default;
7
#
Effects: The iterator is destroyed.
If is_­trivially_­destructible_­v<T> is true, then this destructor is a trivial destructor.

27.6.1.2 istream_­iterator operations [istream.iterator.ops]

const T& operator*() const;
1
#
Returns: value.
const T* operator->() const;
2
#
Returns: addressof(operator*()).
istream_iterator& operator++();
3
#
Requires: in_­stream != 0.
4
#
Effects: As if by: *in_­stream >> value;
5
#
Returns: *this.
istream_iterator operator++(int);
6
#
Requires: in_­stream != 0.
7
#
Effects: As if by: 
istream_iterator tmp = *this;
*in_stream >> value;
return (tmp);
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);
8
#
Returns: x.in_­stream == y.in_­stream.
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);
9
#
Returns: !(x == y)

27.6.2 Class template ostream_­iterator [ostream.iterator]

1
#
ostream_­iterator writes (using operator<<) successive elements onto the output stream from which it was constructed.
If it was constructed with charT* as a constructor argument, this string, called a delimiter string, is written to the stream after every T is written.
It is not possible to get a value out of the output iterator.
Its only use is as an output iterator in situations like
while (first != last)
  *result++ = *first++;
2
#
ostream_­iterator is defined as:
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   = void;
    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 T& value);

    ostream_iterator& operator*();
    ostream_iterator& operator++();
    ostream_iterator& operator++(int);
  private:
    basic_ostream<charT,traits>* out_stream;  // exposition only
    const charT* delim;                       // exposition only
  };
}

27.6.2.1 ostream_­iterator constructors and destructor [ostream.iterator.cons.des]

ostream_iterator(ostream_type& s);
1
#
Effects: Initializes out_­stream with addressof(s) and delim with null.
ostream_iterator(ostream_type& s, const charT* delimiter);
2
#
Effects: Initializes out_­stream with addressof(s) and delim with delimiter.
ostream_iterator(const ostream_iterator& x);
3
#
Effects: Constructs a copy of x.
~ostream_iterator();
4
#
Effects: The iterator is destroyed.

27.6.2.2 ostream_­iterator operations [ostream.iterator.ops]

ostream_iterator& operator=(const T& value);
1
#
Effects: As if by: 
*out_stream << value;
if (delim != 0)
  *out_stream << delim;
return *this;
ostream_iterator& operator*();
2
#
Returns: *this.
ostream_iterator& operator++(); ostream_iterator& operator++(int);
3
#
Returns: *this.

27.6.3 Class template istreambuf_­iterator [istreambuf.iterator]

1
#
The class template istreambuf_­iterator defines an input iterator ([input.iterators]) that reads successive characters from the streambuf for which it was constructed.
operator* provides access to the current input character, if any.
Each time operator++ is evaluated, the iterator advances to the next input character.
If the end of stream is reached (streambuf_­type​::​sgetc() returns traits​::​eof()), the iterator becomes equal to the end-of-stream iterator value.
The default constructor istreambuf_­iterator() and the constructor istreambuf_­iterator(0) both construct an end-of-stream iterator object suitable for use as an end-of-range.
All specializations of istreambuf_­iterator shall have a trivial copy constructor, a constexpr default constructor, and a trivial destructor.
2
#
The result of operator*() on an end-of-stream iterator is undefined.
For any other iterator value a char_­type value is returned.
It is impossible to assign a character via an input iterator.
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   = typename traits::off_type;
    using pointer           = unspecified;
    using reference         = charT;
    using char_type         = charT;
    using traits_type       = traits;
    using int_type          = typename traits::int_type;
    using streambuf_type    = basic_streambuf<charT,traits>;
    using istream_type      = basic_istream<charT,traits>;

    class proxy;                          // exposition only

    constexpr istreambuf_iterator() 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 proxy& p) noexcept;
    charT operator*() const;
    istreambuf_iterator& operator++();
    proxy operator++(int);
    bool equal(const istreambuf_iterator& b) const;
  private:
    streambuf_type* sbuf_;                // exposition only
  };

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

27.6.3.1 Class template istreambuf_­iterator​::​proxy [istreambuf.iterator.proxy]

namespace std {
  template <class charT, class traits = char_traits<charT>>
  class istreambuf_iterator<charT, traits>::proxy { // exposition only
    charT keep_;
    basic_streambuf<charT,traits>* sbuf_;
    proxy(charT c, basic_streambuf<charT,traits>* sbuf)
      : keep_(c), sbuf_(sbuf) { }
  public:
    charT operator*() { return keep_; }
  };
}
1
#
Class istreambuf_­iterator<charT,traits>​::​proxy is for exposition only.
An implementation is permitted to provide equivalent functionality without providing a class with this name.
Class istreambuf_­iterator<charT, traits>​::​proxy provides a temporary placeholder as the return value of the post-increment operator (operator++).
It keeps the character pointed to by the previous value of the iterator for some possible future access to get the character.

27.6.3.2 istreambuf_­iterator constructors [istreambuf.iterator.cons]

1
#
For each istreambuf_­iterator constructor in this section, an end-of-stream iterator is constructed if and only if the exposition-only member sbuf_­ is initialized with a null pointer value.
constexpr istreambuf_iterator() noexcept;
2
#
Effects: Initializes sbuf_­ with nullptr.
istreambuf_iterator(istream_type& s) noexcept;
3
#
Effects: Initializes sbuf_­ with s.rdbuf().
istreambuf_iterator(streambuf_type* s) noexcept;
4
#
Effects: Initializes sbuf_­ with s.
istreambuf_iterator(const proxy& p) noexcept;
5
#
Effects: Initializes sbuf_­ with p.sbuf_­.

27.6.3.3 istreambuf_­iterator operations [istreambuf.iterator.ops]

charT operator*() const
1
#
Returns: The character obtained via the streambuf member sbuf_­->sgetc().
istreambuf_iterator& operator++();
2
#
Effects: As if by sbuf_­->sbumpc().
3
#
Returns: *this.
proxy operator++(int);
4
#
Returns: proxy(sbuf_­->sbumpc(), sbuf_­).
bool equal(const istreambuf_iterator& b) const;
5
#
Returns: true if and only if both iterators are at end-of-stream, or neither is at end-of-stream, regardless of what streambuf object they use.
template <class charT, class traits> bool operator==(const istreambuf_iterator<charT,traits>& a, const istreambuf_iterator<charT,traits>& b);
6
#
Returns: a.equal(b).
template <class charT, class traits> bool operator!=(const istreambuf_iterator<charT,traits>& a, const istreambuf_iterator<charT,traits>& b);
7
#
Returns: !a.equal(b).

27.6.4 Class template ostreambuf_­iterator [ostreambuf.iterator]

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   = void;
    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_;                // exposition only
  };
}
1
#
The class template ostreambuf_­iterator writes successive characters onto the output stream from which it was constructed.
It is not possible to get a character value out of the output iterator.

27.6.4.1 ostreambuf_­iterator constructors [ostreambuf.iter.cons]

ostreambuf_iterator(ostream_type& s) noexcept;
1
#
Requires: s.rdbuf() shall not be a null pointer.
2
#
Effects: Initializes sbuf_­ with s.rdbuf().
ostreambuf_iterator(streambuf_type* s) noexcept;
3
#
Requires: s shall not be a null pointer.
4
#
Effects: Initializes sbuf_­ with s.

27.6.4.2 ostreambuf_­iterator operations [ostreambuf.iter.ops]

ostreambuf_iterator& operator=(charT c);
1
#
Effects: If failed() yields false, calls sbuf_­->sputc(c); otherwise has no effect.
2
#
Returns: *this.
ostreambuf_iterator& operator*();
3
#
Returns: *this.
ostreambuf_iterator& operator++(); ostreambuf_iterator& operator++(int);
4
#
Returns: *this.
bool failed() const noexcept;
5
#
Returns: true if in any prior use of member operator=, the call to sbuf_­->sputc() returned traits​::​eof(); or false otherwise.

27.7 Range access [iterator.range]

1
#
In addition to being available via inclusion of the <iterator> header, the function templates in [iterator.range] are available when any of the following headers are included: <array>, <deque>, <forward_­list>, <list>, <map>, <regex>, <set>, <string>, <string_­view>, <unordered_­map>, <unordered_­set>, and <vector>.
template <class C> constexpr auto begin(C& c) -> decltype(c.begin()); template <class C> constexpr auto begin(const C& c) -> decltype(c.begin());
2
#
Returns: c.begin().
template <class C> constexpr auto end(C& c) -> decltype(c.end()); template <class C> constexpr auto end(const C& c) -> decltype(c.end());
3
#
Returns: c.end().
template <class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;
4
#
Returns: array.
template <class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;
5
#
Returns: array + N.
template <class C> constexpr auto cbegin(const C& c) noexcept(noexcept(std::begin(c))) -> decltype(std::begin(c));
6
#
Returns: std​::​begin(c).
template <class C> constexpr auto cend(const C& c) noexcept(noexcept(std::end(c))) -> decltype(std::end(c));
7
#
Returns: std​::​end(c).
template <class C> constexpr auto rbegin(C& c) -> decltype(c.rbegin()); template <class C> constexpr auto rbegin(const C& c) -> decltype(c.rbegin());
8
#
Returns: c.rbegin().
template <class C> constexpr auto rend(C& c) -> decltype(c.rend()); template <class C> constexpr auto rend(const C& c) -> decltype(c.rend());
9
#
Returns: c.rend().
template <class T, size_t N> constexpr reverse_iterator<T*> rbegin(T (&array)[N]);
10
#
Returns: reverse_­iterator<T*>(array + N).
template <class T, size_t N> constexpr reverse_iterator<T*> rend(T (&array)[N]);
11
#
Returns: reverse_­iterator<T*>(array).
template <class E> constexpr reverse_iterator<const E*> rbegin(initializer_list<E> il);
12
#
Returns: reverse_­iterator<const E*>(il.end()).
template <class E> constexpr reverse_iterator<const E*> rend(initializer_list<E> il);
13
#
Returns: reverse_­iterator<const E*>(il.begin()).
template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c));
14
#
Returns: std​::​rbegin(c).
template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c));
15
#
Returns: std​::​rend(c).

27.8 Container access [iterator.container]

1
#
In addition to being available via inclusion of the <iterator> header, the function templates in [iterator.container] are available when any of the following headers are included: <array>, <deque>, <forward_­list>, <list>, <map>, <regex>, <set>, <string>, <unordered_­map>, <unordered_­set>, and <vector>.
template <class C> constexpr auto size(const C& c) -> decltype(c.size());
2
#
Returns: c.size().
template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;
3
#
Returns: N.
template <class C> constexpr auto empty(const C& c) -> decltype(c.empty());
4
#
Returns: c.empty().
template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;
5
#
Returns: false.
template <class E> constexpr bool empty(initializer_list<E> il) noexcept;
6
#
Returns: il.size() == 0.
template <class C> constexpr auto data(C& c) -> decltype(c.data()); template <class C> constexpr auto data(const C& c) -> decltype(c.data());
7
#
Returns: c.data().
template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;
8
#
Returns: array.
template <class E> constexpr const E* data(initializer_list<E> il) noexcept;
9
#
Returns: il.begin().