3 ms·

> but outside of extremely niche use cases, std::unordered_map is basically never the right tool std::map is only useful if you need the data to be ordered, ot

> but outside of extremely niche use cases, std::unordered_map is basically never the right tool std::map is only useful if you need the data to be ordered, otherwise std::unordered_map is the right default choice. > std::unordered_map has massive overhead in space and time. Yes, std::unordered_map uses a bit more memory, but please show me some benchmarks where it is slower than std::map - especially with string keys! BTW, for very small numbers of items the most efficient solution is often a plain std::vector + linear search.

codr7 5y ago
It's a gradient, from the vector you mentioned all the way up to hash maps. And ordered maps fall somewhere in the middle. They might make sense if you're creating massive amounts of medium sized maps. Or if you need range searches etc. It's all compromises, there are no hard rules.
adzm 5y ago
> BTW, for very small numbers of items the most efficient solution is often a plain std::vector + linear search. This is why flat_map is a great solution. It's basically an ordered vector with a map-like interface, but without the memory allocation (and cache locality issues) for each node. Until you start getting into thousands of elements it is probably the best choice of container.
MauranKilom 5y ago
I didn't meant to imply it will perform worse than std::map. My point is that std::unordered_map has very particular design tradeoffs (primarily the requirement for arbitrary load factors and the bucket interface) that fundamentally impose large space and time overhead: Every node has to be stored as separately allocated linked list entry. That's sometimes ok, particularly if you don't care about performance (beyond asymptotic behavior). But if you do, you'd probably be well-advised to try out hash map implementations that actually don't leave performance on the table by design.
- spacechild1 5y ago
  > I didn't meant to imply it will perform worse than std::map You literally suggested to (almost) always prefer std::map... > Every node has to be stored as separately allocated linked list entry. But it's basically the same for std::map. Both containers have similar design constraints. I am aware that std::unordered_map uses more memory than std::map, but why should it be slower in the general case? After all, hashtables trade memory for speed. > But if you do, you'd probably be well-advised to try out hash map implementations that actually don't leave performance on the table by design. I agree. But the same is true for std::map (someone has already mentioned flat maps).

codr7 5y ago

It's a gradient, from the vector you mentioned all the way up to hash maps. And ordered maps fall somewhere in the middle. They might make sense if you're creating massive amounts of medium sized maps. Or if you need range searches etc. It's all compromises, there are no hard rules.

adzm 5y ago

> BTW, for very small numbers of items the most efficient solution is often a plain std::vector + linear search. This is why flat_map is a great solution. It's basically an ordered vector with a map-like interface, but without the memory allocation (and cache locality issues) for each node. Until you start getting into thousands of elements it is probably the best choice of container.

MauranKilom 5y ago

I didn't meant to imply it will perform worse than std::map. My point is that std::unordered_map has very particular design tradeoffs (primarily the requirement for arbitrary load factors and the bucket interface) that fundamentally impose large space and time overhead: Every node has to be stored as separately allocated linked list entry. That's sometimes ok, particularly if you don't care about performance (beyond asymptotic behavior). But if you do, you'd probably be well-advised to try out hash map implementations that actually don't leave performance on the table by design.

spacechild1 5y ago
> I didn't meant to imply it will perform worse than std::map You literally suggested to (almost) always prefer std::map... > Every node has to be stored as separately allocated linked list entry. But it's basically the same for std::map. Both containers have similar design constraints. I am aware that std::unordered_map uses more memory than std::map, but why should it be slower in the general case? After all, hashtables trade memory for speed. > But if you do, you'd probably be well-advised to try out hash map implementations that actually don't leave performance on the table by design. I agree. But the same is true for std::map (someone has already mentioned flat maps).