常量表达式可变参数模板和展开std :: array

Question

我想编写一个constexpr模板函数，用于对作为参数传递的数组元素进行排列。因此，我想到了以下代码：

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)]]);
}

使用示例：

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 }

问题在于上述代码无法编译。由于某种原因，g++ 6.4试图在'processed'模板参数包下隐藏的四个或更多参数中实例化permute模板。你能帮我修改代码并使其编译吗？

完整代码

- Maxez

Answer 1

我将提供一个“快速修复”的例子，展示问题的原因，然后展示如何使用C++11解决这个问题。之后，我会展示如何使用更新的特性（从C++14开始）来实现更简单的解决方案。

诊断

您的编译时间过长的原因是编译器必须生成条件语句的两个分支，并检查它们的正确性，即使它可以证明其中一个分支永远不会被执行。

在较新的C++版本中，我们可以用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 };
}

对于这些更新的C++版本，可以使用std::index_sequence进一步简化，稍后我将展示。

---

C++11代码

C++11没有if constexpr，因此我们需要回归到SFINAE:

#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)]]);
}

在这里，我们为sizeof...(Ts) == N和sizeof...(Ts) != N提供完全独立的函数，并使用std::enable_if在它们之间做出选择。

---

从C++14开始

如果我们能够使用C++14或更高版本，我们就可以使用std::index_sequence，这极大地简化了对数组或元组的所有元素进行操作。这仍然需要两个函数，但这次其中一个函数调用另一个函数，逻辑更容易理解：

#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{});
}

如果你需要多次使用并且只能使用C++11，那么实现自己的index_sequence可能是值得的。

- Toby Speight