Hello,
Recently, I was doing Cow Run (http://www.usaco.org/index.php?page=viewproblem2&cpid=265), and I at first used the Policy Based Data Structure faster map (https://mirror.codeforces.com/blog/entry/60737), but I TLE'd on the last 4 test cases. I then switched back to using the unordered_map, and I passed all the test cases. Can anyone tell me the reason why the unordered_map was faster? I was under the impression that the PBDS map was faster. Thanks!
Code with unordered_map: https://ideone.com/Id7SZM Code using PBDS map: https://ideone.com/sA4UJG
To run this code, simply submit them in a file to the USACO website above, and use C++11.
-dx24816
As I mentioned in the blog post, one downside of gp_hash_table is that it's significantly more fragile to weak hash functions (due to being open addressed and using power of 2 table sizes). I can't currently submit to USACO for whatever reason..., but I did run it on the test data.
I use this hash function
unsigned hash_f(unsigned x) { x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x) * 0x45d9f3b; x = (x >> 16) ^ x; return x; }and I got 0.10 for gp_hash_table versus 0.30 for unordered_map.https://ideone.com/ikfX3E
You can also use
cc_hash_tablefor a hash table that's a lot more resistant to weak hash functions.