# A recursive_minmax Template Function Implementation in C++

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


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.

# 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.

# 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.