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
> > 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
> > 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"
> * 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
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 list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk