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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Daniel James (daniel_james_at_[hidden])
Date: 2009-11-23 18:21:09

2009/11/23 Christopher Jefferson <chris_at_[hidden]>:
>
> On 23 Nov 2009, at 23:23, Stefan Strasser wrote:
>
>> I can't think of a reason why it should be O(n) in this case (perfect hash,
>> erase doesn't rehash).
>> but even if it was, the results should be at worst quadratic.
>
> I suspect the problem you are seeing is that erase returns an iterator to the next member of the unordered_set, which is a possibly O(n) search if the set is sparsely populated, and in particular if, as you get here, you erase the elements in a particularly bad order. I'm not sure why this doesn't occur with the intrusive containers.

That's right, I profiled it and it spends all the time searching for
the next bucket.

> One way to significantly reduce this problem is to use a different hash function, which shuffles the values more.

I could apply another hash function to the hash value to make this
less likely, or perhaps store a pointer to the last non-empty bucket.
I'll think about it.

A workaround is to erase by key or iterator range if possible.

Daniel