Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::lower_bound — prvi položaj koji nije manji od ključa

std::lower_bound u prikladno particioniranom rasponu traži granicu: prvi element koji nije manji od ključa ili kraj raspona. Vraća iterator, a ne potvrdu da postoji jednaka vrijednost.

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

Sintaksa

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

std::lower_bound, deklarirana u <algorithm>, pretražuje [first, last) i vraća prvi iterator za koji je comp(*it, value) netočan ili last ako takav element ne postoji. Ako comp nije naveden, koristi zadanu usporedbu „manje od”. U uzlaznom brojčanom rasponu rezultat pokazuje na prvi element >= value, uključujući prvu dupliciranu vrijednost.

Preduvjet je da je raspon particioniran prema konkretnom ključu: svi elementi za koje vrijedi comp(element, value) moraju biti ispred ostalih. Potpuno sortiranje prema istoj usporedbi dovoljno je, ali nije nužno. Kršenje tog uvjeta uzrokuje nedefinirano ponašanje; funkcija ne sortira podatke.

Rezultat ne potvrđuje da ključ postoji. Provjerite it != last prije korištenja *it. U primjeru s cijelim brojevima kôd prije ispisa pronađene vrijednosti provjerava samo it != values.end(); vrijednost ne uspoređuje s ključem. Ako iterator nije na kraju raspona, jednakost možete zasebno provjeriti pomoću *it == key. Kod prilagođenog poretka ekvivalencija znači !comp(a, b) && !comp(b, a), a ne nužno a == b.

Potrebni su barem iteratori prema naprijed. Za N elemenata broj usporedbi je O(log N), ali bez iteratora s nasumičnim pristupom broj koraka iteratora može biti linearan. Primjer je namijenjen za C++23; povezani dokument promjenjivi je radni nacrt, a ne nepromjenjivo izdanje C++23.

Primjeri

#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';
    }
}

Rezultat

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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori