实现可变参数最小/最大功能

Question

我正在实现可变的最小/最大函数.目标是利用编译时已知的参数数量并执行展开的评估(避免运行时循环).代码的当前状态如下(呈现min - max类似)

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

现在这可行,但我有一些问题/问题:

1. 该非可变参数过载有由价值接受它的参数.如果我尝试传递其他类型的ref,我会得到以下结果

   • 通用引用&&- >编译错误
   • const引用const&- >好的
   • 普通参考&- >编译错误

   现在我知道功能模板与模板混合在一起但是有没有具体的技术诀窍呢？我应该选择什么类型的参数？

2. 参数包的扩展不会足够吗？我是否真的需要将我的参数转发给递归调用？

3. 当在struct中包装并作为静态成员函数公开时,这个函数是否更好地实现.部分专业的能力会给我带来什么吗？

4. 功能版本是否有更强大/更有效的实现/设计？(特别是我想知道一个constexpr版本是否与模板元编程的效率相匹配)

Answer 1

实例

这确实可以完美地转发参数.它依赖于RVO作为返回值,因为它返回值类型而不管输入类型,因为common_type这样做.

我实现了common_type演绎,允许传入混合类型,以及"预期"结果类型输出.

我们支持min of 1元素,因为它使代码更加流畅.

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

现在,虽然以上是一个完全可以接受的解决方案,但它并不理想.

这个表达式((a<b)?a:b) = 7是合法的C++,但vmin( a, b ) = 7不是,因为std::common_type decays是盲目的参数(由我认为过度反应导致它在旧的实现中输入两个值类型时返回rvalue引用std::common_type).

简单地使用decltype( true?a:b )是诱人的,但它都导致rvalue引用问题,并且不支持特化common_type(作为示例std::chrono).所以我们都想使用common_type而不想使用它.

其次,编写一个min不支持无关指针的函数并且不让用户更改比较函数似乎是错误的.

以下是上述更复杂的版本. 实例:

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

上述实现的缺点是大多数类都不支持operator=(T const&)&&=delete- 即,它们不会阻止rvalues被分配,如果其中一种类型min没有,则会导致意外.基本类型.

这是一个旁注:开始删除你的右值参考operator=人.

Answer 2

我很欣赏Yakk提出的返回类型的想法,所以我不需要,但它变得更简单:

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

返回类型推导非常棒(可能需要C++ 14).

Answer 3

C++17 中有一个解决方案，它击败了迄今为止提出的所有答案：

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

请注意：

• 仅需要一项功能
• 你不能使用少于两个参数来调用它
• 它编译最佳

使用gcc10.2 和-O3，接受的答案编译为：

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

无论出于何种原因，都有更多的指令和条件跳转。我的解决方案仅编译为：

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

std::min这与仅递归调用三个参数相同。（参见https://godbolt.org/z/snavK5）

Answer 4

4) 这是实现constexpr此函数版本的一种可能方法：

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

请参阅实例。

编辑：正如@Yakk在评论中指出的那样，代码std::forward<Arg1>(arg1) < std::forward<Arg2>(arg2) ? std::forward<Arg1>(arg1) : std::forward<Arg2>(arg2)在某些情况下可能会导致问题。arg1 < arg2 ? std::forward<Arg1>(arg1) : std::forward<Arg2>(arg2)在这种情况下是更合适的变体。