Boost logo

Boost :

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

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

A similar case is:

      make_filter_range(a, a+len/2).end()
   == make_filter_range(a+len/2,a+len).begin()

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at