> I quickly realized that the map had a high overhead - all those pointers in a red-black tree consume more RAM than my data!
That is true if you use std::map , which should only be used if you have a strong requirement in having sorted keys.
If you do not have a requirement to keep sorted keys, you should use std::unordered_map which internally implements a dictionary as a hash table, exactly as std::unordered_set.
> As I was storing only once and doing lookups many times, it was simpler to simply sort all the keys, and then store the values. When I needed to do a lookup, I'd do a binary search and find it. Algorithmically same complexity as a map.
If you used std::unordered_map instead, you would be doing the same thing with a constant-time computational complexity instead of logarithmic, while retaining linear space complexity.
That is true if you use std::map , which should only be used if you have a strong requirement in having sorted keys.
If you do not have a requirement to keep sorted keys, you should use std::unordered_map which internally implements a dictionary as a hash table, exactly as std::unordered_set.
> As I was storing only once and doing lookups many times, it was simpler to simply sort all the keys, and then store the values. When I needed to do a lookup, I'd do a binary search and find it. Algorithmically same complexity as a map.
If you used std::unordered_map instead, you would be doing the same thing with a constant-time computational complexity instead of logarithmic, while retaining linear space complexity.