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