Menu
What is the typical layout of std::unordered_map<K, V>? Are the K and V objects stored in the buckets themselves, or do the buckets store pointers to nodes containing the keys and values?
I'm trying to figure out the performance implications of using std::unordered_map<K, V> versus std::unordered_map<K, V*>. Assuming I only ever emplace and look up values, is there any reason to prefer the latter, even if the values are quite large? The only reason I can imagine is if the values are stored in-line in buckets, and need to be re-allocated each time the container is rehashed.
Is there anything in the standard that guarantees this won't happen?
613
map is used to store elements as key,value pairs in sorted order. unordered_map is used to store elements as key,value pairs in non-sorted order.
Insertion of dense keys in std::map doesn't present performance difference with std::unordered_map under 1000 elements. In all other situations std::unordered_map tends to perform faster.
Generally, an unordered_map in C++ is faster than map in C++ because the average time complexity for insertion, deletion, and updation is O(1) while in the case of map, the average time complexity for all the operations is O(log(n)) where n is the number of elements present inside the map.
unordered_map is an associated container that stores elements formed by the combination of a key value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.
[unord.req]/8:
Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.
The fact that pointers and references to elements are not invalidated by rehashing (or insertion/deletion, see /13) pretty much means that they have to be node based.
C++17 even exposes node handles so that you can transfer nodes between two unordered_maps.
63
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
