使用二元操作符对`std::array`进行`constexpr`约简

Question

使用二元操作符对`std::array`进行`constexpr`约简

6

我希望编写一个constexpr函数，用于通过二元操作来将给定的std::array缩减。也就是说，这个函数需要实现以下功能：

template <typename T, std::size_t N>
reduce(std::array<T, N>, binary_function);

为了简单起见，我想从加法开始讲解。例如：

sum(std::array<int, 5>{{1,2,3,4,5}});  // returns 15.

我已经得到的内容

我使用通常的索引技巧来索引数组元素。即生成一个 int 序列，可以用于参数列表扩展的索引。

template <int... Is>
struct seq {};
template <int I, int... Is>
struct gen_seq : gen_seq<I - 1, I - 1, Is...> {};
template <int... Is>
struct gen_seq<0, Is...> : seq<Is...> {};  // gen_seq<4> --> seq<0, 1, 2, 3>

然后通过可变模板递归定义了sum函数。

// The edge-condition: array of one element.
template <typename T>
constexpr T sum(std::array<T, 1> arr, decltype(gen_seq<0>{})) {
    return std::get<0>(arr);
}

// The recursion.
template <typename T, std::size_t N, int... Is>
constexpr auto sum(std::array<T, N> arr, seq<Is...>) -> decltype(T() + T()) {
    return sum(std::array<T, N - 1>{ { std::get<Is>(arr)... } },
                gen_seq<N - 2>()) +
           std::get<N - 1>(arr);
}

// The interface - hides the indexing trick.
template <typename T, std::size_t N>
constexpr auto sum(std::array<T, N> arr)
    -> decltype(sum(arr, gen_seq<N - 1>{})) {
    return sum(arr, gen_seq<N - 1>{});
}

这里可以看到它的运行情况。

问题

这个实现方法有效。然而，在目前这个阶段，我有一些问题要问。

我是否可以以完美转发的方式将其添加到这个函数中？那样做是否有意义？或者我应该将那些数组声明为const-references？
到目前为止，假设归约的返回类型是decltype(T() + T())。即当你添加两个元素时得到的结果。虽然这对于大多数情况下的加法来说是正确的，但对于一般归约来说可能不再正确。有没有办法获取a[0]+(a[1]+(a[2]+...))的类型？我尝试了类似这样的方法，但我不知道如何生成<T，T，T......>的模板参数列表。

- Lemming

我真的无法理解这样做的目的。 - Mooing Duck

只有在 constexpr 的情况下才是这样的。 - iavr

@MooingDuck 这是一个非常好的实现。您能否考虑与iavr的答案以及我在这里提出的内容相比的任何优缺点？ - Lemming

@Lemming：从技术上讲，我的代码在某个点上存在未定义的行为。如果你仔细检查第10行，你会发现它调用了一个函数对象，并且在函数对象之间没有序列点。C++1y将添加修复它的能力：http://coliru.stacked-crooked.com/a/43b1cd5841dca9b7至于其他的优缺点，我不知道你的代码是如何工作的，也没有检查过Iavr的代码。我的代码更简单、更灵活，但对编译器更加困难。 - Mooing Duck

@MooingDuck 好的，完全可以。我想现在我会坚持使用下面的版本，因为它支持数组缩减和可变参数的缩减。拥有一些灵活性是不错的... - Lemming

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- iavr · Accepted Answer

我的答案基于我自己实现的这种人员管理方式。

我更喜欢使用通用的reduce（或fold、accumulate）函数直接操作元素作为其自己的函数参数，而不是在像std::array这样的容器中。这样，每次递归不需要构造一个新的数组，而是将元素作为参数传递，整个操作更容易被编译器内联。此外，它更加灵活，例如可以直接使用或在std::tuple的元素上使用。通用代码在这里。我在此重复主要函数：

 template <typename F>
 struct val_fold
 {
    // base case: one argument
    template <typename A>
    INLINE constexpr copy <A>
    operator()(A&& a) const { return fwd<A>(a); }

    // general recursion
    template <typename A, typename... An>
    INLINE constexpr copy <common <A, An...> >
    operator()(A&& a, An&&... an) const
    {
       return F()(fwd<A>(a), operator()(fwd<An>(an)...));
    }
 };

抱歉，这个充满了我的定义，以下是一些帮助：

F 是定义二元操作的函数对象。 copy 是我对std :: decay 的概括，它在数组和元组中递归。 fwd 只是std :: forward 的快捷方式。类似地，common只是std :: common_type 的快捷方式，但旨在实现类似的泛化（通常，每个操作都可能产生一个用于惰性计算的表达式模板，而我们正在强制进行评估）。
如何使用上述内容定义sum？ 首先定义函数对象，
struct sum_fun
{
    template <typename A, typename B>
    INLINE constexpr copy <common <A, B> >
    operator()(A&& a, B&& b) const { return fwd<A>(a) + fwd<B>(b); }
};

那么就
using val_sum = val_fold<sum_fun>;

如果从std::array开始，你会如何称呼这个东西呢？好的，一旦你有了你的Is...，你所需要的就是...
val_sum()(std::get<Is>(arr)...);

您可以将其包装在自己的接口中。请注意，在C++14中，std :: array :: operator [] 是constexpr，因此这将只是
val_sum()(arr[Is]...);

现在回答你的问题：
1) 转发：是的，std::get将数组元素转发到val_sum中，val_sum会递归地将所有内容转发给自己。因此，你只需要提供自己的接口来转发输入的数组，例如：
template <typename A, /* enable_if to only allow arrays here */>
constexpr auto sum(A&& a) -> /* return type here */
{
    return sum(std::forward<A>(a), gen_seq_array<A>{});
}

等等，其中gen_seq_array将采用A的原始类型(std::remove_ref，std::remove_cv等)，推导出N，并调用gen_seq<N>{}。如果数组元素具有移动语义，则转发是有意义的。它应该随处可见，例如上面的val_sum调用将类似于：
val_sum()(std::get<Is>(std::forward<A>(a))...);


2) 返回类型: 如您所见，我正在使用 std::common_type 作为返回类型，这对于 sum 和大多数常见的算术运算应该足够了。它已经是可变参数的了。如果您想要自己的类型函数，可以使用模板递归将二元类型函数变成可变参数。

我自己版本的 common 在 这里。它有点复杂，但仍然是一个递归模板，包含一些 decltype 来执行实际工作。

无论如何，这比您需要的更通用，因为它定义了任意数量的任意给定类型。您只有一个类型 T 在您的数组中，所以您拥有的应该足够了。