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

Arvillaarvin

Perhaps this may help you? I think I've put an example showing this use case – Snook

(here is a live example showing something similar) – Snook

@AndyProwl I want ^this^ as a library ;) – Vacuole

Probably a dup of: #5485430 – Quiberon

@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 – Snook

What if no of elements is not even? – Dysthymia

@PiotrNycz: Depends on how you split the ranges. The library I linked allows you to forward a subrange – Snook

@AndyProwl, Your first days of C++11 are more advanced than many people's first months of C++11. – Rone

@Dysthymia then the first overload (taking one argument) will be called once. – Arvillaarvin

Then, what will be desired behavior, for, let say, 10 elements? ABCDE+FGHIJ, then (A+((B+C)+(D+E))+...? – Dysthymia

@Dysthymia 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))) – Arvillaarvin

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. – Dysthymia

@Dysthymia 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. – Arvillaarvin

@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. – Subsistence

On second thought, this might be useful to get around default compiler template recursion limits. – Subsistence

Answer 1

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

Catheycathi

make_pack_indices is linear. A logarithmic solution is possible, and generally provided in C++14 for make_index_sequence. – Reprehension

Answer 2

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

Folio