Logarithmic time is still very fast. Say it takes N time when you have 1000 objects. Now increase the size so you have a million objects----1000 times as many. Access will now take approximately N*2 time.

You would typically design a key object to contain just the relevant data. If you only need two things, a std:air may be good enough.