3 ms·

std::map is implemented using a tree and not a hash table because it's specified as an ordered data structure.

• sorbits 12y ago
  I am quite sure (based on interviews I’ve read) that Alexander Stepanov’s primary concern was having a data structure with known (fixed) complexity rather than a sorted container. The latter is just a nice side-effect.
  • dfkf 12y ago
    In the worst case scenario the time complexity of a hash table equals that of its bucket, which doesn't have to be a list. So the only advantage of the map over the unordered_map seems to be the ease of use, it only needs a comparer.
    • nly 12y ago
      unordered_map pretty much has to have linked buckets due to its interface and complexity requirements.