CODEWITHSUNDEEP
c++performancehashprimitive-types
Anycorn
Anycorn

Reputation: 51465

computing hash values, integral types versus struct/class

I would like to know if there is a difference in speed between computing hash value (for example std::map key) of primitive integral type, such as int64_t and pod type, for example struct { int16_t v[4]; };. what about int128_t versus struct {int32_t v[4];}?

I know this is going to implementation specific, so my question ultimately pertains to gnu standard library. Thanks

the link I found very useful How can I use a custom type for keys in a boost::unordered_map?

Upvotes: 2

Views: 702

Answers (1)

kennytm
kennytm

Reputation: 523274

std::map is not a hash table. It is usually implemented as a balanced binary tree. What you want is std::unordered_map* .

And for std::unordered_map, C++ only defines the hash value for the internal types and the common ones** such as std::string. You need to implement the hash function for struct { int16_t v[4]; }; yourself. You can cast this struct into int64_t in the computation, then there won't be any difference in hashing speed.

(*: == std::tr1::unordered_map == boost::unordered_map ≈ __gnu_cxx::hash_map == stdext::hash_map etc)

(**: 20.8.16 Class template hash: ... integer types (3.9.1), floating-point types (3.9.1), pointer types (8.3.1), and std::string, std::u16string, std::u32string, std::wstring, std::error_code, std::thread::id, std::bitset, and std::vector<bool>.)

Upvotes: 8

Related Questions