Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

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.

Viri