c++ - C++11 中的高效 Argmin

Question

我有一个元素 vector ，我可以使用一个非常昂贵的函数从每个元素中计算出一个数字。我想要映射到这些数字中最低的元素。我知道如何在 C++03 中执行此操作:*

Foo get_lowest(const std::vector<Foo> &foos) {
  double lowest_so_far = std::numeric_limits<double>::max();
  std::vector<Foo>::iterator best;
  for(std::vector<Foo>::iterator i = foos.begin(); i != foos.end(); i++) {
    const double curr_val = i->bar();
     if( curr_val < lowest_so_far ) { 
       best = i;
       lowest_so_far = curr_val
     }
  }

  return *i;
}

我也可以使用 std::min_element 来做到这一点, 除了天真的做事方式(调用 Foo::bar 并从 < 返回一个 bool 值)调用 Foo::bar比我上面发布的代码更多次。我可以预先计算这些值中的每一个，然后使用 std::min_element ，除了这段代码比上面的代码更复杂。

在 Going Native 中，有人(Sean Parent，感谢 SChepurin!)说现代 C++ 的良好风格指南是避免“原始循环”。是否有更多 C++11 惯用的方式来做我想做的事？

* 我只是在窗口中输入这个，我什至没有尝试编译它。

Answer 1

这是一个有趣的问题:不立即支持基于某个位置的昂贵操作来确定属性。使用 std::min_element() 的版本在每次调用二元谓词时进行计算并不是正确的方法:您不想重新计算当前的值已知的最小值。可能需要编写自定义循环。

一般来说，STL 算法假定获取某个位置的值是相当便宜的。同样，迭代器操作(高级、测试、取消引用)应该很快。在这个例子中假设比较昂贵的操作。当使用匹配这些使用场景时，STL 算法可能确实是更好的选择，例如，因为它们可以做各种疯狂的事情(循环展开、内存操作等)。我当然同意 Herb 的声明，即使用什么来做而不是如何来做，但对于你的情况，我认为 STL 算法不能有效地做到这一点。 p>