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 '18 at 19:37
  • \$\begingroup\$ great, maybe you'll think of something later. \$\endgroup\$ Nov 4 '18 at 20:13
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 '20 at 14:44
  • \$\begingroup\$ @user1095108 Yeah, with P1858 it's gonna become ((seed = hash_combine(tuple.[:], seed)), ...) \$\endgroup\$
    – L. F.
    Mar 11 '20 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, privacy policy and cookie policy

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