ホームページ >バックエンド開発 >C++ >カスタム ハッシュ関数を作成せずに、順序なしマップのキーとしてタプルを使用するにはどうすればよいですか?

カスタム ハッシュ関数を作成せずに、順序なしマップのキーとしてタプルを使用するにはどうすればよいですか?

Linda Hamilton
Linda Hamiltonオリジナル
2024-11-08 06:29:02755ブラウズ

How can I use tuples as keys in unordered maps without writing a custom hash function?

カスタム ハッシュ関数を使用せずに順序なしマップでタプルを使用する

std::unowned_map がそのままタプル キーを簡単に操作できることを期待するかもしれません。ただし、以下に示すように、タプルのハッシュ関数を定義する必要があります。

template<> struct do_hash<tuple<int, int>> {
    size_t operator()(std::tuple<int, int> const& tt) const {...}
};

このプロセスは退屈になる可能性があり、可変引数テンプレートに頼らずに C 0x タプルに対して自動化するかどうかという問題が生じます。

次のアプローチでは、標準ハッシュ可能型を含むすべての C 0x タプルを unowned_map の一部にすることができ、追加の作業なしで unowned_set:

#include <tuple>
namespace std {
    namespace {
        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v) {
            // Modified from Boost
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }

        // Recursive template for hashing tuples
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl {
            static void apply(size_t& seed, Tuple const& 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& seed, Tuple const& tuple) {
                hash_combine(seed, std::get<0>(tuple));
            }
        };
    }

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

関数を std 名前空間に配置すると、引数依存の名前検索 (ADL) 経由でアクセスできます。

標準準拠コード

std 名前空間内のオブジェクトを特殊化することは未定義の動作です。したがって、標準に準拠したソリューションの場合は、コードを別の名前空間に移動し、ADL の利便性を無視します。

namespace hash_tuple {

// Forward non-tuple types to std::hash
template <class TT>
struct hash {
    size_t
    operator()(TT const& tt) const {
        return std::hash<TT>()(tt);
    }
};

// Hash function combining values in a tuple
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
    static void apply(size_t& seed, Tuple const& 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& seed, Tuple const& tuple) {
        hash_combine(seed, std::get<0>(tuple));
    }
};

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

hash_tuple 名前空間内でハッシュ実装を宣言して、すべての非タプル型を std に転送します。 :hash を変更し、std::hash の代わりに hash_tuple::hash を使用するように hash_combine を変更します。残りのコードを hash_tuple 名前空間内に配置します。

このソリューションを使用するには、ADL の利便性を放棄する次のコードを含める必要があります。

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

以上がカスタム ハッシュ関数を作成せずに、順序なしマップのキーとしてタプルを使用するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。