CODEWITHSUNDEEP
c++templatesvariadic-templatesfold
Makogan
Makogan

Reputation: 9632

C++ templated packs, fold twice

I have read some questions that are similar but I don't find the exact thing I am looking for.

In a purely mathematical way a list is defined recursively as: (head, rest).

Where head is the first element in the list and rest is a list. So for example (1,2,3,4) is represented as (1, (2,(3,(4,[])))) where [] is the empty list.

Then if we want to iterate over the list we can write a recursive function more or less like this:

iterate(list)
    head = list.head
    // do stuff and return if head is the empty element
    iterate(list.rest)

And if we want to iterate over every 2 elements we do:

pair_iterate(list)
        head1 = list.head
        head2 = list.rest.head
        // do stuff and return if head is the empty element
        iterate(list.rest.rest)

I am trying to get that second behaviour in C++.

In C++ 17, folds got introduced, so one can do something like this:

template<typename...types>
auto sum(types...values) {
  return (... + values);
}

But let's say we wanted the sum of the products of adjacent parameters, e.g sum(1,2,3,4) is 1*2 + 3*4.

In this case we need to "fold twice" to get the the 2 heads to perform the operation and pass the rest of the list. Similar to my pseudocode.

Does anyone have advice on how to get 2 folds in a row?

EDIT: I specifically want to do it with folds, i.e inside the function declaration without having to rely on recursive templated functions.

Upvotes: 1

Views: 268

Answers (2)

Jarod42
Jarod42

Reputation: 218323

Easier would be to change prototype to take pairs:

template <typename ...Pairs>
auto sum_products(Pairs ...ts)
{
    return (... + (ts.first * ts.second));
}

else a generic solution is to use index_sequence:

template <std::size_t... Is, typename T>
auto sum_products_impl(std::index_sequence<Is...>, const T& t)
{
    return (... + (std::get<2 * Is>(t) * std::get<2 * Is + 1>(t)));
}

template <typename ...Ts>
auto sum_products(Ts ...ts)
{
    static_assert(sizeof...(Ts) % 2 == 0);
    return sum_products_impl(std::make_index_sequence<sizeof...(Ts) / 2>(), std::tie(ts...));
}

Upvotes: 0

cigien
cigien

Reputation: 60440

You can unpack the parameters 2 at a time, like this:

template <typename T1, typename T2, typename ...Ts>
auto sum_products(T1 t1, T2 t2, Ts ...ts)
{
  return t1 * t2 + sum_products(ts...);
}

and provide a base case overload for no arguments:

auto sum_products() { return 0; }

and then use it like this:

std::cout << sum_products(1,2,3,4);  // prints 14

Here's a demo.

Note that this will only work for an even number of arguments, but you can easily add a single argument overload to handle that case.

Upvotes: 2

Related Questions