如何在C++中创建一组无序的整数对？

Question

以下程序不会编译一组无序的整数对,但它会对整数进行编译.Can unordered_set和它的成员函数可以用在用户定义的类型上,我该如何定义它？

#include <unordered_set>
...

class A{
...
private: 
    std::unordered_set< std::pair<int, int> > u_edge_;
};

编译错误:

错误:没有匹配函数来调用'std :: unordered_set> :: unordered_set()'

Answer 1

没有标准方法来计算对上的散列.将此定义添加到您的文件中:

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

现在您可以像这样使用它:

std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

这有效,因为pair<T1,T2>定义了相等.对于不提供测试相等性的方法的自定义类,您可能需要提供单独的函数来测试两个实例是否彼此相等.

当然,这种解决方案仅限于一对两个整数.这是一个答案的链接,可帮助您定义为多个对象制作哈希的更一般方法.

Answer 2

您的代码在VS2010 SP1(VC10)上编译,但无法使用GCC g ++ 4.7.2进行编译.

但是,您可能需要boost::hash从Boost.Functional考虑哈希a std::pair(使用此添加,您的代码也使用g ++编译).

#include <unordered_set>
#include <boost/functional/hash.hpp>

class A
{
private: 
    std::unordered_set< 
        std::pair<int, int>, 
        boost::hash< std::pair<int, int> > 
    > u_edge_;
};

Answer 3

正如该问题的大多数其他答案中已经提到的，您需要为 提供一个哈希函数std::pair<int, int>。但是，从C++11开始，您还可以使用lambda 表达式来代替定义哈希函数。以下代码以Sergey给出的解决方案为基础：

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

Ideone 上的代码

我想重复谢尔盖的免责声明：该解决方案仅限于两个整数对。这个答案提供了更通用的解决方案的想法。

Answer 4

问题是std::unordered_set使用std::hash模板来计算其条目的哈希值,并且没有对象的std::hash专门化.所以你必须做两件事:

1. 确定要使用的哈希函数.
2. 专门std::hash为您的键类型(std::pair<int, int>)使用该功能.

这是一个简单的例子:

#include <unordered_set>

namespace std {
template <> struct hash<std::pair<int, int>> {
    inline size_t operator()(const std::pair<int, int> &v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};

}

int main()
{
    std::unordered_set< std::pair<int, int> > edge;
}

Answer 5

好的，这是一个保证不冲突的简单解决方案。只需将您的问题简化为现有的解决方案，即将您的解决方案转换int为string如下所示：

 auto stringify = [](const pair<int, int>& p, string sep = "-")-> string{
    return to_string(p.first) + sep + to_string(p.second);
 }

 unordered_set<string> myset;
 myset.insert(stringify(make_pair(1, 2)));
 myset.insert(stringify(make_pair(3, 4)));
 myset.insert(stringify(make_pair(5, 6)));

享受！

Answer 6

您需要提供std::hash<>适用于 的专业化std::pair<int, int>。这是一个非常简单的示例，说明如何定义专业化：

#include <utility>
#include <unordered_set>

namespace std
{
    template<>
    struct hash<std::pair<int, int>>
    {
        size_t operator () (std::pair<int, int> const& p)
        {
            // A bad example of computing the hash, 
            // rather replace with something more clever
            return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
        }
    };
}

class A
{
private:
    // This won't give you problems anymore
    std::unordered_set< std::pair<int, int> > u_edge_;
};