Почему std :: map принимает std :: pair в качестве ключа, а std :: unordered_map - нет?

Question

Прежде чем рассматривать дубликат, пожалуйста, поймите основание моего вопроса.

Почему C ++ std::map принимает std::pair в качестве типа ключа, а std::unordered_map - нет?

Первый случай отлично компилируется:

#include <map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

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

    return 0;
}

Второй случай дает массу ошибок компиляции. Из этого вопроса SO и этого вопроса SO стало ясно, что необходимо создать пользовательскую хеш-функцию и оператор эквивалентности.

#include <unordered_map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

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

    return 0;
}

Вопрос здесь заключается не в в том, как написать хеш-функцию для std::unordered_map. Вопрос в том, зачем он вообще нужен, когда std::map не нужен?

Я знаю, std::map - это дерево двоичного поиска (BST), но как именно в этом отношении проводится сравнение между ключами неосновного типа (int_pair)?

Answer 1

std::map ничего не хэширует. В качестве компаратора по умолчанию используется std::less. Это будет работать для любого типа, который поддерживает operator<.

std::unordered_map сортирует свои элементы, используя хэш, предоставленный std::hash.

Так получилось, что std::pair предоставляет operator<, но не имеет специализации для std::hash.