A recent talk about unordered_map
in C++ made me realize that I should use unordered_map
for most cases where I used map
before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I use a map, I use either int
or std::string
as the key type; hence, I've got no problems with the definition of the hash function. The more I thought about it, the more I came to realize that I can't find any reason of using a std::map
over a std::unordered_map
in the case of keys with simple types -- I took a look at the interfaces, and didn't find any significant differences that would impact my code.
Hence the question: is there any real reason to use std::map
over std::unordered_map
in the case of simple types like int
and std::string
?
I'm asking from a strictly programming point of view -- I know that it's not fully considered standard, and that it may pose problems with porting.
Also, I expect that one of the correct answers might be "it's more efficient for smaller sets of data" because of a smaller overhead (is that true?) -- hence I'd like to restrict the question to cases where the amount of keys is non-trivial (>1 024).
Edit: duh, I forgot the obvious (thanks GMan!) -- yes, maps are ordered of course -- I know that, and am looking for other reasons.
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 spread keys in std::map tends to outperform std::unordered_map when map size is under 10000 elements. 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.
unordered_map vs map : map (like set) is an ordered sequence of unique keys whereas in unordered_map key can be stored in any order, so unordered. The map is implemented as a balanced tree structure that is why it is possible to maintain order between the elements (by specific tree traversal).
Because unordered_map containers do not allow for duplicate keys, this means that the function actually returns 1 if an element with that key exists in the container, and zero otherwise.
Don't forget that map
keeps its elements ordered. If you can't give that up, obviously you can't use unordered_map
.
Something else to keep in mind is that unordered_map
generally uses more memory. map
just has a few house-keeping pointers, and memory for each object. Contrarily, unordered_map
has a big array (these can get quite big in some implementations), and then additional memory for each object. If you need to be memory-aware, map
should prove better, because it lacks the large array.
So, if you need pure lookup-retrieval, I'd say unordered_map
is the way to go. But there are always trade-offs, and if you can't afford them, then you can't use it.
Just from personal experience, I found an enormous improvement in performance (measured, of course) when using unordered_map
instead of map
in a main entity look-up table.
On the other hand, I found it was much slower at repeatedly inserting and removing elements. It's great for a relatively static collection of elements, but if you're doing tons of insertions and deletions the hashing + bucketing seems to add up. (Note, this was over many iterations.)
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