Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::upper_bound — granica iza ekvivalentnih elemenata

`std::upper_bound` pronalazi granicu podjele raspona za traženu vrijednost: vraća iterator na prvi element od kojeg je `value` prema primijenjenoj usporedbi manji, ili `last` ako takvog elementa nema. Uz zadanu usporedbu za uzlazno poredane brojeve to je prvi broj veći od `value`.

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

Sintaksa

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

std::upper_bound, deklariran u <algorithm>, pretražuje poluotvoreni raspon [first, last). Uz zadanu usporedbu i uzlazni poredak vraća prvi element veći od value, preskačući sve duplikate te vrijednosti. Rezultat je iterator, a ne indeks ni oznaka prisutnosti. Ako nema odgovarajućeg elementa, uključujući i prazan raspon, rezultat je last. Prije dereferenciranja provjerite je li rezultat jednak last.

Preopterećenje koje prima comp traži prvi element e za koji je comp(value, e) istinito. Preduvjet je particioniranost raspona: najprije moraju biti svi elementi za koje vrijedi !comp(value, e), a zatim ostali. Potpuno sortiranje prema kompatibilnom poretku dovoljno je, ali nije nužno za jedno traženje. Nemojte pretraživati proizvoljno neuređene podatke: kršenje preduvjeta uzrokuje nedefinirano ponašanje. Značenje riječi „veći” ovisi o komparatoru, a ne nužno o brojčanom operatoru >.

U uzlaznom rasponu std::lower_bound pronalazi prvi element koji nije manji od value, dok std::upper_bound pronalazi prvi veći element. U sortiranom rasponu te granice omeđuju elemente koji su ekvivalentni prema usporedbi. Obratite pozornost na redoslijed argumenata: std::upper_bound koristi comp(value, element), a ne comp(element, value).

Potrebni su barem forward iteratori. Broj usporedbi je O(log N), ali bez nasumičnog pristupa broj koraka iteratora može biti O(N); s iteratorima std::vector broj koraka je logaritamski. Primjer koristi sintaksu kompatibilnu s C++23. Povezani radni nacrt razvija se i može sadržavati novije deklaracije.

Primjeri

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{1, 2, 2, 2, 4, 7};
    const auto it = std::upper_bound(values.begin(), values.end(), 2);
    std::cout << "index=" << (it - values.begin()) << '\n';
    if (it != values.end()) {
        std::cout << "value=" << *it << '\n';
    }
    const auto end = std::upper_bound(values.begin(), values.end(), 7);
    std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}

Rezultat

index=4
value=4
at_end=true

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori