How to do a prefix sum on std::index_sequence?

Question

I want to compute the exclusive prefix sum (scan) of the indices of a std::index_sequence, but I'm unsure where to start. I've investigated the implementation of std::make_index_sequence looking for a generalization, but it is mysterious to me.

How can I implement exclusive_scan_index_sequence below to make the program succeed?

#include <type_traits>
#include <cassert>
#include <cstddef>

// define something like std::index_sequence
template<size_t... Indices>
struct index_sequence {};

// compute the exclusive scan of IndexSequence
// initializing the first value in the result sequence to Init
template<size_t Init, class IndexSequence>
struct exclusive_scan_index_sequence;

template<size_t Init, size_t... Indices>
struct exclusive_scan_index_sequence<Init,index_sequence<Indices...>>
{
  // what goes here?
};

int main()
{
  using ones = index_sequence<1,1,1,1,1>;

  using scanned = exclusive_scan_index_sequence<0,ones>;

  using expected = index_sequence<0,1,2,3,4>;

  assert((std::is_same<expected,scanned>::value));

  return 0;
}

score 2 · Accepted Answer · answered Feb 12 '15 at 19:01

I think the following, while still recursive, is easier:

template<typename Current, size_t Next, class IndexSequence>
struct exclusive_scan_index_sequence_impl
{
    using type = Current;
};

template<size_t... Current, size_t Next, size_t First, size_t... Indices>
struct exclusive_scan_index_sequence_impl<
           index_sequence<Current...>,
           Next,
           index_sequence<First,Indices...>
       >
    : exclusive_scan_index_sequence_impl<
          index_sequence<Current...,Next>,
          Next+First,
          index_sequence<Indices...>
      >
{ };

template<size_t Init, class IndexSequence>
using exclusive_scan_index_sequence =
    typename exclusive_scan_index_sequence_impl<
        index_sequence<>,
        Init,
        IndexSequence
    >::type;

Live example

score 1 · Answer 2 · answered Feb 11 '15 at 07:19

Here's a recursive solution which concatenates index_sequences:

template<class IndexSequence1, class IndexSequence2>
struct index_sequence_cat_impl;

template<size_t... Indices1, size_t... Indices2>
struct index_sequence_cat_impl<index_sequence<Indices1...>,index_sequence<Indices2...>>
{
  using type = index_sequence<Indices1...,Indices2...>;
};

template<class IndexSequence1, class IndexSequence2>
using index_sequence_cat = typename index_sequence_cat_impl<IndexSequence1,IndexSequence2>::type;

// compute the exclusive scan of IndexSequence
// initializing the first value in the sequence to Init
template<size_t Init, class IndexSequence>
struct exclusive_scan_index_sequence_impl;

template<size_t Init, size_t Index0, size_t... Indices>
struct exclusive_scan_index_sequence_impl<Init,index_sequence<Index0, Indices...>>
{
  using rest = typename exclusive_scan_index_sequence_impl<Init + Index0, index_sequence<Indices...>>::type; 

  using type = index_sequence_cat<index_sequence<Init>, rest>;
};

template<size_t Init, size_t Index0>
struct exclusive_scan_index_sequence_impl<Init,index_sequence<Index0>>
{
  using type = index_sequence<Init>;
};

template<size_t Init, class IndexSequence>
using exclusive_scan_index_sequence = typename exclusive_scan_index_sequence_impl<Init,IndexSequence>::type;

Maybe it's possible to do it iteratively somehow.

There is no iteration in template metaprogramming. It's a pure functional language. — tsuki, Feb 11 '15 at 07:20
@tsuki : I believe this could be done with an iterative constexpr function. — ildjarn, Feb 11 '15 at 07:25
The compiler could iterate :-) The implementation of `exclusive_scan_index_impl` is recursive: it is defined in terms of itself. By contrast, a solution which expanded a pack of indices could be called "iterative". [Recursive types can be more expensive for a compiler to parse](http://stackoverflow.com/a/9643480/722294). — Jared Hoberock, Feb 11 '15 at 07:25

How to do a prefix sum on std::index_sequence?

2 Answers2