为什么我不能将我的对象存储在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：错误：无效使用不完整类型'struct std： ：哈希”

c：\ qt \ qt5.1.0 \ tools \ mingw48_32 \ lib \ gcc \ i686-w64-mingw32 \ 4.8.0 \ include \ c ++ \ bits \ functional_hash.h：58：错误：'struct std :: hash'的声明

错误：没有匹配函数来调用'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：错误：无法匹配调用'（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：错误：不匹配'operator =='（操作数类型是'const someType'和'const someType'）

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

Answer 1

要在unordered_set或unordered_map中使用type，您需要为您的类型提供散列函数。对于常见类型，如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

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

Answer 2

正如Starl1ght给出的answer所解释的那样，你需要为someType提供一个哈希函数。但是，我会通过该哈希函数组合您的类的所有成员。否则，您可能会遇到很多碰撞，例如，如果相同的name经常发生，但具有不同的code值。要创建哈希函数，您可以使用Boost，但您也可以使用handcraft。

Starl1ght还提到你需要为operator==重载someType，但你也可以定义一个单独的比较函数并将其提供给unordered_set。此外，您可以使用lambda expressions而不是定义哈希和比较函数。如果你把所有东西放在一起，那么你的代码可以写成如下：

auto hash = [](const someType& st){
    return std::hash<std::string>()(st.name) * 31 + std::hash<int>()(st.code);
};
auto equal = [](const someType& st1, const someType& st2){
    return st1.name == st2.name && st1.code == st2.code;
};
std::unordered_set<someType, decltype(hash), decltype(equal)> myset(8, hash, equal);

Code on Ideone