Splitting argpack in half?

Question

How can I split an argument pack in two equal parts?

For example, I would like to do something like this:

template<typename T> T sum(const T& t)
{ return t; }

template<typename T> T sum(const T& t1, const T& t2)
{ return t1 + t2; }

template<typename ...T> T sum(T&& ...t)
{ sum(first_half(t)...) + sum(second_half(t)...); }

Perhaps [this](http://stackoverflow.com/questions/14261183/how-to-make-generic-computations-over-heterogeneous-argument-packs-of-a-variadic) may help you? I think I've put an example showing this use case — Andy Prowl, May 29 '13 at 18:52
(here is a [live example](http://ideone.com/AEgjB9) showing something similar) — Andy Prowl, May 29 '13 at 19:03
Probably a dup of: http://stackoverflow.com/questions/5484930/split-variadic-template-arguments — Shafik Yaghmour, May 29 '13 at 19:13
@DyP: I don't think it's a good idea :D I was really in my first days of C++11 when I wrote it, so perhaps the code is not that good. But as an inspiration it may help the OP — Andy Prowl, May 29 '13 at 19:13
@PiotrNycz: Depends on how you split the ranges. The library I linked allows you to forward a subrange — Andy Prowl, May 29 '13 at 19:17
@AndyProwl, Your first days of C++11 are more advanced than many people's first months of C++11. — chris, May 29 '13 at 19:28
@PiotrNycz then the first overload (taking one argument) will be called once. — StackedCrooked, May 29 '13 at 19:41
Then, what will be desired behavior, for, let say, 10 elements? `ABCDE+FGHIJ`, then `(A+((B+C)+(D+E))+...`? — PiotrNycz, May 30 '13 at 15:24
@PiotrNycz `sum(1, 2, 3, 4, 5, 6, 7, 8)` would become `sum(sum(sum(1, 2), sum(3, 4)), sum(sum(5, 6), sum(7, 8)))` — StackedCrooked, May 30 '13 at 16:53
I can understand that power of 2 `(8 = 2^3)` is easy to divide by 2 multiple times. That was why I asked about 10 elements not 8, you must start thinking about not easy cases to understand what you want to have. Understanding of the problem is first step to solve it. — PiotrNycz, Jun 01 '13 at 14:58
@PiotrNycz I guess it would become: `(5 5) ==> ((2 3) (2 3)) ((2 3) (2 3)) ==> ((2 (1 2)) (2 (1 2))) ((2 (1 2)) (2 (1 2)))`. Which is not ideal, but I can tweak later. — StackedCrooked, Jun 01 '13 at 16:56
@StackedCrooked, why do you want this? The compiler will optimize the shit out of the standard implementation. This implementation I'm not so sure about. — OmnipotentEntity, Jun 07 '13 at 21:27
On second thought, this might be useful to get around default compiler template recursion limits. — OmnipotentEntity, Jun 07 '13 at 21:33

Joe · Accepted Answer · 2013-06-07T20:33:07.250

I would suggest something along the lines of this, as the required nesting depth and amount of boilerplate code is lower than in the suggested solution. However, the actual parameter pack is never split, instead two ranges of indices are produced to index the input values which are forwarded as tuples to be then accessed via std::get. Aside from the nesting depth, it is far easier to specify how the splitting is performed (rounding up, down, or taking a power of two and the remainder).

int sum(int a) { return a; }
int sum(int a, int b) { return a + b; }

template<typename... Args> int sum(Args&&... args);

template<typename Tuple, size_t... index>
int sum_helper(pack_indices<index...>, Tuple&& args)
{
    return sum(std::get<index>(args)...);
}

template <size_t begin, size_t end, typename... Args>
int sum_helper(Args&&... args)
{
    typename make_pack_indices<end, begin>::type indices;
    return sum_helper(indices, std::forward_as_tuple(std::forward<Args>(args)...));
}

template<typename... Args>
int sum(Args&&... args)
{
    constexpr size_t N = sizeof...(Args);
    return sum(
        sum_helper<0, N/2>(std::forward<Args>(args)...),
        sum_helper<N/2, N>(std::forward<Args>(args)...)
    );
}

which requires

template <size_t...>
struct pack_indices {};

template <size_t Sp, typename IntPack, size_t Ep>
struct make_indices_imp;

template <size_t Sp, size_t Ep, size_t... Indices>
struct make_indices_imp<Sp, pack_indices<Indices...>, Ep>
{
    typedef typename make_indices_imp<Sp+1, pack_indices<Indices..., Sp>, Ep>::type type;
};

template <size_t Ep, size_t... Indices>
struct make_indices_imp<Ep, pack_indices<Indices...>, Ep>
{
    typedef pack_indices<Indices...> type;
};

template <size_t Ep, size_t Sp = 0>
struct make_pack_indices
{
    static_assert(Sp <= Ep, "make_tuple_indices input error");
    typedef typename make_indices_imp<Sp, pack_indices<>, Ep>::type type;
};

`make_pack_indices` is linear. A logarithmic solution is possible, and generally provided in C++14 for `make_index_sequence`. — Deduplicator, Apr 27 '19 at 21:36

score 2 · Answer 2 · 2013-06-06T19:10:11.540

A possible solution is to convert the argument list into a tuple and then extract the needed arguments via std::get and std::index_sequence (it will appear only in C++14, but you can easily implement the same functionality in the meantime).

Untested example code follows:

template<class T1, class T2>
struct append_index_seq;

template<std::size_t N, std::size_t... NN>
struct append_index_seq<N, std::index_sequence<NN...>> {
    using type = std::index_sequence<N, NN...>;
};

template<std::size_t M, std::size_t N1, std::size_t... N>
struct add_index_seq_impl {
    using type = append_index_seq<N1+M, add_index_seq<N, M>::type>::type;
};

template<std::size_t M, std::size_t N1>
struct add_index_seq_impl {
    using type = std::index_sequence<N1+M>::type;
};

template<std::size_t M, std::size_t... N>
struct add_index_seq;

template<std::size_t M, std::size_t... N>
struct add_index_seq<m, std::index_sequence<N...>> {
    using type = add_index_seq_impl<M, N...>;
}

template<std::size_t N>
struct get_first_half {
    static_assert(N % 2 == 0, "N must be even");
    using indexes = std::make_index_sequence<N/2>;
};

template<std::size_t N>
struct get_second_half {
    static_assert(N % 2 == 0, "N must be even");
    using indexes_1st = std::make_index_sequence<N/2>;
    using indexes = add_index_seq<N/2, indexes_1st>::type;
};

template<class F, class Tuple, std::size_t... I>
auto apply(F&& f, Tuple&& t, index_sequence<I...>) 
{
    return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
}

template<class ...T> T sum(T&& ...t)
{ 
     auto params = std::make_tuple(t);
     T r1 = apply(sum, params, get_first_half<T...>::indexes);
     T r2 = apply(sum, params, get_second_half<T...>::indexes);
     return r1 + r2;
}

Splitting argpack in half?

2 Answers2

Linked