Re: [boost] lifetime of ranges vs. iterators

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

  assert(
      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
http://www.boostpro.com