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

Question

以下程序无法编译整数对的无序集合，但可以编译整数。是否可以在自定义类型上使用unordered_set及其成员函数，如何定义？

#include <unordered_set>
...

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

编译器错误：

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

- Pippi

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>定义了相等性。对于不提供测试相等性方法的自定义类，您可能需要提供一个单独的函数来测试两个实例是否相等。

当然，这个解决方案仅限于两个整数的一对。这里有一个a link to an answer，可以帮助您定义一种更通用的方式来为多个对象创建哈希值。

- Sergey Kalinichenko

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Brad Larson

你能解释一下哈希需要什么吗？比如我尝试了(1,0)和(0,31)，它们产生了相同的哈希值，但代码仍然可以运行。发生了什么事情？ - Dhruv

@Dhruv 即使两个对象不相等，哈希值相等也是可以的。要求是当两个对象相等时，它们的哈希值应该相同。 - Sergey Kalinichenko

@Dhruv 即使两个对象不相等，它们的哈希值相等也是可以的。要求是当两个对象相等时，它们的哈希值应该相同。 - Sergey Kalinichenko

Answer 2

你的代码可以在VS2010 SP1 (VC10)编译，但却无法通过GCC g++ 4.7.2的编译。

然而，你可以考虑使用Boost.Functional中的boost::hash来对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_;
};

- Mr.C64

Answer 3

问题在于std::unordered_set使用std::hash模板计算其条目的哈希值，而对于键值对，没有std::hash特化。因此，您需要执行两个操作：

1. 决定要使用哪个哈希函数。
2. 使用该函数为键类型（std::pair<int, int>）特化std::hash。

这里是一个简单的示例：

#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;
}

- user405725

---

@WenzelJakob，Andy Prowl的回答也将其添加到std命名空间中。此外，这并不是非法的，只是未定义的行为。在特定版本的GCC上，它总是可以正常工作的。 - user202729

Answer 4

如其他答案中大多数已经提到的，在这个问题上，你需要为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上的代码

我想重复一下Sergey的声明：这个解决方案仅适用于一对整数。 这个答案提供了一个更普遍的解决方案的想法。

- honk

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)));

尽情享受吧！

- SkyWalker

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_;
};

- Andy Prowl

Answer 7

这里的其他答案都建议构建哈希函数，以某种方式组合您的两个整数。这将起作用，但会产生非唯一哈希。虽然这对于您使用的unordered_set来说没问题，但对于某些应用程序来说可能是不可接受的。在您的情况下，如果选择了一个糟糕的哈希函数，可能会导致许多不必要的碰撞。

但是，您可以生成唯一的哈希值！int通常是4个字节。您可以通过使用int32_t来显式表示。哈希的数据类型是std::size_t。在大多数机器上，它为8个字节。您可以在编译时检查这一点。由于一对由两个int32_t类型组成，您可以将两个数字都放入std::size_t中以生成唯一的哈希值。看起来像这样（我无法立即回忆起如何强制编译器将有符号值视为无符号值进行位操作，因此我已经为uint32_t编写了以下内容）。

#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>


struct IntPairHash {
  std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
    assert(sizeof(std::size_t)>=8);  //Ensure that std::size_t, the type of the hash, is large enough
    //Shift first integer over to make room for the second integer. The two are
    //then packed side by side.
    return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
  }
};

int main(){
  std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
  uset.emplace(10,20);
  uset.emplace(20,30);
  uset.emplace(10,20);
  assert(uset.size()==2);
}

- Richard

Answer 8

您缺少一个针对 std::pair<int, int>> 的哈希函数。例如：

struct bad_hash
{
  std::size_t operator()(const std::pair<int,int>& p) const
  {
    return 42;
  }
};

....

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

您还可以为std::hash<T>专门化，以适用于std::hash<std::pair<int,int>>，在这种情况下，您可以省略第二个模板参数。

- juanchopanza

---

你的函数对象应该继承自std::unary_function。 - Alex Chamberlain

@AlexChamberlain 我认为那些东西已经被弃用了。 - juanchopanza

@AlexChamberlain：为什么要这样做？这个类满足所有哈希要求。 - Mike Seymour

@juanchopanza 好的，我理解，但是我在工作中仍然使用C++03。 - Alex Chamberlain

因为你不知道谁会使用你的函数对象。 - Alex Chamberlain

@AlexChamberlain 我了解那种感觉！但是由于这个问题涉及到 std::unordered_set，我认为可以安全地假设 OP 想要一个 C++11 的解决方案。 - juanchopanza

Answer 9

要创建一个无序对集合，您可以创建自定义哈希函数或创建字符串的无序集合。

1. 创建自定义哈希函数：创建自定义哈希取决于数据。因此，没有一种适用于所有情况的哈希函数。良好的哈希函数必须具有较少的冲突，因此在制作哈希函数时需要考虑冲突计数。

2. 使用字符串：使用字符串非常简单，时间也较短。它还保证了很少或没有冲突。我们可以通过使用分隔符（字符或字符串）来表示对，而不是使用unordered_set<pair<int，int>>，我们使用unordered_set。下面给出的示例显示了如何使用分隔符（“;”）插入整数对。

   auto StringPair = [](const pair<int, int>& x){return to_string(x.first) + ";" + to_string(x.second);}; unordered_set Set;

   vector<pair<int, int>> Nums = {{1,2}, {2, 3}, {4, 5}, {1,2}};

   for(auto & pair: Nums) { Set.insert(StringPair(pair)); }

- Venkata Sai Pavan Kumar Vadrev

Answer 10

只是想在这里加入我的两分钱，使用unordered_set需要指定外部哈希函数真的很奇怪。封装原则更倾向于在类内部有一个返回哈希值的'hash()'函数，而unordered_set会调用它。你应该有一个Hashable接口，你的类（在这种情况下是std::pair）将实现该接口。
我认为这是Java等语言采用的方法。不幸的是，C++没有遵循这种逻辑。你可以最接近地模仿它：

1. 从std::pair派生出一个类（这样可以让你的代码更容易阅读）
2. 将哈希函数传递给unordered_set模板

代码示例

class Point : public pair<int, int> {
   public:
   Point() {};
   Point(int first, int second) : pair{first, second}{};
   class Hash {
      public:
      auto operator()(const Point &p) const -> size_t {
         return ((size_t)p.first) << 32 | ((size_t)p.second);
      }
   };
 };

int main()
{
    unordered_set< Point, Point::Hash > us;
    Point mypoint(1000000000,1);
    size_t res = Point::Hash()(mypoint);
    cout<<"Hello World " << res << " " << mypoint.first;

    return 0;
}

如果size_t是64位，int是32位，则使用的简单哈希函数有效，此时该哈希函数保证没有冲突并且是理想的。

- AndrewBloom