nine.nine's blog

Time Complexity for unordered_map{int,multiset{int}} and unordered_map{int,vector{int}}
By nine.nine, history, 4 years ago, In English

If I use unordered_map<int,multiset> to store the values, it gives a TLE. In the same code, if I change it to unordered_map<int,vector>, and sort the map's value when taken into use (to act like multiset), doesn't give a TLE. How/Where is the time complexity different for both ?

P.S. — Pardon me if I did not follow the conventions of a blog, this being the first one. Would be happy to know about my mistakes.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The constant factor of unordered_map is better than that of map.

You can use PBDS hash tables for even faster performance.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

multiset has insert in $$$O(log(n))$$$, while vector has O(1) push_back. Multiset insert, Vector push_back

→ Reply