Subject: Re: [boost] lifetime of ranges vs. iterators
From: David Abrahams (dave_at_[hidden])
Date: 2008-09-05 14:36:53
on Fri Sep 05 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
> Oh! now I see where is where our inpedence mismatch is!. You want to
> store three pointers in filter_range because you correctly want this
> transformation to be lossless:
> pair<filter_iterator, filter_iterator> a;
> filter_range f(a.begin, a.end)
I think you mean
filter_range f(a.first, a.second)
And I'll assume from what you write below this not adding an additional
layer of filtering; it is just storing a.first and a.second (compressed).
> assert(f.begin() == a);
> assert(f.end() == b);
I think you mean
assert(f.begin() == a.first);
assert(f.end() == a.second);
> i.e. the hidden common knowledge of a.begin and a.end of the
> effective end of underlying range (let's call it real_end) is
I wasn't motivated by that, actually. Frankly, I don't see why the
invariant shouldn't hold even if you store only two pointers. The
underlying end iterator would have been advanced to the nearest element
satisfying the predicate, or real_end, by the time you try to construct
A similar case is:
I don't think even our existing filter_iterator implementation supports
that, though ;-). It's not unreasonable to request that all
range-limited iterators traversing the same logical range be initialized
with the same real_end.
> I was naively thinking that, by transforming the pair in a full
> featured range, I could completely forget about real_end, and only
> encode to a.begin, a.end. In practice the whole filter_range
> information would be contained in a.begin, a.end would be completely
> redundant. The consequence of this is that the range could only shrink
> and never widen.
I think that's a great insight... for filter_range's iterator
redundancy. It won't help with other redundancies, I'm pretty sure.
However, they're less likely to occur across levels of stacking than is
the sort of range limitation in filter_iterator.
> Now, in general an iterator adaptor cannot rely on the fact that can
> advance the underlying range 'begin' beyond its 'end' , so real_and is
> effectively completely unecessary. Unfortunately the outside world
> knows better and can use .base() to extract the underlying iterator
> and would expect that real_end to be preserved.
Well, now, the underlying iterator is not real_end anyway. base()
doesn't help you get it.
> Now I see two solution:
> - declare that the filter_range is not semantically equivalent to the
> original iterator pairs, but make the loss of information explicit. In
> practice this would means that the range could only shrink, but would
> make it possible to have space efficient abstractions.
> - just declare defeat, and concede that you are right :)
Not so fast. You may be able to have your cake and eat it too.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk