1
\$\begingroup\$

This is a follow-up question for A recursive_transform_view Template Function Implementation and A recursive_transform_view Template Function which returns a view in C++. In those implementations above, when it comes to Clang 16.0.0, the compiling error occurred with message <source>:63:8: error: class template partial specialization is not more specialized than the primary template [-Winvalid-partial-specialization]. I am trying to fix this error in this post.

The experimental implementation

  • recursive_transform Template Function Implementation:

    namespace UL                                                //   unwrap_level
    {
        template< std::ranges::input_range Container,
                  std::copy_constructible F>
        requires (std::ranges::view<Container>&&
                  std::is_object_v<F>)
        constexpr auto make_view(const Container& input, const F& f) noexcept
        {
            return std::ranges::transform_view(
                    input,
                    [&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
        }
    
        /* Override make_view to catch dangling references.  A borrowed range is
        * safe from dangling..
        */
        template <std::ranges::input_range T>
        requires (!std::ranges::borrowed_range<T>)
        constexpr std::ranges::dangling make_view(T&&) noexcept
        {
            return std::ranges::dangling();
        }
    
        //  clone_empty_container template function implementation
        template< std::size_t unwrap_level = 1,
                  std::ranges::input_range Container,
                  std::copy_constructible F>
        requires (std::ranges::view<Container>&&
                  std::is_object_v<F>)
        constexpr auto clone_empty_container(const Container& input, const F& f) noexcept
        {
            const auto view = make_view(input, f);
            recursive_variadic_invoke_result<unwrap_level, F, Container> output(std::span{input});
            return output;
        }
    
        //  recursive_transform template function implementation (the version with unwrap_level template parameter)
        template<   std::size_t unwrap_level = 1,
                    class T,
                    std::copy_constructible F,
                    class Proj = std::identity>
        requires (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
                  std::ranges::view<T>&&
                  std::is_object_v<F>)         
        constexpr auto recursive_transform(const T& input, const F& f, Proj proj = {} )
        {
            if constexpr (unwrap_level > 0)
            {
                auto output = clone_empty_container(input, f);
                if constexpr (is_reservable<decltype(output)>&&
                              is_sized<decltype(input)>)
                {
                    output.reserve(input.size());
                    std::ranges::transform(
                        input,
                        std::ranges::begin(output),
                        [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); },
                        proj
                    );
                }
                else
                {
                    std::ranges::transform(
                        input,
                        std::inserter(output, std::ranges::end(output)),
                        [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); },
                        proj
                    );
                }
                return output;
            }
            else if constexpr(std::regular_invocable<F, T>)
            {
                return std::invoke(f, std::invoke(proj, input));
            }
            else
            {
                static_assert(!std::regular_invocable<F, T>, "The function passed to recursive_transform() cannot be invoked"
                                                           "with the element types at the given recursion level.");
            }
        }
    
        /* This overload of recursive_transform is to support std::array
        */
        template< std::size_t unwrap_level = 1,
                  template<class, std::size_t> class Container,
                  typename T,
                  std::size_t N,
                  typename F >
        requires (std::ranges::input_range<Container<T, N>>)
        constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
        {
            recursive_array_invoke_result_t<unwrap_level, F, Container, T, N> output{};
    
            if constexpr (unwrap_level > 1)
            {
                std::ranges::transform(
                            input,
                            std::ranges::begin(output),
                            [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
                        );
            }
            else
            {
                std::ranges::transform(
                            input,
                            std::ranges::begin(output),
                            f
                        );
            }
    
            return output;
        }
    
        //  recursive_transform function implementation (the version with unwrap_level, without using view)
        template<std::size_t unwrap_level = 1, class T, class F>
        requires (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
                  !std::ranges::view<T>)
        constexpr auto recursive_transform(const T& input, const F& f)
        {
            if constexpr (unwrap_level > 0)
            {
                recursive_variadic_invoke_result_t<unwrap_level, F, T> output{};
                std::ranges::transform(
                    input,                      //  passing a range to std::ranges::transform()
                    std::inserter(output, std::ranges::end(output)),
                    [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
                );
                return output;
            }
            else
            {
                return std::invoke(f, input);   //   use std::invoke()
            }
        }
    
        //  recursive_transform implementation (the version with unwrap_level, with execution policy)
        template<std::size_t unwrap_level = 1, class ExPo, class T, std::copy_constructible F>
        requires (unwrap_level <= recursive_depth<T>() &&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
                  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_variadic_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, element, f);
                    });
                return output;
            }
            else
            {
                return std::invoke(f, input);
            }
        }
    
        //  recursive_transform implementation (binary case, the version with unwrap_level)
        template<std::size_t unwrap_level = 1, class ExPo, std::ranges::input_range R1, std::ranges::input_range R2, std::copy_constructible F>
        constexpr auto recursive_transform(ExPo execution_policy, const R1& input1, const R2& input2, const F& f)
        {
            if constexpr (unwrap_level > 0)
            {
                recursive_variadic_invoke_result_t<unwrap_level, F, R1> output{};
                output.resize(input1.size());
                std::mutex mutex;
                std::transform(execution_policy, std::ranges::cbegin(input1), std::ranges::cend(input1), std::ranges::cbegin(input2), std::ranges::begin(output),
                    [&](auto&& element1, auto&& element2)
                    {
                        std::lock_guard lock(mutex);
                        return recursive_transform<unwrap_level - 1>(execution_policy, element1, element2, f);
                    });
                return output;
            }
            else
            {
                return std::invoke(f, input1, input2);
            }
        }
    }
    

Full Testing Code

The full testing code:

//  An Updated `recursive_transform` Template Function Implementation in C++

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

//  is_reservable concept
template<class T>
concept is_reservable = requires(T input)
{
    input.reserve(1);
};

//  is_sized concept, https://codereview.stackexchange.com/a/283581/231235
template<class T>
concept is_sized = requires(T x)
{
    std::size(x);
};

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

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

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

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

template<   typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
struct recursive_array_invoke_result<1, F, Container<T, N>>
{
    using type = Container<
        std::invoke_result_t<F, std::ranges::range_value_t<Container<T, N>>>,
        N>;
};

template<   std::size_t unwrap_level,
            typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_invoke_result<unwrap_level, F, Container<T, N>>
{
    using type = Container<
        typename recursive_array_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container<T, N>>
        >::type, N>;
};

template<   std::size_t unwrap_level,
            typename F,
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
using recursive_array_invoke_result_t = typename recursive_array_invoke_result<unwrap_level, F, Container<T, N>>::type;

//  recursive_array_unwrap_type struct implementation, https://stackoverflow.com/a/76347485/6667035
template<std::size_t, typename>
struct recursive_array_unwrap_type { };

template<template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
struct recursive_array_unwrap_type<1, Container<T, N>>
{
    using type = std::ranges::range_value_t<Container<T, N>>;
};

template<std::size_t unwrap_level, template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_unwrap_type<unwrap_level, Container<T, N>>
{
    using type = typename recursive_array_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container<T, N>>
        >::type;
};

template<std::size_t unwrap_level, class Container>
using recursive_array_unwrap_type_t = typename recursive_array_unwrap_type<unwrap_level, Container>::type;

//  https://codereview.stackexchange.com/a/253039/231235
template<template<class...> class Container = std::vector, std::size_t dim, 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<Container, dim - 1, T>(input, times));
    }
}

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
    {
        std::array<decltype(n_dim_array_generator<dim - 1, times>(input)), times> output;
        for (size_t i = 0; i < times; i++)
        {
            output[i] = n_dim_array_generator<dim - 1, times>(input);
        }
        return output;
    }
}

namespace UL                                                //   unwrap_level
{
    template< std::ranges::input_range Container,
              std::copy_constructible F>
    requires (std::ranges::view<Container>&&
              std::is_object_v<F>)
    constexpr auto make_view(const Container& input, const F& f) noexcept
    {
        return std::ranges::transform_view(
                input,
                [&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
    }

    /* Override make_view to catch dangling references.  A borrowed range is
    * safe from dangling..
    */
    template <std::ranges::input_range T>
    requires (!std::ranges::borrowed_range<T>)
    constexpr std::ranges::dangling make_view(T&&) noexcept
    {
        return std::ranges::dangling();
    }

    //  clone_empty_container template function implementation
    template< std::size_t unwrap_level = 1,
              std::ranges::input_range Container,
              std::copy_constructible F>
    requires (std::ranges::view<Container>&&
              std::is_object_v<F>)
    constexpr auto clone_empty_container(const Container& input, const F& f) noexcept
    {
        const auto view = make_view(input, f);
        recursive_variadic_invoke_result<unwrap_level, F, Container> output(std::span{input});
        return output;
    }
    
    //  recursive_transform template function implementation (the version with unwrap_level template parameter)
    template<   std::size_t unwrap_level = 1,
                class T,
                std::copy_constructible F,
                class Proj = std::identity>
    requires (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
              std::ranges::view<T>&&
              std::is_object_v<F>)         
    constexpr auto recursive_transform(const T& input, const F& f, Proj proj = {} )
    {
        if constexpr (unwrap_level > 0)
        {
            auto output = clone_empty_container(input, f);
            if constexpr (is_reservable<decltype(output)>&&
                          is_sized<decltype(input)>)
            {
                output.reserve(input.size());
                std::ranges::transform(
                    input,
                    std::ranges::begin(output),
                    [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); },
                    proj
                );
            }
            else
            {
                std::ranges::transform(
                    input,
                    std::inserter(output, std::ranges::end(output)),
                    [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); },
                    proj
                );
            }
            return output;
        }
        else if constexpr(std::regular_invocable<F, T>)
        {
            return std::invoke(f, std::invoke(proj, input));
        }
        else
        {
            static_assert(!std::regular_invocable<F, T>, "The function passed to recursive_transform() cannot be invoked"
                                                         "with the element types at the given recursion level.");
        }
    }

    /* This overload of recursive_transform is to support std::array
    */
    template< std::size_t unwrap_level = 1,
              template<class, std::size_t> class Container,
              typename T,
              std::size_t N,
              typename F >
    requires (std::ranges::input_range<Container<T, N>>)
    constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
    {
        recursive_array_invoke_result_t<unwrap_level, F, Container, T, N> output{};

        if constexpr (unwrap_level > 1)
        {
            std::ranges::transform(
                        input,
                        std::ranges::begin(output),
                        [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
                    );
        }
        else
        {
            std::ranges::transform(
                        input,
                        std::ranges::begin(output),
                        f
                    );
        }
        
        return output;
    }

    //  recursive_transform function implementation (the version with unwrap_level, without using view)
    template<std::size_t unwrap_level = 1, class T, class F>
    requires (unwrap_level <= recursive_depth<T>()&&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
              !std::ranges::view<T>)
    constexpr auto recursive_transform(const T& input, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_variadic_invoke_result_t<unwrap_level, F, T> output{};
            std::ranges::transform(
                input,                      //  passing a range to std::ranges::transform()
                std::inserter(output, std::ranges::end(output)),
                [&f](auto&& element) { return recursive_transform<unwrap_level - 1>(element, f); }
            );
            return output;
        }
        else
        {
            return std::invoke(f, input);   //   use std::invoke()
        }
    }

    //  recursive_transform implementation (the version with unwrap_level, with execution policy)
    template<std::size_t unwrap_level = 1, class ExPo, class T, std::copy_constructible F>
    requires (unwrap_level <= recursive_depth<T>() &&        //  handling incorrect unwrap levels more gracefully, https://codereview.stackexchange.com/a/283563/231235
              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_variadic_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, element, f);
                });
            return output;
        }
        else
        {
            return std::invoke(f, input);
        }
    }

    //  recursive_transform implementation (binary case, the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class ExPo, std::ranges::input_range R1, std::ranges::input_range R2, std::copy_constructible F>
    constexpr auto recursive_transform(ExPo execution_policy, const R1& input1, const R2& input2, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_variadic_invoke_result_t<unwrap_level, F, R1> output{};
            output.resize(input1.size());
            std::mutex mutex;
            std::transform(execution_policy, std::ranges::cbegin(input1), std::ranges::cend(input1), std::ranges::cbegin(input2), std::ranges::begin(output),
                [&](auto&& element1, auto&& element2)
                {
                    std::lock_guard lock(mutex);
                    return recursive_transform<unwrap_level - 1>(execution_policy, element1, element2, f);
                });
            return output;
        }
        else
        {
            return std::invoke(f, input1, input2);
        }
    }
}

template<std::ranges::input_range T>
constexpr auto recursive_print(const T& input, const int level = 0)
{
    T 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 T>
requires (std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr T recursive_print(const T& input, const int level = 0)
{
    T 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;
}

void tests()
{
    //  non-nested input test, lambda function applied on input directly
    std::cout << "non-nested input test, lambda function applied on input directly:\n";
    int test_number = 3;
    auto ul_recursive_transform_output1 = UL::recursive_transform<0>(test_number, [](auto&& element) { return element + 1; });
    std::cout << "UL::recursive_transform function output: \n"
              << ul_recursive_transform_output1 << '\n';

    //  test with non-nested std::array container
    std::cout << "test with non-nested std::array container:\n";
    static constexpr std::size_t Times = 3;
    auto test_array = n_dim_array_generator<1, Times>(1);
    auto ul_recursive_transform_output2 = UL::recursive_transform<1>(test_array, [](auto&& element) { return element + 1; });
    std::cout << "UL::recursive_transform function output: \n";
    for(int i = 0; i < ul_recursive_transform_output2.size(); ++i)
    {
        std::cout << ul_recursive_transform_output2[i] << " ";
    }
    std::cout << '\n';

    //  test with nested std::arrays
    auto test_nested_array = std::array< decltype(test_array), Times >{test_array, test_array, test_array};
    std::cout << "test with nested std::arrays: \n";
    recursive_print(UL::recursive_transform<2>(test_nested_array, [](auto&& element) { return element + 1; }));

    std::cout << "std::vector input test, lambda function applied on input directly:\n";
    std::vector<int> test_vector1 = {
        1, 2, 3
    };
    auto ul_recursive_transform_output3 = UL::recursive_transform<0>(test_vector1, [](auto element)
        {
            element.push_back(4);
            element.push_back(5);
            return element;
        });
    std::cout << "UL::recursive_transform function output: \n";
    for(int i = 0; i < ul_recursive_transform_output3.size(); ++i)
    {
        std::cout << ul_recursive_transform_output3[i] << " ";
    }
    std::cout << '\n';
    
    std::vector<int> test_vector = {
        1, 2, 3
    };
    auto test_priority_queue = 
        std::priority_queue<int>(std::ranges::begin(test_vector), std::ranges::end(test_vector));
    std::cout << "test with std::priority_queue container: \n"
              << UL::recursive_transform<0>(test_priority_queue, [](auto element)
                    {
                        element.push(4);
                        element.push(5);
                        element.push(6);
                        return element;
                    }).top() << '\n';
}

int main()
{
    auto start = std::chrono::system_clock::now();
    tests();
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    std::cout << "Computation finished at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << '\n';
    return 0;
}

The output of the test code above:

non-nested input test, lambda function applied on input directly:
UL::recursive_transform function output: 
4
test with non-nested std::array container:
UL::recursive_transform function output: 
2 2 2 
test with nested std::arrays: 
Level 0:
 Level 1:
 2
 2
 2
 Level 1:
 2
 2
 2
 Level 1:
 2
 2
 2
std::vector input test, lambda function applied on input directly:
UL::recursive_transform function output: 
1 2 3 4 5 
test with std::priority_queue container: 
6
Computation finished at Mon Apr  8 06:18:06 2024
elapsed time: 0.00169829

Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

0

Your Answer

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