Re: [boost] lifetime of ranges vs. iterators

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-09-01 19:19:18

On Mon, Sep 1, 2008 at 11:35 PM, Arno Schödl <aschoedl_at_[hidden]> wrote:
> I fixed filter_range::begin() and filter_range::end() as you said. iterator::equal was still exponential, but can be fixed by only comparing begin(). I think the exponential cases are now gone.
>

it should be ok to compare only begin. If the two iterators have
different ends, probably things would be a "little" messed up anyway.

> Most things are still quadratic in the stack size, though... end() for example constructs a parameter of size N-1, which to be constructed, must construct a parameter of size N-2 and so
> on. NRVO does not help, as far as I understand it. You would need "upward" NRVO, constructing parameters right into the respective members. Instead of passing a pointer to the >
> function where it wants the return value to be constructed (NRVO), the caller would need to get a pointer from the callee where the callee wants its parameters constructed. I don't think > compilers do that, at least not reliably enough to build a whole paradigm on it:-(

Hum, I've played a little with some mockup iterators, and  I can
definitely see the N^2 stack growth, and with some expression template
heavy program, I wouldn't be surprised if the  growth would actually
become noticeable (even if it weren't enough to blow the stack, it
could still produce cache misses and such).   I can't seem to come-up
with any clever scheme to reduce the growth (short of using pointers
to the original range of course).

Enough for today. Maybe tomorrow I'll get some idea.

-- 
gpd