Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 02:57:29

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

> > 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. You propose that iterators stay the primary vehicle and to convert them to/from ranges by stripping the common information. But that would mean that there is no "lean" iterator, all iterators would contain the redundant information. 

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.

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.

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229