1

I used unordered_map<long long int, long long int> the key may take values of upto 1e9, this lead to my answer being Time Limit Exceeded.

when I used map<long long int, long long int> it was succesful.

I came to know from other answers that unordered_map is bad when hash function is bad , is there a way to change the hash function of this unordered_map?

Ram Prabodh Induri
  • 95
  • 1
  • 11
  • 1
    Have a look at this: https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key – ghost Jun 29 '20 at 06:58
  • It seems very unlikely that the standard hash function for `long long int` would be bad, and even more unlikely that `map` would be better. I think your problems are probably caused by some other issue. – john Jun 29 '20 at 07:03

2 Answers2

2

Yes, you are free to do so.

The third template parameter of std::unordered_map is the hash function going to be used, and it should be a functor that satisfy the requirement listed here.

LIU Qingyuan
  • 524
  • 5
  • 18
  • https://en.cppreference.com/w/cpp/container/unordered_map Also check here, google or follow the link for anything you don't understand and it should not be too hard to follow. – LIU Qingyuan Jun 29 '20 at 07:03
1

I think there might be another cause to this.

If there are more insertions and deletions as compared to lookups, then map is faster. However, if there are more lookups, then unordered_map should provide a performance boost.

Have a look at this: https://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys#:~:text=map%20just%20has%20a%20few,it%20lacks%20the%20large%20array.

PS: Could you share the question once, for a greater insight?

ghost
  • 1,107
  • 3
  • 12
  • 31
  • 1
    *"If there are more insertions and deletions as compared to lookups, then map is faster. However, if there are more lookups, then unordered_map should provide a performance boost."* - that's awfully presumptuous; a lot will depend on collision proneness of keys, hash function used, hash table size (e.g. GCC tends to use prime sizes, Visual C++ powers of 2), CPU/memory/cache architectural properties, number of values stored.... See also https://stackoverflow.com/a/3999891/410767 for hard stats contradicting that. – Tony Delroy Jun 30 '20 at 11:42