A Crash Course in Iterators

Before continuing with containers, we'd better pause briefly to explain iterators. Iterators are important because they allow us to move through elements of a container. There are a few kinds of iterators, so we'll discuss each of them in turn briefly now - the purpose here is to merely describe the different kinds of iterators available, to prepare you for the succeeding sections.

It is very important to understand the capabilities of each iterator because each container uses a certain type of iterator, and generic algorithms require certain iterators. Because containers can be used with generic algorithms to search or replace an element (for example), it is important to be able to distinguish which iterators can be used with which algorithms (more on this later - Introducing Generic Algorithms).

An iterator is a smart pointer; it enables us to keep track of where we are in a container. We can use operators, like ++ to move forward one element, as well as the usual operators that we'd use for pointer arithmetic. Well, almost; the kind of iterator we're using determines exactly what operators can be used. There is a hierarchy of iterators to be aware of that will carry us through the rest of this chapter - certain containers and algorithms have to use certain iterators, which we have to be strict about to avoid compile errors.

The different iterators available are described hierarchically below in figure (FIXME: fig. ref. to do.):

Each level possesses all the abilities of any iterators that are above it; so bidirectional iterators posses the abilities of forward and input/output iterators, whereas random access iterators possess all of the abilities of input/output, forward and bidirectional iterators, as well as its own operators.

Let's look at these each in turn:

Input iterators read elements they encounter element by element. Input iterators can read an element only once, thus if you attempt to reread the same position, it is not gauranteed that you'll read the same element. A good example of an input iterator would be reading characters from a stream, like when you read characters from the keyboard.

Similar to input iterators, output iterators write elements out element by element, and you cannot re-iterate over the same range of elements once you have started traversing them. Again, a good example of an output iterator would involve writing characters out to a stream - for example writing characters from the keyboard to standard output.

Forward iterators, as well as having all of the operations of input iterators and some of the operations of output iterators, can also refer to the same element more than once. Thus, you could traverse the range of elements from start to end, and then re-iterate over that range - for example finding an element in a vector. We can search for the first occurence of some value, and then search the container again starting from where we left off.

As well as having the properties of forward (and therefore, input and output) iterators, bidirectional iterators can also move backwards through a range of elements. Thus instead of being restricted to only searching forwards (as in the previous example), we can also step backwards through the container of elements.

Random access iterators have all the properties of bidirectional iterators (and therefore all of the properties of forward and input/output iterators), but can also access elements without having to traverse them in an element by element fashion. In addition, <, <=, > and >= operators are also provided for. Random access iterators are very powerful because they allow to do things like make binary searches.

A note about iterators and containers. Containers provide two member functions, begin() and end(), to enable us to see the start and end of the range. However, whilst begin() points to the first element of a container (if there exists at least one element), end() points past the last element of the container. This is represented diagramatically below for n elements:

Thus, for any container - vector, map, set, etc., providing there is at least one element, you can be assured begin() will point to the first, and end() will point past the last element. The reason for end() pointing past the last element is practicality; for example, the find algorithm returns an iterator to an object in the container (if it found one), else it returns end(), thus enabling us to check to see if the find failed or not (that is, if end() is returned, the element we're looking for does not exist within that container).

This concludes our (very) brief tour of iterators. Reference texts contain much more information (see STL Reference Section), although we'll not look any further at iterators. The following sections explore the various containers available, which make use of iterators.