A recursive_transform_view Template Function which returns a view in C++

Question

This is a follow-up question for A recursive_transform_view Template Function Implementation. Following the suggestions mentioned in G. Sliepen's answer:

Of course, it might be interesting in itself to create a recursive_transform_view() that does return a view...

I am trying to update recursive_transform_view template function implementation which the return object is a view in this post. On the other hand, there are several updates:

To compare the different implementations in a better way, the version with unwrap_level template parameter is implemented in UL namespace and the other one without unwrap_level template parameter is implemented in NonUL namespace
Considering the constraint of using std::invoke, std::regular_invocable concept is used and recursive_invoke_result struct is also revised.

The experimental implementation

recursive_transform_view template function implementation:

template< std::ranges::input_range Container,
          std::copy_constructible F>
requires (std::ranges::view<Container>&&
          std::is_object_v<F>&&
          std::regular_invocable<F&, std::ranges::range_reference_t<
            recursive_invoke_result_t<F, Container>
            >>)
constexpr auto recursive_transform_view(const Container& input, const F& f)
{
    return std::ranges::transform_view(
        std::ranges::subrange( std::span{input} ),
        [&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
}

The revised version of clone_empty_container template function implementation:

//  clone_empty_container template function implementation
template< std::ranges::input_range Container,
          std::copy_constructible F>
requires (std::ranges::view<Container>&&
          std::is_object_v<F>&&
          std::regular_invocable<F&, std::ranges::range_reference_t<
            recursive_invoke_result_t<F, Container>
            >>)
constexpr auto clone_empty_container(const Container& input, const F& f)
{
    const auto view = recursive_transform_view(input, f);
    recursive_invoke_result_t<F, Container> output(std::ranges::begin(view), std::ranges::end(view));
    return output;
}

Full Testing Code

The full testing code:

//  A recursive_transform_view Template Function which returns a view 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 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::regular_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::regular_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::regular_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::regular_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;

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

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

    //  clone_empty_container template function implementation
    template< std::ranges::input_range Container,
              std::copy_constructible F>
    requires (std::ranges::view<Container>&&
              std::is_object_v<F>&&
              std::regular_invocable<F&, std::ranges::range_reference_t<
                recursive_invoke_result_t<F, Container>
                >>)
    constexpr auto clone_empty_container(const Container& input, const F& f)
    {
        const auto view = recursive_transform_view(input, f);
        recursive_invoke_result_t<F, Container> output(std::ranges::begin(view), std::ranges::end(view));
        return output;
    }
    
    //  recursive_transform template function implementation (the version with unwrap_level template parameter)
    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
    constexpr auto recursive_transform(const T& input, const F& f)
    {
        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); }
                );
            }
            else
            {
                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 if constexpr(std::regular_invocable<F, T>)
        {
            return std::invoke(f, input);
        }
        else
        {
            static_assert(!std::regular_invocable<F, T>, "Uninvocable?");
        }
    }

    /* 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(
                        input,
                        std::ranges::begin(output),
                        [&f](auto&& element){ return recursive_transform<unwrap_level - 1>(element, f); }
                    );

        return output;
    }
}

namespace NonUL
{
    
    template< std::ranges::input_range Container,
              std::copy_constructible F>
    requires (std::ranges::view<Container>&&
              std::is_object_v<F>&&
              std::regular_invocable<F&, std::ranges::range_reference_t<
                recursive_invoke_result_t<F, Container>
                >>)
    constexpr auto recursive_transform_view(const Container& input, const F& f)
    {
        return std::ranges::transform_view(
            std::ranges::subrange( std::span{input} ),
            [&f](const auto&& element) constexpr { return recursive_transform(element, f ); } );
    }

    /* Base case of NonUL::recursive_transform template function
    https://codereview.stackexchange.com/a/283581/231235
    */
    template<   typename T,
                std::regular_invocable<T> F>
    requires (std::copy_constructible<F>)
    constexpr auto recursive_transform( const T& input, const F& f )
    {
        return std::invoke( f, input );
    }

    /* The recursive case of NonUL::recursive_transform template function
    https://codereview.stackexchange.com/a/283581/231235
    */
    template< std::ranges::input_range Container,
              std::copy_constructible F>
    requires (std::ranges::view<Container>&&
              std::is_object_v<F>&&
              std::regular_invocable<F&, std::ranges::range_reference_t<
                recursive_invoke_result_t<F, Container>
                >>)
    constexpr auto recursive_transform(const Container& input, const F& f)
    {
        const auto view = recursive_transform_view(input, f);
        recursive_invoke_result_t<F, Container> output( std::ranges::begin(view), std::ranges::end(view) );

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

        return output;
    }

    /* The recursive case of NonUL::recursive_transform template function for std::array
    https://codereview.stackexchange.com/a/283581/231235
    */
    template< template<typename, std::size_t> typename Container,
            typename T,
            std::size_t N,
            std::copy_constructible 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
                        input,
                        std::ranges::begin(output),
                        [&f](auto&& element){ return recursive_transform(element, f); }
                    );

        // One last sanity check.
        if constexpr( is_sized<Container<T, N>> && is_sized<recursive_invoke_result_t<F, Container<T, N>>> )
        {
            assert( output.size() == input.size() );
        }

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

    auto nonul_recursive_transform_output1 = NonUL::recursive_transform(test_number, [](auto&& element) { return element + 1; });
    std::cout << "NonUL::recursive_transform function output: \n"
              << nonul_recursive_transform_output1 << "\n\n";

    assert(ul_recursive_transform_output1 == nonul_recursive_transform_output1);

    //  test with non-nested std::array container
    std::cout << "test with non-nested std::array container:\n";
    static constexpr std::size_t D = 3;
    auto test_array = std::array< double, D >{1, 2, 3};
    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';

    //  Without specifying unwrap_level, generic lambda (auto&& or auto) cannot be used.
    //  error: invalid operands to binary expression ('std::array<double, 3>' and 'int')
    //auto nonul_recursive_transform_output2 = NonUL::recursive_transform(test_array, [](auto&& element) { return element + 1; });
    auto nonul_recursive_transform_output2 = NonUL::recursive_transform(test_array, [](int&& element) { return element + 1; });
    std::cout << "NonUL::recursive_transform function output: \n";
    for(int i = 0; i < nonul_recursive_transform_output2.size(); ++i)
    {
        std::cout << nonul_recursive_transform_output2[i] << " ";
    }
    std::cout << "\n\n";

    //  TODO: 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"
    //          << UL::recursive_transform<2>(test_nested_array, [](auto&& element) { return element + 1; })[0][0] << '\n';

    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_vector2 = {
        1, 2, 3
    };
    //  [A Issue to Be Addressed] Error from Clang:
    //  error: no matching function for call to '__begin'
    /*
    auto nonul_recursive_transform_output3 = NonUL::recursive_transform(test_vector2, [](int element)
        {
            return element;
        });
    std::cout << "NonUL::recursive_transform function output: \n";
    for(int i = 0; i < nonul_recursive_transform_output3.size(); ++i)
    {
        std::cout << nonul_recursive_transform_output3[i] << " ";
    }
    */
    std::cout << "\n\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()
{
    tests();

    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
NonUL::recursive_transform function output: 
4

test with non-nested std::array container:
UL::recursive_transform function output: 
2 3 4 
NonUL::recursive_transform function output: 
2 3 4 

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

Godbolt link

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A recursive_transform_view Template Function Implementation
What changes has been made in the code since last question?

I am trying to update recursive_transform_view template function implementation which the return object is a view in this post.
Why a new review is being asked for?

Please review the revised experimental implementation of recursive_transform_view template function with using std::span and std::ranges::subrange.

I have actually been working on a variation of view traversals that support element-wise arithmetic through expression templates, like std::valarray, but better-optimized. Adding two views would give a transform-view whose transformation function adds the result of its operands’ transformation functions, for example, and you could also add or multiply views by scalars. — Davislor
– Davislor, Commented Mar 9, 2023 at 1:08
@Davislor Thank you for the comments. I am trying to implement those different version recursive_transform template function with / without recursion-depth parameter and determine the pros and cons case by case in various scenario. — JimmyHu
– JimmyHu, Commented Mar 9, 2023 at 3:03
Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. — pacmaninbw
– pacmaninbw ♦, Commented Mar 9, 2023 at 13:21
The edit showed up in The 2nd Monitor which means you edited the code after the answer was posted. I also looked at the history before I rolled it back and commented. — pacmaninbw
– pacmaninbw ♦, Commented Mar 10, 2023 at 14:25

Davislor · Accepted Answer · 2023-03-10 02:39:55Z

2

Do I Contradict Myself?

Very well, then I contradict myself. Since you asked specifically about the use of std::ranges::subrange versus std::span, and you based that on some code I had previously written, I’ll bring up something you made me realize and edit into my answer here, I will repeat one thing I said there.

You don’t actually need either one. You are already constraining the container type to be a std::ranges::input_range, a great idea that I hadn’t thought of, and which is much better than reinventing the wheel like I originally did. It also means you can pass the input argument directly as the first argument to std::ranges::transform_view, since it meets the requirements. There is no need to convert it to any other type. (You still need to compile with Clang Trunk on Godbolt. Versions up to Clang 15.0.0, GCC 12.2 or ICX 2022 do not work.)

However

Returning a non-owning view of a temporary object will result in a dangling reference!

So what you really want to do is create the transformed container, and construct a view of that.

To Prevent this Happening by Accident

If you have a function that constructs a view object of a container, best practice is to add an overload for an expiring input reference, and have that overload return std::ranges::dangling. This will help a programmer catch this logic error.

/* Normally, this would construct some kind of view object from the
 * input range.  What type is not important here.
 */
template <std::ranges::input_range T> 
constexpr auto make_view(const T&) noexcept;

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

edited Mar 10, 2023 at 2:39

answered Mar 9, 2023 at 3:44

Davislor

9,16519 silver badges39 bronze badges

\$\begingroup\$ Thank you for answering. > You still need to compile with Clang Trunk on Godbolt. Versions up to Clang 15.0.0, GCC 12.2 or ICX 2022 do not work. I am trying to figure out the reason and to address the issue... \$\endgroup\$

JimmyHu
– JimmyHu

2023-03-09 04:20:17 +00:00
Commented Mar 9, 2023 at 4:20
\$\begingroup\$ @JimmyHu Okay. See my edit; it’s important. \$\endgroup\$

Davislor
– Davislor

2023-03-09 04:24:59 +00:00
Commented Mar 9, 2023 at 4:24
1

\$\begingroup\$ @JimmyHu And I think it’s too bleeding-edge to be implemented in older versions of libstdc++ or libc++. \$\endgroup\$

Davislor
– Davislor

2023-03-09 04:28:15 +00:00
Commented Mar 9, 2023 at 4:28
\$\begingroup\$ Do you know more details about the point “ it’s too bleeding-edge to be implemented in older versions of libstdc++ or libc++”? \$\endgroup\$

JimmyHu
– JimmyHu

2023-03-09 04:34:22 +00:00
Commented Mar 9, 2023 at 4:34
1

\$\begingroup\$ @JimmyHu I haven’t attempted to debug the older versions, beyond verifying that it works in the current version. If you try compiling with -std=c++20 -stdlib=libc++ on Godbolt, you get told that it doesn’t come with <ranges> at all. If you try -std=c++20 -stdlib=libstdc++, on Clang 15.0.0, you get the error you reported with a broken std::ranges::begin on well-formed code. If you try it on the version I told you about, it works. \$\endgroup\$

Davislor
– Davislor

2023-03-09 04:38:34 +00:00
Commented Mar 9, 2023 at 4:38

| Show 2 more comments

G. Sliepen · Accepted Answer · 2023-03-09 10:22:16Z

This is not useful

Davislor mentioned correctly that:

Returning a non-owning view of a temporary object will result in a dangling reference!

So what you really want to do is create the transformed container, and construct a view of that.

But if you have a transformed container, you probably don't even need to create a view of that; most (or all?) algorithms that work on views will work directly on containers as well. So you only need recursive_transform() in that case.

What would be useful?

If you want a view, you don't want to create a new object. I see two possible ways to create a recursive, transformed view. The first is to just provide a transformed view of the innermost container(s):

std::vector<std::vector<int>> data = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
auto make_square = [](auto& value){ return value * value; };
auto squares = recursive_transform_view(data, make_square);
for (auto square: squares) {
    std::cout << square << ' ';
}

// Expected output:
// 1 4 9 16 25 36 49 64 81

Note that there is std::ranges::join_view, which flattens a range of ranges into a single view. You could create a recursive_join_view that joins recursively, and then use a regular std::ranges::transform_view to transform the result of that.

The second way would be to return nested views, so you have to traverse the view recursively yourself. Doing that manually:

for (auto row: squares) { // Each row is a view itself
    for (auto square: row) {
         std::cout << square << ' ';
    }
}

Or by using one of your existing recursive algorithms:

recursive_print(squares);

// Expected output:
// Level 0:
//  Level 1:
//  1
//  4
//  9
//  Level 1:
//  16
// …

And ideally, you want this to be composable just like std::views are:

recursive_print(data | recursive_transform_view(make_square));

I see a couple of potential use cases for it. One is to slice the transformed data structure, perhaps for a divide-and-conquer algorithm. Another is if you want to create a new class that extends the concept of a view. In a comment above, I brought up using expression templates to compose parallel operations on containers into a view. — Davislor
– Davislor, Commented Mar 9, 2023 at 19:38

Stack Exchange Network

A recursive_transform_view Template Function which returns a view in C++

2 Answers 2

Do I Contradict Myself?

However

To Prevent this Happening by Accident

This is not useful

What would be useful?

You must log in to answer this question.

Linked

Hot Network Questions

A recursive_transform_view Template Function which returns a view in C++

2 Answers 2

Do I Contradict Myself?

However

To Prevent this Happening by Accident

This is not useful

What would be useful?

You must log in to answer this question.

Linked

Related

Hot Network Questions