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
|Move to the beginning of the range||All standard containers, and some collections that are not strictly containers, provide a
|Advance to the next element||Using pointer semantics, the prefix and postfix forms of the
|Return the referent||Also using pointer semantics, the dereference operator
|Interrogate the iterator to see if it is at the end of the range||Similar to the
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:
typedefon a standard container
- A pointer to an element in an array of objects
Iteratorclass 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
i->f is also valid.