prthptl14's blog

Doubt, Help me.
By prthptl14, history, 4 years ago, In English

Doubt When should I use unordered_map and when should I use a map in c++.In this question Div 3 #479 contest question F when I submit using unordered_map I got TLE but the same solution when I submit using a map my code accepted. Here is my solution using unordered_map and using map. Please help me.

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

It's because of you use 

#define int long long

in the first code but don't use it in the second one

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

I just modified your code a little bit:

AC (140ms) after using custom hash: 80916930. Learn more here.

AC (124ms) after further optimization: 80917090. Learn more here.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you link to a nice resource about custom hashes?

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

Since unordered_map is not sorted as elements are stored in hash tables, you use that when u want to access the single element i.e no traversal is required or store the frequency of element and u don't want it sorted.

Whereas ordered_map or simply map is sorted as elements are stored in BST, it is used when u want elements in a sorted manner, when u want to traverse in order. Or u want to find(search) an element as it uses the concept of binary search O(log n). U can also use the concept of lower_bound and upper_bound in this.

→ Reply