CKTIS / C++
std::upper_bound — hranica za ekvivalentnými prvkami
`std::upper_bound` nájde hranicu rozdelenia rozsahu pre hľadanú hodnotu: vráti iterátor na prvý prvok, od ktorého je `value` podľa použitého porovnania menšia, alebo `last`, ak taký prvok neexistuje. Pri predvolenom porovnaní vzostupne zoradených čísel ide o prvé číslo väčšie ako `value`.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound deklarované v <algorithm> prehľadáva polootvorený rozsah [first, last). Pri predvolenom porovnávaní a vzostupnom poradí vráti prvý prvok väčší ako value; všetky duplikáty tejto hodnoty preskočí. Výsledkom je iterátor, nie index ani informácia o prítomnosti hodnoty. Ak neexistuje žiadny vyhovujúci prvok, a to aj v prázdnom rozsahu, výsledkom je last. Pred dereferencovaním skontrolujte, či výsledok nie je last.
Preťaženie s comp hľadá prvý prvok e, pre ktorý platí comp(value, e). Podmienkou je rozdelenie rozsahu: najprv musia byť všetky prvky, pre ktoré platí !comp(value, e), a potom ostatné. Úplné zoradenie podľa kompatibilného usporiadania stačí, ale pri jedinom vyhľadávaní nie je potrebné. Neprehľadávajte ľubovoľne neusporiadané údaje: porušenie podmienky spôsobuje nedefinované správanie. Význam slova „väčší“ závisí od komparátora, nie nevyhnutne od číselného operátora >.
Vo vzostupne zoradenom rozsahu nájde std::lower_bound prvý prvok, ktorý nie je menší ako value, zatiaľ čo std::upper_bound nájde prvý väčší prvok. V zoradenom rozsahu tieto hranice vymedzujú prvky ekvivalentné podľa porovnania. Všimnite si poradie argumentov: std::upper_bound používa comp(value, element), nie comp(element, value).
Vyžadujú sa aspoň forward iterátory. Počet porovnaní je O(log N), ale bez náhodného prístupu môže byť počet krokov iterátora O(N); pri iterátoroch std::vector je počet krokov logaritmický. Príklad používa syntax kompatibilnú s C++23. Odkázaný pracovný návrh sa vyvíja a môže obsahovať novšie deklarácie.
Príklady
#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';
}
Výsledok
index=4 value=4 at_end=true
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.