How to calculate prefix sum of tuple of std::integral

I would like to calculate the prefix sum of std::integral_constants.

Given is a collection of std::integral_constant in a std::tuple.

Example

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

How can the the prefix sum be calculated at compile time, preferably in a way using a function that's return type is deduced (since template metaprogramming is pretty painful)?

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

The return type should look like

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

I experienced various failure attempts, like a recursive way, passing the i'th partial sum to the next level as template argument. Not sure if that's a good approach at all, thinking of maximum recursion depth.

A failing example is

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

CodePudding user response：

There is already an algorithm for prefix sum in the standard, i.e., 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{}));

Demo