24 Iterators library [iterators]

24.5 Iterator adaptors [predef.iterators]

24.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).

24.5.1.1 Class template reverse_iterator [reverse.iterator]

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

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

    Iterator base() const;      // explicit
    reference operator*() const;
    pointer   operator->() const;

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

    reverse_iterator  operator+ (difference_type n) const;
    reverse_iterator& operator+=(difference_type n);
    reverse_iterator  operator- (difference_type n) const;
    reverse_iterator& operator-=(difference_type n);
    unspecified operator[](difference_type n) const;
  protected:
    Iterator current;
  private:
    Iterator deref_tmp;         // exposition only
  };

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

24.5.1.2 reverse_iterator requirements [reverse.iter.requirements]

The template parameter Iterator shall meet all the requirements of a Bidirectional Iterator ([bidirectional.iterators]).

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 global 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]).

24.5.1.3 reverse_iterator operations [reverse.iter.ops]

24.5.1.3.1 reverse_iterator constructor [reverse.iter.cons]

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.

explicit reverse_iterator(Iterator x);

Effects: Initializes current with x.

template <class U> reverse_iterator(const reverse_iterator<U> &u);

Effects: Initializes current with u.current.

24.5.1.3.2 reverse_iterator::operator= [reverse.iter.op=]

template <class U> reverse_iterator& operator=(const reverse_iterator<U>& u);

Effects: Assigns u.base() to current.

Returns: *this.

24.5.1.3.3 Conversion [reverse.iter.conv]

Iterator base() const; // explicit

Returns: current.

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

reference operator*() const;

Effects:

deref_tmp = current;
--deref_tmp;
return *deref_tmp;

Note: This operation must use an auxiliary member variable rather than a temporary variable to avoid returning a reference that persists beyond the lifetime of its associated iterator. (See [iterator.requirements].)  — end note ]

24.5.1.3.5 operator-> [reverse.iter.opref]

pointer operator->() const;

Returns: &(operator*()).

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

reverse_iterator& operator++();

Effects: -- current;

Returns: *this.

reverse_iterator operator++(int);

Effects:

reverse_iterator tmp = *this;
--current;
return tmp;

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

reverse_iterator& operator--();

Effects: ++current

Returns: *this.

reverse_iterator operator--(int);

Effects:

reverse_iterator tmp = *this;
++current;
return tmp;

24.5.1.3.8 operator+ [reverse.iter.op+]

reverse_iterator operator+(typename reverse_iterator<Iterator>::difference_type n) const;

Returns: reverse_iterator(current-n).

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

reverse_iterator& operator+=(typename reverse_iterator<Iterator>::difference_type n);

Effects: current -= n;

Returns: *this.

24.5.1.3.10 operator- [reverse.iter.op-]

reverse_iterator operator-(typename reverse_iterator<Iterator>::difference_type n) const;

Returns: reverse_iterator(current+n).

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

reverse_iterator& operator-=(typename reverse_iterator<Iterator>::difference_type n);

Effects: current += n;

Returns: *this.

24.5.1.3.12 operator[] [reverse.iter.opindex]

unspecified operator[]( typename reverse_iterator<Iterator>::difference_type n) const;

Returns: current[-n-1].

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

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

Returns: x.current == y.current.

24.5.1.3.14 operator< [reverse.iter.op<]

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

Returns: x.current > y.current.

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

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

Returns: x.current != y.current.

24.5.1.3.16 operator> [reverse.iter.op>]

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

Returns: x.current < y.current.

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

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

Returns: x.current <= y.current.

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

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

Returns: x.current >= y.current.

24.5.1.3.19 operator- [reverse.iter.opdiff]

template <class Iterator1, class Iterator2> auto operator-( const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) -> decltype(y.current - x.current);

Returns: y.current - x.current.

24.5.1.3.20 operator+ [reverse.iter.opsum]

template <class Iterator> reverse_iterator<Iterator> operator+( typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);

Returns: reverse_iterator<Iterator> (x.current - n).

24.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.

24.5.2.1 Class template back_insert_iterator [back.insert.iterator]

namespace std {
  template <class Container>
  class back_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;

  public:
    typedef Container container_type;
    explicit back_insert_iterator(Container& x);
    back_insert_iterator<Container>&
      operator=(const typename Container::value_type& value);
    back_insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    back_insert_iterator<Container>& operator*();
    back_insert_iterator<Container>& operator++();
    back_insert_iterator<Container>  operator++(int);
  };

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

24.5.2.2 back_insert_iterator operations [back.insert.iter.ops]

24.5.2.2.1 back_insert_iterator constructor [back.insert.iter.cons]

explicit back_insert_iterator(Container& x);

Effects: Initializes container with &x.

24.5.2.2.2 back_insert_iterator::operator= [back.insert.iter.op=]

back_insert_iterator<Container>& operator=(const typename Container::value_type& value);

Effects: container->push_back(value);

Returns: *this.

back_insert_iterator<Container>& operator=(typename Container::value_type&& value);

Effects: container->push_back(std::move(value));

Returns: *this.

24.5.2.2.3 back_insert_iterator::operator* [back.insert.iter.op*]

back_insert_iterator<Container>& operator*();

Returns: *this.

24.5.2.2.4 back_insert_iterator::operator++ [back.insert.iter.op++]

back_insert_iterator<Container>& operator++(); back_insert_iterator<Container> operator++(int);

Returns: *this.

24.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).

24.5.2.3 Class template front_insert_iterator [front.insert.iterator]

namespace std {
  template <class Container>
  class front_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
  protected:
    Container* container;

  public:
    typedef Container container_type;
    explicit front_insert_iterator(Container& x);
    front_insert_iterator<Container>&
      operator=(const typename Container::value_type& value);
    front_insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    front_insert_iterator<Container>& operator*();
    front_insert_iterator<Container>& operator++();
    front_insert_iterator<Container>  operator++(int);
  };

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

24.5.2.4 front_insert_iterator operations [front.insert.iter.ops]

24.5.2.4.1 front_insert_iterator constructor [front.insert.iter.cons]

explicit front_insert_iterator(Container& x);

Effects: Initializes container with &x.

24.5.2.4.2 front_insert_iterator::operator= [front.insert.iter.op=]

front_insert_iterator<Container>& operator=(const typename Container::value_type& value);

Effects: container->push_front(value);

Returns: *this.

front_insert_iterator<Container>& operator=(typename Container::value_type&& value);

Effects: container->push_front(std::move(value));

Returns: *this.

24.5.2.4.3 front_insert_iterator::operator* [front.insert.iter.op*]

front_insert_iterator<Container>& operator*();

Returns: *this.

24.5.2.4.4 front_insert_iterator::operator++ [front.insert.iter.op++]

front_insert_iterator<Container>& operator++(); front_insert_iterator<Container> operator++(int);

Returns: *this.

24.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).

24.5.2.5 Class template insert_iterator [insert.iterator]

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

  public:
    typedef Container container_type;
    insert_iterator(Container& x, typename Container::iterator i);
    insert_iterator<Container>&
      operator=(const typename Container::value_type& value);
    insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    insert_iterator<Container>& operator*();
    insert_iterator<Container>& operator++();
    insert_iterator<Container>& operator++(int);
  };

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

24.5.2.6 insert_iterator operations [insert.iter.ops]

24.5.2.6.1 insert_iterator constructor [insert.iter.cons]

insert_iterator(Container& x, typename Container::iterator i);

Effects: Initializes container with &x and iter with i.

24.5.2.6.2 insert_iterator::operator= [insert.iter.op=]

insert_iterator<Container>& operator=(const typename Container::value_type& value);

Effects:

iter = container->insert(iter, value);
++iter;

Returns: *this.

insert_iterator<Container>& operator=(typename Container::value_type&& value);

Effects:

iter = container->insert(iter, std::move(value));
++iter;

Returns: *this.

24.5.2.6.3 insert_iterator::operator* [insert.iter.op*]

insert_iterator<Container>& operator*();

Returns: *this.

24.5.2.6.4 insert_iterator::operator++ [insert.iter.op++]

insert_iterator<Container>& operator++(); insert_iterator<Container>& operator++(int);

Returns: *this.

24.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).

24.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 dereference operator implicitly converts the value returned by the underlying iterator's dereference operator to an rvalue reference. 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 ]

24.5.3.1 Class template move_iterator [move.iterator]

namespace std {
  template <class Iterator>
  class move_iterator {
  public:
    typedef Iterator                                              iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type   difference_type;
    typedef Iterator                                              pointer;
    typedef typename iterator_traits<Iterator>::value_type        value_type;
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef value_type&&                                          reference;

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

    iterator_type base() const;
    reference operator*() const;
    pointer operator->() const;

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

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

  private:
    Iterator current;   // exposition only
  };

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

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

24.5.3.2 move_iterator requirements [move.iter.requirements]

The template parameter Iterator shall meet the requirements for 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.

24.5.3.3 move_iterator operations [move.iter.ops]

24.5.3.3.1 move_iterator constructors [move.iter.op.const]

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.

explicit move_iterator(Iterator i);

Effects: Constructs a move_iterator, initializing current with i.

template <class U> move_iterator(const move_iterator<U>& u);

Effects: Constructs a move_iterator, initializing current with u.base().

Requires: U shall be convertible to Iterator.

24.5.3.3.2 move_iterator::operator= [move.iter.op=]

template <class U> move_iterator& operator=(const move_iterator<U>& u);

Effects: Assigns u.base() to current.

Requires: U shall be convertible to Iterator.

24.5.3.3.3 move_iterator conversion [move.iter.op.conv]

Iterator base() const;

Returns: current.

24.5.3.3.4 move_iterator::operator* [move.iter.op.star]

reference operator*() const;

Returns: std::move(*current).

24.5.3.3.5 move_iterator::operator-> [move.iter.op.ref]

pointer operator->() const;

Returns: current.

24.5.3.3.6 move_iterator::operator++ [move.iter.op.incr]

move_iterator& operator++();

Effects: ++current.

Returns: *this.

move_iterator operator++(int);

Effects:

move_iterator tmp = *this;
++current;
return tmp;

24.5.3.3.7 move_iterator::operator-- [move.iter.op.decr]

move_iterator& operator--();

Effects: --current.

Returns: *this.

move_iterator operator--(int);

Effects:

move_iterator tmp = *this;
--current;
return tmp;

24.5.3.3.8 move_iterator::operator+ [move.iter.op.+]

move_iterator operator+(difference_type n) const;

Returns: move_iterator(current + n).

24.5.3.3.9 move_iterator::operator+= [move.iter.op.+=]

move_iterator& operator+=(difference_type n);

Effects: current += n.

Returns: *this.

24.5.3.3.10 move_iterator::operator- [move.iter.op.-]

move_iterator operator-(difference_type n) const;

Returns: move_iterator(current - n).

24.5.3.3.11 move_iterator::operator-= [move.iter.op.-=]

move_iterator& operator-=(difference_type n);

Effects: current -= n.

Returns: *this.

24.5.3.3.12 move_iterator::operator[] [move.iter.op.index]

unspecified operator[](difference_type n) const;

Returns: std::move(current[n]).

24.5.3.3.13 move_iterator comparisons [move.iter.op.comp]

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

Returns: x.base() == y.base().

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

Returns: !(x == y).

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

Returns: x.base() < y.base().

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

Returns: !(y < x).

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

Returns: y < x.

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

Returns: !(x < y).

24.5.3.3.14 move_iterator non-member functions [move.iter.nonmember]

template <class Iterator1, class Iterator2> 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> move_iterator<Iterator> operator+( typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);

Returns: x + n.

template <class Iterator> move_iterator<Iterator> make_move_iterator(const Iterator& i);

Returns: move_iterator<Iterator>(i).