27 Iterators library [iterators]

27.5 Iterator adaptors [predef.iterators]

27.5.1 Reverse iterators [reverse.iterators]

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]

The template parameter Iterator shall meet all the requirements of a Bidirectional Iterator.
Additionally, Iterator shall meet the requirements of a random access iterator 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();
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);
Effects: Initializes current with x.
template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
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);
Effects: Assigns u.base() to current.
Returns: *this.

27.5.1.3.3 Conversion [reverse.iter.conv]

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

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

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

27.5.1.3.5 operator-> [reverse.iter.opref]

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

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

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

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

constexpr reverse_iterator& operator--();
Effects: As if by ++current.
Returns: *this.
constexpr reverse_iterator operator--(int);
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;
Returns: reverse_­iterator(current-n).

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

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

27.5.1.3.10 operator- [reverse.iter.op-]

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

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

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

27.5.1.3.12 operator[] [reverse.iter.opindex]

constexpr unspecified operator[](difference_type n) const;
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);
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);
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);
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);
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);
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);
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());
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);
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);
Returns: reverse_­iterator<Iterator>(i).

27.5.2 Insert iterators [insert.iterators]

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.
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);
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);
Effects: As if by: container->push_­back(value);
Returns: *this.
back_insert_iterator& operator=(typename Container::value_type&& value);
Effects: As if by: container->push_­back(std​::​move(value));
Returns: *this.

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

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

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

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

27.5.2.2.5 back_­inserter [back.inserter]

template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
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);
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);
Effects: As if by: container->push_­front(value);
Returns: *this.
front_insert_iterator& operator=(typename Container::value_type&& value);
Effects: As if by: container->push_­front(std​::​move(value));
Returns: *this.

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

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

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

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

27.5.2.4.5 front_­inserter [front.inserter]

template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
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);
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);
Effects: As if by:
iter = container->insert(iter, value);
++iter;
Returns: *this.
insert_iterator& operator=(typename Container::value_type&& value);
Effects: As if by:
iter = container->insert(iter, std::move(value));
++iter;
Returns: *this.

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

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

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

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

27.5.2.6.5 inserter [inserter]

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

27.5.3 Move iterators [move.iterators]

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.
[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);
}
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]

The template parameter Iterator shall meet the requirements for an input iterator.
Additionally, if any of the bidirectional or random access traversal functions are instantiated, the template parameter shall meet the requirements for a Bidirectional Iterator or a Random Access Iterator, 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();
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);
Effects: Constructs a move_­iterator, initializing current with i.
template <class U> constexpr move_iterator(const move_iterator<U>& u);
Effects: Constructs a move_­iterator, initializing current with u.base().
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);
Effects: Assigns u.base() to current.
Requires: U shall be convertible to Iterator.

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

constexpr Iterator base() const;
Returns: current.

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

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

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

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

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

constexpr move_iterator& operator++();
Effects: As if by ++current.
Returns: *this.
constexpr move_iterator operator++(int);
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--();
Effects: As if by --current.
Returns: *this.
constexpr move_iterator operator--(int);
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;
Returns: move_­iterator(current + n).

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

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

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

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

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

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

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

constexpr unspecified operator[](difference_type n) const;
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);
Returns: x.base() == y.base().
template <class Iterator1, class Iterator2> constexpr bool operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
Returns: !(x == y).
template <class Iterator1, class Iterator2> constexpr bool operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
Returns: x.base() < y.base().
template <class Iterator1, class Iterator2> constexpr bool operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
Returns: !(y < x).
template <class Iterator1, class Iterator2> constexpr bool operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
Returns: y < x.
template <class Iterator1, class Iterator2> constexpr bool operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
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());
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);
Returns: x + n.
template <class Iterator> constexpr move_iterator<Iterator> make_move_iterator(Iterator i);
Returns: move_­iterator<Iterator>(i).