2
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++ and A recursive_print Function For Various Type Arbitrary Nested Iterable Implementation in C++. Besides the usage with single Ranges input like recursive_transform<1>(Ranges, Lambda), I am attempting to extend recursive_transform function to deal with the binary operation cases recursive_transform<>(Ranges1, Ranges2, Lambda) which Lambda here could take two inputs. For example:

std::vector<int> a{ 1, 2, 3 }, b{ 4, 5, 6 };
auto result1 = recursive_transform<1>(a, b, [](int element1, int element2) { return element1 + element2; });
for (auto&& element : result1)
{
    std::cout << element << std::endl;
}

This code can be compiled and the output:

5
7
9

The experimental implementation

  • recursive_invoke_result2 struct implementation: in order to determine the type of output, recursive_invoke_result2 struct is needed.

    template<typename, typename, typename>
    struct recursive_invoke_result2 { };
    
    template<typename T1, typename T2, std::invocable<T1, T2> F>
    struct recursive_invoke_result2<F, T1, T2> { using type = std::invoke_result_t<F, T1, T2>; };
    
    //  Ref: https://stackoverflow.com/a/66821371/6667035
    template<typename F, class...Ts1, class...Ts2, template<class...>class Container1, template<class...>class Container2>
    requires (
        !std::invocable<F, Container1<Ts1...>, Container2<Ts2...>>&&
        std::ranges::input_range<Container1<Ts1...>>&&
        std::ranges::input_range<Container2<Ts2...>>&&
        requires { typename recursive_invoke_result2<F, std::ranges::range_value_t<Container1<Ts1...>>, std::ranges::range_value_t<Container2<Ts2...>>>::type; })
        struct recursive_invoke_result2<F, Container1<Ts1...>, Container2<Ts2...>>
    {
        using type = Container1<typename recursive_invoke_result2<F, std::ranges::range_value_t<Container1<Ts1...>>, std::ranges::range_value_t<Container2<Ts2...>>>::type>;
    };
    
    template<typename F, typename T1, typename T2>
    using recursive_invoke_result_t2 = typename recursive_invoke_result2<F, T1, T2>::type;
    
  • recursive_transform for the binary operation cases implementation:

    //  recursive_transform for the binary operation cases (the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class T1, class T2, class F>
    constexpr auto recursive_transform(const T1& input1, const T2& input2, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_invoke_result_t2<F, T1, T2> output{};
            std::transform(
                std::ranges::cbegin(input1),
                std::ranges::cend(input1),
                std::ranges::cbegin(input2),
                std::inserter(output, std::ranges::end(output)),
                [&f](auto&& element1, auto&& element2) { return recursive_transform<unwrap_level - 1>(element1, element2, f); }
            );
            return output;
        }
        else
        {
            return f(input1, input2);
        }
    }
    

The full testing code

//  A recursive_transform template function for the binary operation cases in C++

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <mutex>
#include <numeric>
#include <optional>
#include <ranges>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

//  recursive_print implementation
template<std::ranges::input_range Range>
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::ranges::transform(std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
        [level](auto&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range Range> requires (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::ranges::transform(std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
        [level](auto&& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

//  recursive_invoke_result_t implementation
template<typename, typename>
struct recursive_invoke_result { };

template<typename T, std::invocable<T> F>
struct recursive_invoke_result<F, T> { using type = std::invoke_result_t<F, T>; };

template<typename, typename, typename>
struct recursive_invoke_result2 { };

template<typename T1, typename T2, std::invocable<T1, T2> F>
struct recursive_invoke_result2<F, T1, T2> { using type = std::invoke_result_t<F, T1, T2>; };

template<typename F, template<typename...> typename Container, typename... Ts>
requires (
    !std::invocable<F, Container<Ts...>>&&
    std::ranges::input_range<Container<Ts...>>&&
    requires { typename recursive_invoke_result<F, std::ranges::range_value_t<Container<Ts...>>>::type; })
    struct recursive_invoke_result<F, Container<Ts...>>
{
    using type = Container<typename recursive_invoke_result<F, std::ranges::range_value_t<Container<Ts...>>>::type>;
};

//  Ref: https://stackoverflow.com/a/66821371/6667035
template<typename F, class...Ts1, class...Ts2, template<class...>class Container1, template<class...>class Container2>
requires (
    !std::invocable<F, Container1<Ts1...>, Container2<Ts2...>>&&
    std::ranges::input_range<Container1<Ts1...>>&&
    std::ranges::input_range<Container2<Ts2...>>&&
    requires { typename recursive_invoke_result2<F, std::ranges::range_value_t<Container1<Ts1...>>, std::ranges::range_value_t<Container2<Ts2...>>>::type; })
    struct recursive_invoke_result2<F, Container1<Ts1...>, Container2<Ts2...>>
{
    using type = Container1<typename recursive_invoke_result2<F, std::ranges::range_value_t<Container1<Ts1...>>, std::ranges::range_value_t<Container2<Ts2...>>>::type>;
};

template<typename F, typename T>
using recursive_invoke_result_t = typename recursive_invoke_result<F, T>::type;

template<typename F, typename T1, typename T2>
using recursive_invoke_result_t2 = typename recursive_invoke_result2<F, T1, T2>::type;

//  recursive_transform implementation (the version with unwrap_level)
template<std::size_t unwrap_level = 1, class T, class F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t<F, T> output{};
        std::ranges::transform(
            std::ranges::cbegin(input),
            std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
        );
        return output;
    }
    else
    {
        return f(input);
    }
}

//  recursive_transform implementation (the version with unwrap_level, with execution policy)
template<std::size_t unwrap_level = 1, class ExPo, class T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t<F, T> output{};
        std::mutex mutex;

        //  Reference: https://en.cppreference.com/w/cpp/algorithm/for_each
        std::for_each(execution_policy, input.cbegin(), input.cend(),
            [&](auto&& element)
            {
                auto result = recursive_transform<unwrap_level - 1>(execution_policy, element, f);
                std::lock_guard lock(mutex);
                output.emplace_back(std::move(result));
            }
        );

        return output;
    }
    else
    {
        return f(input);
    }
}

//  recursive_transform for the binary operation cases (the version with unwrap_level)
template<std::size_t unwrap_level = 1, class T1, class T2, class F>
constexpr auto recursive_transform(const T1& input1, const T2& input2, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t2<F, T1, T2> output{};
        std::transform(
            std::ranges::cbegin(input1),
            std::ranges::cend(input1),
            std::ranges::cbegin(input2),
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element1, auto&& element2) { return recursive_transform<unwrap_level - 1>(element1, element2, f); }
        );
        return output;
    }
    else
    {
        return f(input1, input2);
    }
}

void binary_test_cases();

int main()
{
    binary_test_cases();
    return 0;
}

void binary_test_cases()
{
    //  std::vector<int>
    std::vector<int> a{ 1, 2, 3 }, b{ 4, 5, 6 };
    auto result1 = recursive_transform<1>(a, b, [](int element1, int element2) { return element1 + element2; });
    for (auto&& element : result1)
    {
        std::cout << element << std::endl;
    }

    //  std::vector<std::vector<int>>
    std::vector<decltype(a)> c{ a, a, a }, d{ b, b, b };
    auto result2 = recursive_transform<2>(c, d, [](int element1, int element2) { return element1 + element2; });
    recursive_print(result2);

    //  std::deque<int>
    std::deque<int> test_deque;
    test_deque.push_back(1);
    test_deque.push_back(1);
    test_deque.push_back(1);

    auto result3 = recursive_transform<1>(test_deque, test_deque, [](int element1, int element2) { return element1 + element2; });
    for (auto&& element : result3)
    {
        std::cout << element << std::endl;
    }

    //  std::deque<std::deque<int>>
    std::deque<decltype(test_deque)> test_deque2;
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);
    auto result4 = recursive_transform<2>(test_deque2, test_deque2, [](int element1, int element2) { return element1 + element2; });
    recursive_print(result4);

    //  std::list<int>
    std::list<int> test_list = { 1, 2, 3, 4 };
    auto result5 = recursive_transform<1>(test_list, test_list, [](int element1, int element2) { return element1 + element2; });
    for (auto&& element : result5)
    {
        std::cout << element << std::endl;
    }

    //  std::list<std::list<int>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
    auto result6 = recursive_transform<2>(test_list2, test_list2, [](int element1, int element2) { return element1 + element2; });
    recursive_print(result6);
    return;
}

The output of the above tests:

5
7
9
Level 0:
 Level 1:
 5
 7
 9
 Level 1:
 5
 7
 9
 Level 1:
 5
 7
 9
2
2
2
Level 0:
 Level 1:
 2
 2
 2
 Level 1:
 2
 2
 2
 Level 1:
 2
 2
 2
2
4
6
8
Level 0:
 Level 1:
 2
 4
 6
 8
 Level 1:
 2
 4
 6
 8
 Level 1:
 2
 4
 6
 8
 Level 1:
 2
 4
 6
 8

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$
1
\$\begingroup\$

The only remark I have is that you have a lot of code duplication between the version that takes a unary operator and one that takes a binary operator. I'm sure the implementation of std::transform() has a lot of duplication as well. However, with C++20 it should be easy to make a version that takes a predicate that can have any number of parameters, not just one or two. The only issue is that the order of parameters to your function should be such that all the containers come last. To illustrate, here is a version of std::transform that works with any \$n\$-ary function:

template<typename OutputIt, typename NAryOperation, typename InputIt, typename... InputIts>
OutputIt transform(OutputIt d_first, NAryOperation op, InputIt first, InputIt last, InputIts... rest) {
    while (first != last) {
        *d_first++ = op(*first++, (*rest++)...);
    }
    return d_first;
}

We can combine support for \$n\$-ary functions with support for recursion. For example:

template<typename F, typename... Ts>
struct recursive_invoke_result {
    using type = std::invoke_result_t<F, Ts...>;
};

template<typename F, typename... Ts>
requires (std::ranges::input_range<Ts> && ...)
struct recursive_invoke_result<F, Ts...> {
    using type = recursive_invoke_result<F, std::ranges::range_value_t<Ts>...>::type;
};

So all this together should allow you to create a recursive_transform() that accepts a predicate that takes an arbitrary number of parameters.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the answering. Does func in the transform template function block seem to be op? \$\endgroup\$
    – JimmyHu
    Jul 8 at 8:26
  • 1
    \$\begingroup\$ Yes, fixed it :) \$\endgroup\$
    – G. Sliepen
    Jul 8 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.