CODEWITHSUNDEEP
c++c++11
CollioTV
CollioTV

Reputation: 686

Map and unordered_map

My question is more for learning purpose than for debugging purpose:

I'm currently optimising a code for a little game of mine, and I wanted to know:

I'm using a map for dispatching some value inside my programme, so is a unordered_map faster in use than a map?

(btw sorry for my english, it's not my native language!)

Upvotes: 2

Views: 297

Answers (2)

Mats Petersson
Mats Petersson

Reputation: 129314

A std::unordered_map is a "hash_map", which means that searching it is O(1), where a std::map is a red-black tree, searching that is O(log2(n)). So, if you have 1000 elements, the difference is looking at 10 keys in the std::map before finding the "right" one, vs. looking at one. With 1 million elements, we look at 20 keys in the std::map before getting to the "right" one - still only one in a std::unordered_map.

However, you need to hash the "key", which means doing some form of calculation to make it a number.

It also depends on how often you insert/remove elements, compared to how often you just look up the elements.

For larger data-sets, the size and locality can also have a big impact, and searching through the "first few layers" is often quick because it's in the cache [if you are searching through the same map several times], where unordered map is taking up more space (have to have some "spare" slots, because it's very unlikely that all 10000 elements generate hash values that are exactly 10000 elements, so typically, the hash map is far from "full"). Because "recent" hash searches are unlikely to match current ones, cache probably doesn't help much either.

And of course, the std::unordered_map is, as the name implies, unordered - if you iterate through it, the keys are in hash-order (modulo bucket-count, so even if you know the hash, it's typically hard to know what order it is), not in "sorted" order. This can be important in some cases.

So whether that gives you any noticeable performance benefit is something you will have to figure out by measuring the performance.

Upvotes: 2

Westranger
Westranger

Reputation: 1367

The difference here is that a map internally uses a red black tree and a unordered map is s hash table. The unordermap is very fast compared to the map because putting elements into the map required just 1 (O(1)) "actions" where the map needs to find the correct position in the tree to store the value which was put into the map (O(log n)). You can also read the C++ doc for map and unordermap

Upvotes: 0

Related Questions