Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::lower_bound — pierwsza pozycja nie mniejsza od klucza

std::lower_bound wyszukuje granicę w odpowiednio podzielonym zakresie: pierwszy element nie mniejszy od klucza albo koniec zakresu. Zwraca iterator, nie informację o znalezieniu równej wartości.

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

Składnia

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

std::lower_bound z nagłówka <algorithm> przeszukuje [first, last) i zwraca pierwszy iterator, dla którego comp(*it, value) jest fałszywe, lub last, jeśli takiego elementu nie ma. Bez comp używa domyślnego porównania mniejszości. W rosnącym zakresie liczb wynik wskazuje pierwszy element >= value, także pierwszy spośród duplikatów.

Warunek wstępny to podział względem danego klucza: wszystkie elementy spełniające comp(element, value) muszą poprzedzać pozostałe. Pełne posortowanie zgodnie z tym samym porównaniem wystarcza, ale nie jest konieczne. Naruszenie warunku oznacza niezdefiniowane zachowanie; funkcja nie sortuje danych.

Wynik nie potwierdza obecności klucza. Przed *it sprawdź it != last. W przykładzie z liczbami całkowitymi przed wypisaniem wartości kandydata kod sprawdza tylko it != values.end(); nie porównuje wartości z kluczem. Aby sprawdzić równość, można po wykluczeniu końca zakresu osobno wykonać test *it == key. Dla własnego porządku równoważność oznacza !comp(a, b) && !comp(b, a), niekoniecznie a == b.

Wymagane są co najmniej iteratory jednokierunkowe. Dla N elementów liczba porównań wynosi O(log N), lecz bez iteratorów o dostępie swobodnym liczba kroków iteratora może być liniowa. Przykład używa C++23; podlinkowany dokument jest rozwijanym szkicem standardu, a nie zamrożoną edycją C++23.

Przykłady

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

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Wynik

3: index=1, value=3
4: index=3, value=7
9: index=4, end

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

Źródła