I think of it in these terms: If you're implementing a key for a std::map, you have to implement operator<, which in turn implies that std::map is tree-based. S

I think of it in these terms: If you're implementing a key for a std::map, you have to implement operator<, which in turn implies that std::map is tree-based. Similar for unordered_map, which would want operator== and a hash function. Either of these interfaces are effectively describing what the internals are going to look like, even if the official standard decides to be coy about using the terms "tree" or "hash map" when describing them. In the case of Python, the fact that {}.keys() has no guaranteed order (for example) already implies that dictionaries are hash based and would have similar characteristics to any other hash map.