Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue

Subject: Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue
From: Michel Morin (mimomorin_at_[hidden])
Date: 2012-06-24 05:51:32

Jeffrey Lee Hellrung, Jr. wrote:
>> > What if we introduced a metafunction that dictated what
>> > reverse_range<R> should store its adapted range by, either R& (most of
>> > the time) or R (in the case that the adapted range is a directly or
>> > indirectly a moved_range/by_value_range).
>>
>> Do you mean reverse_range<R> stores reverse_forwarder and R
>> for the latter case?
>>
>
> Yes (I think so).

Then, compared to the current implementation of reverse_range,
the implementations of your reverse_range and my moved_range
are essentially the same, right?

> Now I'm curious: what are the advantages and disadvantages of implementing
> reverse_range<R> as a pair of reverse_iterator< R::iterator >'s (I'm being
> sloppy here, but based on your above assertion, this is the present
> implementation) versus as a wrapper around an R (held by reference or
> value) directly? In the latter case, for example, reverse_range<R>::begin
> would return reverse_iterator< R::iterator >(boost::end(r)) (where r is the
> wrapped range of type R).

Below, I say boost::begin(r) and boost::end(r) as the underlying iterators.

Your range adaptors are "lazy adaptors":
* Pipe operators does not adapt the underlying iterators in effect.
* The underlying iterators are adapted only when begin/end is called.
And each time begin/end of your range adaptors is called,
the underlying iterators needs to be adapted.

But, in some range adaptors, adapting the underlying iterators
is a bit expensive. For example
* In filtered_range, adapting the begin iterator can be expensive,
since it needs to advance the begin iterator to the first "unfiltered"
iterator.
* In oven's dropped_range (this ignores the first n elements in the range)
on bidirectional range, adapting the begin iterator takes O(n) time.

So your range adaptors are inefficient in these cases.
(moved_range internally caches the adapted iterators to avoid
this problem.)

Regards,
Michel