Performance difference for iteration over all elements std::unordered_map vs std::map?

Question

I wanted to map data with pointer as the key. What container should I have chosen, map or unordered_map? There are multiple questions on stackoverflow for this topic but none of them covers the performance aspect when we need to iterate over all the key-value pairs.

std::map<classKey* , classData*> myMap;
std::unordered_map<classKey* , classData*> myUnorderedMap;

for (auto & iter : myMap) { //loop1
    display(iter.second);
}

for (auto & iter : myUnorderedMap) { //loop2
    display(iter.second);
}

loop1 vs loop2 which one gives better performance. Bench Mark Provided by @RetiredNinja

For size = 10,000,000 We get following benchmark results:

Interesting. Off had I have no idea. I'd put my money on std::map though. Are you able to set up some test cases for profiling? — Bathsheba
– Bathsheba, Commented Jun 30, 2019 at 14:28
Structurally, I would expect std::map to be slightly faster, but that the difference would be small enough to be swamped by other concerns (like whether the elements of either one were in your cache) — Marshall Clow
– Marshall Clow, Commented Jun 30, 2019 at 14:31
@MichaelChourdakis again, OP asks about performance, not efficiency regarding time complexities. — Fureeish
– Fureeish, Commented Jun 30, 2019 at 14:35
Quick Bench is outstanding; have used it to great effect (if I do say so myself) — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Jun 30, 2019 at 16:17

JimPri · Accepted Answer · 2019-06-30 15:47:46Z

7

As you might expect, this depends heavily on the actual implementation of the standard library data structures. Therefore, this answer will be a bit more theoretical and less tied to any one implementation.

A std::map uses a balanced binary tree under the covers. This is why it has O(log(n)) insertion, deletion, and lookup. Iterating over it should be linear because you just have to do a depth-first traversal (which will require O(log(n)) memory in the form of stack space). The benefit of using a std::map for iteration is that you will iterate over the keys in sorted order and you will get that benefit "for free".

A std::unordered_map uses a hash table under the covers. This allows you to have an amortized constant time insertion, deletion, and lookup. If the implementation is not optimized for iterating, a naive approach would be to iterate over every bucket in the hash table. Since a good hash table (in theory) has exactly one element in 50% of the buckets and zero in the rest, this operation will also be linear. However, it will take more "wall clock time" than the same linear operation for a std::map. To get around this, some hash table implementations keep a side list of all of the elements for fast iterations. If this is the case, iterating on a std::unordered_map will be faster because you can't get much better than iterating over contiguous memory (still linear time though, obviously).

In the extremely unlikely case that you actually need to optimize to this level (instead of just being curious about the performance in theory), you likely have much bigger performance bottlenecks elsewhere in your code.

All of this ignores the oddity of keying off of a pointer value, but that's neither here nor there.

Sources for further reading:

GCC std::map implementation

GCC std::unordered_map implementation

How GCC std::unordered_map achieves fast iteration

edited Jun 30, 2019 at 15:47

answered Jun 30, 2019 at 15:05

JimPri

1,43510 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

πάντα ῥεῖ Over a year ago

"A std::map uses a balanced binary tree under the covers", "A std::unordered_map uses a hash table under the covers." Any reliable source for these claims?

JimPri Over a year ago

Admittedly, it is a broad statement since there is nothing explicitly in the standard to require those design choices. However, both the GCC and MS VS compilers implement them this way (as do most well known compilers).

Fureeish Over a year ago

@πάνταῥεῖ humanity's inability to (so far) come up with better implementations satisfying standard's requirements combined with no contraindications to implement the structures in such a way is, for me, enough to assume this (or close to this) implementation. Yes, the standard says nothing about the concrete implementations, but what else do we got?

Quimby Over a year ago

Your last source says that the hash map keeps a linked list of iterators(= pointers ) to buckets. That is not contiguous at all(2 indirections). Only buckets will be. And there's no reason why the map cannot do the same with nodes. I would really like to see some measurements as an answer.

Sebastian Redl Over a year ago

"Iterating over it should be linear because you just have to do a depth-first traversal (which will require O(log(n)) memory in the form of stack space)." - That's not how std::map iterators work. They are external iterators and cannot allocate any stack space. Incrementing a tree iterator is only amortized constant time. (Iterating over the entire tree is still linear.) See here: github.com/gcc-mirror/gcc/blob/…

|

Collectives™ on Stack Overflow

Performance difference for iteration over all elements std::unordered_map vs std::map?

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related