TITLE: Safe iteration schemes 

PROBLEM: rmartin@willing.Rational.COM (Bob Martin), 17 Mar 92
         Rational, Inc.


The issue of iterating safely over the elements within a container is
interesting to say the least.  When writing a container class, it is
very important to specify how to safely iterate over its elements.

Iterators are often used, they have the advantage that more than one
of them can be active at any one time.  Thus you can use several
iterators to manage several different scans of the data at the same
time. 

Some container classes provide iteration facilities of their own.  In
the simplest cases, this will only allow one scan of the data to be
active at any given time.  However, some container classes maintain
a stack of iteration states.  This allows clients to start up a new
iteration by pushing the old one, and then popping it back when the
new iteration is complete.  

Iteration techniques like this can be much more efficient than query
methods.  For example, imagine a linked list class which has an
operator[](int) query method.  By saying list[n] you can access the
nth element of the list.  Presumably this is accomplished by walking
the list to the nth element.  The following code is horribly
inefficient:

  for (int i=0; i<list.size();; i++)
  {
      element = list[i];
      // do something with element.
  }

For a list of N elements, (N^2+N)/2 nodes will be touched.  However an
iterator of the list could remember its last position in the list.
WHen asked to go to the next element, the iterator could simply walk
to the next element.  If the following code used such an iterator,
then it would be very efficient:

  for(ListIterator i(list); !i.is_done(); i.next())
  {
      element = i.get_element();
      // do somethint with element
  }

In this case the iteration will only touch N nodes, a great
improvement.  However, efficiency of this sort requires memory of the
current state of the list.  The iterator had to maintain a pointer to
the current element so that it could quickly traverse to the next
element.  But what would have happened if the current element were to
be removed from the list???  The iterator could become hopelessly
lost!

In fact, almost any iteration scheme will utterly fail to do the
following pseudo code properly:

   INIT_ITERATOR
   WHILE ITERATOR IS NOT DONE
     DELETE THE ELEMENT REFERED TO BY THE ITERATOR
     MOVE THE ITERATOR TO THE NEXT ELEMENT.

Both the iteration schemes mentioned above fail when used in this
algorithm.

It is generally very difficult to create iterators which can survive
when the container is modified during the course of an iteration.

Some safety can be built into iterators, but generally it is at the
expense of efficiency.  The most efficient iterators are often the
least flexible in terms of what can be done to the container during an
iteration.  Conversely, the safest iterators are often the slowest
iterators.

What is the morale?  When designing an iteration scheme, make sure you
document the conditions under which it is safe.  When using an
iteration scheme, make sure you know what operations are safe in the
midst of an iteration.