爲什麼需要std :: minmax_element？

爲什麼我們需要std::min_element和std::max_element的組合版本std::minmax_element？這僅僅是爲了節省比較，還是其他好處？爲什麼需要std :: minmax_element？

2015-12-02 Chen OT

std::min_element和std::max_element需要在返回之前遍歷整個容器。如果你使用std::min_element然後std::max_element那麼這是兩個遍歷，而如果你使用std::minmax_element那麼你只需要一個。

所以是的，這只是保存比較的「正義」，但我認爲減少檢索所需數據而不損失清晰度所需的工作量是非常值得的。

2015-12-02 10:22:35 TartanLlama

還要注意'std :: minmax_element'找到_last_最大的元素，而'std :: max_element'找到_first_最大的元素。 [來源]（http://en.cppreference.com/w/cpp/algorithm/minmax_element） –

是的。 O（n）有點貴。保存一個遍歷看起來值得。 –

@ Konrad'Zegis'很高興知道，謝謝。 – Quentin

它列出了兩點不同：

這種算法是從std::make_pair(std::min_element(), std::max_element())不同，不僅在效率，而且在這個算法找到最後最大的元素，而std::max_element發現第一最大的元素。

所提到的效率增益，是因爲std::minmax_element只需要一次處理的數據，而同時運行std::min_element和std::max_element需要兩次處理的數據。

2015-12-02 10:26:55

這不僅僅是處理一次數據，它還可以通過這種方式執行更少的比較（3n/2而不是2n）。順便說一下，在某些情況下，它比調用min_element和max_element要慢（例如，由於分支預測更差，所以在x86上是int或double隨機順序的數組）。 –

回答