Min function accepting varying number of arguments in C++17

Question

Come across this problem once again in the book The Modern C++ Challenge.

18. Minimum function with any number of arguments

Write a function template that can take any number of arguments and returns the minimum value of them all, using operator < for comparison. Write a variant of this function template that can be parameterized with a binary comparison function to use instead of operator <.

I wonder how simple and elegant the implementation could be using c++17. The following is the parameterized version. Ideas?

#include <algorithm>
template <typename Less, typename T, typename... Ts>
constexpr const T& min(Less less, const T& a, const T& b, const Ts&... rems) {
 if constexpr (sizeof...(rems)) {
 return min(less, std::min(a, b, less), rems...);
 }
 else {
 return std::min(a, b, less);
 }
}

• user1118321: Interesting question! Is Less supposed to be a comparison object? (Like one that implement "less than" for type T?)
• Lingxi: @user1118321 Yes. std::less<void> would also fit :)
• Damon: While it's exactly the same number of operations, wouldn't pipelining make it worthwhile to divide-and-conquer rather than chain linearly? That way one would effectively run two or three cmp/cmov ops in parallel. So, basically instead of min(min(min(min(... it should expand to min(min(min(...), min(...)), min(min(), min()))
• Lingxi: @Damon I would consider it premature optimization here.

Answer 1

template <typename Less, typename T, typename... Ts>
constexpr const T& min(Less less, const T& a, const T& b, const Ts&... rems) {

This function requires a minimum of 2 elements. A minimum element will exist if the user provides a single argument variadic list. Consider handling that.

auto& min1 = min(std::less<>{}, 4, 5); // okay!
auto& min2 = min(std::less<>{}, 4); // candidate function not viable, reqs 3 args, 2 provided

---

 return min(less, std::min(a, b, less), rems...);

Your approach here uses recursion and implementations are permitted to put a recursion depth limit on constexpr calculations. Consider an iterative solution that expands the pack while calculating the minimum.

template <typename Comparator, typename First, typename... Rest>
constexpr decltype(auto) variadic_min(Comparator cmp, First const& first, Rest const&... rest) {
 const First* result = std::addressof(first);
 // cast each evaluated expr to void in case of overloaded comma operator shenanigans
 ((void)(result = std::addressof(std::min(*result, rest, cmp))), ...);
 return *result;
}

An explanation with what is going on with the fold expression:

((void)(result = std::addressof(std::min(*result, rest, cmp))), ...);
 ^ ^ ^ ^ 
 | | | expand using comma op
 | | safer than built-in, now constexpr in 17
 | evaluate the expression for each pack variable
 cast to void the entire expression to avoid overloaded comma op.

---

Just thinking beyond the standard library and reinventing the wheel. This min works fine for homogenous packs. What about heterogenous packs?

auto& min1 = min(std::less<>{}, 4, 5, -1); // min1 = -1
auto& min2 = min(std::less<>{}, 4, 5, -1.); // candidate template ignored...

One of the benefits of the conditional operator (?:) is that if both resulting expressions return lvalues of the same type, then the result will have the same type. If that type is T&, we could assign to that variable. Could we mimic that behavior with min and friends?

auto a = 4;
auto b = 5;
((b < a) ? b : a) = 42; // a = 42, b = 5
min(std::less<>{}, a, b) = 42; // cannot assign to return value, returns const-qualified type
std::min(a, b) = 42; // same with standard library.
min(std::less<>{}, 5, 6) = 42 // cannot assign, makes sense!

• Lingxi: Wow O_O Need some time to digest.
• Lingxi: Oh, the fold expression is performed on the comma operator. What a trick, but very nice!
• Qaz: @Lingxi, It's fine with constexpr
• Lingxi: @chris Oh my. I didn't expect compiler to be that smart, given the address-of operator in action here.
• Qaz: @Lingxi, Yeah, constexpr has come a long way since its introduction. C++20 will include the ability to make std::vector constexpr and will actually include a constexprified vector, unless something big changes in the next year.

Answer 2

This looks nice! Two issues I see here,

1. When compiling your template with clang, it refuses the if constexpr dispatch for every recursive instantiation with sizeof...(rems) > 1, e.g.

   error: constexpr if condition evaluates to 2, which cannot be narrowed to type bool [-Wc++11-narrowing]

   gcc seems to accept this, but the fix is quite simple, just be more explicit about it:

   if constexpr (sizeof...(rems) > 0)
   

2. Never underestimate the standard library. You are doing more work than necessary, have a look at overload #4 in the std::min signature. You can expand the parameter pack into a std::initializer_list and pass this to std::min, which simplifies your template and avoids its recursive instantiation. Additionally wrapping the arguments into a std::reference_wrapper ships around unnecessary copies.

   #include <functional>
   template <typename Less, typename... Ts>
   constexpr decltype(auto) min(Less less, const Ts&... rems) {
    return std::min({std::cref(rems)...}, less).get();
   }
   

   The return type of the std::min invocation is a std::reference_wrapper, to get around this, its get() member function is called.

   Of course, you will pay for the construction of sizeof...(rems) std::reference_wrapper instances and for the std::initializer_list.

• Lingxi: 1) I guess clang is standard-compliant here. 2) Emm... Not sure whether the return type is fine. Maybe have T deduced from second argument, and have return type explicitly specified as const T&? That is, something like template <typename Less, typename T, typename... Ts>.
• lubgr: I added .get() on the std::min return value to dereference the std::reference_wrapper.
• Qaz: You can see here how the compiler can optimize out those things you claim you pay for.
• Qaz: @lubgr, I don't see why not considering that the reference wrapper is essentially a pointer and the initializer list thus essentially contains pointers regardless of the pointed-to type. I don't see lingering wrappers in here with std::string.
• Snowhawk: @chris yea, that works as long as the user remembers to pass a comparator that invokes std::cref<T>::operator T&(). Passing a comparator defined with generalized auto params results in std::cref<T> arguments that need to be unwrapped.

Answer 3

It works well, according to my simple test program:

#include <functional>
int main()
{
 return min(std::less<int>(), 2, 0, 3);
}

I suggest that when you present code for review, you include the tests, too - I imagine that your testing is much more thorough than mine, and I'm too lazy to re-create the full suite. It also helps reviewers identify scenarios that are missing from the tests (or, conversely, scenarios that are redundant).

---

I recommend using perfect forwarding for the comparator:

constexpr const T& min(Less&& less,
// ^^

 return std::min(a, b, std::forward<Less>(less));
// ^^^^^^^^^^^^^^^^^^

There's a couple of other uses that need to be forwarded, too.

---

As lubgr mentioned, it's worth using an initializer list. If we want to avoid copying (if the inputs are large, or can't be copied), then we'll want to use a initializer-list of reference wrappers, and use std::min_element() (since the initializer-list std::min() returns a copy). That can be achieved like this:

#include <algorithm>
#include <functional>
template<typename Less, typename... T>
constexpr auto& min(Less&& less, const T& ...values)
{
 auto const compare_wrapped =
 [&less](auto const&a, auto const& b) {
 return std::forward<Less>(less)(a.get(), b.get());
 };
 auto const list = { std::ref(values)..., };
 auto const smallest =
 std::min_element(list.begin(), list.end(), compare_wrapped);
 return smallest->get();
}

int main()
{
 auto const a = 3;
 auto const b = 0;
 auto const c = 2;
 auto const& lowest = min(std::less<int>(), a, b, c);
 return &lowest != &b;
}

Or, more succinctly:

template<typename Less, typename... T>
constexpr auto& min(Less&& less, const T& ...values)
{
 return std::min({std::cref(values)...,}, std::forward<Less>(less)).get();
}

One defect in this implementation is that it will accept xvalues and happily return a (useless) reference in that case. I think it ought to be possible to distinguish that case, and forward the chosen xvalue as result, but I haven't had time to implement that.

• Lingxi: I don't think perfect forwarding is necessary here. std::min takes less by value anyway.
• Toby Speight: Fair enough - in which case, you end up with exactly lubgr's suggestion (modulo auto& vs decltye(auto) - I'm not quite sure which is correct. Possibly the decltype version, if it means we get a copy from xvalue arguments but a reference from lvalue arguments; I'd need to check).