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

Question

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)?

std::map requires std::less<T> whereas std::unordered_map requires std::hash<T>, simple as that. As to "why" simply look up how to implement a red-black tree (map) vs a hash table (unordered_map), then you'll have your answer. — Cory Kramer
– Cory Kramer, Commented May 3, 2018 at 20:36
std::map compiles because std::pair has an operator< which is called by std::less see: en.cppreference.com/w/cpp/utility/pair/operator_cmp — Richard Critten
– Richard Critten, Commented May 3, 2018 at 20:53
@Neargye you didn't seem to understand the question, I was asking about the differences not just why an unordered_map won't compile — Max
– Max, Commented May 3, 2018 at 21:00

Remy Lebeau · Accepted Answer · 2018-05-03 21:40:49Z

13

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.

edited May 3, 2018 at 21:40

Remy Lebeau

609k36 gold badges516 silver badges875 bronze badges

answered May 3, 2018 at 20:36

François Andrieux

29.2k6 gold badges60 silver badges93 bronze badges

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

2 Comments

Max Over a year ago

thank you for the clarification, essentially it comes down to the fact that operator< is provided by std::pair

Max Over a year ago

For those wondering, you can find the pair operators here

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related