c++ - C++中的无序集合，为什么需要散列？

Question

我只想将几个对象存储在一个无序集合中。创建几个集合，

auto set1 = std::unordered_set<Myclass>();

我有时会遇到很多这样的错误:

Implicit instantiation of undefined template 'std::__1::hash'

除开箱即用的 unordered_set 之外，是否没有其他替代方案？为什么需要“哈希”？

Answer 1

std::unordered_set 通过散列您使用的键来索引其存储中的值，很像散列表或 C++ std::unordered_map 实现。

如果您不想为 Myclass 编写哈希函数，只需使用 std::set 即可。这可能比定义散列函数并使用 std::unordered_set 时表现更差，但如果编写散列函数对您的类来说很困难，那么这样做可能是值得的。取决于类(class)和您的应用程序。

如果要使用std::unordered_set，需要为Myclass提供一个哈希函数。为您的类提供 std::hash 的特化，或者为 std::unordered_set 提供散列策略。

//specialize std::hash
namespace std
{
    template<>
    struct hash<Myclass>
    {
        typedef Myclass argument_type;
        typedef std::size_t result_type;

        result_type operator()(argument_type const& s) const
        {
            //some code to hash a Myclass object
        }
    };
}
auto set1 = std::unordered_set<Myclass>();   

//hashing policy version
class MyclassHash
{
public:
    std::size_t operator()(Myclass const& s) const 
    {
        //some code to hash a Myclass object
    }
};
auto set1 = std::unordered_set<Myclass, MyclassHash>();