TL;DR: The Policy Hash Table has 20-30% faster linear insertion/deletion, equal performance for random insertion/deletion, and 3-10x increase for writes/reads. Only downside is that clear is slower on a Policy Hash Table with random insertion order.

I've often been irritated by how slow unordered_map is in C++. Too often, I have something that runs fast enough in terms of complexity, but the constant factor from unordered_map slows down the solution too much. Yesterday though, after using the useful order statistics tree from https://codeforces.me/blog/entry/11080, I was curious if there were any other useful data structures hiding in the Policy STL. And lo and behold, I found a hash table.

Well, enough backstory, let's look at some numbers.

unordered map linear insertion:                                 0.743023
policy hash table linear insertion:                             0.465051

unordered map linear read/write:                                0.205146
policy hash table linear read/write:                            0.034896

unordered map random insertion:                                 3.08992
policy hash table random insertion:                             3.0686

unordered map random read/write:                                0.225844
policy hash table random read/write:                            0.051624