c++ - template - how does std tuple work




Implementing variadic min/max functions (3)

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)


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.


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.


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







variadic-templates