It's easy to use an unordered_set, or unordered_map with a basic key type, like int, float, string.

You simply set it up like

std::unordered_set<string> simple_hash_table;

But how does one create hash functors and compare functors for a more complex key?

Many times the key is composite, and a decent hash functor needs to be provided. For a struct like

you should write the hash and equality functors:

A good implementation of hash_combine() can be found in boost.

You simply set it up like

std::unordered_set<string> simple_hash_table;

But how does one create hash functors and compare functors for a more complex key?

Many times the key is composite, and a decent hash functor needs to be provided. For a struct like

struct XXX { int a; float b; string c; };

you should write the hash and equality functors:

struct XXX_Hash { size_t operator() (const XXX& p) const { size_t seed = 0; hash_combine( seed, p.a ); hash_combine( seed, p.b ); hash_combine( seed, p.c ); return seed; } }; struct XXX_Equals { bool operator() (const XXX& left, const XXX& right) const { return left.a == right.a && left.b == right.b && left.c == right.c; } }; std::unordered_set <XXX, XXX_Hash, XXX_Equals> complex_hash_table;

A good implementation of hash_combine() can be found in boost.

Many thanks!

ReplyDelete