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-17 19:34:17

On 17 March 2010 22:06, Howard Hinnant <howard.hinnant_at_[hidden]> wrote:
>
> Just a few minutes ago I changed my implementation of unordered_map to use a "lazy increment" for the iterator and ran it against Brad's test:
>
> $ time a.out
> Add 500000 elements...done!
>
> remove the elements...done!
>
> real    0m0.153s
> user    0m0.127s
> sys     0m0.020s
>
> This time is about the same as I got using an erase() that did not increment the iterator.  The "lazy increment" allows the iterator to walk off of the end of bucket, and does not try to find the next bucket until dereference, another increment, or comparison.  I do not claim this is "the solution" it is one of several I'm exploring.  I mention it here in case others want to try it and report their experience.

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.

Daniel