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

Question

下面的程序不会编译一组无序的整数对，但它会编译整数。可以unordered_set在用户定义的类型上使用及其成员函数，我该如何定义它？

#include <unordered_set>
...

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

编译器错误：

错误：没有匹配函数调用“std::unordered_set >::unordered_set()”

Answer 1

There is no standard way of computing a hash on a pair. Add this definition to your file:

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

Now you can use it like this:

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

This works, because pair<T1,T2> defines equality. For custom classes that do not provide a way to test equality you may need to provide a separate function to test if two instances are equal to each other.

Of course this solution is limited to a pair of two integers. Here is a link to an answer that helps you define a more general way of making hash for multiple objects.

Answer 2

Your code compiles on VS2010 SP1 (VC10), but it fails to compile with GCC g++ 4.7.2.

However, you may want to consider boost::hash from Boost.Functional to hash a std::pair (with this addition, your code compiles also with 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::unordered_set使用std::hash模板来计算其条目的哈希值，并且没有std::hash专门化对。所以你必须做两件事：

1. 确定要使用的散列函数。
2. Specialize std::hash for your key type (std::pair<int, int>) using that function.

Here is a simple example:

#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 4

As already mentioned in most of the other answers on this question, you need to provide a hash function for std::pair<int, int>. However, since C++11, you can also use a lambda expression instead of defining a hash function. The following code takes the solution given by Sergey as basis:

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

Code on Ideone

I'd like repeat Sergey's disclaimer: This solution is limited to a pair of two integers. This answer provides the idea for a more general solution.

Answer 5

OK here is a simple solution with guaranteed non collisions. Simply reduce your problem to an existing solution i.e. convert your pair of int to string like so:

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

Enjoy!

Answer 6

You need to provide a specialization for std::hash<> that works with std::pair<int, int>. Here is a very simple example of how you could define the specialization:

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

Answer 7

The other answers here all suggest building a hash function that somehow combines your two integers.

This will work, but produces non-unique hashes. Though this is fine for your use of unordered_set, for some applications it may be unacceptable. In your case, if you happen to choose a bad hash function, it may lead to many unnecessary collisions.

But you can produce unique hashes!

int is usually 4 bytes. You could make this explicit by using int32_t.

The hash's datatype is std::size_t. On most machines, this is 8 bytes. You can check this upon compilation.

Since a pair consists of two int32_t types, you can put both numbers into an std::size_t to make a unique hash.

That looks like this (I can't recall offhandedly how to force the compiler to treat a signed value as though it were unsigned for bit-manipulation, so I've written the following for 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);
}

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>>，在这种情况下，您可以省略第二个模板参数。