> I choose 64-bit integers, but strings would do fine as well.

No it would not.

Sorting 64 bits integers in a vector is fast obviously since they are stored contiguously in memory, so you get to benefit from all the caching layers (L1, L2, L3, TLB) nicely.

Since string are of unknown size, the actual string content is stored somewhere in the heap and reference it via a pointer [1]. If you have a vector of strings, to compare string i and string j, you will need to make those 2 pointers dereference , which will jump to 2 random memory locations.

With the hash table you already pay for 1 indirection, which is really what is slow here. With a vector<string> you now also need to pay for 1 indirection, so the performance compared to a vector<int> would be very different.

[1] https://stackoverflow.com/questions/42049778/where-is-a-stds...