10.2 Iterators

An iterator is an abstraction of a pointer used for pointing into containers and other sequences. An ordinary pointer can point to different elements in an array. The ++ operator advances the pointer to the next element, and the * operator dereferences the pointer to return a value from the array. Iterators generalize the concept so that the same operators have the same behavior for any container, even trees and lists. See the <iterator> section of Chapter 13 for more details.

10.2.1 Iterator Categories

There are five categories of iterators:

Input

Permits you to read a sequence in one pass. The increment (++) operator advances to the next element, but there is no decrement operator. The dereference (*) operator returns an rvalue, not an lvalue, so you can read elements but not modify them.

Output

Permits you to write a sequence in one pass. 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

Permits unidirectional access to a sequence. You can refer to and assign to an item as many times as you want. You can use a forward iterator wherever an input iterator is required or wherever an output iterator is required.

Bidirectional

Similar to a forward iterator but also supports the -- (decrement) operator to move the iterator back one position.

Random access

Similar to a bidirectional iterator but also supports 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 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 value, but otherwise behaves as described previously. See Section 10.2.5 later in this chapter for details.

10.2.2 Iterator Safety

The most important point to remember about iterators is that they are inherently unsafe. Like pointers, an iterator can point to a container that has been destroyed or to an element that has been erased. You can advance an iterator past the end of the container the same way a pointer can point past the end of an array. With a little care and caution, however, iterators are safe to use.

The first key to safe use of iterators is to make sure a program never dereferences an iterator that marks the end of a range. Two iterators can denote a range of values, typically in a container. One iterator points to the start of the range and another marks the end of the range by pointing to a position one past the last element in the range. The mathematical notation of [first, last) tells you that the item that first points to is included in the range, but the item that last points to is excluded from the range.

A program must never dereference an iterator that points to one past the end of a range (e.g., last) because that iterator might not be valid. It might be pointing to one past the end of the elements of a container, for example.

Even a valid iterator can become invalid and therefore unsafe to use, for example if the item to which the iterator points is erased. The detailed descriptions in Chapter 13 tell you this information for each container type. In general, iterators for the node-based containers (list, set, multiset, map, multimap) become invalid only when they point to an erased node. Iterators for the array-based containers (deque, vector) become invalid when the underlying array is reallocated, which might happen for any insertion and for some erasures.

10.2.3 Special Iterators

Iterators are often used with containers, but they have many more uses. You can define iterators for almost any sequence of objects. The standard library includes several examples of non-container iterators, most notably I/O iterators and inserters.

At the lowest level, a stream is nothing more than a sequence of characters. At a slightly higher level, you can think of a stream as a sequence of objects, which would be read with operator>> or written with operator<<. Thus, the standard library includes the following I/O iterators: istreambuf_iterator, ostreambuf_iterator, istream_iterator, and ostream_iterator. Example 10-4 shows how to use streambuf iterators to copy one stream to another.

Example 10-4. Copying streams with streambuf iterators

template<typename charT, typename traits>
void copy(std::basic_ostream<charT,traits>& out,
          std::basic_istream<charT,traits>& in)
{
  std::copy(std::istreambuf_iterator<charT>(in),
            std::istreambuf_iterator<charT>(  ),
            std::ostreambuf_iterator<charT>(out));
}

Another kind of output iterator is an insert iterator, which inserts items into a sequence collection. The insert iterator requires a container and an optional iterator to specify the position where the new items should be inserted. You can insert at the back of a sequence with back_insert_iterator, at the front of a sequence with front_insert_iterator, or at a specific position in any kind of container with insert_iterator. Each of these iterator class templates has an associated function template that creates the iterator for you and lets the compiler deduce the container type. Example 10-5 shows how to read a series of numbers from a stream, store them in reverse order in a list, and print the list, one number per line.

Example 10-5. Inserting numbers in a vector

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

int main(  )
{
  using namespace std;

  list<double> data;
  copy(istream_iterator<double>(cin),
       istream_iterator<double>(  ),
       front_inserter(data));
  // Use the data...
  // Write the data, one number per line.
  copy(data.begin(  ), data.end(  ),
       ostream_iterator<double>(cout, "\n"));
}

10.2.4 Custom Iterators

The simplest way to write your own iterator is to derive from the iterator class template. Specify the iterator category as the first template parameter and the item type as the second parameter. In most cases, you can use the default template arguments for the remaining parameters. (See <iterator> in Chapter 13 for details.) The slist container from Example 10-1 needs an iterator and a const_iterator. The only difference is that a const_iterator returns rvalues instead of lvalues. Most of the iteration logic can be factored into a base class. Example 10-6 shows iterator and base_iterator; const_iterator is almost identical to iterator, so it is not shown.

Example 10-6. Writing a custom iterator

// The declaration for iterator_base is nested in slist.
class iterator_base : 
  public std::iterator<std::forward_iterator_tag, T> {
    friend class slist;
public:
  bool operator==(const iterator_base& iter) const
  { return node_ == iter.node_; }
  bool operator!=(const iterator_base& iter) const
  { return ! (*this == iter); }

protected:
  iterator_base(const iterator_base& iter)
  : prev_(iter.prev_), node_(iter.node_) {}
  iterator_base(slist::link_type* prev,
                slist::link_type* node)
  : prev_(prev), node_(node) {}
  // If node_ == 0, the iterator == end(  ).
  slist::link_type* node_;
  // A pointer to the node before node_ is needed to support erase(  ). If 
  // prev_ == 0, the iterator points to the head of the list.
  slist::link_type* prev_;
private:
  iterator_base(  );
};

// The declaration for iterator is nested in slist.
class iterator : public iterator_base {
  friend class slist;
public:
  iterator(const iterator& iter) : iterator_base(iter) {}
  iterator& operator++(  ) {              // Pre-increment
    this->prev_ = this->node_;
    this->node_ = this->node_->next;
    return *this;
  }
  iterator  operator++(int) {           // Post-increment
    iterator tmp = *this;
    operator++(  );
    return tmp;
  }
  T& operator*(  )         { return  this->node_->value; }
  T* operator->(  )        { return &this->node_->value; }
private:
  iterator(slist::link_type* prev, slist::link_type* node)
  : iterator_base(prev, node) {}
};

10.2.5 const_iterators

Every container must provide an iterator type and a const_iterator type. Functions such as begin and end return iterator when called on a non-const container and return const_iterator when called on a const container.

Note that a const_iterator (with underscore) is quite different from a const iterator (without underscore). A const iterator is a constant object of type iterator. Being constant, it cannot change, so it cannot advance to point to a different position. A const_iterator, on the other hand, is a non-const object of type const_iterator. It is not constant, so its value can change. The key difference between iterator and const_iterator is that iterator returns lvalues of type T, and const_iterator returns unmodifiable objects, either rvalues or const lvalues of type T. The standard requires that a plain iterator be convertible to const_iterator, but not vice versa.

One problem is that some members of the standard containers (most notably erase and insert) take iterator as a parameter, not const_iterator. If you have a const_iterator, you cannot use it as an insertion or erasure position.

Another problem is that it might be difficult to compare an iterator with a const_iterator. If the compiler reports an error when you try to compare iterators for equality or inequality, try swapping the order of the iterators, that is, if a == b fails to compile, try b == a. Most likely, the problem is that b is a const_iterator and a is a plain iterator. By swapping the order, you let the compiler convert a to a const_iterator and allow the comparison.

For a full explanation of how best to work with const_iterators, see Scott Meyers's Effective STL (Addison-Wesley).

10.2.6 Reverse Iterators

Every container that supports bidirectional or random access iterators also provides reverse iterators, that is, iterators that start with the last element and "advance" toward the first element of the container. These iterators are named reverse_iterator and const_reverse_iterator.

The standard library includes the reverse_iterator class template as a convenient way to implement the reverse_iterator type. The reverse_iterator class template is an iterator adapter that runs in the reverse direction of the adapted iterator. The adapted iterator must be a bidirectional or random access iterator. You can obtain the adapted iterator, given a reverse iterator, by calling the base function.

On paper, the reverse iterator seems like a good idea. After all, a bidirectional iterator can run in two directions. There is no reason why an iterator adapter could not implement operator++ by calling the adapted iterator's operator-- function.

Reverse iterators share a problem with const_iterators, namely that several members, such as insert and erase, do not take an iterator template parameter but require the exact iterator type, as declared in the container class. The reverse_iterator type is not accepted, so you must pass the adapted iterator instead, which is returned from the base function.

As an insertion point, the base iterator works fine, but for erasing, it is one off from the desired position. The solution is to increment the reverse iterator, then call base, as shown in Example 10-7.

Example 10-7. A reverse iterator

int main(  )
{
  std::list<int> l;
  l.push_back(10); l.push_back(42); l.push_back(99);
  print(l);
  std::list<int>::reverse_iterator ri;
  ri = std::find(l.rbegin(  ), l.rend(  ), 42);
  l.insert(ri.base(  ), 33);
  // OK: 33 inserted before 42, from the point of view of a reverse iterator,
  // that is, 33 inserted after 42

  ri = std::find(l.rbegin(  ), l.rend(  ), 42);
  l.erase(ri.base(  ));
  // Oops! Item 33 is deleted, not item 42.

  ri = std::find(l.rbegin(  ), l.rend(  ), 42);
  l.erase((++ri).base(  ));
  // That's right! In order to delete the item ri points to, you must advance ri
  // first, then delete the item.
}

For a full explanation of how best to work with reverse iterators, see Scott Meyer's Effective STL (Addison-Wesley).