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.com/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