A recursive_transform Template Function with Calling reserve for Performance Improvement

Question

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.

• Davislor: 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. =
• JimmyHu: @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.
• Davislor: 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.
• JimmyHu: @Davislor Thank you for the comments. Let me think about the suggested opinion...

Answer 1

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();
 }
 ...
}