вычисление хеш-значений, целочисленных типов и структур / классов

Question

Я хотел бы знать, есть ли разница в скорости между вычислением хеш-значения (например, std :: map key) примитивного целочисленного типа, такого как int64_t, и типа pod, например struct { int16_t v[4]; };. как насчет int128_t против struct {int32_t v[4];}?

Я знаю, что это зависит от конкретной реализации, поэтому мой вопрос в конечном счете относится к стандартной библиотеке GNU. Спасибо

ссылка, которую я нашел очень полезной Как я могу использовать пользовательский тип для ключей в boost :: unordered_map?

Answer 1

std::map не является хеш-таблицей. Обычно это реализовано в виде сбалансированного бинарного дерева. То, что вы хотите, это std::unordered_map*.

А для std::unordered_map C ++ определяет только значение хеш-функции для внутренних типов и общих **, таких как std::string. Вам нужно реализовать хеш-функцию для struct { int16_t v[4]; }; самостоятельно. Вы можете преобразовать эту структуру в int64_t в вычислениях, тогда не будет никакой разницы в скорости хеширования.

---

_{(*: == std::tr1::unordered_map == boost::unordered_map & asymp; __gnu_cxx::hash_map == stdext::hash_map и т. Д.)}

_{(**: 20.8.16 Шаблон класса hash: ... целочисленные типы (3.9.1), типы с плавающей точкой (3.9.1), типы указателей (8.3.1) и std::string, std::u16string, std::u32string, std::wstring, std::error_code, std::thread::id, std::bitset и std::vector<bool>.)}