Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::minmax_element — pozycje minimum i maksimum

std::minmax_element wyszukuje minimum i maksimum zakresu, zwracając parę iteratorów. Przy remisach wybiera pierwsze minimum i ostatnie maksimum; pusty zakres wymaga sprawdzenia wyniku przed dereferencją.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#include <algorithm>
std::minmax_element(first, last)
std::minmax_element(first, last, comp)
// Result: std::pair<ForwardIterator, ForwardIterator>

std::minmax_element z nagłówka <algorithm> przeszukuje zakres [first, last) i zwraca std::pair iteratorów, a nie kopie wartości. Pole first wskazuje minimum, a second maksimum. Potrzebne są co najmniej iteratory jednokierunkowe wieloprzebiegowe (forward iterators); iteratory jednoprzebiegowe nie wystarczają.

Przy elementach równoważnych według porządku algorytm wybiera pierwsze minimum i ostatnie maksimum. To istotna różnica względem std::max_element, które wybiera pierwsze maksimum. Dla pustego zakresu wynikiem jest {first, first}, czyli {last, last}; nie wolno dereferencjonować tych iteratorów. Dla jednego elementu oba wskazują ten element.

W C++23 klasyczne przeciążenie bez comp używa operator<. W przypadku wskaźników ten operator nie gwarantuje ścisłego porządku całkowitego, który zapewnia std::less. Wariant z comp wymaga ścisłego słabego porządku: comp(a, b) oznacza, że a poprzedza b; nie używaj <=. Algorytm nie sortuje zakresu. Zwrócone iteratory można wykorzystywać tylko tak długo, jak pozostają ważne.

Dla N elementów wykonuje najwyżej max(floor(3 * (N - 1) / 2), 0) porównań, więc złożoność jest liniowa. Istnieją również przeciążenia z polityką wykonania jako pierwszym argumentem; przykład używa zwykłego przeciążenia bez polityki.

Przykłady

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 5> values{4, 1, 9, 1, 9};
    const auto [lo, hi] = std::minmax_element(values.begin(), values.end());

    if (lo != values.end()) {
        std::cout << "min=" << *lo << " index=" << (lo - values.begin()) << '\n';
        std::cout << "max=" << *hi << " index=" << (hi - values.begin()) << '\n';
    }
}

Wynik

min=1 index=1
max=9 index=4

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła