By Lingxi


2019-03-15 03:50:47 8 Comments

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

3 comments

@Snowhawk 2019-03-15 10:18:56

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 2019-03-15 11:52:12

Wow O_O Need some time to digest.

@Lingxi 2019-03-15 11:54:30

Oh, the fold expression is performed on the comma operator. What a trick, but very nice!

@Lingxi 2019-03-15 12:00:25

The only disadvantage I can see in your solution is that it cannot be constexpr. Or am I wrong?

@chris 2019-03-15 12:59:08

@Lingxi 2019-03-15 13:25:24

@chris Oh my. I didn't expect compiler to be that smart, given the address-of operator in action here.

@chris 2019-03-15 13:33:54

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

@Toby Speight 2019-03-15 10:42:29

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 2019-03-15 11:58:31

I don't think perfect forwarding is necessary here. std::min takes less by value anyway.

@Toby Speight 2019-03-15 12:24:28

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

@lubgr 2019-03-15 08:59:10

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 2019-03-15 09:14:34

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 2019-03-15 09:23:16

I added .get() on the std::min return value to dereference the std::reference_wrapper.

@Lingxi 2019-03-15 12:02:24

I think @Snowhawk 's solution beats both of us XD

@chris 2019-03-15 13:03:47

You can see here how the compiler can optimize out those things you claim you pay for.

@lubgr 2019-03-15 13:09:11

@chris Nice! Can we assume that the same optimization is applied for large objects?

@chris 2019-03-15 13:17:20

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

@lubgr 2019-03-15 14:38:36

@chris That makes sense. Thanks for the explanation!

@Snowhawk 2019-03-15 20:36:35

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

Related Questions

Sponsored Content

3 Answered Questions

[SOLVED] The perfect function alias

1 Answered Questions

1 Answered Questions

[SOLVED] Template function for splitting strings in C++

  • 2018-05-27 08:45:15
  • Edityouprofile
  • 188 View
  • 2 Score
  • 1 Answer
  • Tags:   c++ strings c++17

4 Answered Questions

[SOLVED] Accept either a existing stream or a filename (to be opened) in a constructor

  • 2017-08-18 13:31:16
  • Serge Ballesta
  • 872 View
  • 7 Score
  • 4 Answer
  • Tags:   c++ stream reference

1 Answered Questions

[SOLVED] Functions asking for user input, with default prompts

1 Answered Questions

[SOLVED] C++ Linked list with smart pointers

0 Answered Questions

Trinary Search Tree

  • 2015-09-23 21:11:49
  • prestokeys
  • 185 View
  • 5 Score
  • 0 Answer
  • Tags:   c++ tree search

0 Answered Questions

1 Answered Questions

[SOLVED] Most elegant variadic functor

  • 2014-01-21 16:58:23
  • yannick
  • 615 View
  • 7 Score
  • 1 Answer
  • Tags:   c++ c++11 variadic

Sponsored Content