A recursive_transform Template Function with Execution Policy

Question

This is a follow-up question for A recursive_transform for std::vector with various return type, A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ and A recursive_transform for std::array with various return type. The execution policy parameter is available since C++17. I am trying to add this into the recursive_transform template function. The experimental version code is as below.

//  With execution policy
template<class ExPo, class T, class F>
auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    return f(input);
}

template<class ExPo, class T, std::size_t S, class F>
requires std::is_execution_policy_v<std::remove_cvref_t<ExPo>>
auto recursive_transform(ExPo execution_policy, const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(execution_policy, input.cbegin(), input.cend(), output.begin(),
        [execution_policy, f](auto& element)
        {
            return recursive_transform(execution_policy, element, f);
        }
    );
    return output;
}

template<class ExPo, template<class...> class Container, class Function, class... Ts>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>> && is_iterable<Container<Ts...>> && !is_elements_iterable<Container<Ts...>>)
// non-recursive version
auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(f(*input.cbegin()));
    Container<TransformedValueType> output(input.size());
    std::transform(execution_policy, input.cbegin(), input.cend(), output.begin(), f);
    return output;
}

template<class ExPo, template<class...> class Container, class Function, class... Ts>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>> && is_elements_iterable<Container<Ts...>>)
auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output(input.size());

    std::transform(execution_policy, input.cbegin(), input.cend(), output.begin(),
        [&](auto& element)
        {
            return recursive_transform(execution_policy, element, f);
        }
    );

    return output;
}

I found that std::back_inserter(output) cannot be used in here due to the error happened Parallel algorithms require forward iterators or stronger. Instead of using std::back_inserter() to fill the containers, the .size() function is used for constructing container. If there is any better way to handle the output container size, please let me know.

The test of this version of recursive_transform template function:

//  std::vector<int> -> std::vector<std::string>
std::vector<int> test_vector = {
    1, 2, 3
};
auto recursive_transform_result = recursive_transform(
    std::execution::par,
    test_vector,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing

std::cout << "string: " + recursive_transform_result.at(0) << std::endl;            //  recursive_transform_result.at(0) is a std::string


//  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
std::vector<decltype(test_vector)> test_vector2 = {
    test_vector, test_vector, test_vector
};

auto recursive_transform_result2 = recursive_transform(
    std::execution::par,
    test_vector2,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing

std::cout << "string: " + recursive_transform_result2.at(0).at(0) << std::endl;     // recursive_transform_result.at(0).at(0) is also a std::string


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

auto recursive_transform_result3 = recursive_transform(
    std::execution::par,
    test_deque,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result3.at(0) << std::endl;


//  std::deque<std::deque<int>> -> std::deque<std::deque<std::string>>
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 recursive_transform_result4 = recursive_transform(
    std::execution::par,
    test_deque2,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result4.at(0).at(0) << std::endl;


//  std::array<int, 10> -> std::array<std::string, 10>
std::array<int, 10> test_array;
for (int i = 0; i < 10; i++)
{
    test_array[i] = 1;
}
auto recursive_transform_result5 = recursive_transform(
    std::execution::par,
    test_array,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result5.at(0) << std::endl;

//  std::array<std::array<int, 10>, 10> -> std::array<std::array<std::string, 10>, 10>
std::array<std::array<int, 10>, 10> test_array2;
for (int i = 0; i < 10; i++)
{
    test_array2[i] = test_array;
}
auto recursive_transform_result6 = recursive_transform(
    std::execution::par,
    test_array2,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result6.at(0).at(0) << std::endl;


//  std::list<int> -> std::list<std::string>
std::list<int> test_list = { 1, 2, 3, 4 };
auto recursive_transform_result7 = recursive_transform(
    std::execution::par,
    test_list,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result7.front() << std::endl;


//  std::list<std::list<int>> -> std::list<std::list<std::string>>
std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
auto recursive_transform_result8 = recursive_transform(
    std::execution::par,
    test_list2,
    [](int x)->std::string { return std::to_string(x); });                          //  For testing
std::cout << "string: " + recursive_transform_result8.front().front() << std::endl;

Here's the Godbolt link.

All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

  A recursive_transform for std::vector with various return type,

  A recursive_transform Function For Various Type Nested Iterable With std::variant Implementation in C++ and

  A recursive_transform for std::array with various return type

• What changes has been made in the code since last question?

  The execution policy parameter is considered here in this version of recursive_transform template function.

• Why a new review is being asked for?

  In my opinion, I am not sure if it is a good idea to add the execution policy parameter in the above way. Especially the usage of std::is_execution_policy_v<std::remove_cvref_t<ExPo>> in constraint expression.

Answer 1

Make sure every template overload requires is_execution_policy<ExPo>

The overload for a single element does not place restrictions on the type of execution_policy. This means that if you pass something that is no an execution policy, it will always pick the first overload, which is most likely not what you want, and it may or may not give an error while compiling. Consider:

std::vector<char> test_vector = {1, 2, 3};

auto sum_sizeofs = recursive_transform(
    42,
    test_vector, [](auto &x){return std::to_string(sizeof x);});

The expected result is a std::vector<string> containing {"1", "1", "1"}, but the above will compile without errors and return a std::string containing "24" (when compiled with GCC on a 64-bits architecture).

Container size vs. std::back_inserter()

Indeed there is no way to use std::back_inserter(), since the transforms of elements can happen in parallel and std::back_inserter() is not thread safe. This means that you have to give the output container the right size before calling std::transform(). If this would not work, for example if TransformedValueType is a type that you could not assign to after it was constructed, then you have a problem. The only solution I see is to create a tread-safe back inserter, using std::for_each() instead of std::transform(), like so:

template<class ExPo, template<class...> class Container, class Function, class... Ts>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>> && is_elements_iterable<Container<Ts...>>)
auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;
    output.reserve(input.size());
    std::mutex mutex;

    std::for_each(execution_policy, input.cbegin(), input.cend(),
        [&](auto& element)
        {
            auto result = recursive_transform(execution_policy, element, f);
            std::lock_guard lock(mutex);
            output.emplace_back(std::move(result));
        }
    );

    return output;
}

However, that still requires the type to be at least move constructible, and this version might actually be slower than your version, depending on the overhead of the mutex.

What about std::vector<std::string>?

What if I want to convert a vector of strings to a vector of ints?

std::vector<std::string> test_vector = {"1", "2", "3"};

auto result = recursive_transform(
    std::execution::par,
    test_vector,
    [](const std::string &x){return std::stoi(x);});