Re: [boost] lifetime of ranges vs. iterators

From: David Abrahams (dave_at_[hidden])
Date: 2008-09-01 12:51:06

on Mon Sep 01 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

>> > If we subscribe to the rule that ranges must stay valid for their
>> > iterators to be valid,
>
>> I don't.  I do subscribe to the rule that generic code cannot afford to
>> destroy an arbitrary range while its iterators are still in use.
>
> Isn't that what I said? 

No, but it might be what you meant.

> There may be iterators that work without their ranges,
> but in general they don't.
>
>> > the adapted_range::iterator can use the common data stored in the
>> > range, while the adapted_iterator stores the common data itself. Both
>> > could even be derived from the same source code. 
>
>> Yeah, that's still a lot of coding effort.
>
> I think you could write it generically, a la iterator_facade/adaptor,
> so it is a one-time fixed cost.

I'm not sure if it's worth the effort.

>> > Do you then still need a factored iterator?
>
>> You need to be able to take two adapted iterators and turn them into a
>> range.  Do you want that range to contain redundant data?  I don't.
>
>> > Or do you want to avoid people having to use the range abstraction? 
>
>> I certainly don't want to force it on them.
>
> Ok, now I understand. The debate is about primacy of ranges or
> iterators.

I'm not sure I agree.

> You propose that iterators stay the primary vehicle 

Let's say, I propose that they are first-class citizens that work
without an underlying Range object.  

        char* buffer=malloc(lotsabytes);
        
How am I going to operate on that if there needs to be an underlying
range object?  There isn't one; the iterators stand alone.

(Ranges can be first-class citizens too if you like).

> and to convert
> them to/from ranges by stripping the common information.

As an optimization.

> But that would mean that there is no "lean" iterator, all iterators
> would contain the redundant information.

I think int* is plenty lean.

I don't know what you mean by "lean iterator," actually.  You can store
the common information in the iterator itself, or you'll have pointers
or references to the common information, but either way there will be
redundant bits in a pair of filter_iterators.

> When stacking N difference_ranges, the size difference between "fat"
> and "lean" iterators is 2^N. Thus in fully generic code where you
> don't know anything about the stacking depth, even generating a single
> fat iterator carries a potentially exponential penalty.

You've lost me.  Maybe you'd better spell out what you mean by "fat" and
"lean," and by "generating a fat iterator."

> This fact makes me think that range is not merely a fancy name for a
> pair of iterators but a concept in its own right between containers
> and iterators. Generic algorithms must be written on the basis of
> ranges rather than iterators or take a significant performance hit.

Have you actually measured anything yet?

I think you're being at least very hasty.  If you do something that
slows down operation on pairs of pointers, you won't be doing anyone
favors.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com