マップルックアップのために順序付けられていないキーの組み合わせを使用する

Question

unordered_mapを作成します。ここで、キーは2つの整数の組み合わせです。

#include <unordered_set> 
#include <unordered_map> 

using namespace std; 

int main() 
{ 
    unordered_set<int> key_set1 = {21, 42}; 
    unordered_map<unordered_set<int>, char> map; 
    map[key_set1] = 'a'; 
    ... 
    unordered_set<int> key_set2 = {42, 21}; 
    if(map[key_set2] == map[key_set2]) 
     success(); 
} 

それはハッシュ関数といくつかの問題のように見える、コンパイル時の場合：

error: no match for call to ‘(const std::hash<std::unordered_set<int> >) (const std::unordered_set<int>&)’ 
    noexcept(declval<const _Hash&>()(declval<const _Key&>()))> 

どのように比較する際のキー値の順序は無視されなければならないとして、私はこのようなキーとしてunordered_setを使用するのではと思いました私はこれを解決することはできますか？または、より良い方法/データ構造がありますか？

Answer 1

std::pairをキーとして直接使用するように先に指摘したように、ハッシュ関数を明示的に定義する必要があります。あなたはそれを避けたい場合は、あなただけの1に2つの符号なし整数のビット単位の組み合わせを行うことができます。

uint64_t makeKey(uint32_t a, uint32_t b) 
{ 
    return a < b ? (static_cast<uint64_t>(a) << 32) + b : (static_cast<uint64_t>(b) << 32) + a; 
} 

int main() 
{ 
    auto key_set1 = makeKey(21, 42); 

    unordered_map<uint64_t, char> map; 
    map[key_set1] = 'a'; 
    //... 

    auto key_set2 = makeKey(42, 21); 
    if(map[key_set1] == map[key_set2]) 
     std::cout << "success" << std::endl; 
} 

Answer 2

unordered_setは、順序付けられていないコンテナのキーとして使用するために構築されていないという問題があります。

pair<int,int> unordered_key(int a, int b) { 
    return a<b?make_pair(a, b):make_pair(b, a); 
} 

Answer 3

：あなたは、常に正確に2つのintを使用している場合は、キーとしてintのペアを使用し、2つの整数から適切に順序対を作る機能を追加するため

は、それがより経済的ですunordered_setにはあらかじめ定義されたハッシュ関数がありませんので、独自に実装する必要があります。そのためのドキュメントはhttp://en.cppreference.com/w/cpp/utility/hashです。

基本的にはあなたが必要があると思います。今

// custom specialization of std::hash can be injected in namespace std 
namespace std 
{ 
    template<> struct hash<unordered_set<int>> 
    { 
     std::size_t operator()(unordered_set<int> const& s) const 
     { 
      std::size_t hash = 0; 
      for (auto && i : s) hash ^= std::hash<int>()(i); 
      return hash; 
     } 
    }; 
} 

xorは、ハッシュ関数を組み合わせるための推奨方法ではありませんが、それはそれは順不同とセット両方です特にため、この場合には動作するはずです。順序付けられていないので、あなたは可換性のある関数が必要です。推奨されるハッシュコンバイナには、通常は "abc"を "bca"とは異なる方法でハッシュしたいので、このプロパティはありません。第二に、それがセットであるという事実は、あなたが重複要素を持たないことを保証します。 x^x == 0が原因でハッシュ関数が失敗するのを防ぎます。

これはcppファイルでこれを定義して、この特定のハッシュ実装をすべての人にstdタイプで公開しないようにしたいということにも言及する必要があります。

Answer 4

順序はここでは重要ではありませんので、ご注文を強制するためにカスタマイズされた工場でstd::pairを使用することができます二つの整数の：もちろん

std::pair<int, int> make_my_pair(int x, int y) { 
    return std::make_pair(std::min(x, y), std::max(x, y)); 
} 

これはあなたが一貫しmake_my_pairを使用する場合は仕事に行くされています。

また、同様のプロパティを持つ独自のキークラスを定義することもできます。