2
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function Implementation with std::invocable concept in C++ and A recursive_transform Template Function with Execution Policy. Based on the previous questions, I am trying to consider execution policy parameter for recursive_transform function here.

The experimental implementation

//  recursive_transform implementation (with execution policy)
template<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)
{
    return f(input);
}

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

    std::array<TransformedValueType, S> output;
    std::transform(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_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));
    Container<TransformedValueType> output(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;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<class ExPo, is_multi_array T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<F, T>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(execution_policy, input[i], f);
    }
    return output;
}
#endif

Test cases

//  std::vector<int> -> std::vector<std::string>
std::vector<int> test_vector = {
    1, 2, 3
};
std::cout << "string: " + recursive_transform(std::execution::par, test_vector, [](int x)->std::string { return std::to_string(x); }).at(0) << std::endl;


//  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
std::vector<decltype(test_vector)> test_vector2 = {
    test_vector, test_vector, test_vector
};
std::cout << "string: " + recursive_transform(std::execution::par, test_vector2, [](int x)->std::string { return std::to_string(x); }).at(0).at(0) << std::endl;

//std::vector<std::vector<int>> -> std::vector<std::size_t>
std::cout << "recursive_count_if: " + recursive_transform(std::execution::par, test_vector2, [](std::vector<int> x) {
    return std::to_string(recursive_count_if(x, [](int number) { return number == 3; }));
    }).at(0) << std::endl;

The full testing code:

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

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

//  recursive_count implementation
template<std::ranges::input_range Range, typename T>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::count(input.cbegin(), input.cend(), target);
}

//  transform_reduce version
template<std::ranges::input_range Range, typename T>
requires std::ranges::input_range<std::ranges::range_value_t<Range>>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [target](auto&& element) {
        return recursive_count(element, target);
        });
}

//  recursive_count implementation (with execution policy)
template<class ExPo, std::ranges::input_range Range, typename T>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_count(ExPo execution_policy, const Range& input, const T& target)
{
    return std::count(execution_policy, input.cbegin(), input.cend(), target);
}

template<class ExPo, std::ranges::input_range Range, typename T>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_count(ExPo execution_policy, const Range& input, const T& target)
{
    return std::transform_reduce(execution_policy, std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [execution_policy, target](auto&& element) {
        return recursive_count(execution_policy, element, target);
        });
}

//  recursive_count_if implementation
template<class T, std::invocable<T> Pred>
constexpr std::size_t recursive_count_if(const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<std::ranges::input_range Range, class Pred>
requires (!std::invocable<Pred, Range>)
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

//  recursive_count_if implementation (with execution policy)
template<class ExPo, class T, std::invocable<T> Pred>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr std::size_t recursive_count_if(ExPo execution_policy, const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<class ExPo, std::ranges::input_range Range, class Pred>
requires ((std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<Pred, Range>))
constexpr auto recursive_count_if(ExPo execution_policy, const Range& input, const Pred& predicate)
{
    return std::transform_reduce(execution_policy, std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

//  recursive_transform implementation
template<class T, std::invocable<T> F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class T, std::size_t S, class F>
constexpr auto recursive_transform(const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

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

template<template<class...> class Container, class Function, class... Ts>
requires (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;

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

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<is_multi_array T, class F>
requires(!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(input[i], f);
    }
    return output;
}
#endif

//  recursive_transform implementation (with execution policy)
template<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)
{
    return f(input);
}

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

    std::array<TransformedValueType, S> output;
    std::transform(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_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(ExPo execution_policy, const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(execution_policy, *input.cbegin(), f));
    Container<TransformedValueType> output(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;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<class ExPo, is_multi_array T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<F, T>)
constexpr auto recursive_transform(ExPo execution_policy, const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(execution_policy, input[i], f);
    }
    return output;
}
#endif

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;
    }
}

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

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

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

template<std::size_t dim, template<class...> class Container = std::vector, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<dim - 1, Container, T>(input, times));
    }
}

int main()
{
    //  std::vector<int> -> std::vector<std::string>
    std::vector<int> test_vector = {
        1, 2, 3
    };
    std::cout << "string: " + recursive_transform(std::execution::par, test_vector, [](int x)->std::string { return std::to_string(x); }).at(0) << std::endl;


    //  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
    std::vector<decltype(test_vector)> test_vector2 = {
        test_vector, test_vector, test_vector
    };
    std::cout << "string: " + recursive_transform(std::execution::par, test_vector2, [](int x)->std::string { return std::to_string(x); }).at(0).at(0) << std::endl;

    //std::vector<std::vector<int>> -> std::vector<std::size_t>
    std::cout << "recursive_count_if: " + recursive_transform(std::execution::par, test_vector2, [](std::vector<int> x) {
        return std::to_string(recursive_count_if(x, [](int number) { return number == 3; }));
        }).at(0) << std::endl;

    //  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;

    return 0;
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

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

I hope someone else can have a look at the use of the mutex. Just some small things I'll note here:

Prefer using {} over 0 when you don't know the type

If you don't know the type of something, don't assume that 0 is implicitly convertible to an element of that type. Prefer default-constructing it in that case. So instead of:

for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)

Write:

for (decltype(+input.shape()[0]) i{}; i != input.shape()[0]; ++i)

Also note that I used != instead of < here, as well as the pre-increment operator. If you already assume it's an integer, then I'd not use decltype here but just write std::size_t i = 0, to make this clear.

Missing test cases

I don't see std::vector<std::string> being used as the input in any of the test cases. This is a very important case to test.

\$\endgroup\$

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.