Różnica w zachowaniu max_element i minmax_element w C++ STL

Question

W C++ max_element, jeśli istnieje wiele elementów, które są maksymalne, zwraca pierwszy taki element. Natomiast minmax_element (C++ 11 lub późniejsze) zwraca ostatni element max.

Czy istnieją jakieś powody ze standardów tego zachowania?

Od cplusplus.com

Jeśli więcej niż jeden równoważnik element ma największą wartość, drugie punkty iteracyjnej do ostatniego z tych elementów.

Porównania są wykonywane przy użyciu operatora < dla pierwszej wersji lub kompu dla drugiego; Element jest największy, jeśli żaden inny element nie porównuje mniej niż on. Jeśli więcej niż jeden element spełnia ten warunek, iterator zwrócił punkty pierwszemu z takich elementów. Dokumentacja

Answer 1

Boost za ich biblioteki obejmuje Problem powierzchnie rationale

definicja gdy ktoś próbuje zaprojektować minmax_element, stosując procedurę zaproponowaną w (CORMEN, Leiserson, Rivesta: „Wprowadzenie do algorytmów” sekcja 9.1). Powinno być możliwe wyprowadzenie algorytmu przy użyciu tylko porównań 3n/2, jeśli [pierwszy, ostatni) ma n elementów, ale jeśli spróbujemy napisać funkcję o nazwie first_min_first_max_element(), która zwraca zarówno std :: min_element i std :: max_element w para, trywialna implementacja nie działa. Problem, raczej subtelnie, dotyczy równych elementów: przez chwilę musiałem się zastanowić, jak znaleźć sposób na wykonanie tylko trzech porównań na parę i zwrócenie pierwszych min i pierwszych elementów max. Przez długi czas wydawało się, że każda próba takiego rozwiązania pochłonie cztery porównania na parę w najgorszym przypadku. Ta implementacja osiąga trzy.

Nie jest możliwa (lub nawet pożądana) zmiana znaczenia max_element, ale nadal korzystne jest zapewnienie funkcji o nazwie minmax_element, która zwraca parę parametrów min_element i max_element. Chociaż łatwo jest wywołać min_element i max_element, wykonuje to porównanie 2 (n-1) i wymaga dwóch przebiegów przez dane wejściowe. W przeciwieństwie do tego, minmax_element wykona mniej porównań i wykona pojedyncze przejście przez dane wejściowe. Oszczędności mogą być znaczące, gdy typ iteratora nie jest wskaźnikiem surowym lub nawet jest tylko modelem koncepcji InputIterator (chociaż w tym przypadku interfejs musiałby zostać zmieniony, ponieważ nie można skopiować typu powrotu, aby można było skopiować np. zwróć wartość).