Am Tuesday 24 November 2009 00:14:55 schrieb Christopher Jefferson:
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
you're right, here is the culprit: void increment() { BOOST_ASSERT(bucket_); node_ = node_->next_; while (!node_) { ++bucket_; node_ = bucket_->next_; } } however, my results show even worse than O(size()), which is the specificied worst case. this TR1 draft from 2005: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf had a "void" result of erase(), but that changed a few month later: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1836.pdf so I guess they had a good reason for changing it, since the complexity requirements stayed the same. does anyone on this list happen to know what caused that change?
, 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.
"void" return type: http://www.boost.org/doc/libs/1_38_0/doc/html/boost/intrusive/unordered_set.... Am Tuesday 24 November 2009 00:40:57 schrieb Thorsten Ottosen:
2) also if this is a real problem in real code.
it happened in real code.