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 +49-30-666473-10 Â· toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl Â· Amtsgericht Charlottenburg, HRB 85229
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk