c++ - 为什么我不能将对象存储在 unordered_set 中？

Question

我知道集合是有序的，因此在不重载 < 的情况下添加对象运算符不允许说出哪个对象较小以保持容器排序。但是，我不明白为什么这对于 unordered_set 是不可能的。 .

如果我尝试这样的事情:

#include <iostream>
#include <string
#include <unordered_set>

struct someType{
    string name;
    int code;
};

int main(){
    std::unordered_set <someType> myset;
    myset.insert({"aaa",123});
    myset.insert({"bbb",321});
    myset.insert({"ccc",213});
    return 0;
}

我遇到了一些错误，例如:

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\hashtable_policy.h:1070: error: invalid use of incomplete type 'struct std::hash'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\functional_hash.h:58: error: declaration of 'struct std::hash'

error: no matching function for call to 'std::unordered_set::unordered_set()'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\hashtable_policy.h:1103: error: no match for call to '(const std::hash) (const someType&)'

c:\qt\qt5.1.0\tools\mingw48_32\lib\gcc\i686-w64-mingw32\4.8.0\include\c++\bits\stl_function.h:208: error: no match for 'operator==' (operand types are 'const someType' and 'const someType')

为什么会这样，我该如何解决？

Answer 1

要在 unordered_set 或 unordered_map 中使用类型，您需要为您的类型使用哈希函数。对于常见类型，如 int 或 std::string - 哈希函数由标准库提供。对于您的类型，您可以重载标准 std::hash，如下所示:

namespace std {
    template <> struct hash<someType> {
        size_t operator()(const someType & x) const {
            std::hash<std::string> h;
            return h(x.name);
            // or simply return x.code
            // or do something more interesting,
            // like xor'ing hashes from both members of struct
        }
    };
}

另一种方法是为您自己的类型提供重载的 operator() 并将其作为散列模板参数放入 unordered_set 中，如下所示:

struct someTypeHasher {
    size_t operator()(const someType& x) const {
        return x.code;
    }
};
std::unordered_set<someType, someTypeHasher> myset;

有关基于哈希的容器的理论的好读物是 here

另外，不要忘记，您需要为 someType 重载 operator==，没有它 - 它也不会工作。