-2

Consider the following:

In C++, the std::unordered_map uses a hash function in the insertion process to determine where the new inserted element will be located.

However, the std::map does not use a hash function in the insertion process and determines the location of the new inserted element using the same method that is used to determine the location of the new inserted element in any binary search tree. By this, I mean the method by which the location of the new element is determined in any binary search tree is for example, if the element is greater than the current element then go right, or if it is less than the current element then go left.

Is my conclusion 100% accurate?

Improve this question
18
  • One question per question. Commented Apr 24, 2024 at 14:45
  • 2
    Yes, std::map is usually implemented as a tree and std::unordered_map is usually implemented as a hash table. Neither implementation is a requirement by the standard. See map and unordered_map. Commented Apr 24, 2024 at 14:50
  • It also depends on the implementation. Commented Apr 24, 2024 at 14:51
  • 2
    In theory the standard does not demand any specific implementation, but in practice there is no good way to implement these abstract data types that is substantially different from hashtable/balanced tree. Commented Apr 24, 2024 at 15:00
  • 2
    @ChristianStieber - The committee surely had a possible implementation in mind when specifying the requirements. They didn't want to spell that out though, on the odd chance that a better way happens to be invented later. Commented Apr 24, 2024 at 15:30

1 Answer 1

Reset to default
7

std::map has a type parameter Compare that is required to provide an ordering to the keys of the map, and also determine when keys are equivalent by the relation equiv(a, b) iff !comp(a, b) && !comp(b, a)

std::unordered_map has a type parameter Hash that is required to provide a hashing of the keys of the map. It also has a type parameter Equal that is required to determine equivalence between keys, in a manner consistent with Hash, i.e. hash(a) == hash(b) if equal(a, b).

These requirements, and the complexity requirements on certain member functions, mean that whilst there is theoretically room for implementations to do things with a different data structure, to be conforming std::map has to be a balanced binary tree, and std::unordered_map has to be a hash table with chaining

Improve this answer
Sign up to request clarification or add additional context in comments.

33 Comments

@f877576 Yes, that is right
@f877576 It's very nearly correct. It doesn't have to be operator< / operator==, those are just what is used by the default Compare and Equal, respectively
@f877576 the source you link is correct when you use std::map<K, V>, because that's actually the same as std::map<K, V, std::less<K>, std::allocator<std::pair<const K, V>>>, and std::less is a function object type that compares via <, but you can have a map with a different comparison, e.g. std::map<K, V, std::greater<K>> is std::map<K, V> with the order reversed.
@f877576 for std::map the position in the tree is determined by using the compare function
@f877576 It is correct, so long as you are clear what defines "less" or "greater"
|