maps and unordered_maps time complexity analysis

0
votes

I used to believe that unordered_map is better in time-complexity than map in C++. But today while I was doing a problem(Molly's Chemicals), I got time-limit exceeded. After a lot of guess-work(because I thought my solution was correct), I tried using a map instead of an unordered_map and as a surprise I got it accepted.In some cases in which due to a lot of collisions unordered_map can have a big constant multiplier which will increase its actual complexity to greater than that of a map(corrections are welcomed).

i searched a lot about time complexity of different functions of maps and unordered maps but i didnt find a proper content as i want to know that when should i use maps or unordered maps. Can anybody please explain difference between the use of maps and unoredered_maps in terms of time complexity.

2
c++dictionarymapstime-complexityc++14
ordered maps keep keys in a sorted manner (as the name suggests). Time complexity for these depends on where they are used (how frequent inserts are, how frequent lookups are, etc.) - ghost
Does this answer your question? Is there any advantage of using map over unordered_map in case of trivial keys? - ghost
thanks for suggesting me @ghost. but i want to know the difference between the use of maps and unoredered maps in terms of time complexity . In simple terms , please tell me the insertion , seraching , finding in maps time complexity - Tushar Jain
I did get TLE in the same problem since too many elements in the same bucket. - yao99

2 Answers

2
votes

unordered_map

Requirements of unordered_map in ISO C++, [tab:container.hash.req]:

+------------------+-----------------------------------------------------+
|    Expression    |                     Complexity                      |
+------------------+-----------------------------------------------------+
| a_­uniq.insert(t) | Average case O(1), worst case O(a_uniq.size()).     |
| a.erase(k)       | Average case O(a.count(k)), worst case O(a.size()). |
| b.find(k)        | Average case O(1), worst case O(b.size()).          |
+------------------+-----------------------------------------------------+

The time complexity of each operator in unordered_map in the worst case is O(n). It will happen if all elements in the same bucket.

And a special test data may be constructed by tracing the code of compiler like the post on Codeforces shows how to construct such test data on gcc.

map

Requirements of map in ISO C++, [tab:container.assoc.req]:

+------------------+--------------------------+
|     Expression   |        Complexity        |
+------------------+--------------------------+
| a_­uniq.​insert(​t) | logarithmic              |
| a.erase(k)       | log(a.size())+a.count(k) |
| b.find(k)        | logarithmic              |
+------------------+--------------------------+

The time complexity of map is guaranteed to be O(log n).

0
votes

The data structure behind map is rb-tree while unordered_map uses hash table as its data structure. So we can analayze these two containers via anaylayzing rb-tree and hash table.

find/insert an element in map: O(log n) find/insert an element in unordered_map: O(1)