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下編譯。兩者都返回與問題中的函數相同的值（一旦錯字被修復）。