2

unordered_mapのキーとして整数配列を使用したいと思います。基本的な考え方は、問題のさまざまな状態があり、それらはとして表されるということint state[16]です。配列の値は、次のように0から15までの数値の順列です。

a= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; 
b= { 14, 1, 9, 6, 4, 8, 12, 5, 7, 2, 3, 0, 10, 11, 13, 15}; ...

そしてそれらはunordered_mapのキーになります(値は他のものとのクラスになります)。どうやってやるの?値を比較するために新しいハッシュ関数を実装する必要がありますか、それともC ++によって提供されるものを使用できますか?私の目標はこれをハッシュテーブルとして使用することですが、他にもっと良い方法はありますか?

4

2 に答える 2

3

16!は約2*10 ^ 13であるため、順列の序数を64ビット整数で格納し、順列を格納またはハッシュする必要なしに、それをマップキーとして使用できます。

0...N-1の順列と0...Nの数の間の自然な全単射については、http://en.wikipedia.org/wiki/Permutation#Numbering_permutationsを参照してください。-1。

std::mapまたは、 ;を使用することもできます。順列は、辞書式に比較するのに効率的です。

3番目の選択肢は、値が;std::stringに簡単に収まるため、キーとしてaを使用することです。に特化しています。charstd::hashstd::string

于 2012-09-05T10:06:31.637 に答える
0

hash_rangeBoostから使用できます。

namespace std
{
    template <typename T, typename A>
    struct hash<vector<T, A>>
    {
        size_t operator()(vector<T, A> const & v) const
        {
            return boost::range_hash(v.cbegin(), v.cend());
        }
    };
}
于 2012-09-05T10:06:25.273 に答える