Почему у нас нет хеша и функторов pred для карты?

Question

В случае unordered_map мы определяем функторы hash и pred всякий раз, когда мы используем user-defined ключи.

Синтаксис шаблона для карты следующий:

template < class Key,                                     // map::key_type
       class T,                                           // map::mapped_type
       class Compare = less<Key>,                         // map::key_compare
       class Alloc = allocator<pair<const Key,T> >       // map::allocator_type
       > class map;

В случае карты нет функторов hash и pred.У нас никогда не было столкновений в случае map.Если происходят столкновения, то почему у нас нет функторов hash и pred, как в unordered_map?Я что-то здесь упускаю?

Answer 1

std::map и std::unordered_map - это два разных типа контейнеров, которые оба предоставили отображение пары ключ-значение.Как они это делают, хотя это совершенно другое.

std::map использует древовидную структуру для своей реализации.Обычно это RBTree, но может работать любое дерево, которое может гарантировать операции O(logN) в худшем случае.Это означает, что он должен иметь только оператор сравнения для типа ключа, так как вы можете получить полное упорядочение и проверить равенство с помощью компаратора, который реализует строгое слабое упорядочение.Это означает, что у вас никогда не будет коллизии хеша, поскольку вы не используете хеш.

std::unordered_map основан на реализации хеш-таблицы.Поскольку он хеширует ключ, вам нужен оператор хеширования.Вам также нужен оператор сравнения, поскольку два значения могут хэшировать одно и то же значение (коллизия хэшей).Без оператора сравнения вы не сможете определить, является ли дублирующий хеш действительно дублирующим элементом.

Answer 2

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