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

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

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

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


c++ performance hash primitive-types
person Anycorn    schedule 13.03.2010    source источник

Ответы (1)


arrow_upward
8
arrow_downward

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 __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>.)

person kennytm    schedule 13.03.2010