std::map is actually O(logn) to find. A hashmap (std::unordered_map) would be what to use for efficiency

I'm not an expert but, IIUC, there are more efficient solutions here. This one is O(n log n) due to sorting. But there are some that use either std::map or vectors to keep counts of each letter in each string. Those should be O(n).

It doesn't change anything, this approach would work fine.

But there's a caveat: if the first string is really long it'll be slow.