Re: [boost] lifetime of ranges vs. iterators

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-08-29 11:11:31

On Fri, Aug 29, 2008 at 4:48 PM, David Abrahams <dave_at_[hidden]> wrote:
>
> 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.
>

<snip>

> 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.
>

Nice!

>> 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.

I think that the OP is talking about a different problem: let say you
want to name the result of stacked applications of range adaptors:

template<typename Range>
void my_algo(Range& r) {
  auto stacked_range = r | filtered(filter) | mapped(mapper);
  // use stacked_range
}

This may lead iterator lifetime problems, not because r iterators may
be invalid, but because the iterators of the range returned by
filtered(...) may become invalid as that temporary has been
destructed. There are many solutions:

The easiest is splitting apart the expression, but is ugly.

Then you could use expression templates to make the whole pipe
expression return a range only at the end.

Finally, both filtered and mapped could guarantee that the iterators
are not invalidated when the range is destructed, but that may prevent
some space optimizations (like storing the predicate inside the range
instead of the iterator)).

>
>> 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.
>

BTW, ranges are equivalent to GoF iterators: you just spell 'at_end'
as 'empty(r)';
'next()' as 'r = range(next(begin(r)), end(r))'   (equivalently: 'r =
rest(r))'; and '.get()' as
'*begin(r)';

The nice thing about ranges is that you can take them apart into their
iterator components when you need the extra flexibility.

-- 
gpd