Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-06 09:52:33

> > increment() {
> >    for( difference_type i=0; i<N && !base.empty(); ++i ) {
> >       base.increment(); // the adapted_range::increment which increments begin,
> > base is a range
> >    }
> > }

> I don't think you're fully appreciating what a huge impact such a
> complex implementation of increment() would have on performance.

Sorry, I meant this as the implementation for forward range. You don't want to use increment for random_access ranges, obviously. 

Thinking about it some more, I believe the associated_range abstraction is not quite the right one yet. It works for forward_ranges, which is why I did not notice earlier, but not for bidirectional and random_access_ranges.

The correct abstration is bounded_iterator, which is an iterator + the knowledge of whatever bounds it needs. The extra functionality offered over iterators is to test overrun of begin/end in increment/decrement/advance. begin/end may have a bool return value whether increment/decrement succeeded or not, and advance may return the difference_type that actually got executed until begin/end was reached.

The bounded_forward_iterator is a bit similar to a range. Its base iterator implementation must store the current iterator + the end. This is essentially what Giovanni introduced as associated_range.

The bounded_bidrectional_iterator and bounded_random_access_iterator base implementation must store begin, current and end base iterators.

All iterators needing the underlying iterator bounds can then run on top of bounded_iterators, and are implement the bounded_iterator interface themselves. I think this eliminates all space overhead of any adaptors we have been mentioning so far. In particular this applies to strided_iterators of all categories.

The corresponding adaptor ranges would return bounded iterators from their begin()/end() functions. They store their base range internally instead of two iterator adaptors, to avoid any space overhead in ranges.

Arno

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