4 ms·
> did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n) Weird, never heard of that. What i
by jey 14y ago
> did you know that thanks to a standards committee decision, erase by iterator in a typical C++ TR1 hash set or map is O(n)
Weird, never heard of that. What is it about the iterator requirements that causes erase to be O(n)?
- jzwinck 14y agoIt's the fact that erase(iterator) returns the "next" iterator. Since hash tables often don't shrink, they can become quite sparse, and the "next" operation is linear. This is the best link I have right now--a ticket I filed (and was fixed) for Boost's implementation: https://svn.boost.org/trac/boost/ticket/3693 https://svn.boost.org/trac/boost/ticket/3693 Note the references to GCC's implementation. As far as I can tell they fixed it in 4.7, but caused some other performance regression which is still open. And most people don't use GCC 4.7 in production environments yet.
- pilooch 14y agoReading your comment, I thought I would mention this especially nasty bug in 4.7.1: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54075 Short description: a measured 3x performance regression from 4.6.2 to 4.7.1 when using std::unordered_map Not sure what the status is now, my Ubuntu and Debian boxes all report gcc 4.7.2.
- deleted 14y ago[deleted]