4 ms·
In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though,
by overgard 7y ago
In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
- darwingr 7y agoIs this something you’ve actually seen? I’ve often wondered.
- overgard 7y agoWell, it was the case at my last three jobs and most open source i’ve seen. It is anecdotal though
- taneq 7y agostd::unordered_map was only added in C++11, which explains why it's not used in legacy code. Habit, inertia and a desire to keep codebases internally consistent explains why it's less common now.
- adrianN 7y agoAlso 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.
- bnegreve 7y agoDevelopers primarily use sorted maps because the sorted map is the default map type in C++, by name. (I would be different if you had map/sorted_map instead). The real question, is why C++ designers chose to prioritize sorted maps (RBTrees) over unsorted maps (Hash Maps). I don't think it's a matter of speed though. I think it's because RBTrees are safer to use. Things can go really wrong with a hashmap if you have a poor hashing function (worst case search is O(n) vs. O(log(n)) for a RBTree)
- repsilat 7y agoIt probably varies by company, and by team. In my old hobby code there was a lot of std::map, but in my more recent professional experience I see a lot more absl::flat_hash_map and friends.
- deleted 7y ago[deleted]