[sagarm]

std::unordered_map is usually slow while std::sort is quite fast. std::unordered_map's API includes pointer stability across map resizes, which requires storing the contents of the map out-of-line in a separately allocated memory block.

This results in poor cache utilization and higher memory management overhead.

The SwissTable family of containers are much faster if you do not have this requirement. See https://abseil.io/about/design/swisstables

for more on the optimizations that make them fast.

I wrote a quick benchmark to compare sorting, std::set, std::unordered_set, and ska::flat_hash_set (an older version of SwissTable I believe) and flat_hash_set was generally ~2.4x faster, even up to 100M integers.

https://pastebin.com/y5UsPek5