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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk