[kyllo]

It'd be interesting to see how std::map (implemented with a red-black tree) would do on these same benchmarks. A high ratio of inserts to lookups could favor the tree-based map.

[jonstewart]

It’s hard to get slower than std::map and std::set. They combine logarithmic algorithms with nonlocal memory access.

[chopin]

A tree map is O(n*log n) on inserts, though.

For a hash map to be faster, you'd need to trade memory for speed, i.e have significantly more buckets than the expected size. This may however collide with good caching performance which I suspect is what the author observes.