Re: [boost] [unordered] unordered_set::erase() complexity bug?

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