A recursive_minmax Template Function Implementation in C++

Question

This is a follow-up question for A Maximum Function For Various Type Arbitrary Nested Iterable Implementation in C++. Besides the function for finding maximum, I am trying to implement recursive_minmax template function which returns both minimum and maximum values.

The experimental implementation

recursive_minmax template function implementation

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!(std::ranges::input_range<T>))          //  non-range overloading
constexpr auto recursive_minmax(const T& input, Comp comp = {}, Proj proj = {})
{
    return input;
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
constexpr auto recursive_minmax(const T& numbers, Comp comp = {}, Proj proj = {})
{
    return std::make_pair(
        recursive_min(numbers, comp, proj),
        recursive_max(numbers, comp, proj)
        );
}

recursive_min template function implementation

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!std::ranges::input_range<T>)          //  non-range overloading
static inline T recursive_min(T inputNumber, Comp comp = {}, Proj proj = {})
{
    return std::invoke(proj, inputNumber);
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
static inline auto recursive_min(const T& numbers, Comp comp = {}, Proj proj = {})
{
    auto output = recursive_min(numbers.at(0), comp, proj);
    for (auto& element : numbers)
    {
        output = std::ranges::min(
            output,
            recursive_min(element, comp, proj),
            comp,
            proj);
    }
    return output;
}

recursive_max template function implementation

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!std::ranges::input_range<T>)          //  non-range overloading
static inline T recursive_max(T inputNumber, Comp comp = {}, Proj proj = {})
{
    return std::invoke(proj, inputNumber);
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
static inline auto recursive_max(const T& numbers, Comp comp = {}, Proj proj = {})
{
    auto output = recursive_max(numbers.at(0), comp, proj);
    for (auto& element : numbers)
    {
        output = std::ranges::max(
            output,
            recursive_max(element, comp, proj),
            comp,
            proj);
    }
    return output;
}

Full Testing Code

The full testing code:

//  A `recursive_minmax` Template Function Implementation in C++

#include <algorithm>
#include <array>
#include <chrono>
#include <concepts>
#include <execution>
#include <iostream>
#include <ranges>
#include <vector>

template<class T>
requires (std::ranges::input_range<T>)
constexpr auto recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << "\n";
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [level](auto&& x)
        {
            std::cout << std::string(level, ' ') << x << "\n";
            return x;
        }
    );
    return output;
}

template<class T>
requires (std::ranges::input_range<T> &&
          std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr T recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << "\n";
    std::transform(input.cbegin(), input.cend(), output.begin(),
        [level](auto&& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

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

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!std::ranges::input_range<T>)          //  non-range overloading
static inline T recursive_min(T inputNumber, Comp comp = {}, Proj proj = {})
{
    return std::invoke(proj, inputNumber);
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
static inline auto recursive_min(const T& numbers, Comp comp = {}, Proj proj = {})
{
    auto output = recursive_min(numbers.at(0), comp, proj);
    for (auto& element : numbers)
    {
        output = std::ranges::min(
            output,
            recursive_min(std::invoke(proj, element), comp, proj),
            comp,
            proj);
    }
    return output;
}

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!std::ranges::input_range<T>)          //  non-range overloading
static inline T recursive_max(T inputNumber, Comp comp = {}, Proj proj = {})
{
    return std::invoke(proj, inputNumber);
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
static inline auto recursive_max(const T& numbers, Comp comp = {}, Proj proj = {})
{
    auto output = recursive_max(numbers.at(0), comp, proj);
    for (auto& element : numbers)
    {
        output = std::ranges::max(
            output,
            recursive_max(std::invoke(proj, element), comp, proj),
            comp,
            proj);
    }
    return output;
}

template<class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
requires(!(std::ranges::input_range<T>))          //  non-range overloading
constexpr auto recursive_minmax(const T& input, Comp comp = {}, Proj proj = {})
{
    return std::invoke(proj, input);
}

template<std::ranges::input_range T, class Proj = std::identity,
         std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = std::ranges::less>
constexpr auto recursive_minmax(const T& numbers, Comp comp = {}, Proj proj = {})
{
    return std::make_pair(
        recursive_min(numbers, comp, proj),
        recursive_max(numbers, comp, proj)
        );
}

void recursive_minmax_test()
{
    std::array test_array1{3, 1, 4, 1, 5, 15, 2, 6, 5};
    std::array test_array2{3, 1, 4, -1, 5, 9, 2, 6, 5};
    std::vector<decltype(test_array1)> v = {test_array1, test_array2};
    auto [min, max] = recursive_minmax(v);
    std::cout << "Min value is " << min << "\n";
    std::cout << "Max value is " << max << "\n";
}

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

Min value is -1
Max value is 15
Computation finished at Sun Dec  3 08:04:27 2023
elapsed time: 3.4378e-05

Godbolt link is here.

All suggestions are welcome.

The summary information:

Which question it is a follow-up to?

A Maximum Function 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 recursive_minmax template function in this post.
Why a new review is being asked for?

Please review recursive_minmax template function implementation and all suggestions are welcome.

G. Sliepen · Accepted Answer · 2023-12-03 13:43:15Z

Separate concerns

You are not following the principle of separation of concerns. Whenever you write a recursive_foo() function, you should separate the concern of recursively iterating over a container from applying foo() to each element. Since the minmax operation is a reduction operation, ideally you'd want to write something like:

void recursive_minmax_test()
{
    …
    std::vector<decltype(test_array1)> v = {test_array1, test_array2};
    auto [min, max] = recursive_reduce(v, minmax);
    …
}

Where minmax() would be a generic function that takes a value and an existing min/max pair, and returns a new pair that is updated based on the given value.

The benefit should be obvious. Instead of having to write many recursive_something() functions, you only have to write one. If you want a recursive sum: recursive_reduce(v, std::plus{}), if you want a recursive minimum: recursive_reduce(v, std::min), and so on.

Allow for passing an initial value

Many standard library algorithms allow (or sometimes require) you to pass an initial value. This is very useful for several reasons:

It avoids having to treat the first element as a special case. This is also avoids the issue you have if the container you pass in is empty.
It allows chaining multiple reduction operations, by simply passing the result of the first reduction as an initial value for the second reduction.
There might be cases where the initial value of the reduction operation cannot be one of the values of the container, for example when the reduced value has a different type... like with the min/max reduction!

`recursive_minmax()` is inefficient

Your recursive_minmax() just calls recursive_min() and recursive_max(). That means it will iterate twice over the containers. But you only need one pass to get both the minimum and maximum.

Deduplicator · Accepted Answer · 2023-12-03 16:45:09Z

Bug

You iterate the range twice, once for each partial result, which is forbidden for a simple std::ranges::input_range.
You need at least a std::ranges::forward_range.

Design

This design is inefficient, not composable, nor does it take advantage of existing building blocks.

It is inefficient because it iterates the range twice, once per sub-result.
It is not composable, as fully flattening the range and applying some aggregate-function are not separated.
There is already std::views::join for flattening a view by one level, which can be chained as needed.
Thereafter the normal aggregate-functions will do the job just fine.

Summary

The only building block you might want to implement, is recursive_join to fully flatten the range. Everything else is already done and ready for use.

Stack Exchange Network

A recursive_minmax Template Function Implementation in C++

2 Answers 2

Separate concerns

Allow for passing an initial value

`recursive_minmax()` is inefficient

Bug

Design

Summary

Linked

Hot Network Questions

A recursive_minmax Template Function Implementation in C++

2 Answers 2

Separate concerns

Allow for passing an initial value

recursive_minmax() is inefficient

Bug

Design

Summary

Linked

Related

Hot Network Questions

`recursive_minmax()` is inefficient