CKTIS / C++
std::lower_bound — prvi položaj, ki ni manjši od ključa
std::lower_bound v ustrezno razdeljenem območju poišče mejo: prvi element, ki ni manjši od ključa, ali konec območja. Vrne iterator, ne pa potrditve, da enaka vrednost obstaja.
Različica: 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 v <algorithm>, preišče [first, last) in vrne prvi iterator, za katerega je comp(*it, value) neresničen, ali last, če takega elementa ni. Če comp ni podan, uporabi privzeto primerjavo »manjše od«. V naraščajočem številskem območju rezultat kaže na prvi element >= value, tudi na prvo podvojitev.
Predpogoj je, da je območje razdeljeno glede na določeni ključ: vsi elementi, za katere velja comp(element, value), morajo biti pred preostalimi. Popolno razvrščanje po isti primerjavi zadostuje, ni pa nujno. Kršitev tega pogoja povzroči nedefinirano vedenje; funkcija podatkov ne razvršča.
Rezultat ne potrjuje, da ključ obstaja. Pred uporabo *it preverite it != last. V primeru s celimi števili koda pred izpisom najdene vrednosti preveri samo it != values.end(); vrednosti ne primerja s ključem. Če iterator ni na koncu območja, lahko enakost ločeno preverite z *it == key. Pri lastnem urejanju ekvivalenca pomeni !comp(a, b) && !comp(b, a), ne nujno a == b.
Potrebni so vsaj naprej usmerjeni iteratorji. Za N elementov je število primerjav O(log N), vendar je lahko brez iteratorjev z naključnim dostopom število korakov iteratorja linearno. Primer je namenjen C++23; povezani dokument je sproti razvijajoči se delovni osnutek, ne nespremenjena izdaja C++23.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.