[boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 03:53:19

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