I always listened that unordered_map is more cache friendlier than map. My intuition tells me unordered_map is better to iterate, and map is better to random access.
Unordered map is a hash map. Map is a binary search tree.
There’s no random access for hash map, in the sense of “give me the fifth element”. If you mean a lookup, like map[key], hash map has an O(1) amortized look up, where as a binary tree has an O(log n) look up, so hash map will generally be faster in this regard.
By "iterate" I expect they mean to just look at all the key/value pairs in the map. Since it says "Unordered" right in the name they don't care what order they see the elements, just that they see them all.
This is easy to do in all sane hash map designs, and is very fast in a linear design like Abseil's Swiss Tables.
Also sadly C++ std::unordered_map is guaranteed to be not just a hash table but an open hash table, using buckets to keep all the stuff which collided together. This is probably not what you wanted, but too bad that's what was standardized.
> so hash map will generally be faster in this regard.
Complexity is not a measure of runtime. The performance drawbacks for std::map have to do with cache, not O(log) vs O(1). log(billion) is 30. And that's exactly how many comparisons you have to do, not a constant multiple of that.
With an open addressing hash table, who knows how many steps you will need to find an element. It's even more questionable if it does linked list chaining.
> binary search tree.
It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.
> My intuition tells me unordered_map is better to iterate, and map is better to random access.
map is definitely not better for random access, with the possible exception of adversarial input: IIRC std::map pretty much requires an rbtree so you get an O(log2(n)) access, while unordered_map is a hashmap so has an O(1) best case but O(n) worst case.
unordered_map might have a better cache friendliness (though that's debatable as IIRC the standard requires closed-hashing), however iterating it is a long series of unpredictable branches (each bucket can be empty or full and the better your hash function the more random it is), std::map requires a lot of pointer-chasing instead but it's all completely predictable.
Map is unfriendly in several ways because of the nodes being allocated with new by default. You can significantly improve its behavior by constructing the map with an arena allocator. Then you will enjoy better cache locality and cheaper mutations.
powersnail|3 years ago
There’s no random access for hash map, in the sense of “give me the fifth element”. If you mean a lookup, like map[key], hash map has an O(1) amortized look up, where as a binary tree has an O(log n) look up, so hash map will generally be faster in this regard.
tialaramex|3 years ago
This is easy to do in all sane hash map designs, and is very fast in a linear design like Abseil's Swiss Tables.
Also sadly C++ std::unordered_map is guaranteed to be not just a hash table but an open hash table, using buckets to keep all the stuff which collided together. This is probably not what you wanted, but too bad that's what was standardized.
sicp-enjoyer|3 years ago
Complexity is not a measure of runtime. The performance drawbacks for std::map have to do with cache, not O(log) vs O(1). log(billion) is 30. And that's exactly how many comparisons you have to do, not a constant multiple of that.
With an open addressing hash table, who knows how many steps you will need to find an element. It's even more questionable if it does linked list chaining.
> binary search tree.
It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.
masklinn|3 years ago
map is definitely not better for random access, with the possible exception of adversarial input: IIRC std::map pretty much requires an rbtree so you get an O(log2(n)) access, while unordered_map is a hashmap so has an O(1) best case but O(n) worst case.
unordered_map might have a better cache friendliness (though that's debatable as IIRC the standard requires closed-hashing), however iterating it is a long series of unpredictable branches (each bucket can be empty or full and the better your hash function the more random it is), std::map requires a lot of pointer-chasing instead but it's all completely predictable.
jeffbee|3 years ago