What Is an Iterator in C++, Part 1
Pages: 1, 2, 3, 4

What Is an Iterator?

So, what's really going on with the syntax? If vector<int>::const_iterator can be a typedef for some other type, then what is the actual type of the iterator?

The answer is shamelessly dodgy: it depends. As far as the standard containers go, the standard does not specify exactly what an iterator is. What it does say is that, for example, the class vector has to at least have a public typedef that looks like the following, where the token unspecified is a type that can be whatever the implementation wants:

// In <vector>, within the declaration of vector
typedef unspecified iterator;
typedef unspecified const_iterator;

Your favorite standard library implementation can use any type it wants in place of unspecified, so long as that type meets the strict requirements for the operations it must provide as defined by the standard. These requirements, apart from those I enumerated a moment ago, are dictated by the category of the iterator provided by the container. Categories are collections of requirements that describe the different forms of iterator, and they are the subjects of the next section. Allowing implementations to choose their iterator type permits flexibility to use different approaches in different libraries.

All categories satisfy the requirements defined by the iterator pattern, but, as I said, not literally. Table 1 explains how the iterators in the C++ standard library satisfy the requirements of the pattern.

Table 1. How C++ meets iterator requirements

Requirement C++ Manifestation
Move to the beginning of the range All standard containers, and some collections that are not strictly containers, provide a begin member function, which returns an iterator that refers to the first element in the container, if it exists.
Advance to the next element Using pointer semantics, the prefix and postfix forms of the ++ operator move the iterator to the next element. Some iterator categories also support --, -=, +=, +, and - operators.
Return the referent Also using pointer semantics, the dereference operator * is used to return the referent. For example, if p is an iterator, then x = *p would assign the value referred to by p to x (assuming x and the referent are compatible types).
Interrogate the iterator to see if it is at the end of the range Similar to the begin member function, there is an end member function on all standard containers that returns an iterator that refers to one past the end of the container. Dereferencing this iterator yields undefined behavior, but you can compare the value returned by end to the current iterator to test if you are done iterating through the range.

The definition I usually read for C++ iterators is something like, "a generalization of a pointer", or, "an abstraction of a pointer." Both of these are technically correct, but somewhat high-level. Here's a more concrete one: an iterator is any type that behaves like an iterator. What this means is that any type that supports the interface described in Table 1 is an iterator, including a pointer to an element in a plain, static array. The following types are iterators:

  • An iterator or const_iterator typedef on a standard container
  • A pointer to an element in an array of objects
  • Your Iterator class that you will read about in the second part of this article

But it does not mean that these types are equivalent, nor does it mean that they all inherit from a common base class. It means that you can use each one of these with pointer semantics: if i is an iterator, then *i returns the object referred to by the iterator; i++ advances the iterator to the next element; and where (*i).f is valid, meaning i refers to something that has a member function or variable named f, i->f is also valid.

Pages: 1, 2, 3, 4

Next Pagearrow