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.

To be fair, this hit could be avoided by storing the sub-iterators of the difference_iterator in their factored form, e.g., m_ittrav/m_ittravEnd would be stored as m_ittrav/m_ittravEnd/m_travcommon. But this would put a big burden on the compiler to optimize the frequent compose/decompose operations. For example: *m_ittrav; would become *compose( m_ittrav, m_travcommon ) // common data not used at all and ++m_ittrav; would become m_ittrav=decompose( ++compose( m_ittrav, m_travcommon ) ).first; -Arno -- Dr. Arno Schoedl · aschoedl@think-cell.com 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