infinitepro's blog

Is tr1::unordered_map better than a regular hash table [C++]?
By infinitepro, history, 5 years ago, In English

I was solving 877F today. My code kept TLE'ing on TC #11 while using both map<> and unordered_map<>. While skimming through the accepted solutions, I stumbled on this solution, which is exactly similar to my solution, but uses tr1::unordered_map<> instead of the regular std::unordered_map<>.

Unsurprisingly, changing my code to tr1::unordered_map<> gives an AC.

Now, I have some questions.

  • Is this relatively unknown implementation better than the regular unordered_map?
  • Can this ds be hacked similar to how unordered_map is hacked? If yes, how?
  • Are all the other variants like tr1::set<>, tr1::unordered_set<> etc better than the regular ones?
  • Vote: I like it
  • +23
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

btw i got tle on unordered_map,but got ac on map

→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

check this

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

Anyone?

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

    My guess is that std::tr1::unordered_map has a different hash function for ints/long long's than std::unordered_map. Now when people are trying to make anti-unordered_map hash tests, they might miss submissions that use std::tr1::unordered_map. In the future, never use std::unordered_map or std::tr1::unordered_map without a custom hash. By default, std::unordered_map hash is dogshit. Instead read this awesome blog by neal that outlines how std::unordered_map can be hacked and how to avoid it.

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

    You asked this question 14 months ago. You could've become an expert, or at least be very advanced on modern C++ and standard library by now.

    You shouldn't use the std::tr1 namespace in C++17, as it is being deprecated and its existence likely depends on a compiler version.

    TR1 stands for Technical Report 1. All its content went into standard in C++11. I didn't dive into the implementation of standard unordered map, but I'm guessing not much has changed. So probably the difference is a single detail, like size of an empty container, resizing constant or default underlying container.

    Instead of treating the standard library as a black box, try to understand it. Search in google for benchmarks of containers. Start here: https://en.cppreference.com/w/cpp/container/unordered_map

    → Reply