Monday, November 4, 2013

Using a std::unordered_set

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

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.


1 comment: