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

Subject: Re: [boost] [Range] Range adaptor approach for temporary range lifetime issue
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-06-24 06:35:52

On Sun, Jun 24, 2012 at 2:51 AM, Michel Morin <mimomorin_at_[hidden]> wrote:

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

More or less, modulo storage rules. Your moved_range always stores the
underlying range by value; my reverse_range would store by value or by
reference depending on some type property of the underlying range.

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

Correct.

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

Ah, of course.

My initial attempt to address this would be to cache begin/end iterators on
those range adaptors for which it made sense (e.g., filtered_range and
dropped_range above).

In any case, just thinking out loud, really. Even if lazy range adaptors
were viable, it doesn't sounds like it would be very applicable to
Boost.Range.

- Jeff