CODEWITHSUNDEEP
c++hashmapbinary-search-treeunordered-mapstd-pair
Max
Max

Reputation: 2162

Why does std::map accept a std::pair as key, but std::unordered_map does not?

Before considering a duplicate, please understand the basis of my question.

Why does a C++ std::map accept a std::pair as a key type, but a std::unordered_map does not?

The first case compiles perfectly:

#include <map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    map<int_pair,int> m;

    return 0;
}

The second case gives a ton of compile errors. It has become clear from this SO question and this SO question that a custom hash function and equivalence operator must be created.

#include <unordered_map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    unordered_map<int_pair,int> m;

    return 0;
}

The question here is not how to write the hash function for the std::unordered_map. The question is, why one is needed at all when std::map doesn't require one?

I know std::map is a Binary Search Tree (BST), but how exactly are the comparisons being made for that matter between keys of a non-fundamental type (int_pair)?

Upvotes: 4

Views: 2251

Answers (1)

Fran&#231;ois Andrieux
Fran&#231;ois Andrieux

Reputation: 29072

std::map doesn't hash anything. It uses std::less as its default comparator. It will work for any type that supports operator<.

std::unordered_map sorts its elements using a hash provided by std::hash.

It so happens that std::pair provides operator<, but doesn't have a specialization for std::hash.

Upvotes: 13

Related Questions