Iterators

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Iterators

In this section we introduce an abstraction called an iterator. An iterator provides a means for visiting one-by-one all the objects in a container. Iterators are an alternative to using the visitors described in Section . The basic idea is that for every concrete container class we will also implement a related concrete iterator derived from an abstract Iterator class.

Program gives the declaration of the abstract Iterator class. It defines an interface comprised of a virtual destructor and four pure virtual member functions--Reset, IsDone and two overloaded operators.

program5041
Program: Iterator Class Definition

The Iterator class is intended to be used as the base class from which other classes are derived in a polymorphic class hierarchy. Consequently, the destructor is declared as a virtual member function. Since the Iterator class is an abstract class which has no member variables, the behavior of the destructor trivial--it does nothing.

In addition to the destructor, the Iterator class interface comprises the Reset and IsDone functions and two overloaded operators--operator* and operator++. In order to understand the desired semantics, it is best to consider first an example which illustrates the use of an iterator.

Consider the implementation of a concrete container class, say SomeContainer, which is derived from the abstract base class Container. Associated with this container class is a concrete iterator, say SomeIterator, which is derived from the abstract base class Iterator. The following code fragment serves to illustrate the use of the iterator to visit one-by-one the objects contained in the container:

SomeContainer c;
Iterator& i = c.NewIterator ();
while (!i.IsDone ()) {
    cout << *i << endl;
    ++i;
}
delete &i;

The NewIterator function of the SomeContainer class is defined as follows:

Iterator& SomeContainer::NewIterator () const
    { return *new SomeIterator (*this); }

I.e., given an instance c of SomeContainer, the call

c.NewIterator ();

results in the creation of a new instance of SomeIterator associated with container c.

In order to have the desired effect, the member functions IsDone, operator*, and operator++, must have the following behaviors:

IsDone: The IsDone member function is called in the loop-termination test of the while statement. The IsDone function returns false if the iterator still refers to an object in the container, and true when the container has been exhausted. I.e., if all of the contained objects have been visited.
operator*: The pointer dereferencing operator, operator*, is used to access the object to which the iterator currently refers. If this function is called when the container has been exhausted, a reference to the NullObject instance is returned.
operator++: The pre-increment operator is used to advance the iterator to the next object in the container. If the container is exhausted, the increment operator has no effect on the iterator.

Given these semantics for the iterator operators, the program fragment shown above systematically visits all of the objects in the container and prints each one on its own line of the standard output file.

After an iterator has exhausted all the contained objects, it can be reset via the Reset function and used again like this:

Iterator& i = c.NewIterator ();
while (!i.IsDone ()) {
    cout << *i << endl;
    ++i;
}
i.Reset ()
while (!i.IsDone ()) {
    cout << *i << endl;
    ++i;
}
delete &i;

One of the advantages of using an iterator object which is separate from the container is that it is possible then to have more than one iterator associated with a given container. This provides greater flexibility than possible using a visitor, since only one visitor can be accepted by the container at any given time. E.g., consider the following code fragment:

SomeContainer c;
Iterator& i = c.NewIterator ();
while (!i.IsDone ()) {
    Iterator& j = c.NewIterator ();
    while (!j.IsDone ()) {
        if (*i == *j)
            cout << *i << endl;
	++j
    }
    delete &j;
    ++i;
}
delete &i;

This code compares all pairs of objects, (i,j), in the container and prints out those which are equal.

A certain amount of care is required when defining and using iterators. In order to simplify the implementation of iterators, we shall assume that while an iterator is in use, the associated container will not be modified. Specifically, this means that the no non-const member function of the associated container may be called. In particular, this also means that the container must not be deleted while an iterator is in use!