> 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.

> 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. Not necessarily. For example a skip list can satisfy the same requirements but it is not a tree