Hello guys,
Since a long time i was under the impression that STL unordered_map is faster due to its non ordering than STL map.
But in a problem when i submitted the solution using unordered_map i got TLE but with map i got AC.
Can anyone please provide an insight into this because i am not able to understand why this happened for this particular solution.
For reference, this is the solution using unordered_map : 33578534 and this one using map : 33578782.
This is the actual problem 776C - Химикаты Молли
.
This can be explained by a single fact that Unordered_map is implemented using a hash table. In which a hash key is generated for the input and it is stored at the key location. Whereas in case of Ordered Map or map it is stored in a tree.
So whenever same values are stored in an unordered_map then there will be a link list at the key. And it will take O(n) time to access a link list. Whereas in ordered_map it will always take O(log n) time.
So, it is advisable to use unordered_map in case of unique elements only.
Correct me if i am wrong but in this problem, the value of the corresponding key is being updated(adding) and not appending so i guess there is nothing like linked list in this case.
I thought by definition map and unordered map only store unique elements and you have to use multimap and unordered multimap to deal with non-unique elements.
Antihashmap test.
I didn't get you dalex ... Can you please elaborate?
Hashmap works in O(n) per query in worst case. This test is the worst case.