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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Christopher Jefferson (chris_at_[hidden])
Date: 2009-11-23 18:14:55

On 23 Nov 2009, at 23:23, Stefan Strasser wrote:

> 
> I think there is something very wrong with boost's implementation of 
> unordered_set/map.
> 
> 1	unordered_set<int> s;
> 2	for(int c=0;c<nr;++c) s.insert(c);
> 3	for(int c=nr-1;c>=0;--c) s.erase(s.find(c));
> 
> results:
> 
> nr: time
> 20000: 0m0.244s
> 40000: 0m0.940s
> 60000: 0m5.584s
> 80000: 0m4.232s
> 100000:    0m34.814s
> 120000:    0m33.486s 
> 
> 
> the function that's causing this is erase(), which is specified to be O(1) 
> average, O(n) worst.
> 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.

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

I don't know if there is an algorithmic improvement which can fix this. there certainly isn't an obvious one.

Chris