Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::lower_bound — prvá pozícia, ktorá nie je menšia ako kľúč

std::lower_bound hľadá v náležite rozdelenom rozsahu hranicu: prvý prvok, ktorý nie je menší ako kľúč, alebo koniec rozsahu. Vráti iterátor, nie potvrdenie, že existuje rovnaká hodnota.

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

Syntax

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

std::lower_bound deklarovaná v <algorithm> prehľadáva [first, last) a vracia prvý iterátor, pre ktorý je comp(*it, value) nepravdivé, alebo last, ak taký prvok neexistuje. Bez comp používa predvolené porovnanie „menší ako“. Vo vzostupnom číselnom rozsahu výsledok ukazuje na prvý prvok >= value, vrátane prvého duplicitného prvku.

Predpokladom je rozdelenie rozsahu podľa konkrétneho kľúča: všetky prvky spĺňajúce comp(element, value) musia predchádzať ostatným. Úplné usporiadanie podľa rovnakého porovnania postačuje, ale nie je nevyhnutné. Porušenie tejto podmienky vedie k nedefinovanému správaniu; funkcia údaje netriedi.

Výsledok nepotvrdzuje, že kľúč existuje. Pred použitím *it skontrolujte it != last. V príklade s celými číslami kód pred vypísaním nájdenej hodnoty kontroluje iba it != values.end(); hodnotu s kľúčom neporovnáva. Ak iterátor nie je na konci rozsahu, môžete rovnosť overiť samostatne pomocou *it == key. Pri vlastnom usporiadaní znamená ekvivalencia !comp(a, b) && !comp(b, a), nie nevyhnutne a == b.

Vyžadujú sa aspoň dopredné iterátory. Pre N prvkov je počet porovnaní O(log N), ale bez iterátorov s náhodným prístupom môže byť počet krokov iterátora lineárny. Príklad je určený pre C++23; odkazovaný dokument je priebežne vyvíjaný pracovný návrh, nie nemenné vydanie C++23.

Prí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ýsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje