Kornel Kisielewicz Kornel Kisielewicz - 11 months ago 50
C++ Question

Is there any advantage of using map over unordered_map in case of trivial keys?

A recent talk about

in C++ made me realize, that I should use
for most cases where I used
before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I use a map I use either
's or
as keys, 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
in case of simple types over a
-- 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
unordered map
in case of simple types like

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, map's are ordered of course -- I know that, and am looking for other reasons.

Answer Source

Don't forget the map's keep their elements ordered. If you can't give up that, obviously you can't use an unordered_map.

Something else to keep in mind is that unordered_map's generally use more memory. A map just has a few house-keeping pointers then memory for each object. Contrarily, unordered_map's have 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, a map should prove better, because it lacks the large array.

So, if you need pure lookup-retrieval, I'd say an 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 an unordered_map instead of a 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.)