13.31 <iterator>

The <iterator> header declares classes and templates for defining and using iterators. (See Chapter 10.) Iterators are especially important when using the standard algorithms in <algorithm>.

An iterator gives a program access to the contents of a container or other sequence, such as an I/O stream. You can think of an iterator as an abstraction of a pointer; the syntax for using iterators resembles that of pointers. Conceptually, an iterator points to a single element in a container or sequence and can be advanced to the next element with the ++ (increment) operator. The unary * (dereference) operator returns the element that the iterator points to. Iterators (except for output iterators) can be compared: two iterators are equal if they point to the same position in the same sequence, or if they both point to one position past the end of the same sequence.

There are five categories of iterators:

Input iterators

Permit one pass to read a sequence. The increment operator advances to the next element, but there is no decrement operator. The dereference operator does not return an lvalue, so you can read elements but not modify them.

Output iterators

Permit one pass to write a sequence. The increment operator advances to the next element, but there is no decrement operator. You can dereference an element only to assign a value to it. You cannot compare output iterators.

Forward iterators

Are like a combination of an input and an output iterator. You can use a forward iterator anywhere an input iterator is required or where an output iterator is required. A forward iterator, as its name implies, permits unidirectional access to a sequence. You can refer to a single element and modify it multiple times before advancing the iterator.

Bidirectional iterators

Are like forward iterators but also support the decrement operator (--) to move the iterator backward by one position.

Random access iterators

Are like bidirectional iterators but also support the [] (subscript) operator to access any index in the sequence. Also, you can add or subtract an integer to move a random access iterator by more than one position at a time. Subtracting two random access iterators yields an integer distance between them. Thus, a random access iterator is most like a conventional pointer, and, in fact, a pointer can be used as a random access iterator.

An input, forward, bidirectional, or random access iterator can be a const_iterator. Dereferencing a const_iterator yields a constant (an rvalue or a const lvalue). Chapter 10 discusses const_iterators in more depth.

An iterator can point to any element in a sequence or to one position past the end. You cannot dereference an iterator that points to one past the end, but you can compare it with other iterators (provided it is not an output iterator) or, if it is a bidirectional or random access iterator, decrease its position so it points to a valid element of the sequence.

Iterators are often used in ranges. A range has two iterators: a starting point and an ending point. The end iterator typically points to one position past the last element in the range. Thus, a range is often written using the mathematical notation of [first, last), in which the square bracket means first is included in the range, and the parenthesis means last is excluded from the range.

Like ordinary pointers, iterators can be uninitialized or otherwise have invalid values, such as x.begin( ) - 1, in which x is any container. It is your responsibility to ensure that you dereference only valid iterators, that you don't let iterators run past their valid end-points, and so on.

To create your own iterator class, see the iterator class template.

template <typename InputIterator, typename Distance>
  void advance(InputIterator& i, Distance n);

The advance function template advances an input iterator i by a distance n. If the iterator is bidirectional or random access, n can be negative. If the iterator is random access, the advance function is specialized as i + n; other iterators apply the ++ operator n times (or -- for a bidirectional iterator when n is negative).

See Also

distance function template

template <typename 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=(typename Container::const_reference value);
  back_insert_iterator<Container>& operator*(  );
  back_insert_iterator<Container>& operator++(  );
  back_insert_iterator<Container> operator++(int);
};

The back_insert_iterator class template implements an output iterator that stores elements in a container by calling the container's push_back function. The most convenient way to create a back_insert_iterator object is to use the back_inserter function template.

The way back_insert_iterator works seems slightly unconventional, although it is perfectly reasonable for an output iterator: the * operator returns the iterator, not an element of the container. Thus, the expression *iter = value assigns value to the iterator itself. The iterator's assignment operator appends value to the underlying container by calling the container's push_back function. Thus, the iterator does not maintain any notion of a position, and the increment operator is a no-op.

The following are the member functions of back_insert_iterator:

explicit back_insert_iterator(Container& x)

Initializes the container member with &x.

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

Calls container->push_back(value). The return value is *this.

back_insert_iterator<Container>& operator*( )

Returns *this.

back_insert_iterator<Container>& operator++( )

back_insert_iterator<Container> operator++(int)

Returns *this with no side effects.

See Also

back_inserter function template, front_insert_iterator class template, insert_iterator class template

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

The back_inserter function template constructs a back_insert_iterator object for the container x. Example 13-18 shows how to use back_inserter to read integers from a file into a vector.

Example

Example 13-18. Using back_inserter to add numbers to a vector

std::ifstream in("experiment.dat");
std::vector<int> data;
std::copy(std::istream_iterator<int>(in),
          std::istream_iterator<int>(  ),
          std::back_inserter(data));

See Also

back_insert_iterator class template, front_inserter function template, inserter function template

struct bidirectional_iterator_tag :
  public forward_iterator_tag {};

Use the bidirectional_iterator_tag class as the iterator category when declaring a new bidirectional iterator class. When writing a generic algorithm or similar function, you can use the iterator's category to write specialized implementations for different kinds of iterators. See Example 13-19 (under the distance function template).

See Also

bidirectional_iterator_tag class, forward_iterator_tag class, input_iterator_tag class, iterator class template, output_iterator_tag class, random_access_iterator_tag class

template<typename InputIterator>
  typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

The distance function returns the number of elements between first and last. The function is specialized for random access iterators to use the - operator; for other input iterators, the function applies the ++ operator to first until first == last. The behavior is undefined if first and last refer to different containers or if last points to an element earlier than first.

Example 13-19 shows a simple implementation of the distance function. The first specialized implementation works for any iterator (except output iterators, which do not support comparison with the != operator). The second one works only with random access iterators and uses the subtraction operator to compute the distance in constant time. The compiler picks the more specialized function when it can, so random access iterators can compute distances in constant time, compared to linear time for other iterators.

Example

Example 13-19. A simple implementation of distance

namespace std {
  template<typename InputIter>
  typename iterator_traits<InputIter>::difference_type
  specialize_distance(InputIter first, InputIter last, ...)
  {
    typename iterator_traits<InputIter>::difference_type n;
    for (n = 0; first != last; ++first)
      ++n;
    return n;
  }
   
  template<typename InputIter>
  typename iterator_traits<InputIter>::difference_type
  specialize_distance(InputIter first, InputIter last,
                      random_access_iterator_tag)
  {
    return last - first;
  }
   
  template<typename InputIter>
  typename iterator_traits<InputIter>::difference_type
  distance(InputIter first, InputIter last)
  {
    return specialize_distance(first, last,
      iterator_traits<InputIter>::iterator_category(  ));
  }
}

See Also

advance function template

struct forward_iterator_tag : public input_iterator_tag {};

Use the forward_iterator_tag class as the iterator category when declaring a new forward iterator class. When writing a generic algorithm or similar function, you can use the iterator's category to write specialized implementations for different kinds of iterators. See Example 13-19 (under the distance function template).

See Also

bidirectional_iterator_tag class, forward_iterator_tag class, input_iterator_tag class, iterator class template, output_iterator_tag class, random_access_iterator_tag class

template <typename 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=(typename Container::const_reference value);
  front_insert_iterator<Container>& operator*(  );
  front_insert_iterator<Container>& operator++(  );
  front_insert_iterator<Container> operator++(int);
};

The front_insert_iterator class template implements an output iterator that stores elements in a container by calling the container's push_front function. The most convenient way to create a front_insert_iterator object is to use the front_inserter function template.

The way front_insert_iterator works seems slightly unconventional, although it is perfectly reasonable for an output iterator: the * operator returns the iterator, not an element of the container. Thus, the expression *iter = value assigns value to the iterator itself. The iterator's assignment operator adds value to the underlying container by calling the container's push_front function. Thus, the iterator does not maintain any notion of a position, and the increment operator is a no-op.

The following are the member functions of front_insert_iterator:

explicit front_insert_iterator(Container& x)

Initializes the container member with &x.

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

Calls container->push_front(value). The return value is *this.

front_insert_iterator<Container>& operator*( )

Returns *this.

front_insert_iterator<Container>& operator++( )

front_insert_iterator<Container> operator++(int)

Returns *this with no side effects.

See Also

back_insert_iterator class template, front_inserter function template, insert_iterator class template

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

The front_inserter function template constructs a front_insert_iterator object for the container x. Example 13-20 shows how to use front_inserter to read integers from a file into a list in reverse order.

Example

Example 13-20. Using a front_inserter to add numbers to a list

std::ifstream in("experiment.dat");
std::list<int> data;
std::copy(std::istream_iterator<int>(in),
          std::istream_iterator<int>(  ),
          std::front_inserter(data));

See Also

back_inserter function template, front_insert_iterator class template, inserter function template

struct input_iterator_tag {};

Use the input_iterator_tag class as the iterator category when declaring a new input iterator class. When writing a generic algorithm or similar function, you can use the iterator's category to write specialized implementations for different kinds of iterators. See Example 13-19 (under the distance function template).

See Also

bidirectional_iterator_tag class, forward_iterator_tag class, iterator class template, output_iterator_tag class, random_access_iterator_tag class

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& cont, typename Container::iterator iter);
  insert_iterator<Container>&
    operator=(typename Container::const_reference value);
  insert_iterator<Container>& operator*(  );
  insert_iterator<Container>& operator++(  );
  insert_iterator<Container>& operator++(int);
};

The insert_iterator class template implements an output iterator that stores elements in a container by calling the container's insert function. The most convenient way to create a insert_iterator object is to use the inserter function template.

The way insert_iterator works seems slightly unconventional, although it is perfectly reasonable for an output iterator: the * operator returns the iterator, not an element of the container. Thus, the expression *iter = value assigns value to the iterator itself. The iterator's assignment operator adds value to the underlying container by calling the container's insert function. Thus, the iterator does not maintain any notion of a position, and the increment operator is a no-op.

The following are the member functions of insert_iterator:

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

Initializes the container member with &x and iter with i. Thus, the elements to be inserted in the container will be inserted at position i.

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

Assigns a value to an element in the iterator's container, performing the equivalent of the following:

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

insert_iterator<Container>& operator*( )

Returns *this.

insert_iterator<Container>& operator++( )

insert_iterator<Container> operator++(int)

Returns *this with no side effects.

See Also

back_insert_iterator class template, front_insert_iterator class template, inserter function template

template <typename Container, typename Iterator>
  insert_iterator<Container>
    inserter(Container& x, Iterator i);

The inserter function template constructs an insert_iterator object for the container x to insert items starting at position i. Figure 13-22 illustrates a simple use of the inserter function.

Figure 13-22. Using inserter to insert a vector in the middle of another vector

See Also

back_inserter function template, front_inserter function template, insert_iterator class template

template <typename T, typename charT = char, 
          typename traits = char_traits<charT>, typename Distance = ptrdiff_t>
class istream_iterator :
  public iterator<input_iterator_tag,
    T, Distance, const T*, const T&>
{
public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef basic_istream<charT,traits> istream_type;
  istream_iterator(  );
  istream_iterator(istream_type& stream);
  istream_iterator(const istream_iterator<T,charT,traits,Distance>& x);
  ~istream_iterator(  );
  const T& operator*(  ) const;
  const T* operator->(  ) const;
  istream_iterator<T,charT,traits,Distance>& operator++(  );
  istream_iterator<T,charT,traits,Distance> operator++(int);
};

The istream_iterator class template wraps an input iterator around an input stream (an instance of basic_istream), making the stream appear to be a sequence of items, each of type T.

Example 13-20 (under the front_inserter function template) shows how an istream_iterator can be used to read a series of integers from a file.

The following are the member functions of istream_iterator:

istream_iterator( )

Constructs an istream_iterator that denotes the end of the stream. End-of-stream iterators are equal to each other and are not equal to any other istream_iterator.

istream_iterator(istream_type& stream)

Constructs an istream_iterator to read from a stream. The constructor might read the first item from the stream. An istream_iterator that wraps a stream is equal to an end-of-stream iterator when stream.eof( ) is true.

istream_iterator(const istream_iterator<T,charT,traits,Distance>& iter)

Constructs a copy of iter. Note that two istream_iterator objects are the same (operator== is true) if they point to the same stream object.

const T& operator*( ) const

Returns the item that was read most recently from the stream.

const T* operator->( ) const istream_iterator<T,charT,traits,Distance>& operator++( )

Returns a pointer to the item that was read most recently from the stream.

istream_iterator<T,charT,traits,Distance>operator++(int)

Reads the next item from the stream using operator>>. The return value is *this.

See Also

istreambuf_iterator class template, ostream_iterator class template, basic_istream in <istream>

template<typename charT, typename traits=char_traits<charT> >
class istreambuf_iterator :
  public iterator<input_iterator_tag, charT, typename traits::off_type, charT*,
                  charT&>
{
public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef typename traits::int_type int_type;
  typedef basic_streambuf<charT,traits> streambuf_type;
  typedef basic_istream<charT,traits> istream_type;
  class proxy; // Exposition only

  istreambuf_iterator(  ) throw(  );
  istreambuf_iterator(istream_type& s) throw(  );
  istreambuf_iterator(streambuf_type* s) throw(  );
  istreambuf_iterator(const proxy& p) throw(  );
  charT operator*(  ) const;
  istreambuf_iterator<charT,traits>& operator++(  );
  proxy operator++(int);
  bool equal(istreambuf_iterator& b) const;
};

The istreambuf_iterator class template wraps a stream buffer object (instance of basic_streambuf) as an input iterator to read characters from the stream buffer. Example 13-21 shows how to use streambuf_iterators to copy files.

Examples

Example 13-21. Copying files using streambuf iterators

void copyfile(const char* from, const char* to)
{
  std::ifstream in(from);
  std::ofstream out(to);
   
  std::copy(std::istreambuf_iterator<char>(in),
            std::istreambuf_iterator<char>(  ),
            std::ostreambuf_iterator<char>(out));
}

The post-increment operator (++) returns a proxy object, which is an object that stands in for the istreambuf_iterator object. Its use is largely transparent, and you rarely need to think about it. The definition and name of the proxy class are implementation-defined, but the class has at least the capability to return the input character and the underlying stream buffer. This section assumes that the class name is proxy. Example 13-22 shows a prototypical implementation of proxy.

Example 13-22. A trivial implementation of the proxy class

template<typename charT, typename traits=char_traits<charT> >
class istreambuf_iterator<charT, traits>::proxy
{
  friend template<typename charT, typename traits>
    class istreambuf_iterator<charT,traits>;
  charT keep;
  basic_streambuf<charT,traits>* sbuf;
  proxy(charT c, basic_streambuf<charT,traits>* sbuf);
    : keep(c), sbuf(sbuf) {}
public:
  charT operator*(  ) { return keep; }
};

In the following descriptions of the member functions of istreambuf_iterator, the data member sbuf is a pointer to the iterator's stream buffer. The sbuf member serves only to keep the function descriptions clear and simple; the class is not required to have such a member, nor is the class required to have a member with that name.

istreambuf_iterator( ) throw( )

Constructs the end-of-stream iterator.

istreambuf_iterator(istream_type& s) throw( )

istreambuf_iterator(streambuf_type* sb) throw( )

istreambuf_iterator (const proxy& p) throw( )

Constructs an istreambuf_iterator and initializes sbuf to s.rdbuf( ), sb, or p.sbuf. If sb == 0, an end-of-stream iterator is constructed.

charT operator*( ) const

Returns sbuf->sgetc( ).

istreambuf_iterator<charT,traits>& operator++( )

Calls sbuf->sbumpc( ) and returns *this.

proxy operator++ (int)

Returns proxy(sbuf->sbumpc( ), sbuf).

bool equal(istreambuf_iterator& b) const

Returns true if both iterators are end-of-stream iterators or if neither iterator is an end-of-stream iterator. The iterators do not have to use the same stream buffer.

See Also

istream_iterator class template, ostreambuf_iterator class template, basic_streambuf in <streambuf>

template<typename Category, typename T, typename Difference = ptrdiff_t,
         typename Pointer = T*, typename Reference = T&>
struct iterator{
  typedef T value_type;
  typedef Difference difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
  typedef Category iterator_category;
};

The iterator class template is a convenient base-class template to use when implementing your own iterator.

The following are the template parameters, which are all type parameters:

Category

Must be one of the five iterator category tags: bidirectional_iterator_tag, forward_iterator_tag, input_iterator_tag, output_iterator_tag, or random_access_iterator_tag.

T

The element type. It can be void for an output iterator because you cannot dereference an output iterator.

Difference

An integral type that represents the distance between two iterators. It can be void for an output iterator because you cannot measure the distance between two output iterators. This parameter is optional; the default is ptrdiff_t, which is suitable for typical pointer-like iterators.

Pointer

The pointer-to-element type. This parameter is optional; the default is T*, which is correct for most iterators.

Reference

The reference-to-element type. This parameter is optional; the default is T&, which is correct for most iterators.

See Also

iterator_traits class template, reverse_iterator class template

template<typename Iterator>
struct iterator_traits{
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
  typedef typename Iterator::iterator_category iterator_category;
};

The iterator_traits class template declares traits for an iterator. If you use the iterator class template as the base for your custom iterator, you don't need to specialize iterator_traits. If you are writing a custom container or algorithm, you should always use iterator_traits to obtain the traits of an iterator. If you use a plain pointer as an iterator, the standard library specializes iterator_traits for you. See the next subsection.

If you write your own specialization, the iterator_category type must be one of the five iterator tag classes. (See the iterator class template.) For an output iterator, difference_type and value_type are void.

When writing a generic algorithm or other function that uses iterators, you can use iterator_traits to specialize the behavior for certain kinds of iterators. See Example 13-19 (under distance), which shows how iterator traits can be used to improve the performance of a function.

See Also

iterator class template

template<typename  T>
struct iterator_traits<T*>{
  typedef ptrdiff_t difference_type;
  typedef T value_type;
  typedef T* pointer;
  typedef T& reference;
  typedef random_access_iterator_tag iterator_category;
};

The iterator_traits class template is specialized for pointers. This specialization lets you use a pointer as a random access iterator.

See Also

iterator_traits class template

template<typename  T>
struct iterator_traits<const T*>{
  typedef ptrdiff_t difference_type;
  typedef T value_type;
  typedef const T* pointer;
  typedef const T& reference;
  typedef random_access_iterator_tag iterator_category;
};

The iterator_traits class template is specialized for pointers to const. This specialization lets you use a pointer as a random access iterator.

See Also

iterator_traits class template

template <typename T, typename charT = char,  
          typename traits = char_traits<charT> >
class ostream_iterator :
  public iterator<output_iterator_tag,void,void,void,void>
{
public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef basic_ostream<charT,traits> ostream_type;
  ostream_iterator(ostream_type& s);
  ostream_iterator(ostream_type& s, const charT* delimiter);
  ostream_iterator(const ostream_iterator<T,charT,traits>& x);
  ~ostream_iterator(  );
  ostream_iterator<T,charT,traits>& operator=(const T& value);
  ostream_iterator<T,charT,traits>& operator*(  );
  ostream_iterator<T,charT,traits>& operator++(  );
  ostream_iterator<T,charT,traits>& operator++(int);
};

The ostream_iterator class template wraps an output iterator around an output stream (instance of basic_ostream), making the stream appear to be a sequence of items, each of type T. For example, suppose you have a vector of data. You can print the data, one number per line, by using an ostream_iterator:

std::vector<int> data;
 . . .  // Acquire data.
std::copy(data.begin(  ), data.end(  ), 
          std::ostream_iterator(std::cout, "\n"));

The following are the member functions of ostream_iterator:

ostream_iterator(ostream_type& stream)

ostream_iterator(ostream_type& stream, const charT* delimiter)

ostream_iterator(const ostream_iterator<T,charT,traits>& x)

Prepares to write items to stream. If delimiter is present, it will be written after each item. The copy constructor copies the reference to the stream and to the delimiter from x.

ostream_iterator<T,charT,traits>& operator=(const T& value)

Writes value to the stream using operator<<. If the ostream_iterator has a delimiter, it is written after value. The return value is *this.

ostream_iterator<T,charT,traits>& operator*( )

Returns *this.

ostream_iterator<T,charT,traits>& operator++( )

ostream_iterator<T,charT,traits>& operator++(int)

Returns *this with no side effects.

See Also

istream_iterator class template, ostreambuf_iterator class template, basic_ostream in <ostream>

template<typename charT, typename traits=char_traits<charT> >
class ostreambuf_iterator :
  public iterator<output_iterator_tag,void,void,void,void>
{
public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef basic_streambuf<charT,traits> streambuf_type;
  typedef basic_ostream<charT,traits> ostream_type;

  ostreambuf_iterator(ostream_type& s) throw(  );
  ostreambuf_iterator(streambuf_type* s) throw(  );
  ostreambuf_iterator& operator=(charT c);
  ostreambuf_iterator& operator*(  );
  ostreambuf_iterator& operator++(  );
  ostreambuf_iterator& operator++(int);
  bool failed(  ) const throw(  );
};

The ostreambuf_iterator class template wraps a basic_streambuf object as an output iterator to write characters to the stream buffer. Example 13-21 (under istreambuf_iterator) shows how to use streambuf iterators to copy files.

In the following descriptions of the member functions of ostreambuf_iterator, the data member sbuf is a pointer to the iterator's stream buffer. The sbuf member serves only to keep the function descriptions clear and simple; the class is not required to have such a member, or a member with that name.

ostreambuf_iterator(ostream_type& s) throw( )

ostreambuf_iterator(streambuf_type* sb) throw( )

Saves the stream buffer s.rdbuf( ) or sb in sbuf.

ostreambuf_iterator& operator=(charT c)

Calls sbuf->sputc(c) (only if failed( ) returns false) and returns *this.

ostreambuf_iterator& operator*( )

Returns *this.

ostreambuf_iterator& operator++( )

ostreambuf_iterator& operator++(int)

Returns *this.

bool failed( ) const throw( )

Returns true if sbuf->sputc( ) ever returned traits::eof( ). Otherwise, it returns false.

See Also

istreambuf_iterator class template, ostream_iterator class template, basic_streambuf in <streambuf>

struct output_iterator_tag {};

Use the output_iterator_tag class as the iterator category when declaring a new output iterator class. When writing a generic algorithm or similar function, you can use the iterator's category to write specialized implementations for different kinds of iterators. See Example 13-19 (under the distance function template).

See Also

bidirectional_iterator_tag class, forward_iterator_tag class, input_iterator_tag class, iterator class template, random_access_iterator_tag class

struct random_access_iterator_tag :
  public bidirectional_iterator_tag {};

Use the random_access_iterator_tag class as the iterator category when declaring a new random access iterator class. When writing a generic algorithm or similar function, you can use the iterator's category to write specialized implementations for different kinds of iterators. See Example 13-19 (under the distance function template).

See Also

bidirectional_iterator_tag class, forward_iterator_tag class, input_iterator_tag class, iterator class template, output_iterator_tag class

template <typename 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>
{
protected:
  Iterator current;
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 <typename U>
  reverse_iterator(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);
  reference operator[](difference_type n) const;
};

The reverse_iterator class template is an adapter for a bidirectional or random access iterator to iterate the sequence in the opposite direction of the adapted iterator. In other words, if the adapted iterator advances from the first to the last item in a container, a reverse iterator starts with the last items and "advances" to the first item. In addition to the reverse_iterator template, there are also several function templates for the comparison and arithmetic (+ and -) operators.

The standard containers return reverse_iterator objects from the rbegin( ) and rend( ) functions. The following example shows a simple implementation of these functions:

reverse_iterator rbegin(  ) { return reverse_iterator(end(  )); }
reverse_iterator rend(  ) { return reverse_iterator(begin(  )); }

Because an iterator can point to one past the last item in a container but cannot point to one item before the first, a reverse iterator conceptually points to one item before the position to which the adapted iterator points. In other words, given an iterator, iter, which points to 42 in Example 13-23, if you construct a reverse iterator that adapts iter, the reverse iterator appears to point to 29. When you increment the reverse iterator, it decrements the adapted iterator. Thus, the "next" element in the sequence of the reverse iterator is 12. (The adapted iterator points to 29.) The adapted iterator is also called the base iterator. See Chapter 10 for a discussion of some of the interesting ramifications of using reverse_iterator.

Figure 13-23. How a reverse iterator works

The following member functions of reverse_iterator refer to adapted as the data member that stores the base( ) iterator. The adapted member is purely a convenience for the function descriptions and is not necessarily part of any real implementation of reverse_iterator:

reverse_iterator( )

Initializes the adapted data member with its default constructor.

explicit reverse_iterator(Iterator iter)

Initializes the adapted data member to iter.

template <typename U> reverse_iterator(const reverse_iterator<U>& ri)

Initializes the adapted data member to ri.base( ).

Iterator base( ) const

Returns the adapted iterator, adapted. Note that the adapted iterator points to one position after the reverse iterator's logical position.

reference operator*( ) const

Returns a reference to the item that the reverse iterator logically points to, which is one item before the item to which base( ) points. Thus, you can think of the dereference function working as follows:

reference operator*(  ) const {
  iterator_type tmp = base(  );
  --tmp;
  return *tmp;
}

pointer operator->( ) const

Returns a pointer to the item that the reverse iterator logically points to, that is, &(operator*( )).

reverse_iterator& operator++( )

Decrements adapted and returns *this.

reverse_iterator operator++(int)

Saves a copy of the current item (operator*( )), decrements adapted, and returns the saved item.

reverse_iterator& operator--( )

Increments adapted and returns *this.

reverse_iterator operator--(int)

Saves a copy of the current item (operator*( )), increments adapted, and returns the saved item.

reverse_iterator operator+(difference_type n) const

Returns reverse_iterator(base( ) - n).

reverse_iterator& operator+=(difference_type n)

Subtracts n from adapted and returns *this.

reverse_iterator operator-(difference_type n) const

Returns reverse_iterator(base( ) + n).

reverse_iterator& operator-=(difference_type n)

Adds n to adapted and returns *this.

reference operator[](difference_type n) const

Returns base( )[-n-1].

The following are several nonmember functions that compare reverse iterators and perform basic arithmetic such as finding the distance between two reverse iterators and advancing a reverse iterator by an integer:

template <typename Iterator>

bool operator==(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when the base iterators are equal, that is, x.base( ) == y.base( ).

template <typename Iterator>

bool operator!=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when x and y have different base iterators, that is, x.base( ) != y.base( ).

template <typename Iterator>

bool operator<(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when x is closer than y to the beginning of the sequence. Because x and y are reverse iterators, the function returns y.base( ) < x.base( ).

template <typename Iterator>

bool operator>(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when x is farther than y from the beginning of the sequence. Because x and y are reverse iterators, the function returns y.base( ) > x.base( ).

template <typename Iterator>

bool operator>=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when x is farther than y from the beginning of the sequence or x equals y. Because x and y are reverse iterators, the function returns y.base( ) >= x.base( ).

template <typename Iterator>

bool operator<=(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns true when x is closer than y to the beginning of the sequence or x equals y. Because x and y are reverse iterators, the function returns y.base( ) <= x.base( ).

template <typename Iterator>

typename reverse_iterator<Iterator>::difference_type

operator-(const reverse_iterator<Iterator>& x, const reverse_iterator<Iterator>& y)

Returns the distance between two reverse iterators, that is, y.base( ) - x.base( ).

template <typename Iter>

reverse_iterator<Iter>

operator+(typename reverse_iterator<Iter>::difference_type n, constreverse_iterator<Iter>& ri)

Advances a reverse iterator ri by n. This function is a counterpart to the operator+ member function, allowing you to write ri + n and n + ri, which yield the same result.

See Also

iterator class template, Chapter 10