1
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function with Unwrap Level for std::array Implementation in C++. Following the suggestion mentioned in G. Sliepen's answer, the function recursive_transform implementation is updated. The constraint using requires clause is performed instead of using static_assert(). The is_iterable concept is replaced by std::ranges::input_range in STL. Moreover, std::ranges::transform() is used in the overload that handles std::array. For the part of performance acceleration, another overload is added for those containers with reserve() member function. To separate the version for dealing with containers with / without reserve member function, additional concept is_reservable is added in this post.

The experimental implementation

The experimental implementations of recursive_transform function and the used is_reservable concept are as follows.

  • recursive_transform function implementation:

    //  recursive_transform implementation (the version with unwrap_level)
    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
                !is_reservable<T>)                          //
    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(
                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, reserve space)
    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
                is_reservable<T>) 
    constexpr auto recursive_transform(const T& input, const F& f)
    {
        if constexpr (unwrap_level > 0)
        {
            recursive_invoke_result_t<F, T> output{};
            output.reserve(input.size());                   //  Call reserve() if possible, https://codereview.stackexchange.com/a/283563/231235
            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()
        }
    }
    
    /* 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)
    {
        Container<recursive_invoke_result_t<F, T>, N> output;
    
        std::ranges::transform(                     //  Use std::ranges::transform() for std::arrays as well
                        input,
                        std::begin(output),
                        [&f](auto&& element){ return recursive_transform<unwrap_level - 1>(element, f); }
                    );
    
        return output;
    }
    
  • is_reservable concept implementation:

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

Full Testing Code

The full testing code:

//  A recursive_transform Template Function with Calling reserve for Performance Improvement

#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>

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

//  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<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 F, template<typename...> typename Container, typename... Ts>
requires (
    !std::invocable<F, Container<Ts...>>&&          //  F cannot be invoked to Container<Ts...> directly
    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
                >;
};

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

template<template<typename, std::size_t> typename Container,
    typename T,
    std::size_t N,
    typename F>
requires (
    !std::invocable<F, Container<T, N>>&&          //  F cannot be invoked to Container<Ts...> directly
    requires { typename recursive_invoke_result<F, std::ranges::range_value_t<Container<T, N>>>::type; })
struct recursive_invoke_result<F, Container<T, N>>
{
    using type = Container<
                    typename recursive_invoke_result<
                        F,
                        std::ranges::range_value_t<Container<T, N>>
                    >::type
                , N>;
};

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

//  recursive_transform implementation (the version with unwrap_level)
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
            !is_reservable<T>)                          //
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(
            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, reserve space)
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
            is_reservable<T>) 
constexpr auto recursive_transform(const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        recursive_invoke_result_t<F, T> output{};
        output.reserve(input.size());                   //  Call reserve() if possible, https://codereview.stackexchange.com/a/283563/231235
        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()
    }
}

/* 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)
{
    Container<recursive_invoke_result_t<F, T>, N> output;

    std::ranges::transform(                     //  Use std::ranges::transform() for std::arrays as well
                    input,
                    std::begin(output),
                    [&f](auto&& element){ return recursive_transform<unwrap_level - 1>(element, f); }
                );

    return output;
}

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

    //  test with non-nested std::array container
    static constexpr std::size_t D = 3;
    auto test_array = std::array< double, D >{1, 2, 3};
    std::cout << "test with non-nested std::array container: \n"
              << recursive_transform<1>(test_array, [](auto&& element) { return element + 1; })[0] << '\n';

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

    //  nested input test, lambda function applied on input directly
    std::vector<int> test_vector = {
        1, 2, 3
    };
    std::cout << recursive_transform<0>(test_vector, [](auto element)
        {
            element.push_back(4);
            element.push_back(5);
            return element;
        }).size() << '\n';

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

    std::cout << "std::vector<int> -> std::vector<std::string>: " +
        recursive_transform_result.at(0) << '\n';                                  //  recursive_transform_result.at(0) is a std::string
    
    //  std::vector<string> -> std::vector<int>
    std::cout << "std::vector<string> -> std::vector<int>: " 
        << recursive_transform<1>(
            recursive_transform_result,
            [](std::string x) { return std::atoi(x.c_str()); }).at(0) + 1 << '\n'; //  std::string element to int

    //  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<2>(
        test_vector2,
        [](int x)->std::string { return std::to_string(x); }
    );                                                                                  //  For testing

    std::cout << "string: " + recursive_transform_result2.at(0).at(0) << '\n';     // 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<1>(
        test_deque,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing

    std::cout << "string: " + recursive_transform_result3.at(0) << '\n';

    //  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<2>(
        test_deque2,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing

    std::cout << "string: " + recursive_transform_result4.at(0).at(0) << '\n';

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


    //  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_result6 = recursive_transform<2>(
        test_list2,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result6.front().front() << '\n';
    return 0;
}

The output of the test code above:

non-nested input test, lambda function applied on input directly: 
4
test with non-nested std::array container: 
2
5
std::vector<int> -> std::vector<std::string>: 1
std::vector<string> -> std::vector<int>: 2
string: 1
string: 1
string: 1
string: 1
string: 1

Godbolt link

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_transform Template Function with Unwrap Level for std::array Implementation in C++

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

    • The constraint using requires clause is performed instead of using static_assert().

    • New concept is_reservable is proposed and another overload calling reserve() member function is added.

  • Why a new review is being asked for?

    Please review the updated version recursive_transform template function. I am not sure there is any other better way to deal with containers with / without reserve member function for performance improvement. Any other further suggestion is welcome, certainly.

\$\endgroup\$
4
  • \$\begingroup\$ At this point, you’ve seen my previous answers and implementations (which remove the recursive-depth parameter, add support for additional types of containers, etc.) You’ve basically seen my suggestions. = \$\endgroup\$
    – Davislor
    Mar 3, 2023 at 7:08
  • 1
    \$\begingroup\$ @Davislor Thank you for the comments. I want to reserve the capability to deal with the case auto container_sum(const auto&) and there are some related discussions about this issue in Quuxplusone's comment. If there is any misunderstanding, please let me know. \$\endgroup\$
    – JimmyHu
    Mar 3, 2023 at 7:44
  • \$\begingroup\$ U post a solution for container_sum here, although it’s not so simple and would add std::valarray objects together rather than taking their sums. \$\endgroup\$
    – Davislor
    Mar 3, 2023 at 9:01
  • \$\begingroup\$ @Davislor Thank you for the comments. Let me think about the suggested opinion... \$\endgroup\$
    – JimmyHu
    Mar 3, 2023 at 9:37

1 Answer 1

1
\$\begingroup\$

Avoid code duplication

You have two versions of recursive_transform() that look very similar, and only differ in whether reserve() is called. I would avoid the code duplication here by making use of if constexpr:

template<std::size_t unwrap_level = 1, class T, class F>
requires (unwrap_level <= recursive_depth<T>()) 
constexpr auto recursive_transform(const T& input, const F& f)
{
    …
    recursive_invoke_result_t<F, T> output{};
    if constexpr (is_reservable<decltype(output)>) {
        output.reserve();
    }
    …
}
\$\endgroup\$

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.