Hashes
(library/util/hashes.hpp)

• View this file on GitHub
• Last update: 2022-10-23 23:57:23+09:00
• Include: #include "library/util/hashes.hpp"

Hashes

std::pair, std::tuple, std::array の hash を定義し、std::unordered_map の key として使えるようにする。

Required by

• ZDD (library/datastructure/ZDD.hpp)
• Tree Isomorphism Classification (library/tree/tree_isomorphism_classification.hpp)

Verified with

• test/src/datastructure/ZDD/maximum_independent_set.test.cpp
• test/src/tree/tree_isomorphism_classification/rooted_tree_isomorphism_classification.test.cpp

Code

#ifndef SUISEN_TUPLE_HASH
#define SUISEN_TUPLE_HASH

#include <array>
#include <cstdint>
#include <tuple>
#include <utility>

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

        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl {
            static void apply(size_t& seed, Tuple const& t) {
                HashValueImpl<Tuple, Index - 1>::apply(seed, t);
                hash_combine(seed, get<Index>(t));
            }
        };

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

    template <typename T, typename U>
    struct hash<std::pair<T, U>> {
        size_t operator()(std::pair<T, U> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::pair<T, U>>::apply(seed, tt);
            return seed;
        }
    };
    template <typename ...Args>
    struct hash<std::tuple<Args...>> {
        size_t operator()(std::tuple<Args...> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::tuple<Args...>>::apply(seed, tt);
            return seed;
        }
    };
    template <typename T, std::size_t N>
    struct hash<std::array<T, N>> {
        size_t operator()(std::array<T, N> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::array<T, N>>::apply(seed, tt);
            return seed;
        }
    };
}

#endif // SUISEN_TUPLE_HASH

#line 1 "library/util/hashes.hpp"



#include <array>
#include <cstdint>
#include <tuple>
#include <utility>

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

        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl {
            static void apply(size_t& seed, Tuple const& t) {
                HashValueImpl<Tuple, Index - 1>::apply(seed, t);
                hash_combine(seed, get<Index>(t));
            }
        };

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

    template <typename T, typename U>
    struct hash<std::pair<T, U>> {
        size_t operator()(std::pair<T, U> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::pair<T, U>>::apply(seed, tt);
            return seed;
        }
    };
    template <typename ...Args>
    struct hash<std::tuple<Args...>> {
        size_t operator()(std::tuple<Args...> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::tuple<Args...>>::apply(seed, tt);
            return seed;
        }
    };
    template <typename T, std::size_t N>
    struct hash<std::array<T, N>> {
        size_t operator()(std::array<T, N> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::array<T, N>>::apply(seed, tt);
            return seed;
        }
    };
}

Back to top page