3
\$\begingroup\$

This is a follow-up question for A recursive_flatten Template Function Implementation in C++. I am trying to follow G. Sliepen's answer to create recursive_flatten_view template function for iterating over a nested container. I know that all unnecessary copy operations should be avoided, but I am not sure the way which I've done is correct. If there is any possible improvement, please let me know.

The experimental implementation

  • recursive_flatten_view template function implementation

    namespace impl {
    struct recursive_flatten_view_fn
    {
        template<std::ranges::range Container>
        requires (std::ranges::range<std::ranges::range_value_t<Container>>)
        constexpr auto operator()(const Container& input) const
        {
            recursive_unwrap_type_t<recursive_depth<Container>() - 1, Container> output_container;
            return std::views::all(recursive_flatten(input, output_container));
        }
    };

    inline constexpr recursive_flatten_view_fn recursive_flatten_view;
}

  • recursive_flatten template function implementation

    namespace impl {
    struct recursive_flatten_fn
    {
        //  recursive_flatten template function implementation
        template<std::ranges::range T, class OutputContainer>
        constexpr auto operator()(const T& input, OutputContainer output_container) const
        {
            output_container.append_range(input);
            return output_container;
        }

        template<std::ranges::range Container, class OutputContainer>
        requires (std::ranges::range<std::ranges::range_value_t<Container>>)
        constexpr auto operator()(const Container& input, OutputContainer output_container) const
        {
            for (const auto& element : input) {
                output_container = operator()(element, output_container);
            }
            return output_container;
        }
    };

    inline constexpr recursive_flatten_fn recursive_flatten;
}

  • recursive_minmax template function implementation: The usage example of recursive_flatten_view template function.

    template<std::ranges::input_range R, class Proj = std::identity,
         std::indirect_strict_weak_order<
              std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less>
requires std::indirectly_copyable_storable<std::ranges::iterator_t<R>, std::ranges::range_value_t<R>*>
constexpr auto recursive_minmax(R&& numbers, Comp comp = {}, Proj proj = {})
{
    return std::ranges::minmax(impl::recursive_flatten_view(numbers), comp, proj);
}

Full Testing Code

The full testing code:

//  A recursive_flatten_view Template Function Implementation in C++

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <concepts>
#include <deque>
#include <execution>
#include <iostream>
#include <list>
#include <numeric>      //  for std::reduce
#include <ranges>
#include <vector>

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

template<class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_unwrap_type<1, Container1<Ts1...>, Ts...>
{
    using type = std::ranges::range_value_t<Container1<Ts1...>>;
};

template<std::size_t unwrap_level, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_unwrap_type<unwrap_level, Container1<Ts1...>, Ts...>
{
    using type = typename recursive_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container1<Ts1...>>
        >::type;
};

template<std::size_t unwrap_level, typename T1, typename... Ts>
using recursive_unwrap_type_t = typename recursive_unwrap_type<unwrap_level, T1, Ts...>::type;

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

struct recursive_print_fn
{
    template<std::ranges::input_range T>
    constexpr auto operator()(const T& input, const int level = 0) const
    {
        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),
            [&](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 auto operator()(const T& input, const int level = 0) const
    {
        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),
            [&](auto&& element)
            {
                return operator()(element, level + 1);
            }
        );
        return output;
    }
};

inline constexpr recursive_print_fn recursive_print;

bool comp(int a, int b){
  return a > b;
}

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

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
    {
        auto element = n_dim_array_generator<dim - 1, times>(input);
        std::array<decltype(element), times> output;
        std::fill(std::ranges::begin(output), std::ranges::end(output), element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_deque_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_deque_generator<dim - 1>(input, times);
        std::deque<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_list_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_list_generator<dim - 1>(input, times);
        std::list<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, class T, template<class...> class Container = std::vector>
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<dim - 1, T, Container>(input, times));
    }
}

namespace impl {
    struct recursive_flatten_fn
    {
        //  recursive_flatten template function implementation
        template<std::ranges::range T, class OutputContainer>
        constexpr auto operator()(const T& input, OutputContainer output_container) const
        {
            output_container.append_range(input);
            return output_container;
        }

        template<std::ranges::range Container, class OutputContainer>
        requires (std::ranges::range<std::ranges::range_value_t<Container>>)
        constexpr auto operator()(const Container& input, OutputContainer output_container) const
        {
            for (const auto& element : input) {
                output_container = operator()(element, output_container);
            }
            return output_container;
        }
    };
    
    inline constexpr recursive_flatten_fn recursive_flatten;

    struct recursive_flatten_view_fn
    {
        template<std::ranges::range Container>
        requires (std::ranges::range<std::ranges::range_value_t<Container>>)
        constexpr auto operator()(const Container& input) const
        {
            recursive_unwrap_type_t<recursive_depth<Container>() - 1, Container> output_container;
            return std::views::all(recursive_flatten(input, output_container));
        }
    };

    inline constexpr recursive_flatten_view_fn recursive_flatten_view;
}

template<std::ranges::input_range R, class Proj = std::identity,
         std::indirect_strict_weak_order<
              std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less>
requires std::indirectly_copyable_storable<std::ranges::iterator_t<R>, std::ranges::range_value_t<R>*>
constexpr auto recursive_minmax(R&& numbers, Comp comp = {}, Proj proj = {})
{
    return std::ranges::minmax(impl::recursive_flatten_view(numbers), comp, proj);
}

template<std::ranges::input_range Container>
constexpr auto recursive_reduce_all(const Container& input)
{
    auto flattened_view = impl::recursive_flatten_view(input);
    return std::reduce(std::ranges::cbegin(flattened_view), std::ranges::cend(flattened_view));
}

template<class ExPo, std::ranges::input_range Container>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_reduce_all(ExPo execution_policy, const Container& input)
{
    auto flattened_view = impl::recursive_flatten_view(input);
    return std::reduce(execution_policy, std::ranges::cbegin(flattened_view), std::ranges::cend(flattened_view));
}

template<std::ranges::input_range Container, class InitT>
constexpr auto recursive_reduce_all(const Container& input, InitT init)
{
    auto flattened_input = impl::recursive_flatten_view(input);
    return std::reduce(std::ranges::cbegin(flattened_input), std::ranges::cend(flattened_input), init);
}

template<class ExPo, std::ranges::input_range Container, class InitT>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_reduce_all(ExPo execution_policy, const Container& input, InitT init)
{
    auto flattened_input = impl::recursive_flatten_view(input);
    return std::reduce(execution_policy, std::ranges::cbegin(flattened_input), std::ranges::cend(flattened_input), init);
}

template<std::ranges::input_range Container, class InitT, class BinaryOp>
constexpr auto recursive_reduce_all(const Container& input, InitT init, BinaryOp op)
{
    auto flattened_input = impl::recursive_flatten_view(input);
    return std::reduce(std::ranges::cbegin(flattened_input), std::ranges::cend(flattened_input), init, op);
}

template<class ExPo, std::ranges::input_range Container, class InitT, class BinaryOp>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_reduce_all(ExPo execution_policy, const Container& input, InitT init, BinaryOp op)
{
    auto flattened_input = impl::recursive_flatten_view(input);
    return std::reduce(execution_policy, std::ranges::cbegin(flattened_input), std::ranges::cend(flattened_input), init, op);
}

//  Copy from https://stackoverflow.com/a/37264642/6667035
#ifndef NDEBUG
#   define M_Assert(Expr, Msg) \
    __M_Assert(#Expr, Expr, __FILE__, __LINE__, Msg)
#else
#   define M_Assert(Expr, Msg) ;
#endif

void __M_Assert(const char* expr_str, bool expr, const char* file, int line, const char* msg)
{
    if (!expr)
    {
        std::cerr << "Assert failed:\t" << msg << "\n"
            << "Expected:\t" << expr_str << "\n"
            << "Source:\t\t" << file << ", line " << line << "\n";
        abort();
    }
}

void recursive_flatten_test()
{
    auto test_vector = n_dim_container_generator<3>(3, 3);
    test_vector.at(0).at(0).at(0) = 5;
    test_vector.at(0).at(0).at(1) = -5;

    auto [min_number, max_number] = recursive_minmax(test_vector);
    M_Assert(
        max_number == 5,
        "recursive_minmax test case failed");
    M_Assert(
        min_number == -5,
        "recursive_minmax test case failed");
    M_Assert(
        recursive_reduce_all(test_vector) == 75,
        "recursive_reduce_all test case failed");
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_flatten_test();
    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:

Computation finished at Sat Apr 27 10:25:54 2024
elapsed time: 3e-05

Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_flatten Template Function Implementation in C++

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

    I am trying to create recursive_flatten_view template function in this post.

  • Why a new review is being asked for?

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

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

Copies everywhere

I know that all unnecessary copy operations should be avoided, but I am not sure the way which I've done is correct.

You haven't avoided unnecessary copies at all. In fact, you are making copies a lot: every time recursive_flatten_fn::operator() is called, you make a copy of output_container.

It doesn't work for already flat containers

recursive_flatten_view() only works on nested containers. Of course you can wonder why someone would want to flatten something which wasn't nested to begin with, but ideally generic code also handles trivial edge cases.

It's not a view in spirit

Technically you are returning a view, but you are actually first building a whole new container. Ideally you avoid that; the view should not do anything except to allow iteration over all the elements in the nested container you pass it.

C++26 will introduce std::views::concat(). I would imagine recursive_flatten_view() to be a version of that that handles more than one level of nesting. That would be a lot of work though, your usual way to recursively traverse nested structures wouldn't work, not even using std::views::concat() itself. This brings me to:

Consider using std::generator

The problem is much more tractable using std::generator<>. Consider this:

template<typename T>
auto recursive_flatten_view(const T& value) -> std::generator<const T&> {
    co_yield value;
}

template<std::ranges::range R>
auto recursive_flatten_view(const R& range) -> std::generator<const recursive_value_type<R>&> {
    for (const auto& element: range)
        for (const auto& value: recursive_flatten_view(element))
            co_yield value;
}

A bit of more work is required to make it a niebloid and to make it work with non-const inputs. That said, GCC generates terrible code here, and none of the other major compilers support std::generator<> yet.

\$\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.