How to dynamically get the variable types inside a tuple at C++ compiler time?

Question

I'm trying to write a genreric Hash function to be consumed in a hash table I'm going to use in the program runtime.

But I'm stuck here with a problem, to use the constexpr std::hash() function. I want to dynamically enumerate my tuple values, but I am not being able to do that by specifing constexpr in my operator overload method.

What am I doing wrong?

#include <iostream>
#include <unordered_map>

using llong = long long;
using ullong = unsigned long long;
using tlong = std::tuple<llong, llong>;
using tllong = std::tuple<llong, llong, llong>;
using tlllong = std::tuple<llong, llong, llong, llong>;
using tulong = std::tuple<ullong, ullong>;
using tullong = std::tuple<ullong, ullong, ullong>;
using tulllong = std::tuple<ullong, ullong, ullong, ullong>;

template<class Args>
struct KeyHash
{
    constexpr std::size_t operator()(const Args &args) const
    {
        std::size_t seed = 1, _size = std::tuple_size<Args>::value;
        for(auto i = 0ul; i< _size; i++)
        {
            seed += std::hash<std::tuple_element<(const std::size_t)i, Args>::type>()(std::get<i>(args)) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4);
        }

        return seed;
    }
};

template<class Args>
struct KeyEqual
{
    bool operator()(const Args &v1, const Args &v2) const 
    {
        return (v1 == v2);
    }
};

using  umtlong = std::unordered_map<tlong, int, KeyHash<tlong>, KeyEqual<tlong>>;
using  umtllong = std::unordered_map<tllong, int, KeyHash<tllong>, KeyEqual<tllong>>;
using  umtlllong = std::unordered_map<tlllong, int, KeyHash<tlllong>, KeyEqual<tlllong>>;

using  umtulong = std::unordered_map<tulong, int, KeyHash<tlong>, KeyEqual<tlong>>;
using  umtullong = std::unordered_map<tullong, int, KeyHash<tllong>, KeyEqual<tllong>>;
using  umtulllong = std::unordered_map<tulllong, int, KeyHash<tlllong>, KeyEqual<tlllong>>;

int main()
{
    return 0;
}

The error, I'm getting here is

g++ hash-map-tuple-keys.cc -o hash-map-tuple-keys.o -std=c++17
hash-map-tuple-keys.cc:21:50: error: non-type template argument is not a constant expression
            seed += std::hash<std::tuple_element<(const std::size_t)i, Args>::type>()(std::get<i>(args)) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4);
                                                 ^~~~~~~~~~~~~~~~~~~~
hash-map-tuple-keys.cc:21:69: note: read of non-const variable 'i' is not allowed in a constant expression
            seed += std::hash<std::tuple_element<(const std::size_t)i, Args>::type>()(std::get<i>(args)) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4);
                                                                    ^
hash-map-tuple-keys.cc:19:18: note: declared here
        for(auto i = 0ul; i< _size; i++)
                 ^
1 error generated.

I'm too lazy to figure out the full solution, but it's likely to involve [`std::index_sequence`](https://en.cppreference.com/w/cpp/utility/integer_sequence) and [fold expressions](https://en.cppreference.com/w/cpp/language/fold). The example in the second article uses both together. — Igor Tandetnik, Oct 20 '19 at 03:45

walnut · Answer 1 · 2019-10-20T06:45:07.383

The expressions inside a constexpr function, even when being evaluated as constant expression, still have to have static types. Therefore you cannot use a for loop, expecting it to operate on different types in each iteration.

You can use fold expressions (assuming C++17) instead. But to do so, you need a parameter pack. You can obtain this (in the case of tuples) for example by a call to std::apply with a generic lambda.

In the code below I use a partial specialization of KeyHash in addition to std::apply, but that is mostly for convenience, so that I have Args and don't need to use std::remove_reference_t<decltype(args)> instead in the lambda.

template<class>
struct KeyHash;

template<class... Args>
struct KeyHash<std::tuple<Args...>>
{
    constexpr std::size_t operator()(const std::tuple<Args...> &args) const
    {
        std::size_t seed = 1;
        std::apply([&](const auto&... args){
            (..., (seed += std::hash<Args>()(args) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4)));
        }, args);
        return seed;
    }
};

Instead of std::apply you can also use std::integer_sequence. With credit to @super for using this to fix my previously wrong code:

template<class Args, class I = std::make_index_sequence<std::tuple_size_v<Args>>>
struct KeyHash;

template<class... Args, std::size_t... Is>
struct KeyHash<std::tuple<Args...>, std::index_sequence<Is...>>
{
    constexpr std::size_t operator()(const std::tuple<Args...> &args) const
    {
        std::size_t seed = 1;
        (..., (seed += std::hash<Args>()(std::get<Is>(args)) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4)));
        return seed;
    }
};

I don't think it's safe to use `i++` multiple times in the same statement. You should use a `std::index_sequence` to obtain a pack of integers and expand it together with `args` to avoid unspecified order of evaluation. — super, Oct 20 '19 at 06:05
gcc complains that `i` is not constexpr: [compiler explorer](https://godbolt.org/z/nFBDSi) — ph3rin, Oct 20 '19 at 06:06
@super The comma operator is evaluated strictly left-to-right, including all side-effects. So I think this is fine as there are no unsequenced access to `i`. — walnut, Oct 20 '19 at 06:09
@KaenbyouRin Yes true, I made the same mistake as OP, pretty stupid. I will fix that. — walnut, Oct 20 '19 at 06:10
@KaenbyouRin Slightly different route, but it should be fine now. — walnut, Oct 20 '19 at 06:30

ph3rin · Answer 2 · 2019-10-20T06:29:47.550

Why your code doesn't compile?

For why your code does not work, see this answer.

Solution:

If you are on c++ 17 or later, then you may use fold expressions (I believe someone else has posted an answer about it).

If you are on c++ 14, then use recursive constexpr functions on a std::index_sequence:

#include <iostream>
#include <unordered_map>

using llong = long long;
using ullong = unsigned long long;
using tlong = std::tuple<llong, llong>;
using tllong = std::tuple<llong, llong, llong>;
using tlllong = std::tuple<llong, llong, llong, llong>;
using tulong = std::tuple<ullong, ullong>;
using tullong = std::tuple<ullong, ullong, ullong>;
using tulllong = std::tuple<ullong, ullong, ullong, ullong>;

template <typename T>
struct tuple_to_index_seq {
    using type = std::make_index_sequence<std::tuple_size<T>::value>;
};

template <typename T>
std::size_t calc_hash(std::size_t seed, const T& obj) {
    return std::hash<T>{}(obj) + 0x2e3dbcd34 + (seed << 6) + (seed >> 4);
}

template <typename T>
constexpr std::size_t key_hash_impl(std::size_t seed, const T& tup, std::index_sequence<>) {
    return seed;
}

template <typename T, size_t First, size_t... Rest>
constexpr std::size_t key_hash_impl(std::size_t seed, const T& tup, std::index_sequence<First, Rest...>) {
    seed += calc_hash(seed, std::get<First>(tup));
    return key_hash_impl(seed, tup, std::index_sequence<Rest...>{});
}

template<typename TupleType>
struct KeyHash
{
    constexpr std::size_t operator()(TupleType tup) const
    {
        return key_hash_impl(1u, tup, typename tuple_to_index_seq<TupleType>::type{});
    }
};

template<class Args>
struct KeyEqual
{
    bool operator()(const Args& v1, const Args& v2) const
    {
        return (v1 == v2);
    }
};

using  umtlong = std::unordered_map<tlong, int, KeyHash<tlong>, KeyEqual<tlong>>;
using  umtllong = std::unordered_map<tllong, int, KeyHash<tllong>, KeyEqual<tllong>>;
using  umtlllong = std::unordered_map<tlllong, int, KeyHash<tlllong>, KeyEqual<tlllong>>;

using  umtulong = std::unordered_map<tulong, int, KeyHash<tlong>, KeyEqual<tlong>>;
using  umtullong = std::unordered_map<tullong, int, KeyHash<tllong>, KeyEqual<tllong>>;
using  umtulllong = std::unordered_map<tulllong, int, KeyHash<tlllong>, KeyEqual<tlllong>>;

int main()
{
    KeyHash<tlong> key;
    auto tup = std::make_tuple(1LL, 2LL);
    std::cout << key(tup);
    umtlong my_map;
    my_map.insert(std::make_pair(std::make_tuple(0LL, 0LL), 0));
    return 0;
}

Compiler Explorer

Here is the removed answer in a fixed version on [godbolt](https://godbolt.org/z/0OCUTO). I'll just leave it here and maybe the guy who posted it in the first place can get around to re-posting it. — super, Oct 20 '19 at 06:19
@super I fixed it by now. If you still want to comment on the order of evaluation issue, you can do so now — walnut, Oct 20 '19 at 06:31

How to dynamically get the variable types inside a tuple at C++ compiler time?

2 Answers2

Why your code doesn't compile?

Solution: