2009/11/23 Christopher Jefferson <chris@bubblescope.net>:
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