std::tuple の Hash
(src/utility/tuple-hash.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/utility/tuple-hash.hpp"

TupleHash

テンプレート実引数が組み込み型であるような std::tuple の hash 関数を提供します。

そのままで使うことはおそらく多くなく、以下のように std::unordered_map や std::unordered_set などと組み合わせて使うことになるかと思います。

再帰で実装されている都合上、std::tuple のもつ型が多くなるとコンパイルができなくなることがあります。

usage

Tuple は、 std::hash< T >()(x) が動作するような型 T の列 (Args...) によって構成された std::tuple< Args... > に対して動作します。

ユーザ定義の構造体については、std::hash のオーバーロードをすることによって動作させることができます。

例として、std::tuple< bool, char, short, int, long, long logn > のような型で動作します。

std::unordered_map

std::unordered_map<
  std::tuple< Args... >,
  ValueType,
  TupleHash > mp;

std::unordered_multimap

std::unordered_multimap<
  std::tuple< Args... >,
  ValueType,
  TupleHash > mp;

std::unordered_set

std::unordered_set<
  std::tuple< Args... >,
  TupleHash > st;

std::unordered_multiset

std::unordered_multiset<
  std::tuple< Args... >,
  TupleHash > st;

Depends on

• size alias (src/cpp-template/header/size-alias.hpp)

Required by

• (offine) 木のパス $u-v$ 上の $k$ 番目の頂点 (Offline Jump On Tree) (src/graph/tree/offline-query/offline-query-jump-on-tree.hpp)

Verified with

• test/library-checker/jump_on_tree.test.cpp
• unit-test/utility/tuple-hash.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"

#include <functional>
#include <tuple>
#include <utility>

namespace luz::impl_tuple_hash {

  template < usize Index >
  class ImplTupleHash {
   public:
    template < typename T >
    usize hash_combine(const T &x, usize hr) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

    template < class Tuple >
    usize operator()(const Tuple &t) const noexcept {
      usize hr = ImplTupleHash< Index - 1 >()(t);
      return hash_combine(std::get< Index - 1 >(t), hr);
    }
  };

  template <>
  class ImplTupleHash< 0 > {
   public:
    template < class Tuple >
    usize operator()([[maybe_unused]] const Tuple &_) const noexcept {
      return 0;
    }
  };

} // namespace luz::impl_tuple_hash

namespace luz {

  class TupleHash {
    template < usize Index >
    using ImplTupleHash = impl_tuple_hash::ImplTupleHash< Index >;

   public:
    template < class... Args >
    usize operator()(const std::tuple< Args... > &t) const {
      using Tuple = std::tuple< Args... >;
      return ImplTupleHash< std::tuple_size< Tuple >::value >()(t);
    }
  };

} // namespace luz

#line 2 "src/utility/tuple-hash.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/utility/tuple-hash.hpp"

#include <functional>
#include <tuple>
#include <utility>

namespace luz::impl_tuple_hash {

  template < usize Index >
  class ImplTupleHash {
   public:
    template < typename T >
    usize hash_combine(const T &x, usize hr) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

    template < class Tuple >
    usize operator()(const Tuple &t) const noexcept {
      usize hr = ImplTupleHash< Index - 1 >()(t);
      return hash_combine(std::get< Index - 1 >(t), hr);
    }
  };

  template <>
  class ImplTupleHash< 0 > {
   public:
    template < class Tuple >
    usize operator()([[maybe_unused]] const Tuple &_) const noexcept {
      return 0;
    }
  };

} // namespace luz::impl_tuple_hash

namespace luz {

  class TupleHash {
    template < usize Index >
    using ImplTupleHash = impl_tuple_hash::ImplTupleHash< Index >;

   public:
    template < class... Args >
    usize operator()(const std::tuple< Args... > &t) const {
      using Tuple = std::tuple< Args... >;
      return ImplTupleHash< std::tuple_size< Tuple >::value >()(t);
    }
  };

} // namespace luz

Back to top page