为什么std::unordered_map慢?

在implement TAAT (Term-at-a-time)的时候，我使用了std::unordered_map这个data structure, 它的运行速度很慢, 浏览了一些网页, 发现了其中的原因, 将其总结起来, 以便自己理解和吸收.

1. 首先STL这个library的出发点不是具有好的performance, 如果想有好的performance, 还是要自己implement这个data structure, 因为自己对这个application有很好的理解. 就正如Hao在implement heap(heap sort)一样, 而不是选择使用STL中已经有的data structure, 所以为了提高performance, 要自己implement适合的data structure. the problem is that the STL api is loaded with unnecessary features that make it hard to write a well performing implementation. 

2. unordered_map在erase的时候, 速度最慢可达O(N), 这其中会有rehash, 这会导致速度慢.  the g++ implementation will automatically rehash to a larger hash table, and this would be a big drag on performance.

3. a.erase(a) Erases the element pointed to by q. Return value is the iterator immediately following q prior to the erasure. STL mandates that .erase() returns an iterator to the next item in the container. There’s no simple implementation of that for hashtables other than to walk the hashtable, which is quite slow.

references: http://stackoverflow.com/questions/13730470/how-do-i-prevent-rehashing-of-an-stdunordered-map-while-removing-elements

http://www.clifford.at/blog/index.php?/archives/132-C++11-stdunordered_set-and-stdunordered_map-are-slower-than-a-naive-implementation.html

http://stackoverflow.com/questions/11614106/is-gcc-stdunordered-map-implementation-slow-if-so-why

http://www.drdobbs.com/cpp/c-stl-hash-containers-and-performance/198800559?pgno=1