Допустим, мне нужно сделать некий шаблонный контейнер Map на хэш-таблице. Контейнер, естественно, может принимать ключем значение любых типов - как, в таком случае, написать хэш-функцию? Как привести произвольный тип T (для которого может быть не перегружен оператор приведения) к целочисленному типу?
Вроде как должен помочь reinterpret_cast, который приводит к указателю, но конструкция вида
reinterpret_cast
Отказывается компилироваться, когда key имеет не-целочисленный тип.
Если же приводить указатель к указателю (как в примере на msdn)
reinterpret_cast
то теряется смысл хэш таблицы - поиск по ней не будет работать, поскольку ключ с идентичным значением будет иметь другой адрес, и результат хэш-функции будет тоже другой.
Можно ли как-то насильно интерпретировать байты произвольного объекта в памяти как целочисленный тип?
Вообще, какое решение будет правильным? Как эта проблема решена в std::unordered_map или QMap?
Ответ
Классы наподобие unordered_set вычисляют хеш не сами, а используют std::hash (а также дают возможность пользователю указать свою реализацию хеширования, если он недоволен стандартной, или если её не существует).
std::hash, в свою очередь, тоже не пользуется никакой особой магией, а просто имеет шаблонные специализации для примитивных типов, строк и указателей (обычных и «умных»).
Мне кажется, вам стоит не изобретать велосипед, а воспользоваться той же идеей. А ещё проще, просто используйте std::hash. Поверьте, в написании контейнера есть много сложностей помимо этой.
Таким образом, просто используйте
size_t hash_value = std::hash
Комментариев нет:
Отправить комментарий