18
\$\begingroup\$

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 . 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);
  }
}
\$\endgroup\$
  • \$\begingroup\$ Interesting question! Is Less supposed to be a comparison object? (Like one that implement "less than" for type T?) \$\endgroup\$ – user1118321 Mar 15 at 5:20
  • 1
    \$\begingroup\$ @user1118321 Yes. std::less<void> would also fit :) \$\endgroup\$ – Lingxi Mar 15 at 5:47
  • 1
    \$\begingroup\$ 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())) \$\endgroup\$ – Damon Mar 15 at 19:05
  • 2
    \$\begingroup\$ @Damon I would consider it premature optimization here. \$\endgroup\$ – Lingxi Mar 16 at 6:16
17
\$\begingroup\$
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!
\$\endgroup\$
  • \$\begingroup\$ Wow O_O Need some time to digest. \$\endgroup\$ – Lingxi Mar 15 at 11:52
  • 3
    \$\begingroup\$ Oh, the fold expression is performed on the comma operator. What a trick, but very nice! \$\endgroup\$ – Lingxi Mar 15 at 11:54
  • 4
    \$\begingroup\$ @Lingxi, It's fine with constexpr \$\endgroup\$ – chris Mar 15 at 12:59
  • 1
    \$\begingroup\$ @chris Oh my. I didn't expect compiler to be that smart, given the address-of operator in action here. \$\endgroup\$ – Lingxi Mar 15 at 13:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – chris Mar 15 at 13:33
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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>. \$\endgroup\$ – Lingxi Mar 15 at 9:14
  • 1
    \$\begingroup\$ I added .get() on the std::min return value to dereference the std::reference_wrapper. \$\endgroup\$ – lubgr Mar 15 at 9:23
  • 2
    \$\begingroup\$ You can see here how the compiler can optimize out those things you claim you pay for. \$\endgroup\$ – chris Mar 15 at 13:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – chris Mar 15 at 13:17
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Snowhawk Mar 15 at 20:36
9
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think perfect forwarding is necessary here. std::min takes less by value anyway. \$\endgroup\$ – Lingxi Mar 15 at 11:58
  • \$\begingroup\$ 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). \$\endgroup\$ – Toby Speight Mar 15 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.