CKTIS / C++
std::upper_bound — meja za enakovrednimi elementi
`std::upper_bound` poišče mejo razdelitve območja za iskano vrednost: vrne iterator na prvi element, od katerega je `value` po uporabljeni primerjavi manjša, ali `last`, če takega elementa ni. Pri privzeti primerjavi naraščajoče razvrščenih števil je to prvo število, večje od `value`.
Različica: 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 v <algorithm>, preišče polodprto območje [first, last). Pri privzeti primerjavi in naraščajočem vrstnem redu vrne prvi element, ki je večji od value, ter preskoči vse njegove dvojnike. Rezultat je iterator, ne indeks ali podatek o prisotnosti vrednosti. Če ni ustreznega elementa, tudi v praznem območju, je rezultat last. Pred dereferenciranjem preverite, ali je rezultat enak last.
Preobremenitev s comp poišče prvi element e, za katerega velja comp(value, e). Predpogoj je, da je območje razdeljeno: najprej morajo biti vsi elementi, za katere velja !comp(value, e), nato pa preostali. Popolno razvrščanje po združljivem vrstnem redu zadostuje, vendar za eno samo poizvedbo ni nujno. Ne iščite po poljubno neurejenih podatkih: kršitev predpogoja povzroči nedefinirano vedenje. Pomen besede »večji« je odvisen od primerjalnika in ne nujno od številskega operatorja >.
V naraščajočem območju std::lower_bound poišče prvi element, ki ni manjši od value, std::upper_bound pa prvi večji element. V razvrščenem območju ti meji omejujeta elemente, ki so po primerjavi enakovredni. Bodite pozorni na vrstni red argumentov: std::upper_bound uporablja comp(value, element), ne comp(element, value).
Potrebni so vsaj forward iteratorji. Število primerjav je O(log N), vendar je lahko brez naključnega dostopa število korakov iteratorja O(N); pri iteratorjih std::vector je število korakov logaritemsko. Primer uporablja sintakso, združljivo s C++23. Povezani delovni osnutek se razvija in lahko vsebuje novejše deklaracije.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.