constexpr variadic template and unpacking std::array

Question

I'd like to write a constexpr template function that permutes elements of an array passed in as a parameter. So I've come up with something like this:

template <typename T, std::size_t N, typename... Ts>
constexpr std::array<T, N> permute(const std::array<T, N>& arr, const std::array<int, N>& permutation, Ts&&... processed)
{
    return (sizeof...(Ts) == N) ?
        std::array<T, N>{ std::forward<Ts>(processed)... } :
        permute(arr, permutation, std::forward<Ts>(processed)..., arr[permutation[sizeof...(Ts)]]);
}

Usage example:

constexpr std::array<int, 3> arr{ 1, 2, 3 };
constexpr std::array<int, 3> permutation{ 2, 1, 0 };
constexpr auto result = permute(arr, permutation); //result should contain { 3, 2, 1 }

The problem is the above code doesn't compile. For some reason g++ 6.4 tries to instantiate the permute template with 4 and more parameters hidden under 'processed' template parameter pack. Can you help me correct my code and make it compile?

Full code

Answer 1

I'll present a "quick fix" that demonstrates the cause of the problem, then show how to solve the problem in C++11. After that, I'll show how to use newer features (C++14 onward) to get a simpler implementation.

---

Diagnosis

The cause of your runaway compilation is that the compiler has to generate both branches of the conditional and check them for correctness, even though it could prove that one of them will never be evaluated.

In newer versions of C++, we can make it work by replacing the ? with an if constexpr:

#include <array>
#include <cstddef>
#include <utility>

template <typename T, std::size_t N, typename... Ts>
constexpr std::array<T, N> permute(const std::array<T, N>& arr,
                                   const std::array<int, N>& permutation,
                                   Ts&&... processed)
{
    if constexpr (sizeof...(Ts) == N)
        return std::array<T, N>{ std::forward<Ts>(processed)... };
    else
        return permute(arr, permutation, std::forward<Ts>(processed)...,
                       arr[permutation[sizeof...(Ts)]]);
}

int main()
{
    constexpr std::array<int, 3> arr{ 1, 2, 3 };
    constexpr std::array<int, 3> permutation{ 2, 1, 0 };
    constexpr auto result = permute(arr, permutation);

    return result != std::array<int, 3>{ 3, 2, 1 };
}

(For these newer versions of C++, this can be simplified further using std::index_sequence, as I'll show later).

---

C++11 code

C++11 doesn't have if constexpr, so we'll need to revert to SFINAE instead:

#include <array>
#include <cstddef>
#include <utility>

template <typename T, std::size_t N, typename... Ts>
constexpr typename std::enable_if<sizeof...(Ts) == N, std::array<T, N> >::type
permute(const std::array<T, N>&, const std::array<int, N>&,
        Ts&&... processed)
{
    return std::array<T, N>{ std::forward<Ts>(processed)... };
}

template <typename T, std::size_t N, typename... Ts>
constexpr typename std::enable_if<sizeof...(Ts) != N, std::array<T, N> >::type
permute(const std::array<T, N>& arr, const std::array<int, N>& permutation,
        Ts&&... processed)
{
    return permute(arr, permutation, std::forward<Ts>(processed)...,
                   arr[permutation[sizeof...(Ts)]]);
}

Here, we provide completely separate functions for sizeof...(Ts) == N and sizeof...(Ts) != N, and use std::enable_if to select between them.

---

C++14 onwards

If we're able to use C++14 or later, we get std::index_sequence, which greatly simplifies operating on all the elements of an array or tuple. This still requires two functions, but this time one of them calls the other, and the logic is a bit easier to follow:

#include <array>
#include <cstddef>
#include <utility>

template<typename T, std::size_t N, std::size_t... I>
constexpr std::array<T, N>
permute_impl(const std::array<T, N>& a, const std::array<int, N>& p,
             std::index_sequence<I...>)
{
    return { a[p[I]]... };
}


template<typename T, std::size_t N, typename I = std::make_index_sequence<N>>
constexpr std::array<T, N>
permute(const std::array<T, N>& a, const std::array<int, N>& p)
{
    return permute_impl(a, p, I{});
}

It might even be worth implementing your own index_sequence if you need this more than once and you're constrained to using only C++11.