CKTIS / C++
std::lower_bound — první pozice, která není menší než klíč
std::lower_bound hledá v náležitě rozděleném rozsahu hranici: první prvek, který není menší než klíč, nebo konec rozsahu. Vrací iterátor, nikoli potvrzení, že existuje stejná hodnota.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)std::lower_bound deklarovaná v <algorithm> prohledává [first, last) a vrací první iterátor, pro který je comp(*it, value) nepravdivé, nebo last, pokud takový prvek neexistuje. Bez comp používá výchozí porovnání „menší než“. Ve vzestupném číselném rozsahu výsledek ukazuje na první prvek >= value, včetně prvního duplicitního prvku.
Předpokladem je rozdělení rozsahu podle konkrétního klíče: všechny prvky splňující comp(element, value) musí předcházet ostatním. Úplné seřazení podle stejného porovnání postačuje, ale není nutné. Porušení této podmínky vede k nedefinovanému chování; funkce data netřídí.
Výsledek nepotvrzuje, že klíč existuje. Před použitím *it ověřte it != last. V příkladu s celými čísly kód před výpisem nalezené hodnoty ověřuje pouze it != values.end(); hodnotu s klíčem neporovnává. Pokud iterátor není na konci rozsahu, můžete rovnost ověřit samostatně pomocí *it == key. U vlastního uspořádání znamená ekvivalence !comp(a, b) && !comp(b, a), nikoli nutně a == b.
Jsou vyžadovány alespoň dopředné iterátory. Pro N prvků je počet porovnání O(log N), ale bez iterátorů s náhodným přístupem může být počet kroků iterátoru lineární. Příklad cílí na C++23; odkazovaný dokument je průběžně vyvíjený pracovní návrh, nikoli neměnné vydání C++23.
Příklady
#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';
}
}
Výsledek
3: index=1, value=3 4: index=3, value=7 9: index=4, end
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.