It's been a while, so my memory could be playing tricks on me. However, I believe the specified std::unordered_map iterator invalidation behavior rules out efficient use of open addressing unless someone comes up with some timsort-level novel implementation ideas.