为什么我不能将对象存储在 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.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.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.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.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==，没有它 - 它也不会工作。

Answer 2

正如在 given by Starl1ght, you need to provide a hash function for someType. However, I would combine all members of your class by that hash function. Otherwise, you might get a lot of collisions, for example, if the same name occurs very often, but with different code values. For creating a hash function, you can make use of Boost, but you can also handcraft中解释的那样。

Starl1ght 还提到你需要为 someType 重载 operator==, 但您也可以定义一个单独的比较函数，并将其提供给 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

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

Why can't I store my objects in an unordered_set?

c++

unordered-set

c++11