`constexpr` reduction of `std::array` with binary operation
arrays, c++, c++11
Solution
My answer is based on my own implementation of such staff.
I prefer the general reduce (or fold, or accumulate) function to operate directly on elements as its own function arguments rather than being within a container like `std::array`. This way, instead of constructing a new array in every recursion, elements are passed as arguments and I guess the whole operation is easier for the compiler to inline. Plus it's more flexible, e.g. could be used directly or on the elements of a `std::tuple`. The general code is here. I repeat here the main function:
template <typename F>
struct val_fold
{
// base case: one argument
template <typename A>
INLINE constexpr copy <A>
operator()(A&& a) const { return fwd<A>(a); }
// general recursion
template <typename A, typename... An>
INLINE constexpr copy <common <A, An...> >
operator()(A&& a, An&&... an) const
{
return F()(fwd<A>(a), operator()(fwd<An>(an)...));
}
};
I am sorry this is full of my own definitions, so here is some help: `F` is the function object defining the binary operation. `copy` is my generalization of `std::decay` that recurses within arrays and tuples. `fwd` is just a shortcut for `std::forward`. Similarly, `common` is just a shortcut for `std::common_type` but intended for a similar generalization (in general, each operation may yield an expression template for lazy evaluation and here we are forcing evaluation).
How would you define `sum` using the above? First define the function object,
struct sum_fun
{
template <typename A, typename B>
INLINE constexpr copy <common <A, B> >
operator()(A&& a, B&& b) const { return fwd<A>(a) + fwd<B>(b); }
};
then just
using val_sum = val_fold<sum_fun>;
How would you call this when starting with an `std::array`? Well, once you've got your `Is...`, all you need is
val_sum()(std::get<Is>(arr)...);
which you may wrap within your own interface. Note that in C++14, `std::array::operator[]` is constexpr, so this would just be
val_sum()(arr[Is]...);
Now, to your questions:
1) Forwarding: Yes, `std::get` is forwarding array elements into `val_sum`, which is recursively forwarding everything to itself. So all that remains is your own interface to forward the input array, e.g.
template <typename A, /* enable_if to only allow arrays here */>
constexpr auto sum(A&& a) -> /* return type here */
{
return sum(std::forward<A>(a), gen_seq_array<A>{});
}
and so on, where `gen_seq_array` would take the raw type of A (`std::remove_ref`, `std::remove_cv` etc.), deduce `N`, and call `gen_seq<N>{}`. Forwarding makes sense if array elements have move semantics. It should be everywhere, e.g. the call of `val_sum` above would be something like
val_sum()(std::get<Is>(std::forward<A>(a))...);
2) Return type: As you have seen, I am using `std::common_type` as the return type, which should do for `sum` and most common arithmetic operations. This is already variadic. If you'd like your own type function, it's easy to make a variadic out of a binary type function, using template recursion.
My own version of `common` is here. It's a bit more involved, but it is still a recursive template containing some `decltype` to do the actual work.
In any case, this is more general than what you need, because it's defined for an arbitrary number of any given types. You only have one type `T` in your array, so what you have should be enough.
Problem
I want to write a constexpr function, that reduces a given `std::array` with a binary operation. I.e. a function which implements ``` template <typename T, std::size_t N> reduce(std::array<T, N>, binary_function); ``` To keep things simple I want to start with addition. E.g. ``` sum(std::array<int, 5>{{1,2,3,4,5}}); // returns 15. ``` What I got so far. I use the usual indexing trick to index array elements. I.e. generate a `int` sequence, that can be used for indexing with parameter list-expansion. ``` template <int... Is> struct seq {}; template <int I, int... Is> struct gen_seq : gen_seq<I - 1, I - 1, Is...> {}; template <int... Is> struct gen_seq<0, Is...> : seq<Is...> {}; // gen_seq<4> --> seq<0, 1, 2, 3> ``` The `sum` function is then defined through variadic template recursion. ``` // The edge-condition: array of one element. template <typename T> constexpr T sum(std::array<T, 1> arr, decltype(gen_seq<0>{})) { return std::get<0>(arr); } // The recursion. template <typename T, std::size_t N, int... Is> constexpr auto sum(std::array<T, N> arr, seq<Is...>) -> decltype(T() + T()) { return sum(std::array<T, N - 1>{ { std::get<Is>(arr)... } }, gen_seq<N - 2>()) + std::get<N - 1>(arr); } // The interface - hides the indexing trick. template <typename T, std::size_t N> constexpr auto sum(std::array<T, N> arr) -> decltype(sum(arr, gen_seq<N - 1>{})) { return sum(arr, gen_seq<N - 1>{}); } ``` Here you can see it in action. Questions This implementation works. However, I do have a few questions at this stage. - Is there any way, I can add perfect-forward to this function? And does that even make sense? Or should I declare those arrays const-references? - The assumption so far is, that the return-type of the reduction is `decltype(T()+T())`. I.e. what you get when you add two elements. While this should be true for addition in most cases, it might no longer be true for a general reduction. Is there a way, of getting the type of `a[0] + (a[1] + (a[2] + ... ) )`? I tried something like this, but I don't know how I can produce a template parameter list of `<T, T, T, ...>`.