Table of Contents

C++ Iterators

Iterators are used to access elements of a sequence, and can be used in a similar manner to pointers. For example, one might use an iterator to step through the elements of a vector.

The following code creates and uses an iterator with a vector:

    vector<int> the_vector;
    vector<int>::iterator the_iterator;
    for( int i=0; i < 10; i++ ) the_vector.push_back(i);
    int total = 0;
    the_iterator = the_vector.begin();
    while( the_iterator != the_vector.end() ) {
      total += *the_iterator;
    cout << "Total=" << total << endl;

Notice that you can access the elements of the container by dereferencing the iterator.

NOTES: You should prefer pre-increment operator (++iter) to post-increment operator (iter++)
if you are not going to use the old value.
Post-increment is generally implemented as follows:

  Iter operator++(int)
    Iter tmp(*this); // store the old value in a temporary object
    ++*this;         // call pre-increment
    return tmp;      // return the old value

Obviously, it's less efficient than pre-increment.

Iterator Categories

Not every kind of iterator has exactly the same abilities. Reading and writing require different abilities.
Random access is efficient and convenient for a vector, whereas it would be expensive for a list.
For this reason, iterators are classified into five categories according to their abilities:

Iterator CategoryDescriptionProvidersTag
InputRead values with forward movement. These can be incremented, compared, and dereferenced.istreaminput_iterator_tag
OutputWrite values with forward movement. These can be incremented and dereferenced.ostream, inserteroutput_iterator_tag
ForwardRead or write values with forward movement. These combine the functionality of input and output iterators with the ability to store the iterators value. slistforward_iterator_tag
BidirectionalRead and write values with forward and backward movement. These are like the forward iterators, but you can increment and decrement them.list, map, multimap, set, multisetbidirectional_iterator_tag
Random-accessRead and write values with random access. These are the most powerful iterators, combining the functionality of bidirectional iterators with the ability to do pointer arithmetic and pointer comparisons.array, deque, string, vectorrandom_access_iterator_tag

Each of the STL containers is associated with a category of iterator, and each of the STL algorithms uses a certain category of iterator.

For example, vectors are associated with random-access iterators, which means that they can use algorithms that require random access. Since random-access iterators encompass all of the characteristics of the other iterators, vectors can use algorithms designed for other iterators as well.

    vector<int> the_vector(10);
    // generate_n requires output_iterator
    generate_n(the_vector.begin(), 5, rand);
    // fill requires forward_iterator
    fill(the_vector.begin()+5, the_vector.end(), 100);
    // random_shuffle requires random_access_iterator
    random_shuffle(the_vector.begin(), the_vector.end());
    // copy requires input_iterator
    copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));
    // reverse_copy requires bidirectional_iterator
    reverse_copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));

Auxiliary Iterator Functions

The <iterator> header file defines two auxiliary functions.

  void advance( input_iterator& pos, Dist n );

advance() lets pos step n elements forward (or backward).
For bidirectional and random_access_iterators, n can be negative to step backward.
For random_access_iterators, advance() runs in constant time (simply calls pos+=n).
For all other iterators, advance() has linear complexity (calls ++pos n times).

  typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );

distance() returns the distance between two iterators.
For random_access_iterators, distance() runs in constant time (simply returns pos2 - pos1).
For all other iterators, distance() runs in linear time ( pos1 is incremented until it reaches pos2, and returns the number of incrementation).

Invalidating Iterators

Iterators to exisiting elements in a container can become invalidated when the container is changed. This makes changing the container while iterating it problematic. The containers offer different guarantees in this regard:

Related topics: