6
\$\begingroup\$

C++ doesn't supply a std::hash<std::tuple<...>>, so I decided to implement one. However, I was viewing this as more of a hash library than extensions to std, so I placed it all under the namespace utils.

This was my first time seriously using template meta-progamming. I tried to make my code work no matter the cv-ness of the variable, or whether it was an rvalue or an lvalue. I'm not sure on the efficiency of execution, but I believe the compiler can optimize it down to simple arithmetic on hash values.

hash.h

#pragma once

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

#include <cstdint>

namespace utils {

template<class T>
struct hash
{
    template<class Type>
    std::size_t operator()(Type && v) const {
        return std::hash<T>()(std::forward<Type>(v));
    }
};


namespace internal {
    // A simple algorithm for combining two hash values,
    // algorithm from boost: http://www.boost.org/doc/libs/1_61_0/doc/html/hash/reference.html#boost.hash_combine
    constexpr inline std::size_t hash_combine(std::size_t hash1, std::size_t hash2) {
        return hash1 ^ (hash2 * 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
    }

    // Necessary to hold a value so that we can use the fold operator
    struct hash_combine_t
    {
        const std::size_t value;
    };

    // % because it's a non-commutative operator that has been used for things other than
    // it's "intended" purpose before (e.g. string formatting)
    constexpr hash_combine_t operator%(const hash_combine_t &lhs, const hash_combine_t &rhs) {
        return { hash_combine(lhs.value, rhs.value) };
    }

    template<class... Ts>
    constexpr std::size_t hash_combine_impl(Ts&&... args) {
        return (hash_combine_t{ static_cast<std::size_t>(args) } % ...).value;
    }

    template<class... Ts>
    constexpr std::size_t hash_all_impl(Ts&&... args) {
        return hash_combine_impl(utils::hash<std::decay_t<Ts>>()(std::forward<Ts>(args))...);
    }
}

template<class... Ts>
constexpr std::size_t hash_combine(Ts&&... args) {
    return internal::hash_combine_impl(args...);
}

template<class... Ts>
constexpr std::size_t hash_all(Ts&&... args) {
    return internal::hash_all_impl(static_cast<std::decay_t<Ts>>(args)...);
}

template<class... Ts>
struct hash<std::tuple<Ts...>>
{
private:
    // We have this impl_t struct in order to support hashing of the empty tuple:
    //     std::tuple<>
    // The struct gives us partial template specification.
    template<std::size_t I, class Tuple>
    struct impl_t {
        std::size_t operator()(Tuple && tuple) const {
            // If this was called with an lvalue, we need to add an lvalue reference to our
            // types in order to get the correct utils::hash_all function.
            // utils::hash_all<Ts...> does not work; only things similar to
            // utils::hash_all<Ts&...> would work, but then it would not work for
            // rvalues as well.
            //
            // So we determine whether this was called with an lvalue by using std::is_reference<Tuple>.
            return std::apply(
                utils::hash_all<
                    std::conditional_t<
                        std::is_reference<Tuple>::value,
                        std::add_lvalue_reference_t<Ts>,
                        std::add_rvalue_reference_t<Ts>
                    >...
                >,
                std::forward<Tuple>(tuple)
            );
        }
    };
    template<class Tuple>
    struct impl_t<0, Tuple> {
        std::size_t operator()(Tuple && tuple) const {
            // 0 is a good value for the empty tuple; there is only one empty tuple
            return 0;
        }
    };
public:
    template<class Tuple>
    std::size_t operator()(Tuple && tuple) const {
        return impl_t<sizeof...(Ts), Tuple>()(std::forward<Tuple>(tuple));
    }
};

}
\$\endgroup\$
2
\$\begingroup\$

I think we can definitely simplify that:

#include <tuple>
#include <iostream>
#include <functional>
#include <type_traits>

Forward Declaration.

template<typename Tuple, std::size_t... ids>
std::size_t tupleHash(Tuple const& tuple, std::index_sequence<ids...> const&);

Hash All Types

template<typename T>
std::size_t hashValue(T const& value)
{
    // SFINAE kicks in here for tuples.
    // There is no std::hash that works for tuples.
    // So this candidate will be ignored if you use a tuple.
    std::hash<T>    hasher;
    return hasher(value);
}

Have a version for Tuples.

template<typename... Args>
std::size_t hashValue(std::tuple<Args...> const& value)
{
    return tupleHash(value, std::make_index_sequence<sizeof...(Args)>());
}
// Special case the empty tuple (as Args... can not be the empty list).
std::size_t hashValue(std::tuple<> const& value)
{
    // Not an expert in hashing.
    // Do some appropriate thing to get a value;
    return 1;
}

Do all the work in a helper function.

template<typename Tuple, std::size_t... ids>
std::size_t tupleHash(Tuple const& tuple, std::index_sequence<ids...> const&)
{
    // Not an expert in hashing.
    // Not sure 0 is a good seed (or this algorithm is good) solely here for demo purpose.
    std::size_t  result = 0;
    for(auto const& hash: {hashValue(std::get<ids>(tuple))...})
    {
        result ^= hash + 0x9e3779b9 + (result<<6) + (result>>2);
    }
    return result;
};

Tests

int main()
{
    auto tp = std::make_tuple(1,2,"Loki");
    std::cout << hashValue(tp) << "\n";

    auto ttp = std::make_tuple(4,tp,8,tp);
    std::cout << hashValue(ttp) << "\n";

    auto et = std::make_tuple();
    std::cout << hashValue(et) << "\n";
}
\$\endgroup\$
  • \$\begingroup\$ @justin: It was just supposed to show where to combine the values. I did not want to look up an actual hash combining function as there are a couple out there and it would be arbitrary which one I chose (as I have no context for the use case). \$\endgroup\$ – Martin York Aug 3 '16 at 20:12
  • \$\begingroup\$ This fails for nested tuples. You could define Hash as a specialization of std::hash and then it would work for that, but I wanted to not specialize std::hash. \$\endgroup\$ – Justin Aug 3 '16 at 20:23
  • \$\begingroup\$ This also fails for the empty tuple, but a specialization for hash would fix that \$\endgroup\$ – Justin Aug 3 '16 at 20:29
  • \$\begingroup\$ @Justin: Do you want me sit down tonight and actually work on real version rather than giving you hints on how to improve your code? \$\endgroup\$ – Martin York Aug 3 '16 at 22:26
  • \$\begingroup\$ I'm sorry if I came across as demanding. I didn't understand that you were suggesting improvements rather than saying "this is a much better way to do it, just use this code instead" \$\endgroup\$ – Justin Aug 4 '16 at 20:53

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.