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

Question

This is a follow-up question for A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++. I am following the suggestions proposed by G. Sliepen in the answer. The techniques including passing a range to std::ranges::transform() and using std::invoke() are performed in the updated version recursive_transform implementation. On the other hand, recursive_depth function is used here for handling incorrect unwrap levels more gracefully. For dealing with std::array type, another overload is proposed.

The experimental implementation

The experimental implementation of recursive_transform function with the unwrap level parameter is as follows.

• recursive_transform function implementation

  //  recursive_transform function implementation (the version with unwrap_level)
  template<std::size_t unwrap_level = 1, class T, class F>
  constexpr auto recursive_transform(const T& input, const F& f)
  {
      if constexpr (unwrap_level > 0)
      {
          static_assert(unwrap_level <= recursive_depth<T>(),
              "unwrap level higher than recursion depth of input");   //  trying to handle incorrect unwrap levels more gracefully
          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()
      }
  }
  
  /* This overload of recursive_transform is to support std::array.
  */
  template< std::size_t unwrap_level = 1,
            template<class T, std::size_t> class Container,
            typename F,
            typename T,
            std::size_t N >
  requires is_iterable<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::transform( std::begin(input),
                      std::end(input),
                      std::begin(output),
                      [f](auto &x){ return std::invoke(f, x); }
                    );
  
      return output;
  }
  

• recursive_depth helper function implementation

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

Full Testing Code

The full testing code:

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

#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_iterable = requires(T x)
{
    *std::begin(x);
    std::end(x);
};

//  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...>>&&
    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<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>
constexpr auto recursive_transform(const T& input, const F& f)
{
    if constexpr (unwrap_level > 0)
    {
        static_assert(unwrap_level <= recursive_depth<T>(),
            "unwrap level higher than recursion depth of input");   //  trying to handle incorrect unwrap levels more gracefully
        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()
    }
}

/* This overload of recursive_transform is to support std::array
 */
template< std::size_t unwrap_level = 1,
          template<class T, std::size_t> class Container,
          typename F,
          typename T,
          std::size_t N >
requires is_iterable<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::transform( std::begin(input),
                    std::end(input),
                    std::begin(output),
                    [f](auto &x){ return std::invoke(f, x); }
                );

    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 array container
    static constexpr std::size_t D = 3;
    auto test_array = std::array< double, D >{1, 2, 3};
    std::cout << "test with array container: \n"
              << recursive_transform<1>(test_array, [](auto&& element) { return element + 1; })[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 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

A Godbolt link is here.

All suggestions are welcome.

The summary information:

• Which question it is a follow-up to?

  A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++

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

  I am trying to implement another version recursive_transform template function for dealing with various types including std::array.

• Why a new review is being asked for?

  If there is any possible improvement, please let me know.

Answer 1

It's just getting better and better!

Use a constraint instead of static_assert()

You can trivially turn the static_assert() you have in recursive_transform() into a constraint:

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)
{
    …
}

The problem with the static_assert() is that it only triggers when your function has already recursed as much as possible. The error message that the compilers generate will then be quite large. By using a requires clause, the mistake is caught immediately at the outer call to recursive_transform(), resulting in a much shorter error message. The only drawback is that you cannot include a custom error message in this case. Here is the number of lines of error messages for each method at a given recursion depth:

Method @ depth	GCC 12	Clang 17
requires @ 1	22	19
requires @ 2	34	19
requires @ 3	30	19
static_assert @ 1	30	46
static_assert @ 2	114	68
static_assert @ 3	138	105

Use only one method to check if a type is a container

You currently have two ways to check if a type is a container: std::ranges::input_range and is_iterable. These are slightly different, and it's best to use only one of them, on the off-chance that there is a type which satisfies one but not the other, as I imagine this would cause some very hard to debug compiler error.

I think you can just write:

template<…>
requires std::ranges::input_range<Container<T, N>>
constexpr auto recursive_transform(const Container<T, N>& input, const F& f)
{
    …
}

Use std::ranges::transform() for std::arrays as well

For the overload that handles std::array, you can use std::ranges::transform() just like you did in the more generic overload.

Nested std::arrays are not handled

Your code does not handle std::arrays that contain other containers, including other std::arrays.

Ideally, there is only one overload of recursive_transform() that handles all container types. recursive_invoke_result_t<> should handle arrays. The only other issue is that there is no std::inserter<> that works on arrays. You can add some if constexpr code to handle that difference, or create a struct recursive_output_iterator<> to give you the right output iterator.

Call reserve() if possible

Some containers have a reserve() member function (like std::vector and std::deque), and it would help performance a lot if you called it.

What if the input is an rvalue?

Something we haven't looked at is if it makes sense to handle inputs that are rvalues. In case the function we are passing has a return type that is the same as its input, then you can just std::transform() the innermost containers in-place. If not, then there still is the possibility of moving the original values in the input into the function that is being applied. I don't think even std::ranges::transform() does that though.

Handling non-default-constructible containers

You are currently assuming that once you have determined the type of a container using recursive_invoke_result_t<>, that you can default-construct a new container. However, that might not be the case; for example, if an allocator is used that doesn't have a default constructor.

Most STL containers have a get_allocator() member function that will return the allocater object that was used to construct it. You can pass that to the container you want to construct. Of course, that means an increase in complexity of your code. Ideally, you would create an out-of-class function that can create an empty copy of any container, so that you can write:

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)
{
    if constexpr (unwrap_level > 0)
    {
        auto output = clone_empty_container(input);
        std::ranges::transform(
            input,
            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);
    }
}

You could even consider having it handle comparator and hash objects passed to containers like std::map and std::unordered_map, call reserve() based on the size of the input, handle container adapters like std::stack() that take a container as a parameter in the constructor, and maybe even upcoming types like std::flat_set.

Answer 2

The Inserter Fails on Most STL Structures

In particular, std::inserter assumes that the container has a push_back member function, but even within the STL, that is not the case. Some examples of its patterns:

• std::vector has .push_back and .emplace_back
• std::basic_string has only .push_back
• std:forward_list has .push_front(), .insert_after(), and .emplace_after and for this purpose, you would want to iteratively.insert_after().
• std::set has .emplace_hint, .emplace and insert.
• std::map inserts key-value pairs
• std::array is a fixed size and does not support insertion, but can be the target of std::transform without resizing. Try that with std::vector, and the function will silently stop filling the vector when it runs out of room.
• Built-in arrays, such as int a[10], have no member functions, but std::begin() and std::end() do work on them.

Define Concepts to Test for the Type of Container

For example, in an earlier solution I posted to this, I defined the following concept:

template<class T>
concept is_sized = requires(T x)
{
    x.size();
};

Which allowed me to implement the following sanity-check as an if constexpr expression:

// One last sanity check.
if constexpr( is_sized<Container<Ts...>> && is_sized<OutputC> ) {
    assert( output.size() == input.size() );
}

You Don’t Need Recursive Depth as a Template Parameter

There are only two cases: container, and an object in the domain of the transformation function.¹ These can be detected by overloads with requires clauses, or where the type is declared to match a concept. An example of both:

template<class T>
concept is_iterable = requires(T x)
{
    *std::begin(x);
    std::end(x);
};


template< template<typename...> typename Container,
          typename F,
          typename... Ts >
  requires is_iterable<Container<Ts...>>
inline auto traverse ( const Container<Ts...>& input, const F& f );


/* Base case for traversal: a single input to the transformation function.
 */
template< typename T,
          std::invocable<T> F >
constexpr auto traverse( const T& input, const F& f )
{
    return std::invoke( f, input );
}

¹ Pedantic note: G. Sliepen points out in a comment that the base case might itself be a container, but this implementation will work, so long as the transformation function is strongly-typed enough that it matches only the proper type of container. So, for example, an auto container_sum(const auto&) might fail, but the following should work:

#include <concepts>
#include <numeric>

template<typename T>
concept is_additive = requires(T x) {
  {x + x} -> std::same_as<T>;
};

template<template<typename, typename...> class C, typename T, typename... Ts>
  requires is_iterable<C<T, Ts...>> &&
           is_additive<T> &&
           std::default_initializable<T>
constexpr T container_sum(const C<T, Ts...>& input)
{
  return std::accumulate(input.begin(), input.end(), T(), std::plus<T>{});
}

Or, instead of writing out all the template trait bounds, you could just specify the template to use: container_sum<std::vector<double>>.

Arrays Need Special Handling

A function cannot return a built-in array (such as int a[10]). If you want your recursive traversal to accept these, it must convert these to std::array on output.

The size parameter of std::array also breaks template deduction, but an overload can take care of that.

You Can Use a Transforming View

In C++20, you can get around both the different, incompatible container interfaces and the problem of some containers not being default-constructible by constructing the output container from iterators generated by a std::ranges::transform_view of the input.

That is, you can construct a view of the entirety of the input container, pass it through an adapter that transforms the inputs, and pass those transformed iterators to the constructors of most containers in the STL.

There are some exceptions for which that still would not work. In particular, a std::map would require another overload to be able to traverse a key-value pair, and arrays still need special handling. This is also bleeding-edge enough that it works on GCC 12.2 and the latest development version of Clang, but not (as of 2022) either libstdc++ or libc++ using Clang 15.0.0.

// The recursive case.
template< template<typename...> typename Container,
          typename F,
          typename... Ts >
  requires is_iterable<Container<Ts...>>
inline auto traverse ( const Container<Ts...>& input, const F& f )
{
    using TransformedValueType = decltype(traverse(*std::begin(input), f));
    using OutputC = Container<TransformedValueType>;

    const auto view = std::ranges::transform_view(
      std::ranges::subrange( std::begin(input), std::end(input) ),
      [f](const auto& x)constexpr{ return traverse( x, f ); } );
    OutputC output( view.begin(), view.end() );

    // One last sanity check.
    if constexpr( is_sized<Container<Ts...>> && is_sized<OutputC> ) {
        assert( output.size() == input.size() );
    }

    return output;
}

Putting it All Together

This is a rework of an earlier answer of mine..

#include <array>
#include <cassert>
#include <concepts>   // std::invocable
#include <cstdlib>
#include <fmt/ranges.h>
#include <functional> // invoke, negate
#include <iterator>   // begin, end
#include <ranges>
#include <vector>

static constexpr std::size_t D = 3;
using row_t = std::array< double, D >;
using point_matrix = std::vector<row_t>;


template<class T>
concept is_iterable = requires(T x)
{
    *std::begin(x);
    std::end(x);
};

template<class T>
concept is_sized = requires(T x)
{
    x.size();
};


// Prototypes in case we ever want to nest in the opposite order.
template< template<typename...> typename Container,
          typename F,
          typename... Ts >
  requires is_iterable<Container<Ts...>>
inline auto traverse ( const Container<Ts...>& input, const F& f );

template< template<class T, std::size_t> class Container,
          typename F,
          typename T,
          std::size_t N >
  requires is_iterable<Container<T, N>>
constexpr auto traverse( const Container<T, N>& input, const F& f );

template< typename T,
          typename F,
          std::size_t N >
constexpr auto traverse( const T(&input)[N], const F& f );

/* Base case for traversal: a single input to the transformation function.
 */
template< typename T,
          std::invocable<T> F >
constexpr auto traverse( const T& input, const F& f )
{
    return std::invoke( f, input );
}

/* This overload was needed to support traversing std::array.
 */
template< template<class T, std::size_t> class Container,
          typename F,
          typename T,
          std::size_t N >
  requires is_iterable<Container<T, N>>
constexpr auto traverse( const Container<T, N>& input, const F& f )
{
    using TransformedValueType = decltype(traverse(*std::begin(input), f));
    Container<TransformedValueType, N> output;

    std::transform( std::begin(input),
                    std::end(input),
                    std::begin(output),
                    [f](auto &x){ return traverse( x, f ); }
                  );

    return output;
}

/* Since C++ does not allow functions to return built-in arrays, we transform
 * them into std::array objects instead.
 */
template< typename T,
          typename F,
          std::size_t N >
constexpr auto traverse( const T(&input)[N], const F& f )
{
    using TransformedValueType = decltype(traverse(*std::begin(input), f));
    std::array< TransformedValueType, N > output;

    std::transform( std::begin(input),
                    std::end(input),
                    std::begin(output),
                    [f](auto &x){ return traverse( x, f ); }
                  );

    return output;
}

/* The recursive case.
 */
template< template<typename...> typename Container,
          typename F,
          typename... Ts >
  requires is_iterable<Container<Ts...>>
inline auto traverse ( const Container<Ts...>& input, const F& f )
{
    using TransformedValueType = decltype(traverse(*std::begin(input), f));
    using OutputC = Container<TransformedValueType>;

    const auto view = std::ranges::transform_view(
      std::ranges::subrange( std::begin(input), std::end(input) ),
      [f](const auto& x)constexpr{ return traverse( x, f ); } );
    OutputC output( view.begin(), view.end() );

    // One last sanity check.
    if constexpr( is_sized<Container<Ts...>> && is_sized<OutputC> ) {
        assert( output.size() == input.size() );
    }

    return output;
}


auto negative_points(const point_matrix &points) {
  return traverse( points, std::negate<double>{} );
}

int main() {

    const point_matrix points{
        {0, 0, 4},
        {0, 5, 3},
        {1, 7, 0},
        {2, 1, 4},
        {3, 4, 5},
        {4, 2, 3},
        {4, 4, 6},
        {4, 6, 7},
        {5, 0, 2},
        {6, 4, 1},
        {6, 5, 1},
        {6, 7, 0},
        {7, 4, 3}
    };

    fmt::print("Original: {}\n", points);
    fmt::print("Negative: {}\n", negative_points(points));

    return EXIT_SUCCESS;
}