69

次のプログラムは、整数のペアの順序付けられていないセットをコンパイルしませんが、整数に対してはコンパイルします。およびそのメンバー関数はユーザー定義型で使用できunordered_setますか? また、どのように定義できますか?

#include <unordered_set>
...

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

コンパイラ エラー:

エラー: 'std::unordered_set >::unordered_set()' の呼び出しに一致する関数がありません

4

8 に答える 8

55

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.

于 2013-03-01T15:18:50.760 に答える
30

コードは VS2010 SP1 (VC10) でコンパイルされますが、GCC g++ 4.7.2 ではコンパイルできません。

ただし、Boost.Functionalboost::hashからa をハッシュすることを検討することもできます(この追加により、コードは g++ でもコンパイルされます)。std::pair

#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_;
};
于 2013-03-01T15:25:51.043 に答える
17

The problem is that std::unordered_set is using std::hash template to compute hashes for its entries and there is no std::hash specialization for pairs. So you will have to do two things:

  1. Decide what hash function you want to use.
  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;
}
于 2013-03-01T15:18:43.303 に答える
6

この質問に関する他のほとんどの回答ですでに述べたように、 のハッシュ関数を提供する必要がありますstd::pair<int, int>。ただし、C++11以降では、ハッシュ関数を定義する代わりにラムダ式を使用することもできます。次のコードは、セルゲイによって提供されたソリューションを基礎として使用します。

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 の免責事項を繰り返してください: このソリューションは、2 つの整数のペアに制限されています。この回答は、より一般的な解決策のアイデアを提供します。

于 2019-02-06T15:20:31.327 に答える
4

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_;
};
于 2013-03-01T15:18:45.717 に答える
1

のハッシュ関数がありません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>>ます。その場合、2 番目のテンプレート パラメータを省略できます。

于 2013-03-01T15:14:24.213 に答える