Re: [boost] lifetime of ranges vs. iterators

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-29 10:48:37

on Fri Aug 29 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

> Wouldn't it be more natural to represent a forward range as a single
> iterator, with an extra .at_end() check? This would eliminate the
> problem, because a difference_range would only need two such
> iterators, not four. 

As part of
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1873.html one
of the ideas we discussed extensively was allowing the end iterator of a
range to be a different type from the begin iterator.  That would allow
a sort of "universal end iterator" to be used in situations such as
this:

  struct end
  {
      // These definitions are only useful for infinite ranges
      template <class T>
      bool operator==(T const&) { return false; }
      template <class T>
      bool operator=!(T const&) { return true; }
  };

Effectively the data representation of the begin iterator would be the
same as what you're proposing, plus comparison operators against the
universal end type above, but the end iterator type could be empty (and
optimized away).  That allows a generic description of algorithms that
are optimally efficient on pairs of pointers, but could simplify many
classes of iterator (ifstream_iterators, for example) where every
iterator needs all the information required to detect whether it can
advance anyway.

> Stacking them naively would have 2^N storage
> growth, rather than 4^N, and we still don't need to worry about range
> lifetime.

I've been trying to say that generic algorithms *can't* worry about the
range lifetime; they have to assume that the iterators they're passed
will not be invalidated before they're destroyed.

> For other classes of iterators, the situation is
> similar. bidirectional ranges have at_end() and at_begin(), and
> random_access_ranges a size() and an operator[].

Bleah (sorry).  Iterators in general shouldn't be burdened with the
requirement to know the limits of the sequence, and if you go back and
review the class of problems that iterators were "designed" to address,
I think you'll see why.  Just take a look at the classic quicksort
algorithm, for example, or any other divide-and-conquer algorithm.

I put "designed" in quotes because concepts are discovered, not
designed, but that's a whole different topic.

> I know that overthrowing such an established concept as ranges is not
> terribly popular, but I don't see any other way to combine easy
> stacking with no worry about lifetimes.

I'm not sure this is as revolutionary as you think.  Every other
language I've looked at has a get_next()/at_end() iterator abstraction,
which is a lot like what you're proposing.  My advice: make sure you
keep in mind the whole problem domain.  You can't understand the reason
that C++ iterators are unlike those in other languages without looking
at the algorithms.

Generic Programming -- it's about the algorithms, baby!

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com