如何计算std::integral_constant元组的前缀和

Question

我想计算一下std::integral_constants的前缀和。

给定的是std::integral_constant在std::tuple中的集合。

示例

using in_t = std::tuple<
    std::integral_constant<unsigned __int64,1>,
    std::integral_constant<unsigned __int64,1>,
    std::integral_constant<unsigned __int64,2>
>;

如何在编译时计算前缀和，最好是使用导出返回类型的函数的方式(因为模板元编程非常痛苦)？

template <typename Tuple>
constexpr decltype(auto) prefixSum(Tuple t) {
    // ?
}

int main () {
    using in_t = std::tuple<
        std::integral_constant<unsigned __int64,1>,
        std::integral_constant<unsigned __int64,1>,
        std::integral_constant<unsigned __int64,2>
    >;
    
    using out_t = decltype(prefixSum<in_t>());
}

返回类型应该如下所示

std::tuple<
    std::integral_constant<unsigned __int64,1>,
    std::integral_constant<unsigned __int64,2>,
    std::integral_constant<unsigned __int64,4>
>

我经历了各种失败尝试，比如递归方式，将I‘the部分和作为模板参数传递到下一个级别。考虑到最大递归深度，不确定这是否是一种好方法。

一个失败的例子是

template <std::size_t I=0, std::size_t Offset=0, typename Tuple>
constexpr auto prefixSumRecursive(Tuple t) {
    constexpr auto value = Offset + std::get<I>(t);
    constexpr auto tuple = std::make_tuple(std::integral_constant<std::size_t, value>{});
    if constexpr((I+1) < std::tuple_size_v<Tuple>) {
        return std::tuple_cat(tuple, prefixSumRecursive<I + 1, value>(t));
    }
    return tuple;
}

Answer 1

标准中已经有一个前缀和的算法，即std::inclusive_scan。

#include <numeric>
#include <array>
#include <tuple>

using in_t = std::tuple<
  std::integral_constant<int,1>,
  std::integral_constant<int,1>,
  std::integral_constant<int,2>
>;

template<int... values>
constexpr auto prefixSum(
  std::tuple<std::integral_constant<int, values>...>) {
  constexpr auto out = [] {
    constexpr std::array in{values...};
    std::remove_const_t<decltype(in)> out{};
    std::inclusive_scan(in.begin(), in.end(), out.begin());
    return out;
  }();
  return [=]<auto... Is>(std::index_sequence<Is...>) {
    return std::tuple<std::integral_constant<int, out[Is]>...>{};
  }(std::make_index_sequence<out.size()>());
}

using in_t = std::tuple<
  std::integral_constant<int,1>,
  std::integral_constant<int,1>,
  std::integral_constant<int,2>
>;

using out_t = decltype(prefixSum(in_t{}));

演示