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.