Re: [boost] lifetime of ranges vs. iterators

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-08-29 10:32:56

On Fri, Aug 29, 2008 at 4:12 PM, Arno Schödl <aschoedl_at_[hidden]> wrote:
> Indeed, as long as the range does not escape, everything is fine. But here we are in
> trouble:
>
> some_stacked_adaptor_range<...> rng( make_difference_range( vecnA, vecnB ) );
>
> Again, notation makes no difference, but Neil's idea, which I fully endorse, namely
> easy stacking, makes the problem all the more apparent:
>
> some_stacked_adaptor_range<...> rng( vecnA | difference( vecnB ) ); // wrong
>
> What makes this really annoying is that there is an easy way out: 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. Stacking them naively would have 2^N storage growth,
> rather than 4^N, and we still don't need to worry about range lifetime.
>

Ok, now I understand.

The lack of auto and decltype usually means that you use range
adaptors in a strictly LIFO way, i.e. you usually never have named
range adaptors, and iterator validity is never an issue as the scope
of the wrapping range is always a subset of the wrapped range.

Anyways, the solution is simple: if you want your adaptor to survive
the original wrapped range, you have to store a copy of the wrapped
range in the adaptor. As an added benefit, the adaptor size will be
the smallest possible for deep sequences of stacked adaptors.

Of course this means that you have to wrap real containers around
boost::range to prevent expensive copies. (sometimes explicitly
specifying the adaptor template argument as a reference, instead of
relying on a make_*_range, will work).

BTW, This mimics the situation with boost.bind and lambda, were the
default capture is by value and you have to use ref/cref to explicitly
store by reference.

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

In most cases (i.e. every time a default constructed iterator is not a
valid end iterator), this means that an iterator must store the end
point in addition to the initial point. Thus the iterator would
actually be a range. You might as well make that explicit.

P.S. please, don't top post.

-- 
gpd