C++中max_element和minmax_element的行爲差異STL

在C++ max_element中，如果有多個最大元素，則返回第一個這樣的元素。而minmax_element（C++ 11起）返回最後一個最大元素。C++中max_element和minmax_element的行爲差異STL

這種行爲的標準是否存在原因？

從cplusplus.com

如果多於一個當量的元件具有最大的值，所述第二迭代器指向最後一個這樣的元件。

使用第一版本的運算符<或第二版本的comp進行比較;如果沒有其他元素的比較小於一個元素，則元素是最大的。如果多個元素滿足這個條件，則迭代器返回指向這些元素的第一個元素的點。他們的圖書館的

來源

2017-03-09 user3336523

[根據CPPReference，這是預期的行爲。]（http://en.cppreference.com/w/cpp/algorithm/minmax_element）爲什麼這是預期的，我必須去游泳標準。 – user4581301

** [alg.min.max] **（修訂版n4594中的註釋30）規定這是法律。沒有理性上市。 – user4581301

更有趣的是，'minmax_element'對最小元素應用相反的策略（第一個返回）。 –

Boost的文檔包括rationale

定義問題的表面，當一個人試圖設計一個minmax_element，使用（Cormen，Leiserson，維斯特提出的過程：「算法導論」， 9.1節）。如果[first，last）有n個元素，但是如果有人試圖編寫名爲first_min_first_max_element（）的函數，它將返回std :: min_element和std :: max_element，應該只用3n/2比較就可以推導出一個算法。對，簡單的實現不起作用。這個問題相當微妙，大約是相同的元素：我必須考慮一段時間才能找到一種方法，每對執行三次比較並返回第一個最小元素和第一個最大元素。很長一段時間，似乎這樣做的任何嘗試都會在最糟糕的情況下消耗四對比。這個實現達到三個。

改變max_element的含義是不可能的（或者甚至是不可取的），但是提供稱爲minmax_element的函數仍然是有益的，該函數返回一對min_element和max_element。儘管調用min_element和max_element很容易，但它會執行2（n-1）次比較，並且需要在輸入上進行兩次遍歷。相比之下，minmax_element將執行較少的比較，並在輸入上執行一個單獨的遍歷。當迭代器類型不是原始指針，或者甚至只是InputIterator概念的模型時，節省可能很重要（儘管在這種情況下，接口將不得不被改變，因爲返回類型不能被複制，所以可以例如返回一個值）。

來源

2017-03-09 01:23:43 Barmar

C++中max_element和minmax_element的行爲差異STL

回答

相關問題