c++ - 在循环之前选择更少或更大运算符的最佳方法

Question

我有两个包含 x,y 值的数组，y=f(x)。我想提供一个函数来找到对应于 y 的最小或最大采样值的 x 值。

在遍历数组中的值之前选择合适的比较运算符的有效方法是什么？

例如，我想做如下事情:

double FindExtremum(const double* x, const double* y,
                    const unsigned int n, const bool isMin) {
   static std::less<double>    lt;
   static std::greater<double> gt;
   std::binary_function<double,double,bool>& IsBeyond = isMin ? lt : gt;
   double xm(*x), ym(*y);
   for (unsigned int i=0; i<n; ++i, ++x, ++y) {
      if (IsBeyond()(*y,ym)) {
         ym = *y;
         xm = *x;
     }
   }
}

不幸的是，基类 std::binary_function 没有定义虚拟 operator()。

像 g++ 4.8 这样的编译器是否能够优化最直接的实现？

double FindExtremum(const double* x, const double* y,
                    const unsigned int n, const bool isMin) {
   double xm(*x), ym(*y);
   for (unsigned int i=0; i<n; ++i, ++x, ++y) {
      if ( ( isMin && (*y<ym)) ||
           (!isMin && (*y>ym)) ) {
         ym = *y;
         xm = *x;
     }
   }
}

是否有另一种方式来安排事情以便于编译器优化？是否有一个众所周知的算法来执行此操作？

如果可能的话，我宁愿避免使用模板化函数。

Answer 1

您需要将比较仿函数作为模板化函数参数传递，例如

template <typename Compare>
double FindExtremum(const double* x, const double* y,
                    const unsigned int n, Compare compare) {
   double xm(*x), ym(*y);
   for (unsigned int i=0; i<n; ++i, ++x, ++y) {
      if (compare(*y,ym)) {
         ym = *y;
         xm = *x;
     }
   }
}

然后如果你需要运行时选择，写这样的东西:

if (isMin) {
    FindExtremum(x, y, n, std::less<double>());
} else {
    FindExtremum(x, y, n, std::greater<double>());
}

在这种情况下，避免使用模板函数是不可能的。性能最好的代码将是将比较操作直接嵌入循环中的代码，避免函数调用——您可以编写一个模板或编写此函数的两个拷贝。模板化函数显然是更好的解决方案。