Как напрямую использовать ключ как хэш для std :: unordered_map?

Question

Ключи в моем std::unordered_map являются boost::uuids::uuid s, поэтому 128-битные хэши считаются уникальными. Однако компилятор не может этого знать и поэтому говорит об этом.

error C2338: The C++ Standard doesn't provide a hash for this type. 

Как я могу использовать карту как хэши, как они есть? Кстати, std::size_t определяется как unsigned int __w64 в моей системе, что, я думаю, относится только к 64 бит.

Answer 1

Я не нашел возможности использовать UUID как ключи для std::unordered_map, так как UUID имеет длину 128 бит, а хэш для карты - std::size_t, который может содержать только 64 бит.

Вместо этого я сбросил реальные 128-битные UUID только для 64-разрядных идентификаторов, которые могут храниться в типе uint64_t и поддерживаются контейнерами стандартной библиотеки.

Answer 2

вам необходимо предоставить хеш-функцию для типа boost::uuids::uuid. Поскольку он уникален, вы можете просто использовать идентификатор stl.

Здесь размещается объявление неупорядоченного_мапа.

template < class Key,         // unordered_map::key_type 
      class T,          // unordered_map::mapped_type 
      class Hash = hash<Key>,      // unordered_map::hasher 
      class Pred = equal_to<Key>,     // unordered_map::key_equal 
      class Alloc = allocator< pair<const Key,T> > // unordered_map::allocator_type 
      > class unordered_map; 

Answer 3

Я думаю, что самый простой способ это осуществить специализацию std::hash для этого типов, который возвращает тот же вход:

namespace std 
{ 
    template<> 
    struct hash<Foo> 
    { 
     Foo operator(const Foo& foo) 
     { 
      return foo; 
     } 
    }; 
} 

предположив, что тип, Foo в примере, неявно конвертируются в std::size_t.

В вашем случае тип - это 128-битный GUID, а std::size_t использует 32 или 64 бит. Вы можете разбить 128-битный GUID в частях 64/32 бит и объединить значения.

Answer 4

Вам всегда нужно предоставить объект функции, сопоставляющий ключ с хэш-значением, даже если это сопоставление является идентификатором. Вы можете либо определить специализацию для std::hash<boost::uuids::uuid>, либо выбрать std::unordered_map<K, V> автоматически, или вы можете параметризовать неупорядоченную карту с дополнительным параметром шаблона для типа объекта функции. В дополнение к хэшу также нужна операция равенства, но по умолчанию используется operator==().

При этом хеш-значение не будет принимать 128-битное целое число, если ваша система не имеет встроенного 128-битного целочисленного типа. Хэш-значение должно быть std::size_t для использования со стандартными неупорядоченными контейнерами. Полный перечень требований к std::hash<T> специализации указан в 20.8.12 [unord.hash]:

1. std::hash<X> должен быть по умолчанию конструктивно, копировать конструктивны и копировать переуступку.
2. std::hash<X> необходимо заменить.
3. Для типа ключа необходимо указать два вложенных типа argument_type и result_type для типа хешированного значения с последним, равным std::size_t.
4. Для функции отношение k1 == k2 =>h(k1) == h(k2) должно быть правдой, где h - объект функции хэширования.

Итак, вам нужно будет определить что-то вдоль линий этого:

namespace std { 
    template <> 
    struct hash<boost::uuids::uuid> 
    { 
     typedef boost::uuids::uuid argument_type; 
     typedef std::size_t  result_type; 
     std::size_t operator()(boost::uuid::uuid key) const { 
      return transform_to_size_t(key); 
     } 
    }; 
} 

где transform_to_size_t() фактическое преобразование вам необходимо предоставить. };