4 ms·
Also std::unordered_map suffers from a design flaw that forces a poor implementation.
by adrianN 7y ago
Also std::unordered_map suffers from a design flaw that forces a poor implementation.
- taneq 7y agoWould you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.
- abhishekjha 7y agoApparently the standard imposes a set of requirements that the implementation must abide by thus making it a lot slower. [0] : https://www.reddit.com/r/programming/comments/5pwgtn/hash_map_benchmark_stdunordered_map_seems_very/ https://www.reddit.com/r/programming/comments/5pwgtn/hash_ma... [1] : https://stackoverflow.com/questions/42588264/why-is-stdunordered-map-slow-and-can-i-use-it-more-effectively-to-alleviate-t https://stackoverflow.com/questions/42588264/why-is-stdunord... [2] : https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4
- adrianN 7y agoThe interface forces an implementation as a map with linked-list buckets which is suboptimal for many use cases. So people who care about performance usually just implement their own hash map or use a library.
- taneq 7y agoAh, that makes sense. Thanks!
- yuushi 7y agoDepending on what you required, it can still be significantly faster than std::map. Any tree-based data structure is going to play havoc with cache. Also, it will perform an allocation for every single node inserted, which can become rather expensive (unless you're using some customized allocator for this). Honestly, sorted vectors can often be a good replacement, depending on the workload, if you must have ordered data (this is what boost flat_map uses). All 3 (map, unordered_map, sorted vector) can have their uses, depending on what you are doing with the data. If you need a better performing hash map, there's always Abseil as well.
- adrianN 7y agoUnfortunately unordered_map also requires lots and lots of allocations, because it's forced to use linked-list buckets.