C++中的高效Argmin 11

Question

我有一个元素向量，我可以使用非常昂贵的函数从每个元素计算单个数字。我想要映射到这些数字中最小的元素。我知道如何做到这一点在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，但该代码比上面的代码更复杂。

在融入本土，有人（肖恩父母，感谢SChepurin！）说，一个良好的风格指南现代C++是为了避免“原始循环”。有没有更多的C++ 11习惯做我想做的事情？

*我刚才输入到窗口此，我甚至没有尝试编译它。

Answer 1

如果调用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::accumulate有拉姆达做你硬编码的到底是什么，但是这将涉及家政，依靠拉姆达的侧effecets，使得代码更少理解。

Answer 2

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

通常，STL算法假定的位置处获得的值是相当便宜的。同样，迭代器操作（advance，test，dereference）应该很快。在这个例子中，假定比较昂贵的操作是比较。当使用匹配这些使用caes，STL算法可能确实是一个更好的选择，例如，因为他们可以做各种疯狂的事情（循环展开，内存操作等）。我当然有香草的声明同意使用什么做的，而不是如何做到这一点，但对于你的情况，我不认为STL算法能有效地做到这一点。

Answer 3

如果你不想上最好的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 
} 

Answer 4

不是一个真正的答案，但解决问题的方法：你为什么不棒的缓存结果内目的？ 又名

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

BTW就避免了原料循环：
你需要避免它们，当你需要类似代码，你会使用STL的ALG得到。如果你有特殊的需求，你不能定制alg来满足你的需求，使用原始循环。:)
例如这里我认为你可以有状态比较器，记住当前的arg_min地址，以便它可以缓存它的值...但是这只是弯曲设计只是为了使用alg。

Answer 5

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

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. 它依赖太多了自定义的解释标准“返回 第一个迭代器i在范围[first，last）中，使得对于在[first，last）范围内的每个 迭代器j，条件成立：comp（* j， * i）== false”，即“候选人”迷你妈妈总是在右边
2. 由于前面的观点，谓词必须定义为localy：它不能在此上下文之外工作。
3. 由于对谓词进行了检查以确保比较定义了strick弱排序（尽管我不确定这是否是必需的），但它在VS2013的调试模式下不起作用，但它在发布时可以正常工作。

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