2
\$\begingroup\$

This is a follow-up question for A Summation Function For Boost.MultiArray in C++, A recursive_minmax Template Function Implementation in C++ and A recursive_reduce_all Template Function Implementation in C++. I am trying to implement a function which can make nested container be flattened and this operation is useful for applying one dimensional algorithms.

The experimental implementation

  • 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 template function.

    template<std::ranges::forward_range T, class OutputContainer>
constexpr auto recursive_minmax(const T& numbers, OutputContainer output_container)
{
    auto flattened_numbers = impl::recursive_flatten(numbers, output_container);
    auto min = flattened_numbers.at(0);
    auto max = flattened_numbers.at(0);
    for(auto&& each_number : flattened_numbers)
    {
        if(each_number > max) { max = each_number; }
        if(each_number < min) { min = each_number; }
    }
    return std::make_pair(max, min);
}

  • recursive_reduce_all template function implementation: Another usage example of recursive_flatten template function.

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

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

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

template<class ExPo, std::ranges::input_range Container, class InitT, class OutputContainer>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_reduce_all(ExPo execution_policy, const Container& input, InitT init, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    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, class OutputContainer>
constexpr auto recursive_reduce_all(const Container& input, InitT init, BinaryOp op, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    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, class OutputContainer>
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, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    return std::reduce(execution_policy, std::ranges::cbegin(flattened_input), std::ranges::cend(flattened_input), init, op);
}

Full Testing Code

The full testing code:

//  A recursive_flatten 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>

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

template<std::ranges::forward_range T, class OutputContainer>
constexpr auto recursive_minmax(const T& numbers, OutputContainer output_container)
{
    auto flattened_numbers = impl::recursive_flatten(numbers, output_container);
    auto min = flattened_numbers.at(0);
    auto max = flattened_numbers.at(0);
    for(auto&& each_number : flattened_numbers)
    {
        if(each_number > max) { max = each_number; }
        if(each_number < min) { min = each_number; }
    }
    return std::make_pair(max, min);
}

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

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

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

template<class ExPo, std::ranges::input_range Container, class InitT, class OutputContainer>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_reduce_all(ExPo execution_policy, const Container& input, InitT init, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    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, class OutputContainer>
constexpr auto recursive_reduce_all(const Container& input, InitT init, BinaryOp op, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    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, class OutputContainer>
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, OutputContainer output_container)
{
    auto flattened_input = impl::recursive_flatten(input, output_container);
    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 [max_number, min_number] = recursive_minmax(test_vector, std::vector<int>{});
    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, std::vector<int>{}) == 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 Thu Apr 25 16:43:45 2024
elapsed time: 2.6e-05

Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Create a flattened view instead

You have created a function which copies from a nested container into a flat container. However, often you don't want to create a new container, instead you just want to iterate over a nested container as if it were flat. So I think you should create a flattened view instead.

Consider your own example of a recursive_minmax() function: it needs a lot of temporary storage, which even must be provided by the caller, but that is actually not needed. And the caller is just interested in the minimum and maximum, not in a flattened copy. What if it could be rewritten like so?

template<ranges::input_range R>
constexpr auto recursive_minmax(R&& numbers)
{
    return std::ranges::minmax(flattened_view(numbers));
}

And if you still want to create a flattened container from a recursive one, then you can just combine the flattened view with std::ranges::to():

template<class C, ranges::input_range R, class... Args>
constexpr auto flattened_copy(R&& r, Args&&... args)
{
    return std::ranges::to<C>(flattened_view(r), std::forward<Args>(args)...);
}

Or if you want to copy into an existing container, combine the flattened view with std::ranges::copy().

Have a look at the interface of std::ranges::minmax()

If you want to create a recursive minmax function, have a look at the interface of std::ranges::minmax(). Note how it takes a projection and comparison function as arguments. Also, the result often contains references to values in the input container, not copies of the values themselves. The latter is important if the value type is large or not copyable.

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