Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Daniel James (dnljms_at_[hidden])
Date: 2010-03-18 03:25:20
On 18 March 2010 07:12, <joaquin_at_[hidden]> wrote:
> Daniel James escribió:
>> I've attached a patch to do something similar for Boost.Unordered. I
>> got a similar result, although I think it will make some other things
>> slower. And I'm not keen on mutable variables.
> There's an additional problem, I think. Your patch does not
> check_increment() on
> hash_iterator copy ctor, so that the following pathological situation can
Yes, I think that's true.
> Now, if you add check_increment() to the copy ctor you get the quadratic
> back in compilers without RVO.
And on compilers with RVO it might not fix it, since the copy
constructor is elided.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk