3 ms·

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

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).