Re: [boost] lifetime of ranges vs. iterators

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-29 19:51:20

on Fri Aug 29 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:

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

Or you could write the representation of the range in such a way that it
didn't contain an exact representation of the iterators.  When you
assemble a range from two iterators, store the common information
separately, and reassemble the complete iterators only when they are
requested.  When adapting iterators you'd do the same
deconstruction/re-construction.  You could tack on some runtime
error-checking for good measure.

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

Well, they're informationally equivalent...

> 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)';

...but that is so ugly as to make them non-equivalent abstractions in my
book.  And that's a good thing for ranges ;-)

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

IMO ranges will be good for describing transformations at a high level,
but algorithms, for the most part will, need that flexibility.

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