5 ms·

> and it doesn't support unordered_map (or even use it as the default) for objects. std::unordered_map has massive overhead in space and time. Maybe I misunder

> and it doesn't support unordered_map (or even use it as the default) for objects. std::unordered_map has massive overhead in space and time. Maybe I misunderstand your idea, but outside of extremely niche use cases, std::unordered_map is basically never the right tool (unless you don't care in the slightest about performance or memory overhead).

agent327 5y ago
Source? A hash map should in principle be faster than a tree, with far fewer comparisons, and against a computed hash value instead of the whole object, in principle.
- einpoklum 5y ago
  Well, std::unordered_map is faster than than std::map, but it is still slow, since it uses lists for its buckets, with lots of dynamic allocation. See also: https://stackoverflow.com/a/42588384/1593077 https://stackoverflow.com/a/42588384/1593077 and the link there. Not sure that's what GP meant though.
  - agent327 5y ago
    I don't believe it has to, some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type. And I don't like it when people use ridiculous hyperbole to describe what is in reality barely perceptible overhead, so it would be good if the person I originally responded to came out and defended his POV. Hopefully using actual numbers instead of agitated handwaving and screaming...
    - beached_whale 5y ago
      Abseil has a btree based hash map and it performs much better. I think it maintains the same constrains(iterator invalidation/exception safety...) as std::unordered_map. The issue is that the implementors won't change their implementation of unordered_map as it's an ABI break, to say it simply. It could be better. But also, there are other tools like flat maps/open addressing that are not done in the std library.
    - MauranKilom 5y ago
      > some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type Pretty sure that makes it impossible to implement merge without pointer/iterator invalidation, which is a constraint imposed by the standard (https://en.cppreference.com/w/cpp/container/unordered_map/merge https://en.cppreference.com/w/cpp/container/unordered_map/me...). > it would be good if the person I originally responded to came out and defended his POV See https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... if you want numbers, or for example this talk by the same author https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ.
spacechild1 5y ago
> 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).
batty_alex 5y ago
I think you might have it backwards. std::map is the one you only want to reach for in cases where you need a sorted dictionary (it sorts after insert) std::unordered_map is typically the go-to hash map on any given C++ day. You’re probably fine with std::map outside of large n EDIT: being pedantic
wmkn 5y ago
What? I would argue that unordered_map is nearly always a reasonable choice when in need of an unordered associative container. There is nothing particular wrong with it. Not sure what your rationale is for saying it’s only useful for extremely niche use cases. I would be curious to know why you think so.
- MauranKilom 5y ago
  It has the right asymptotic guarantees for a hash map, but beyond that it doesn't have much going for it. The degree to which it emphasizes pointer/iterator stability and arbitrary load factors is not a good tradeoff in almost any practical case (unless you do not care about performance). See https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ for a more comprehensive discussion, or the sibling threads here.

agent327 5y ago

Source? A hash map should in principle be faster than a tree, with far fewer comparisons, and against a computed hash value instead of the whole object, in principle.

einpoklum 5y ago
Well, std::unordered_map is faster than than std::map, but it is still slow, since it uses lists for its buckets, with lots of dynamic allocation. See also: https://stackoverflow.com/a/42588384/1593077 https://stackoverflow.com/a/42588384/1593077 and the link there. Not sure that's what GP meant though.
- agent327 5y ago
  I don't believe it has to, some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type. And I don't like it when people use ridiculous hyperbole to describe what is in reality barely perceptible overhead, so it would be good if the person I originally responded to came out and defended his POV. Hopefully using actual numbers instead of agitated handwaving and screaming...
  - beached_whale 5y ago
    Abseil has a btree based hash map and it performs much better. I think it maintains the same constrains(iterator invalidation/exception safety...) as std::unordered_map. The issue is that the implementors won't change their implementation of unordered_map as it's an ABI break, to say it simply. It could be better. But also, there are other tools like flat maps/open addressing that are not done in the std library.
  - MauranKilom 5y ago
    > some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type Pretty sure that makes it impossible to implement merge without pointer/iterator invalidation, which is a constraint imposed by the standard (https://en.cppreference.com/w/cpp/container/unordered_map/merge https://en.cppreference.com/w/cpp/container/unordered_map/me...). > it would be good if the person I originally responded to came out and defended his POV See https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... if you want numbers, or for example this talk by the same author https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ.

spacechild1 5y ago

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

batty_alex 5y ago

I think you might have it backwards. std::map is the one you only want to reach for in cases where you need a sorted dictionary (it sorts after insert) std::unordered_map is typically the go-to hash map on any given C++ day. You’re probably fine with std::map outside of large n EDIT: being pedantic

wmkn 5y ago

What? I would argue that unordered_map is nearly always a reasonable choice when in need of an unordered associative container. There is nothing particular wrong with it. Not sure what your rationale is for saying it’s only useful for extremely niche use cases. I would be curious to know why you think so.

MauranKilom 5y ago
It has the right asymptotic guarantees for a hash map, but beyond that it doesn't have much going for it. The degree to which it emphasizes pointer/iterator stability and arbitrary load factors is not a good tradeoff in almost any practical case (unless you do not care about performance). See https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ for a more comprehensive discussion, or the sibling threads here.