3 ms·
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 th
by kyllo 7y ago
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.
- chopin 7y agoA 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.
- jonstewart 7y agoIt’s hard to get slower than std::map and std::set. They combine logarithmic algorithms with nonlocal memory access.