CODEWITHSUNDEEP
c++templatesc++11variadic-templates
Nikos Athanasiou
Nikos Athanasiou

Reputation: 31519

Implementing variadic min / max functions

I'm implementing variadic min/max functions. A goal is to take advantage of the compile time known number of arguments and perform an unrolled evaluation (avoid run-time loops). The current state of the code is as follows (presenting min - max is similar)

#include <iostream>  

using namespace std;

template<typename T>
T vmin(T val1, T val2)
{
    return val1 < val2 ? val1 : val2;
}

template<typename T, typename... Ts>
T vmin(T val1, T val2, Ts&&... vs)
{
    return val1 < val2 ?
        vmin(val1, std::forward<Ts>(vs)...) : 
            vmin(val2, std::forward<Ts>(vs)...);
}

int main()
{
    cout << vmin(3, 2, 1, 2, 5) << endl;    
    cout << vmin(3., 1.2, 1.3, 2., 5.2) << endl;
    return 0;
}

Now this works, but I have some questions / problems :

  1. The non variadic overload has to accept its arguments by value. If I try passing other types of ref I have the following results

    • universal references && -> compilation error
    • const references const& -> OK
    • plain references & -> compilation error

    Now I know that function templates mix weirdly with templates but is there any specific know-how for the mix up at hand ? What type of arguments should I opt for?

  2. Wouldn't the expansion of the parameter pack by sufficient ? Do I really need to forward my arguments to the recursive call ?

  3. Is this functionallity better implemented when wrapped inside a struct and exposed as a static member function. Would the ability to partial specialize buy me anything ?

  4. Is there a more robust/efficient implementation/design for the function version ? (particullarly I'm wondering whether a constexpr version would be a match for the efficiency of template metaprogramming)

Upvotes: 41

Views: 11267

Answers (10)

Jan Schultke
Jan Schultke

Reputation: 39568

There is a solution in C++17 which beats all answers proposed so far:

template <typename Head0, typename Head1, typename... Tail>
constexpr auto min(const Head0 &head0, const Head1 &head1, const Tail &... tail)
{
    if constexpr (sizeof...(tail) == 0) {
        return head0 < head1 ? head0 : head1;
    }
    else {
        return min(min(head0, head1), tail...);
    }
}

Notice how this:

  • requires only one function
  • you can't call this with fewer than two parameters
  • it compiles optimally

Using gcc 10.2 with -O3, the accepted answer compiles to:

min(int, int, int):
        cmp     esi, edi
        jge     .L2
        cmp     esi, edx
        mov     eax, edx
        cmovle  eax, esi
        ret
.L2:
        cmp     edi, edx
        mov     eax, edx
        cmovle  eax, edi
        ret

There are more instructions and a conditional jump for whatever reason. My solution compiles only to:

min(int, int, int):
        cmp     esi, edx
        mov     eax, edi
        cmovg   esi, edx
        cmp     esi, edi
        cmovle  eax, esi
        ret

This is identical to just calling std::min recursively for three parameters. (see https://godbolt.org/z/snavK5)

Upvotes: 15

Lorah Attkins
Lorah Attkins

Reputation: 5856

Another approach is to leverage an auto&& return type and perfectly forward your results:

template <class T, class... Ts>
auto&& Min(T&& arg1, Ts&&... args)
{
    if constexpr (sizeof...(Ts))
    {
        auto &&rmin = Min(std::forward<Ts>(args)...);
        return arg1 < rmin ? std::forward<T>(arg1) : rmin;
    }
    else
    {
        return std::forward<T>(arg1);
    }
}

Demo

Upvotes: 0

Muhammet Dabak
Muhammet Dabak

Reputation: 66

With C++11, this solution should be fine ( with using std::max / std::min) :

#include <algorithm>

template<typename T>
T Max(T arg)
{
return arg;
}
template<typename T, typename Ts>
T Max(T arg, Ts... args)
{
return std::max(arg, Max(args...));
}

The performance is not so different from above solutions.

(It is checked via Microsoft VS 2019 / no optimization, using chrono library)

  • Calling the function with single element is valid.

Upvotes: 0

formigoni
formigoni

Reputation: 43

Solution with a lambda and set

auto max = [](auto&& e1, auto&& e2, auto&&... args)
{
    return *std::set<typename std::decay_t<decltype(e1)>>{e1,e2,args...}.rbegin();
};

Upvotes: 1

Amir Kirsh
Amir Kirsh

Reputation: 13752

C++20 version

The solution presented by @Yakk-AdamNevraumont is good, it covers very well aspects of lvalue and rvalue, not allowing to return a reference to a temporary, and yet returning lvalue reference if you can.

But the solution can now be modernized for C++20 and become much more concise and elegant:

template<typename... Ts>
struct common_return {
    using type = std::common_reference_t<Ts...>;
};

template<typename T, typename... Ts>
    requires std::is_lvalue_reference_v<T> &&
            (std::is_lvalue_reference_v<Ts> && ...)
            && ( std::same_as<T, Ts> && ... )
struct common_return<T, Ts...> {
    using type = std::common_reference_t<T, Ts...>&;
};

template<typename... Ts>
using common_return_t = typename common_return<Ts...>::type;

namespace my_min {
    template<typename T>
    T min(T&& t) {
        return std::forward<T>(t);
    }

    template<typename T1, typename T2, typename... Ts>
    common_return_t<T1, T2, Ts...> min(T1&& t1, T2&& t2, Ts&&... ts) {
        if(t2 > t1) {
            return min(std::forward<T1>(t1), std::forward<Ts>(ts)...);
        }
        return min(std::forward<T2>(t2), std::forward<Ts>(ts)...);
    }
}

Upvotes: 2

Sergey Kolesnik
Sergey Kolesnik

Reputation: 3630

With c++17and not using recursion:

template <typename T, T ... vals>
constexpr T get_max(std::integer_sequence<T, vals...> = std::integer_sequence<T, vals...>())
{
     T arr[sizeof...(vals)]{vals...},
         max = 0;
     for (size_t i = 0; i != sizeof...(vals); ++i)
            max = arr[i] > max ? max = arr[i] : max;
     return max;
}

Function can be called by providing either template parameters or integer sequence as argument

get_max<int, 4, 8, 15, 16, 23, -42>();

using seq = std::integer_sequence<int, ...>;
get_max(seq());

Upvotes: 3

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

live example

This does perfect forwarding on arguments. It relies on RVO for return values, as it returns a value type regardless of the input types, because common_type does that.

I implemented common_type deduction, allowing mixed types to be passed in, and the "expected" result type output.

We support the min of 1 element, because it makes the code slicker.

#include <utility>
#include <type_traits>

template<typename T>
T vmin(T&&t)
{
  return std::forward<T>(t);
}

template<typename T0, typename T1, typename... Ts>
typename std::common_type<
  T0, T1, Ts...
>::type vmin(T0&& val1, T1&& val2, Ts&&... vs)
{
  if (val2 < val1)
    return vmin(val2, std::forward<Ts>(vs)...);
  else
    return vmin(val1, std::forward<Ts>(vs)...);
}


int main()
{
  std::cout << vmin(3, 2, 0.9, 2, 5) << std::endl;

  std::cout << vmin(3., 1.2, 1.3, 2., 5.2) << std::endl;

  return 0;
}

Now, while the above is a perfectly acceptable solution, it isn't ideal.

The expression ((a<b)?a:b) = 7 is legal C++, but vmin( a, b ) = 7 is not, because std::common_type decays is arguments blindly (caused by what I consider an over-reaction to it returning rvalue references when fed two value-types in an older implementation of std::common_type).

Simply using decltype( true?a:b ) is tempting, but it both results in the rvalue reference problem, and does not support common_type specializations (as an example, std::chrono). So we both want to use common_type and do not want to use it.

Secondly, writing a min function that doesn't support unrelated pointers and does not let the user change the comparison function seems wrong.

So what follows is a more complex version of the above. live example:

#include <iostream>
#include <utility>
#include <type_traits>

namespace my_min {

  // a common_type that when fed lvalue references all of the same type, returns an lvalue reference all of the same type
  // however, it is smart enough to also understand common_type specializations.  This works around a quirk
  // in the standard, where (true?x:y) is an lvalue reference, while common_type< X, Y >::type is not.
  template<typename... Ts>
  struct my_common_type;

  template<typename T>
  struct my_common_type<T>{typedef T type;};

  template<typename T0, typename T1, typename... Ts>
  struct my_common_type<T0, T1, Ts...> {
    typedef typename std::common_type<T0, T1>::type std_type;
    // if the types are the same, don't change them, unlike what common_type does:
    typedef typename std::conditional< std::is_same< T0, T1 >::value,
      T0,
    std_type >::type working_type;
    // Careful!  We do NOT want to return an rvalue reference.  Just return T:
    typedef typename std::conditional<
      std::is_rvalue_reference< working_type >::value,
      typename std::decay< working_type >::type,
      working_type
    >::type common_type_for_first_two;
    // TODO: what about Base& and Derived&?  Returning a Base& might be the right thing to do.
    // on the other hand, that encourages silent slicing.  So maybe not.
    typedef typename my_common_type< common_type_for_first_two, Ts... >::type type;
  };
  template<typename... Ts>
  using my_common_type_t = typename my_common_type<Ts...>::type;
  // not that this returns a value type if t is an rvalue:
  template<typename Picker, typename T>
  T pick(Picker&& /*unused*/, T&&t)
  {
    return std::forward<T>(t);
  }
  // slight optimization would be to make Picker be forward-called at the actual 2-arg case, but I don't care:
  template<typename Picker, typename T0, typename T1, typename... Ts>
  my_common_type_t< T0, T1, Ts...> pick(Picker&& picker, T0&& val1, T1&& val2, Ts&&... vs)
  {
    // if picker doesn't prefer 2 over 1, use 1 -- stability!
    if (picker(val2, val1))
      return pick(std::forward<Picker>(pick), val2, std::forward<Ts>(vs)...);
    else
      return pick(std::forward<Picker>(pick), val1, std::forward<Ts>(vs)...);
  }

  // possibly replace with less<void> in C++1y?
  struct lesser {
    template<typename LHS, typename RHS>
    bool operator()( LHS&& lhs, RHS&& rhs ) const {
      return std::less< typename std::decay<my_common_type_t<LHS, RHS>>::type >()(
          std::forward<LHS>(lhs), std::forward<RHS>(rhs)
      );
    }
  };
  // simply forward to the picked_min function with a smart less than functor
  // note that we support unrelated pointers!
  template<typename... Ts>
  auto min( Ts&&... ts )->decltype( pick( lesser(), std::declval<Ts>()... ) )
  {
    return pick( lesser(), std::forward<Ts>(ts)... );
  }
}

int main()
{
  int x = 7;
  int y = 3;
  int z = -1;
  my_min::min(x, y, z) = 2;
  std::cout << x << "," << y << "," << z << "\n";
  std::cout << my_min::min(3, 2, 0.9, 2, 5) << std::endl;
  std::cout << my_min::min(3., 1.2, 1.3, 2., 5.2) << std::endl;
  return 0;
}

The downside to the above implementation is that most classes do not support operator=(T const&)&&=delete -- ie, they do not block rvalues from being assigned to, which can lead to surprises if one of the types in the min does not . Fundamental types do.

Which is a side note: start deleting your rvalue reference operator=s people.

Upvotes: 31

Ben Voigt
Ben Voigt

Reputation: 283634

I appreciate the thought Yakk put into return types so I wouldn't have to, but it gets a lot simpler:

template<typename T>
T&& vmin(T&& val)
{
    return std::forward<T>(val);
}

template<typename T0, typename T1, typename... Ts>
auto vmin(T0&& val1, T1&& val2, Ts&&... vs)
{
    return (val1 < val2) ?
      vmin(val1, std::forward<Ts>(vs)...) :
      vmin(val2, std::forward<Ts>(vs)...);
}

Return type deduction is pretty awesome (may require C++14).

Upvotes: 18

Constructor
Constructor

Reputation: 7473

4) Here is one possible way to implement a constexpr version of this function:

#include <iostream>
#include <type_traits>

template <typename Arg1, typename Arg2>
constexpr typename std::common_type<Arg1, Arg2>::type vmin(Arg1&& arg1, Arg2&& arg2)
{
    return arg1 < arg2 ? std::forward<Arg1>(arg1) : std::forward<Arg2>(arg2);
}

template <typename Arg, typename... Args>
constexpr typename std::common_type<Arg, Args...>::type vmin(Arg&& arg, Args&&... args)
{
    return vmin(std::forward<Arg>(arg), vmin(std::forward<Args>(args)...));
}

int main()
{
    std::cout << vmin(3, 2, 1, 2, 5) << std::endl;
    std::cout << vmin(3., 1.2, 1.3, 2., 5.2) << std::endl;
}

See live example.

Edit: As @Yakk noted in comments the code std::forward<Arg1>(arg1) < std::forward<Arg2>(arg2) ? std::forward<Arg1>(arg1) : std::forward<Arg2>(arg2) may cause problems in some situations. arg1 < arg2 ? std::forward<Arg1>(arg1) : std::forward<Arg2>(arg2) is more appropriate variant in this case.

Upvotes: 6

vsoftco
vsoftco

Reputation: 56547

You cannot bind a temporary to a non-const reference, that is why you probably get the compilation error. That is, in vmin(3, 2, 1, 2, 5), the parameters are temporaries. It will work if you declare them as for example int first=3,second=2 and so on, then invoke vmin(first,second...)

Upvotes: 3

Related Questions