3

我有一个元素向量，我可以使用一个非常昂贵的函数从每个元素中计算出一个数字。我想要映射到这些数字中最低的元素。我知道如何在 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从 调用和返回布尔值<）调用Foo::bar次数比我上面发布的代码更多。我可以预先计算这些值中的每一个，然后使用std::min_element，除了这段代码比上面的代码更复杂。

在 Going Native 中，有人（Sean Parent，感谢 Schepurin！）说现代 C++ 的一个好的风格指南是避免“原始循环”。有没有更 C++11 的惯用方式来做我想做的事？

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

4

5 回答 5

4

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

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

于 2013-11-04T16:46:55.680 回答
2

如果调用在性能Foo::bar方面真的很重要（请参阅 juancho 的分析说明），我将首先计算值的向量，bar然后在min_index那里搜索：

Foo const& get_lowest(const std::vector<Foo> &foos) {
  typedef decltype(foos[0].bar()) BarVal;

  std::vector<BarVal> barValues;
  barValues.reserve(foos.size());

  std::transform(begin(foos), end(foos), std::back_inserter(barValues), [](Foo const& f) {
    return f.bar(); 
  });

  auto barPos = std::min_element(begin(barValues), end(barValues));
  auto fooPos = begin(foos) + std::distance(begin(barValues), barPos);
  return *fooPos;
}

更新：另一种方法是使用std::accumulatelambda 来完全执行您手动编码的操作，但这将涉及内务管理并依赖 lambda 的副作用，从而使代码难以理解。

于 2013-11-04T16:43:15.870 回答
1

如果您不想要最好的迭代器Foo，您可以使用for_each：

Foo *get_lowest(const std::vector<Foo> &foos) {

    Foo *best = nullptr;
    double lowest_so_far = std::numeric_limits<double>::max();
    std::for_each(begin(foos), end(foos), [&](Foo &i){
        const double curr_val = i.bar();
        if (curr_val < lowest_so_far) {
            lowest_so_far = curr_val;
            best = &i;
        }
    });

    return best; // Return a "Foo *" to handle the empty vector case
}
于 2013-11-04T16:56:11.740 回答
1

如果我没记错的话，如果您在 STL 中找不到合适的算法，Sean Parent 还建议您编写自己的算法。每个元素只调用一次 bar 并且不必存储它的值。我想主要思想是算法和您的应用程序代码之间的分离问题。

template<class ForwardIterator, class Cost>
ForwardIterator min_cost_element(ForwardIterator first, ForwardIterator last, Cost cost)
{
    typedef decltype(cost(iterator_traits<ForwardIterator>::value_type())) value_t;

    if(first == last)
        return last;
    value_t lowest = cost(*first);
    ForwardIterator found = first;
    while(++first != last) {
        value_t val = cost(*first);
        if(val < lowest) {
            lowest = val;
            found = first;
        }
    }
    return found;
}

const Foo& get_lowest(const vector<Foo>& foos) {
    assert(!foos.empty());
    return *min_cost_element(foos.begin(), foos.end(), mem_fn(&Foo::bar));
}

给定成本函数的返回类型返回支持小于的类型，该算法是通用的并且支持空范围。

为了彻底，我首先调查了使用标准 min_element 的可能性：

const Foo& get_lowest_wierd(const vector<Foo>& foos) {
    struct predicate {
        double lowest;
        predicate(const Foo& first) : lowest(first.bar()) {}
        bool operator()(const Foo& x, const Foo&) {
            auto val = x.bar();
            if(val < lowest) {
                lowest = val;
                return true;
            }
            return false;
        }
    };

    assert(!foos.empty());
    return *min_element(foos.cbegin(), foos.cend(), predicate(foos.front()));
}

但我发现这个解决方案很笨拙：

  1. 它过于依赖对标准定义的解释“返回范围 [first, last) 中的第一个迭代器 i，使得对于范围 [first, last) 中的每个迭代器 j，条件成立：comp(*j, *i) == false"，即“候选”最小值始终在右侧
  2. 由于前一点，谓词必须在本地定义：它在此上下文之外不起作用。
  3. 它不能在 VS2013 的调试模式下工作，因为检查谓词以确保比较定义严格的弱排序（尽管我不确定这里是否需要它）但它在发布时工作正常。

两个代码示例都在 VS2013 下编译。两者都返回与问题中的函数相同的值（一旦错字被修复）。

于 2013-11-05T06:53:39.803 回答
0

不是真正的答案，而是解决您的问题：为什么不在对象内缓存 bar 的结果？又名

double bar()
{
  if (bar_calculated)
      return bar_val;
   //...
}

顺便说一句，关于避免原始循环：
当您需要与使用 STL algs 获得的等效代码时，您需要避免它们。如果您有特殊要求并且无法自定义 alg 以满足您的需求，请使用原始循环。:)
例如，我认为你可以有状态比较器来记住当前的 arg_min 地址，以便它可以缓存它的值......但这只是为了使用 alg 而弯曲设计。

于 2013-11-04T18:46:07.553 回答