std::map (as opposed to std::unordered_map) uses a balanced binary search tree approach and thus guarantees O(log n) lookup for anything that has a well-defined total order (i.e. comparison function), without worrying about hash functions, etc.

So, yes you can ;)

Sure, just use a tree-based map such as `std::map`. (Which, as the name implies, was the OG associative container in C++.)

If you don't care about performance at all you can of course do that. For many real world applications however asymptotic runtimes are not enough, you need to care about constant factors too.