There has been some discussion of sequences vs.
iterators. One major problem that I have with
iterators as defined in the STL is that everything is
done via xxx.begin() to xxx.end() where both represent
an iterator and items are typically processed from
xxx.begin() to, but not including, xxx.end().

The problem is that it is very natural to use
iterators to model many, many things. Some of which
are infinite (or at least unbounded) sequences. So,
there is no xxx.end() possible, and sometimes there is
no xxx.begin() possible.

I created the following definition of an iterator,
which is what I use for modelling sequences. I find
that it works extremely well and I have represented
many different things as iterators. Not just elements
of a list, but also all sorts of random sequences,
buffer accessing, permutations. Basically, anywhere I
can create code that constructs items one at a time
and where I want to see a sequence of those items is
possible. This definition has evolved over a number of
years and it seems to represent things fairly well.

In practice, the lack of infinite numbers requires
various constraints -- positions may exist as separate
objects but it may not always be possible to take the
difference of a position. A position may or may not be
represents by an integer.

Examples of using this approach are...

  for (Iterator I; not I.atUpperBound(); ++I)

or, where a sentential value is defined...

  for (Iterator I; *I != sentential; ++I)

which can sometimes be substantially faster. It is
always possible to convert STL iterators to this form
by defining atUpperBound() as

   bool atUpperBound() const
      {
      return *this == end();
      }

where the expression is to be taken as an idea and not
as working code.

Anyway, the formalism is...

====================================================

   An iterator is formally defined as a tuple...

      <L,U,I,P,r,p,O,M,m,A,X,R,D>

   where...

      L  is the greatest lower bound of the iterator.
         If the iterator is infinite to the left, L
         is the first negative transfinite ordinal
         -N (aleph).

      U  is the least upper bound of the iterator.
         If the iterator is infinite to the right, U
         is the first positive transfinite ordinal
         N (aleph).

      I  is the open interval (L,U) over integers.
         I is called the indexing set of the iterator.
         Notice that I contains neither the greatest
         lower bound nor the least upper bound.

      P  is the open interval (L-1,U+1) over integers.
         If L and U are, respectively, -N and N then
         P = I (see note below). The elements of P
         are called the positions of the iterator.

         Note: It is assumed that we are working in
               a number system which contains the
               negative integers, zero, positive
               integers following the usual rules of
               arithmetic and which has been extended
               with the first negative transfinite
               ordinal (-N) and the first positive
               transfinite ordinal (N) such that:

                  N + n = n + N = N
                  N + N = N
                  n + -N = -N + n = -N
                 -N + -N = -N
                  N + -N = -N + N = 0

               where n is any finite integer, and
               where n + -m is to be considered the
               same as n - m in the usual manner. In
               other words, N and -N are "sticky".
               Similar rules follow for multiplication
               and division.

      r  is an element of P and is called the initial
         position.

      p  is an element of P and is called the
         distinguished position. Immediately following
         creation of the iterator and immediately
         after the iterator has been reset, p = r.

      O  is a set of objects.

      M  is the set of positions at which m is
         defined. It contains p when p is an
         element of I and is a subset of I.

      m  is a map from M onto O, m:M->O.

         Note: Some iterators extend m to m' where m'
               contains at least one of {L, U}. If m'
               is defined at L or U, the value of the
               m'(L) and m'(U) is defined by the
               iterator (and is usually a null value
               or a sentential value appropriate to
the
               iterator). The value may or may not be
               contained in O.

      A  is the set of accessible positions. It always
         contains p and is a subset of P. The set of
         accessible positions are those positions to
         which the distinguished position can be
         moved.

      X  is the set of extensible positions. It is a
         subset of P. The set of extensible positions
         are those positions at which new elements can
         be inserted into the iterator. The mapping
         from the old set of positions to the new set
         of positions is iterator defined, but is
         monotonic.

      R  is the set of replaceable positions. It is a
         subset of M. The set of replaceable positions
         are those positions where the value of the
         iterator may be changed.

      D  is the set of deletable positions. It is a
         subset of M. The set of deletable positions
         are those positions where the value of the
         iterator may be removed from the iterator.
         The mapping from the old set of positions
         to the new set of positions is iterator
         defined, but is monotonic.

   An iterator is a sequence if both I = M and A = P.
It is a temporal sequence if M = {p} and A is a subset
of {p-1, p, p+1}.

====================================================

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]