3

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

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Max
  • 2,072
  • 5
  • 26
  • 42
  • 1
    `std::map` requires `std::less` whereas `std::unordered_map` requires `std::hash`, 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 May 03 '18 at 20:36
  • 1
    see answer https://stackoverflow.com/questions/20590656/error-for-hash-function-of-pair-of-ints?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa – Neargye May 03 '18 at 20:49
  • 1
    `std::map` compiles because `std::pair` has an `operator<` which is called by `std::less` see: http://en.cppreference.com/w/cpp/utility/pair/operator_cmp – Richard Critten May 03 '18 at 20:53
  • 1
    @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 May 03 '18 at 21:00

1 Answers1

12

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.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
François Andrieux
  • 28,148
  • 6
  • 56
  • 87
  • 1
    thank you for the clarification, essentially it comes down to the fact that `operator<` is provided by `std::pair` – Max May 03 '18 at 20:57
  • 1
    For those wondering, you can find the [pair operators here](http://www.cplusplus.com/reference/utility/pair/operators/) – Max May 08 '18 at 14:52