3 ms·

STL data structures are explicitly defined as to their internals, which in turn implies their performance. For example, when you're using a STL map, you know it

• ComputerGuru 16y ago
  Actually, it's the exact opposite. The STL specification specifies the complexity but not the underlying data structure. For instance, if you'll refer to section 23.1.2 of the C++ 2003 standard ("Associative Containers"), you'll find that nowhere does it mention "tree," though it does explicitly lay out the complexity requirements for associative containers such as map and multimap, that at the end of the day, can really only be had with one type of tree or the other. Table 69 goes through all the functions and operations and the complexities allotted for each. Some are even explicitly specified as "compile time" operations. No C++ implementation is allowed to deviate from this, even to provide better performance.
  • deleted 16y ago
    [deleted]
  • beoba 16y ago
    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.
    • ot 16y ago
      > 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
      • beoba 16y ago
        True, but you still end up with similar performance to a tree.