2
\$\begingroup\$

Is there something terribly wrong with this implementation?

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

template <typename T> struct hash;

template <typename ...T>
struct hash<std::tuple<T...>>
{
  template <typename A1, typename ...A, std::size_t ...I>
  static auto apply_tuple(std::tuple<A1, A...> const& t,
    std::index_sequence<I...>) noexcept
  {
    if constexpr(sizeof...(A))
    {
      return hash_combine(std::get<0>(t),
        hash<std::tuple<A const&...>>()({std::get<I + 1>(t)...})
      );
    }
    else
    {
      return std::hash<std::remove_cv_t<std::remove_reference_t<A1>>>()(
        std::get<0>(t));
    }
  }

  auto operator()(std::tuple<T...> const& t) const noexcept
  {
    return apply_tuple(t,
      std::make_index_sequence<sizeof...(T) - 1>()
    );
  }
};

EDIT: This is better, I think:

template <typename ...T>
struct hash<std::tuple<T...>>
{
  template <std::size_t ...I>
  static auto apply_tuple(std::tuple<T...> const& t,
    std::index_sequence<I...>)
  {
    std::size_t seed{};

    return ((seed = hash_combine(std::get<I>(t), seed)), ...);
  }

  auto operator()(std::tuple<T...> const& t) const
  {
    return apply_tuple(t, std::make_index_sequence<sizeof...(T)>());
  }
};
\$\endgroup\$
2
  • \$\begingroup\$ Care about editing code in your question. Otherwise, I didn't notice something wrong in your code. \$\endgroup\$
    – Calak
    Nov 4, 2018 at 19:37
  • \$\begingroup\$ great, maybe you'll think of something later. \$\endgroup\$ Nov 4, 2018 at 20:13

2 Answers 2

2
\$\begingroup\$

Your code doesn't handle empty tuples gracefully. The first version generates a compilation error, and the second version returns void. For the first version, you can add an apply_tuple overload for empty tuples. For the second version, you can change

return ((seed = hash_combine(std::get<I>(t), seed)), ...);

to

((seed = hash_combine(std::get<I>(t), seed)), ...);
return seed;

Is 0 really a good initial seed? Some prime number, I guess, might be better (e.g., 672807365, which is what MSVC returns for std::hash<std::nullptr_t>{}(nullptr)).


The tuple unpacking can be simplified with std::apply, avoiding index_sequences:

template <typename... Args>
struct hash<std::tuple<Args...>> {
    std::size_t operator()(const std::tuple<Args...>& tuple) const noexcept
    {
        return std::apply([](const auto&... args) {
            auto seed = static_cast<std::size_t>(672807365);
            ((seed = hash_combine(args, seed)), ...);
            return seed;
        }, tuple);
    }
};

(live demo)

\$\endgroup\$
2
  • \$\begingroup\$ very nice, one of these days, we are going to hack it down to a one-liner. \$\endgroup\$ Mar 10, 2020 at 14:44
  • \$\begingroup\$ @user1095108 Yeah, with P1858 it's gonna become ((seed = hash_combine(tuple.[:], seed)), ...) \$\endgroup\$
    – L. F.
    Mar 11, 2020 at 0:38
0
\$\begingroup\$

It should have been like this all along:

template <typename> struct hash;

template <std::size_t SEED = 672807365, typename ...T>
constexpr auto hash_combine(T&& ...v)
{
  auto seed{SEED};

  (
    (
      seed ^= hash<std::remove_cvref_t<T>>()(std::forward<T>(v)) +
        0x9e3779b9 + (seed << 6) + (seed >> 2)
    ),
    ...
  );

  return seed;
}

template <typename ...T>
struct hash<std::tuple<T...>>
{
  constexpr auto operator()(std::tuple<T...> const& t) const
  {
    return std::apply(hash_combine, t);
  }
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.