Boost logo

Boost :

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 14:28:06

> Sure, full generality is always good, but if ranges cover 90% of the
> cases, maybe it is good enough.

I agree.

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

> You can't assume that all iterators are lean. In fact most won't.
> Unless you drop compatibility with existing iterators, which is a
> no-no.

Old iterators will have neither the indirection I propose, nor will they offer a non-trivial factorization nor internally store preferred ranges. So any of the schemes discussed make no difference to old iterators. But old iterators are often trivial, so the whole problem should not really apply to them.

> My proposal was aimed at making ranges as lean as possible, not
> necessarily iterators.
> Anyways, as long as all parts of the stack are 'lean' ranges, you
> should have only a 2x storage bloat when using iterators.

The bloat is potentially much worse with your implementation below:

> iterator begin() const{
> return iterator(begin(m_range), end(m_range), m_f);
> }

This triggers recursive unwrapping all the way to the top, causing factor 2^N extra storage to be generated, which is then imploded again inside the iterator ctors. In my other post to Dave, I calculate it in detail. This exponential extra storage is the reason I am making all this fuzz.


Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany · 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, gregod at, cpdaniel at, john at