4
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function with Execution Policy, A recursive_transform Template Function Implementation with std::invocable Concept and Execution Policy in C++, A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++ and A recursive_depth function for calculating depth of nested types implementation in C++. Considering that the previous std::for_each version recursive_transform doesn’t ensure deterministic behavior, the individual results could be emplaced into the output container in an arbitrary order because of the multiple factors. Therefore, another version recursive_transform template function which is order guaranteed and unwrap_level controlled has been proposed in this post. Referencing the latest call signature of std::ranges::transform, the concept std::copy_constructible is used on the input function parameter. Also, the similar way is used here.

The experimental implementation

  • Order guaranteed recursive_transform template function implementation:

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

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

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

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

//  recursive_variadic_invoke_result_t implementation
template<std::size_t, typename, typename, typename...>
struct recursive_variadic_invoke_result { };

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<std::invoke_result_t<F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...>>;
};

template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_variadic_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<
        typename recursive_variadic_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...
        >::type>;
};

template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>
using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;

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

//  recursive_transform for the multiple parameters cases (the version with unwrap_level)
template<std::size_t unwrap_level = 1, class F, class Arg1, class... Args>
requires(unwrap_level <= recursive_depth<Arg1>())
constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_variadic_invoke_result_t<unwrap_level, F, Arg1, Args...> output{};
        transform(
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element1, auto&&... elements) { return recursive_transform<unwrap_level - 1>(f, element1, elements...); },
            std::ranges::cbegin(arg1),
            std::ranges::cend(arg1),
            std::ranges::cbegin(args)...
        );
        return output;
    }
    else if constexpr(std::regular_invocable<F, Arg1, Args...>)
    {
        return std::invoke(f, arg1, args...);
    }
    else
    {
        static_assert(!std::regular_invocable<F, Arg1, Args...>, "Uninvocable?");
    }
}

//  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>>&&
          (unwrap_level <= recursive_depth<T>()))
constexpr auto recursive_transform(ExPo execution_policy, const F& f, const T& input)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t<unwrap_level, F, T> output{};
        output.resize(input.size());
        std::mutex mutex;
        std::transform(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
            [&](auto&& element)
            {
                std::lock_guard lock(mutex);
                return recursive_transform<unwrap_level - 1>(execution_policy, f, element);
            });
        return output;
    }
    else if constexpr(std::regular_invocable<F, T>)
    {
        return std::invoke(f, input);
    }
    else
    {
        static_assert(!std::regular_invocable<F, T>, "Uninvocable?");
    }
}

Full Testing Code

The full testing code:

//  Order guaranteed recursive_transform template function implementation with execution policy in C++

#include <algorithm>
#include <cassert>
#include <concepts>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <string>
#include <vector>

//  recursive_depth function implementation
template<typename T>
constexpr std::size_t recursive_depth()
{
    return 0;
}

template<std::ranges::input_range Range>
constexpr std::size_t recursive_depth()
{
    return recursive_depth<std::ranges::range_value_t<Range>>() + 1;
}

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

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

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

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

//  recursive_variadic_invoke_result_t implementation
template<std::size_t, typename, typename, typename...>
struct recursive_variadic_invoke_result { };

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<std::invoke_result_t<F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...>>;
};

template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_variadic_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<
        typename recursive_variadic_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...
        >::type>;
};

template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>
using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;

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

//  recursive_transform for the multiple parameters cases (the version with unwrap_level)
template<std::size_t unwrap_level = 1, class F, class Arg1, class... Args>
requires(unwrap_level <= recursive_depth<Arg1>())
constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_variadic_invoke_result_t<unwrap_level, F, Arg1, Args...> output{};
        transform(
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element1, auto&&... elements) { return recursive_transform<unwrap_level - 1>(f, element1, elements...); },
            std::ranges::cbegin(arg1),
            std::ranges::cend(arg1),
            std::ranges::cbegin(args)...
        );
        return output;
    }
    else if constexpr(std::regular_invocable<F, Arg1, Args...>)
    {
        return std::invoke(f, arg1, args...);
    }
    else
    {
        static_assert(!std::regular_invocable<F, Arg1, Args...>, "Uninvocable?");
    }
}

//  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>>&&
          (unwrap_level <= recursive_depth<T>()))
constexpr auto recursive_transform(ExPo execution_policy, const F& f, const T& input)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t<unwrap_level, F, T> output{};
        output.resize(input.size());
        std::mutex mutex;
        std::transform(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
            [&](auto&& element)
            {
                std::lock_guard lock(mutex);
                return recursive_transform<unwrap_level - 1>(execution_policy, f, element);
            });
        return output;
    }
    else if constexpr(std::regular_invocable<F, T>)
    {
        return std::invoke(f, input);
    }
    else
    {
        static_assert(!std::regular_invocable<F, T>, "Uninvocable?");
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

void recursiveTransformTest();

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

void recursiveTransformTest()
{
    for (std::size_t N = 1; N < 10; N++)
    {
        std::size_t N1 = N, N2 = N, N3 = N;
        auto test_vector = n_dim_vector_generator<3>(0, 10);

        for (std::size_t z = 1; z <= N3; z++)
        {
            for (std::size_t y = 1; y <= N2; y++)
            {
                for (std::size_t x = 1; x <= N1; x++)
                {
                    test_vector.at(z - 1).at(y - 1).at(x - 1) = x * 100 + y * 10 + z;
                }
            }
        }
        auto expected = recursive_transform<3>([](auto&& element) {return element + 1; }, test_vector);
        auto actual = recursive_transform<3>(std::execution::par, [](auto&& element) {return element + 1; }, test_vector);
        std::cout << "N = " << N << ": " << std::to_string(actual == expected) << '\n';
    }
}

The output of the testing code above:

N = 1: 1
N = 2: 1
N = 3: 1
N = 4: 1
N = 5: 1
N = 6: 1
N = 7: 1
N = 8: 1
N = 9: 1

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

The mutexes inhibit parallel execution

You use a mutex at each recursion level. This inhibits parallel execution of std::transform(). This defeats the purpose of having an execution_policy parameter. Also, it does nothing to preserve the order. The order preservation comes solely from std::transform() itself.

Why is the version without execution policy different?

The version of recursive_transform() that doesn't take an execution policy parameter looks very different from the one that does. I would expect it to look mostly the same, the only difference being the presence of execution_policy.

One version using std::inserter() and the other creating a new container object and calling resize() on it will likely mean that some container types will only work with one version, others only with the other version. Ideally, they both work on the same set of container types, so they can be used interchangeably.

Add a constraint on the invocable

In previous reviews we discussed how to properly constrain the type of invocable passed to your recursive algorithms. That can be done here as well. The use of static_assert() is less desirable, as it will only trigger in the deepest recursion level, causing a long and hard to read error message. And the custom message "Uninvocable?" is not very helpful either. At the very least, don't ask a one-word question, but instead state the exact problem clearly, for example by writing something like:

static_assert(…, "The function passed to recursive_transform() cannot be invoked"
                 "with the element types at the given recursion level.");
\$\endgroup\$
4
  • \$\begingroup\$ Thank you for answering. About the point Why is the version without execution policy different?, how can I perform std::inserter version with execution policy? Should I create another transform with execution policy? \$\endgroup\$
    – JimmyHu
    Commented Feb 28 at 12:42
  • 1
    \$\begingroup\$ What I mean is, why not just write constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args) { return recursive_transform(std::execution::sequenced_policy, f, arg1, args...); }? \$\endgroup\$
    – G. Sliepen
    Commented Feb 28 at 15:29
  • \$\begingroup\$ However, the version with execution policy didn't take variadic input... \$\endgroup\$
    – JimmyHu
    Commented Feb 28 at 22:13
  • \$\begingroup\$ Ah yes, that's another difference... you could zip multiple iterators somehow and then pass that to std::transform(). Or just do what the STL does, and only have support for unary and binary operators. \$\endgroup\$
    – G. Sliepen
    Commented Feb 28 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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