Saini of MODENA: Iterators--A Key to Understanding the Standard Template
Library (STL)

Marian Corcoran
C/C++ SIG Chair
Software Forum

An extremely intelligent group of software professionals showed up at
our second meeting to hear Atul Saini, CEO of MODENA, a commercial
vendor of the STL.

In regular programming, algorithms act upon data structures.  A diagram
might look something like this:

  Algorithm    --->    Container
    or Data Structure

In a perfect world, every algorithm should be able to work on every data
structure or container.  We know this is not the case.  For example, a
quicksort would not be efficient on a linked list, because of the
difficulties with random access.  Indeed, every algorithm cannot work on
every data structure efficiently.

ITERATORS: The Key to STL

Saini stated that all software problems can be simplified by introducing
an extra level of indirection.  In STL, iterators provide that
indirection so a very generalized (and incomplete) architecture of STL
would look like:

  Algorithm  --->  Iterator  ---> Container
    or Data Structure

Iterators allow for a set of operations on a data structure without
saying anything else about the nature of the data structure.  Consider
two different types of sequences, an array and a vector:

   double DbleArray[10000];
   vector<int> IntVec;

A    generic    sort algorithm could work on both of these sequences using
iterators.  (You may think of an iterator as a finger capable of
pointing to or moving across the sequence.)  The general sort algorithm
would receive, as arguments, an iterator (or    finger   ) to the beginning
and one to the end of the sequence (whether it be array or vector).  The
code would be:

   sort(DbleArray, DbleArray + 10000);
   // call to sort to sort all the items in the array DbleArray

   sort(IntVec.begin(), IntVec.end());
  // call to sort to sort all the items in the vector IntVec

The above sort works well with sequences capable of random access.  STL
therefore, does not allow:

  list<int> IntList;

  sort(IntList.begin(), IntList.end() );  //wrong

The class list has its own sort and could be called with IntList.sort(),
i.e., the member function.

The STL has five different iterator categories which may be arranged in
the following hierarchy:
     Random Access
    |
     Bidirectional
    |
        Forward
       /       \
   Input      Output

Any algorithm that works at a lower level will work on the levels above
it.  For example, since find() works on the Input iterator, it will also
work on the ones above it.  The iterators higher up have all the
properties of those below it.

   Input iterators allow one to read from items from a sequence, and
output iterators allow one to write to a sequence.  Input and output
iterators could work on an array or a list. Forward iterators combine
the abilities of input and output iterators (i.e. reading and writing),
but, in addition, one may save a forward iterator for later use.
Bidirectional operators allow for all forward iterator operations plus
the ability to go backwards, so it will work on data structures which
may be traversed forwards or backwards, such as a doubly linked list. If
we create a doubly linked list

  list<int> IntList;

we may reverse it with

   reverse(IntList.begin(), IntList.end())

Remember that the arguments are iterators or pointers to the beginning
and end of the list.

Random access iterators have the properties of those lower in the
hierarchy, plus the ability to reach any other locations within the data
structure in constant time.  For example, a binary search requires that
one be able to reach the middle element in constant time, given
iterators which indicate the beginning and end of the data structure.
Lists do not have this property, but arrays and vectors do.  Consider
the following

   vector<int> IntVec(100,0);

We may perform a binary search with

  bool found = binary_search(vec.begin(), vec.end(), 20);

will search for the value 20.  True will be returned if it is found,
otherwise, false will be returned.

The STL iterator hierarchy serves to combine algorithms and containers
efficiently.  An algorithm that works with an iterator lower in the
hierarchy will also work with those higher up (i.e., those that work
with an input iterator may also be used with forward, bidirectional or
random access iterators.)  Container classes (data structures) are
described in terms of the iterator categories they have.  For example,
lists have bidirectional iterators.  Algorithms are described in terms
of the iterator categories they work with.  Binary searches require
random access iterators.

The material for this article was taken from both the presentation and
an excellent tutorial available from MODENA at 1-800-MODENA-1.

FUTURE MEETINGS: (Fridays, 6:15 to 8:15 p.m.)
April 28     Avoiding Re-Compilation of Class  Libraries
     by Michael Ball of SUN Microsystems
May 12     DirectToSOM C++- Programming
     it Directly in C++     ( IBM   s System
    Object Module for binary compatibility)
     by Tom Pennello, Founder of MetaWare
June 9  Topic to be announced.  Dmitry Lenkov of
 Hewlett Packard Laboratories,
 Chair of ANSI C++ Committee

Location:  UC Santa Cruz Extension,
    3120 De La Cruz Blvd., Santa Clara
Contact or to be placed on
e-mail list:   Marian Corcoran, mcorcora@ix.netcom.com