Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-09-05 13:41:23

On Fri, Sep 5, 2008 at 6:55 PM, David Abrahams <dave_at_[hidden]> wrote:
>
> on Fri Sep 05 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
>
>>> You're completely right about that, and there are even additional
>>> reasons that you didn't mention, as I realized a couple days ago.  I
>>> didn't want to bring it up, though, because it doesn't change the
>>> fundamental reality.  Just replace strided_iterator by another layer of
>>> filter_iterator.
>>
>> Hum, but as long as an iterator contains only a range, you can always
>> encapsulate it with no space overhead. a
>> filter_iterator<filter_iterator<T* > >  has sizeof(T*2) (assuming a
>> stateless predicate), which is optimal.
>
> First of all, there's other kinds of data that's redundant across pairs
> of iterators in a range hey, like the predicate!

that's not a problem, a filter_range would store the predicate only once.

>
> But let's ignore that for a moment.  The range compression formula is:
>
>      sizeof(range<X>) == 2*sizeof(X) - sizeof(common_data<X>::type)
>
>    so when X is filter_iterator<Y>:
>
>       sizeof(X) is 2*sizeof(Y)
>       common_data<X>::type == Y

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)
  assert(f.begin() == a);
  assert(f.end() == b);

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

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.

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

-- 
gpd