Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje