Boost logo

Boost :

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

Yes, I think that's true.

> Now, if you add check_increment() to the copy ctor you get the quadratic
> behavior
> back in compilers without RVO.

And on compilers with RVO it might not fix it, since the copy
constructor is elided.

Daniel


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk