CODEWITHSUNDEEP
c++templatesc++11c++14
claudio
claudio

Reputation: 168

Alternative tuple iteration using constexpr

I want to write a function which kind of iterates over a std::tuple<...>. The iteration itself won't produce any problems regarding the tuple's template types, because '...' have the same types (like int, int, int, ...). I implemented already a working function 'Foo' with a helper struct 'Helper' using template metapgrogramming – everything is fine.

But when I want to implement an alternative version, using a constexpr function 'helper', the compiler (g++ 5.2.0) gets stuck in an infinite loop of error messages. From what I can get from these messages, the 'position' template parameter is instantiated as ridicilously big (== 4294967245) instead of (== 1). I tried to get both versions as close in syntax and nomenclature as possible.

Minimal example

#include <tuple>
// template metaprogramming version
template
<class T, std::size_t position>
struct Helper{
    static int
    help(T tuple) {
        return std::get<position>(tuple) +
            Helper<T,position - 1>::help(tuple);
    }
};

// template metaprogramming version, specialized
template
<class T>
struct Helper<T,0>{
    static int
    help(T tuple) {
        return std::get<0>(tuple);
    }
};
// function version, not working
template
<class T, std::size_t position>
constexpr int
helper(T tuple) {
    return
        0 == position ?
            std::get<position>(tuple) + helper<T,position-1>(tuple) :
            std::get<0>(tuple);
}

template
<class T>
auto
Foo(T tuple) {
    constexpr std::size_t dimension = std::tuple_size<T>::value;
    // working version, using the helper struct
    return Helper<T,dimension - 1>::help(tuple);
    // wrong(?) version, using the constexpr helper function
    return helper<T,dimension - 1>(tuple);
}

int main() {
    std::tuple<int,int> t(1,1);
    Foo(t);
    return 0;
}

My questions:

I am totally aware that, due to the same types in the tuple (int,int,...), one could implement a similar version with vectors. But I think that the tuple version is conceptually better to my kind of problem and faster during runtime.

Upvotes: 3

Views: 1393

Answers (2)

Barry
Barry

Reputation: 302757

When you have a function template - all the code must be compiled out. So here:

template
<class T, std::size_t position>
constexpr int helper(T tuple) {
    return
        0 == position ?
            std::get<position>(tuple) + helper<T,position-1>(tuple) :
            std::get<0>(tuple);
}

We always compile both parts of the conditional (side-note: your conditional is backwards). So when position == 0, both the std::get<0>(tuple) part is compiled and the std::get<0>(tuple) + helper<T, -1>(tuple) part is compiled. But then to do that, we'd need to compile helper<T, -2>(tuple). And helper<T, -3>(tuple). We recursive infinitely.

Your specialization approach works because Helper<T, 0> just does std::get<0>. There is no other logic in there, so we stop. If you want to do this functionally, an easier way would be to pass the position as an argument. That is:

template <std::size_t position>
using Pos = std::integral_constant<std::size_t, position>; // to save me some typing

template <typename T>
constexpr int helper(T const& tuple, Pos<0> )
{
    return std::get<0>(tuple);
}

template <typename T, std::size_t position>
constexpr int helper(T const& tuple, Pos<position> )
{
    return std::get<position>(tuple) + helper(tuple, Pos<position - 1>{});
}

Here, we do the conditional via overloading - so once we get to helper(T, Pos<0> ), we successfully terminate the recursion.

In C++1z, this becomes a ton easier with fold expressions, where you can just do:

template <typename T>
constexpr int sum_tuple(T const& tuple) {
    return sum_tuple(tuple, std::make_index_sequence<std::tuple_size<T>::value>{});
}

template <typename T, std::size_t... Is>
constexpr int sum_tuple(T const& tuple, std::index_sequence<Is...> )
{
    return (std::get<Is>(tuple) + ... );
}

Upvotes: 6

Jonathan Wakely
Jonathan Wakely

Reputation: 171263

So my questions: Is it principally wrong to try this kind of iteration during compile time with constexpr functions?

Yes, it's wrong, as you've done it. It can be done, but you can't terminate the compile-time recursion with a run-time condition.

When you instantiate helper<T, N>(T) that instantiates helper<T, N-1>(T) which instantiates herlper<T, N-2>(t) and so on, with nothing to terminate the recursion.

The class template version terminates when it reaches N==0 because of the partial specialization, but you can't partially specialize a function template.

Barry's solution works by using a second overload to terminate the recursion, so that when it reaches 0 it chooses a different function and doesn't keep instantiating the same one forever.

Upvotes: 3

Related Questions