unordered_map with custom key compiler error

Question

I have a question regarding the std::unordered_map and a custom class as it's key.
I think some background is required first:

The custom class is a variant data type, which implements basic numerical types and the std::string class.
Recently a bro of mine told me that it would be nice if the class supported arrays and hashtables. "Say no more" I thought and started implementing the array functionality (using std::vector) which works really great and then I implemented the hashmap functionality (using unordered_map<Variant, Variant>).

If I understand it right the hash function (or operator() respectively) for the unordered_map has to comply to the signature size_t (*) (const Key_Type &k) const; which my specialized version of the std::hash<Variant> object should do, shouldn't it?
In addition the unordered_map needs to check Key_Type for equality, which should be possible via operator==(), am I correct?

Anyway I'm getting a load of beautiful compiler errors of which this is, in my opinion, the most helpful:
/usr/include/c++/4.9/bits/hashtable_policy.h:85:33: error: no match for call to ‘(const std::hash<Variant>) (const Variant&)’

I really don't understand what's going on and would be really grateful for any insights in what's going on.

Below is a stripped down header of the class Variant, I hope enough information is included (to be honest I fear it's too much information but I was not sure what could be omitted).
But I left out most of the implementation details since the problem seems to occur only in the specialized hash object.

Well this is the stripped down version of the Variant header:

class Variant
{
    private:
        enum Type {NONE = 0, LONG, DOUBLE, STRING, ARRAY, HASH_MAP};
        using Var = struct Var
        {
            union
            {
                int64_t l;
                double d;
                std::string *s;
                std::vector<Variant> *v;
                std::unordered_map<Variant, Variant> *h;
            };
            Type type = NONE;
        };

    public:
        //constructors, destructor and clear function
        Variant() : var() {}
        Variant(long val): Variant(){var.type = LONG; var.l = val;}
        Variant(double val) : Variant(){var.type = DOUBLE; var.d = val;}
        Variant(const std::string &val) : Variant(){var.type = STRING; var.s = new std::string(val);}
        template<typename T, typename... Args>Variant(T val, Args... args) : Variant() {set(val, args...);} //constructs an array

        Variant(const Variant &val); //calls default constructor as well
        Variant(Variant &&val) : Variant() {swap(*this, val);}

        ~Variant(){clear();}
        void clear();

        //set functions
        template<typename T, typename... Args> void set(const T val, Args... args){if(var.type == ARRAY)var.v->clear();add(val, args...);}
        void set(long val);
        void set(double val);
        void set(const std::string &val);
        void set(const Variant &val);

        //add functions
        template<typename T> void add(const T val){add(Variant(val));}
        template<typename T, typename... Args> void add(const T val, Args... args){add(Variant(val)); add(args...);}
        void add(const std::string &val){add(Variant(val));}
        void add(const Variant &val);

        //array access and evaluation functions
        Variant& operator[](const Variant &idx);
        size_t size() const {if(var.type == ARRAY)return var.v->size(); return 0;}
        std::unordered_map<Variant, Variant>::iterator begin(){if(var.type == HASH_MAP)return var.h->begin(); throw Exception("The internal type does not support iterators");}

        //operator= definitions
        template<typename T> Variant& operator=(const T val){set(val); return *this;}
        Variant& operator=(const std::string &val){set(val); return *this;}
        Variant& operator=(Variant val){swap(*this, val); return *this;}

        //operator definitions
        Variant& operator+=(const Variant &right);
        //and operator-=, ^= etc etc...

        //friend definitions (mainly comparison operators)
        friend void swap(Variant &left, Variant &right); //simple swap function
        friend bool operator==(const Variant &left, const Variant &right);
        friend bool operator!=(const Variant &left, const Variant &right);    
        friend std::hash<Variant>;

    private:
        Var var;
};


template <typename T>
inline void hash_combine(std::size_t& seed, const T &v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

namespace std
{
    template<> struct hash<Variant>
    {
        size_t operator()(const Variant &x) const
        {
            if(x.var.type == Variant::DOUBLE)
                return std::hash<double>()(x.var.d);
            else if(x.var.type == Variant::LONG)
                return std::hash<int64_t>()(x.var.l);
            else if(x.var.type == Variant::STRING)
                return std::hash<std::string>()(*x.var.s);
            else if(x.var.type == Variant::ARRAY)
            {
                size_t seed = 0;
                for(size_t i = 0; i < x.var.v->size(); ++i)
                    hash_combine(seed, x.var.v->operator[](i));
                return seed;
            }
            else if(x.var.type == Variant::HASH_MAP)
            {
                size_t seed = 0;
                for(auto it = x.var.h->begin(); it != x.var.h->end(); ++it)
                {
                    hash_combine(seed, it->first);
                    hash_combine(seed, it->second);
                }
                return seed;
            }
            else if(x.var.type == Variant::NONE)
                return 0;
            else
                throw std::runtime_error("This Variant cannot be hashed");
        }
    };
}

inline void swap(Variant &left, Variant &right){Variant::Var tmp(left.var); left.var = right.var; right.var = tmp;}

bool operator==(const Variant &left, const Variant &right);
bool operator!=(const Variant &left, const Variant &right);

Possible duplicate of http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key — Adi Levin, Jan 19 '16 at 13:10
Did you try moving all the specialized `std::` extension *declarations* to above the declaration of the variant class? — Yam Marcovic, Jan 19 '16 at 13:25
Make your `hash_combine` a struct instead: `struct VariantHasher { size_t operator()(...) { return 0; } };` and pass it to the third template parameter like so: `std::unordered_map` — Brian Rodriguez, Jan 19 '16 at 13:56

Ilya Popov · Accepted Answer · 2016-01-19T13:56:25.297

The problem here is that you use unordered_map<Variant, Variant> inside the definition of Variant itself. At this point your hash specialization is not available yet, that's why the compiler produces the error. You cannot just move hash definition before Variant definition because the hash needs access to Variant members. What you can do, is to separate declaration and definition of your hash:

class Variant;

namespace std
{
    template<> struct hash<Variant>
    {
        size_t operator()(const Variant & x) const;
    };
}

class Variant {
/* Variant definition goes here ... */
};

template <typename T>
inline void hash_combine(std::size_t& seed, const T &v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

size_t std::hash<Variant>::operator()(const Variant &x) const
{
    /* hash function implementation here ... */
}

But then you have another problem: inside Variant class definition the Variant itself is incomplete type. In your union you store only pointers to vector and unordered_map, this is OK, but the begin method (actually, specification of its return type already) requires an instantiation of the unordered_map<Variant, Variant> which is not possible at that place.

(Note: Limited support for containers of incomplete types (only vector, list, and forward_list) will be added to C++17)

To solve this second problem, you can have a map member function instead of begin function which gives access to the internal map:

std::unordered_map<Variant, Variant> & map()
{
    if (var.type == HASH_MAP)
        return *var.h; 
    throw Exception("The internal type does not support iterators");
}

Then instead of

Variant v;
v.begin();

you would use

v.map().begin();

Thanks man, I didn't think that my class would suffer from a chicken-egg-problem. Your suggestions fixed the problem, many thanks! — Mäx Müller, Jan 19 '16 at 14:17
There's no need to overload `std::hash`. Instead, place your hashing function in a simple struct and pass it as a template parameter as so: `std::unordered_map` — Brian Rodriguez, Jan 19 '16 at 14:19

unordered_map with custom key compiler error

1 Answers1