Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::upper_bound — granica za równoważnymi elementami

`std::upper_bound` znajduje granicę podziału zakresu dla szukanej wartości: zwraca iterator do pierwszego elementu, od którego `value` jest mniejsze według użytego porównania, albo `last`, jeśli takiego elementu nie ma. Przy domyślnym porównaniu wśród liczb posortowanych rosnąco jest to pierwsza liczba większa od `value`.

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

Składnia

#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)

std::upper_bound z nagłówka <algorithm> przeszukuje półotwarty zakres [first, last). Przy domyślnym porównaniu w zakresie rosnącym zwraca pierwszy element większy od value; pomija wszystkie duplikaty tej wartości. Wynikiem jest iterator, nie indeks ani informacja o obecności wartości. Gdy odpowiedniego elementu nie ma, także w pustym zakresie, wynikiem jest last. Przed dereferencją sprawdź wynik względem last.

Przeciążenie z comp szuka pierwszego elementu e, dla którego comp(value, e) jest prawdziwe. Warunek wstępny wymaga podziału zakresu: najpierw wszystkie elementy spełniające !comp(value, e), potem pozostałe. Pełne sortowanie według zgodnego porządku wystarcza, ale nie jest konieczne dla pojedynczego zapytania. Nie przeszukuj dowolnie nieuporządkowanych danych: naruszenie warunku wstępnego powoduje niezdefiniowane zachowanie. „Większy” zależy od komparatora, nie zawsze od liczbowego >.

Dla zakresu rosnącego std::lower_bound znajduje pierwszy element nie mniejszy od value, a std::upper_bound pierwszy większy. W posortowanym zakresie granice te wyznaczają przedział elementów równoważnych według porównania. Zwróć uwagę na kierunek argumentów: std::upper_bound używa comp(value, element), nie comp(element, value).

Wymagane są co najmniej iteratory forward. Liczba porównań jest O(log N), ale dla iteratorów bez dostępu swobodnego liczba kroków może być O(N); dla iteratorów std::vector jest logarytmiczna. Przykład używa składni zgodnej z C++23. Podlinkowany standard roboczy jest rozwijany i może zawierać nowsze deklaracje.

Przykłady

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{1, 2, 2, 2, 4, 7};
    const auto it = std::upper_bound(values.begin(), values.end(), 2);
    std::cout << "index=" << (it - values.begin()) << '\n';
    if (it != values.end()) {
        std::cout << "value=" << *it << '\n';
    }
    const auto end = std::upper_bound(values.begin(), values.end(), 7);
    std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}

Wynik

index=4
value=4
at_end=true

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

Źródła