Forwards and return type(s) in functional-like reduce function

Question

I need to create a reduce function similar to std::reduce, but instead of working on containers, this function should work on variadic parameters.

This is what I currently have:

template <typename F, typename T>
constexpr decltype(auto) reduce(F&&, T &&t) {
    return std::forward<T>(t);
}

template <typename F, typename T1, typename T2, typename... Args>
constexpr decltype(auto) reduce(F&& f, T1&& t1, T2&& t2, Args&&... args) {
    return reduce(
        std::forward<F>(f),
        std::forward<F>(f)(std::forward<T1>(t1), std::forward<T2>(t2)),
        std::forward<Args>(args)...);
}

The following works as expected:

std::vector<int> vec;
decltype(auto) u = reduce([](auto &a, auto b) -> auto& {
        std::copy(std::begin(b), std::end(b), std::back_inserter(a));
        return a;
    }, vec, std::set<int>{1, 2}, std::list<int>{3, 4}, std::vector<int>{5, 6});

assert(&vec == &u); // ok
assert(vec == std::vector<int>{1, 2, 3, 4, 5, 6}); // ok

But the following does not work:

auto u = reduce([](auto a, auto b) {
        std::copy(std::begin(b), std::end(b), std::back_inserter(a));
        return a;
    }, std::vector<int>{}, std::set<int>{1, 2}, 
    std::list<int>{3, 4}, std::vector<int>{5, 6});

This basically crashes - To make this work, I need to e.g. change the first definition of reduce to:

template <typename F, typename T>
constexpr auto reduce(F&&, T &&t) {
    return t;
}

But if I do so, the first snippet does not work anymore.

The problem problem lies in the forwarding of the parameters and the return type of the reduce function, but I can find it.

How should I modify my reduce definitions to make both snippets work?

Answer 1

You could try

template <typename F, typename T>
constexpr T reduce(F&&, T &&t) {
    return std::forward<T>(t);
}

This returns a prvalue when the second argument was an rvalue, and an lvalue referring to the argument otherwise. Your snippets seem to be fine with it.

Alternatively, just use your second variant and wrap vec in std::ref, mutatis mutandis. That is also the standard approach when templates handle objects by value.

Answer 2

The lambda in your problem case:

[](auto a, auto b) {
    std::copy(std::begin(b), std::end(b), std::back_inserter(a));
    return a;
}

returns by value, so when reduce recurses:

 return reduce(
    std::forward<F>(f),
    std::forward<F>(f)(std::forward<T1>(t1), std::forward<T2>(t2)), // HERE
    std::forward<Args>(args)...);

The second argument is a temporary initialized from that by-value return object. When the recursion finally terminates:

template <typename F, typename T>
constexpr decltype(auto) reduce(F&&, T &&t) {
    return std::forward<T>(t);
}

It returns a reference bound to that temporary object which is destroyed while unwinding the recursion, so that v is initialized from a dangling reference.

The easiest fix for this would be to NOT create a temporary in your lambda and instead accumulate the results in the input object which you know will live at least until the end of the full expression (DEMO):

auto fn = [](auto&& a, auto const& b) -> decltype(auto) {
    std::copy(std::begin(b), std::end(b), std::back_inserter(a));
    // Or better:
    // a.insert(std::end(a), std::begin(b), std::end(b));
    return static_cast<decltype(a)>(a);
};

std::vector<int> vec;
decltype(auto) u = reduce(fn, vec,
    std::set<int>{1, 2}, std::list<int>{3, 4}, std::vector<int>{5, 6});

assert(&vec == &u); // ok
assert((vec == std::vector<int>{1, 2, 3, 4, 5, 6})); // ok

auto v = reduce(fn, std::vector<int>{},
    std::set<int>{1, 2},  std::list<int>{3, 4}, std::vector<int>{5, 6});
assert((v == std::vector<int>{1, 2, 3, 4, 5, 6})); // ok