Boost logo

Boost :

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 10:08:33


> Need to think about it. Could you give a practical example of an
> iterator adapter needing three iterators?

I never needed them in practice. But I would forward this to Dave. He likes the complete generality of factored iterators, I think. I think it is a cleaner concept than saying the common data must be representable as a range, but I cannot really back this up with practical examples. The wrapping/unwrapping (see below) troubles me in either case.

> You would still have to allow for storing the wrapped iterator in the
> wrapper if the wrapped iterator does not support refactoring. I do not
> think there is a way around it.

But in my proposal (actually, yours), all iterators would be "lean", and each iterator would have access to its range, all the way up the iterator/range stack. So each iterator would itself only wrap other lean iterators. Storage bloat for stack size N would only be O(N) for the indirections, rather than O(2^N).

> Also, I have this (completely unfounded) feeling that an iterator that
> relies on accessing common data in the owning range might be harder to
> optimize.

> I think that ranges should be used for long term storage, so if the
> iterator size itself is not optimal shouldn't be a big problem.

Without any kind of storage optimization like your preferred-range templates or Dave's factored-iterators, the storage bloat would be _factor_ 2^N, so ever handling completely unwrapped iterators just does not scale.

So it comes down to:

a) with storage optimization, at every iterator access, unwrap/wrap the iterator out of their storage:

   [Dave]
   void increment() {
      m_itBase=decompose( ++compose( m_itBase, m_commondata ) ).first; // second is common_data again
   }

   or

   [Giovanni]
   void increment() {
      m_rng=TRange( ++m_rng.begin(), m_rng.end() );
   }

or

b) have the iterator carry an indirection to the outside data.

Given that the iterators coming out of a) are decomposed recursively by the next layer of iterators (that is, ItBase::operator++ inside the expression does the same thing again, all the way up), I would think that a) is actually harder to optimize than b), and the effect of no optimization would be much more dramatic.

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