unordered_map 自定义密钥编译器错误

Question

我有一个关于 std::unordered_map 和自定义 class 的问题，因为它是关键。
我认为首先需要一些背景知识：

自定义class是变体数据类型，它实现了基本数值类型和std::string class.
最近我的一个兄弟告诉我，如果 class 支持数组和哈希表就好了。 "Say no more" 我考虑并开始实现数组功能（使用 std::vector），这非常有效，然后我实现了 hashmap 功能（使用 unordered_map<Variant, Variant>）。

如果我理解正确，unordered_map 的散列函数（或分别为 operator()）必须符合我的 [=19= 的专用版本的签名 size_t (*) (const Key_Type &k) const; ] object应该做，不应该吗？
此外，unordered_map 需要检查 Key_Type 是否相等，这应该可以通过 operator==() 实现，我说得对吗？

无论如何，我遇到了很多漂亮的编译器错误，在我看来，这是最有帮助的：
/usr/include/c++/4.9/bits/hashtable_policy.h:85:33: error: no match for call to ‘(const std::hash<Variant>) (const Variant&)’

我真的不明白发生了什么，如果能提供任何关于正在发生的事情的见解，我将不胜感激。

下面是 class Variant 的精简 header，我希望包含足够的信息（老实说，我担心信息太多，但我不确定是什么可以省略）。
但我省略了大部分实现细节，因为问题似乎只出现在专门的哈希 object.

中

好吧，这是 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);

Answer 1

这里的问题是您在 Variant 本身的定义中使用了 unordered_map<Variant, Variant>。此时您的 hash 专业化尚不可用，这就是编译器产生错误的原因。您不能只在 Variant 定义之前移动散列定义，因为散列需要访问 Variant 成员。您可以做的是将 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 ... */
}

但是你还有另一个问题：在 Variant class 定义中 Variant 本身是不完整的类型。在你的联合中，你只存储指向向量和 unordered_map 的指针，这没问题，但是 begin 方法（实际上，它的 return 类型的规范已经）需要 unordered_map<Variant, Variant> 的实例化，这是在那个地方不可能。

（注意：Limited support for containers of incomplete types（仅向量、列表和 forward_list）将添加到 C++17 中）

要解决第二个问题，您可以使用 map 成员函数而不是 begin 函数来访问内部映射：

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

然后

Variant v;
v.begin();

你会用

v.map().begin();

unordered_map 自定义密钥编译器错误

unordered_map with custom key compiler error

c++

unordered-map

c++11