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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk