C で順序なしコレクションのタプルに対する汎用ハッシュ関数を実装するにはどうすればよいでしょうか?

順序なしコレクション内のタプルの汎用ハッシュ

C 標準ライブラリの領域におけるタプルの概念と、std::unowned_map などの順序なしコレクション内のキーとしてのタプルの使用法std::unowned_set は課題を引き起こす可能性があります。デフォルトでは、タプルには汎用ハッシュ関数が定義されていないため、開発者は手動でハッシュ関数を定義するという面倒な作業が必要になります。

汎用ソリューションの必要性

タプルのカスタム ハッシュ関数を定義すると、次のことが可能になります。面倒でエラーが発生しやすくなります。この問題に対処するために、開発者はプロセスを自動化する、より汎用的なソリューションを求めることがよくあります。

標準に準拠したアプローチ

標準ではタプルの汎用ハッシュ関数が明示的に提供されていませんが、標準ではに準拠したアプローチが利用可能です。コードをカスタム名前空間に移動することで、std 名前空間の特殊化に関連する未定義の動作を回避できます。

このアプローチでは、ハッシュ関数の独自の実装を使用してカスタム名前空間 hash_tuple が作成されます。 。この実装は、非タプル型を std::hash 関数にディスパッチします。

namespace hash_tuple{
template <typename TT>
struct hash
{
    size_t
    operator()(TT const&amp; tt) const
    {                                              
        return std::hash<TT>()(tt);                                 
    }                                              
};
}

再帰テンプレート コードは、std::hash:

namespace hash_tuple{
    namespace
    {
        template <class T>
        inline void hash_combine(std::size_t&amp; seed, T const&amp; v)
        {
            seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
    }
}

最後に、std テンプレートの特殊化が hash_tuple 名前空間内に配置されます:

namespace hash_tuple{
    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              
    };
}

このアプローチを使用するには、ユーザーは順序なしコレクション宣言で hash_tuple 名前空間を指定する必要があります:

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

このソリューションは標準に準拠していますが、順序なしコレクション宣言ごとに名前空間を指定する必要があります。

非標準アプローチ

C 標準に準拠していない代替アプローチは次のとおりです。汎用ハッシュ関数コードを std 名前空間に配置します。これにより、引数依存の検索 (ADL) が正しいハッシュ実装を自動的に見つけることができます。

namespace std{
    namespace
    {
        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     http://stackoverflow.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t&amp; seed, T const&amp; v)
        {
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t&amp; seed, Tuple const&amp; tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t&amp; seed, Tuple const&amp; tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

このアプローチでは、順序なしコレクション構文はより単純なままです。

unordered_set<tuple<double, int> > test_set;

ただし、この手法には次のような特徴があります。 std 名前空間の特殊化による未定義の動作のリスク。

結論

順序なしコレクション内のタプルの汎用ハッシュは、カスタム実装が必要となる可能性がある重要な問題です。この記事で概説した標準に準拠したアプローチと非標準のアプローチの両方が、実行可能なソリューションを提供します。最終的に、これらのアプローチのどちらを選択するかは、開発者の要件と、潜在的な未定義の動作に対する許容度によって決まります。

以上がC で順序なしコレクションのタプルに対する汎用ハッシュ関数を実装するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。