Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::upper_bound — hranice za ekvivalentními prvky

`std::upper_bound` najde hranici rozdělení rozsahu pro hledanou hodnotu: vrátí iterátor na první prvek, vůči němuž je `value` podle použitého porovnání menší, nebo `last`, pokud takový prvek neexistuje. Při výchozím porovnání vzestupně seřazených čísel jde o první číslo větší než `value`.

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

Syntaxe

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

std::upper_bound deklarované v <algorithm> prohledává polouzavřený rozsah [first, last). Při výchozím porovnávání a vzestupném pořadí vrací první prvek větší než value; všechny jeho duplicity přeskočí. Výsledkem je iterátor, nikoli index ani informace o přítomnosti hodnoty. Pokud žádný odpovídající prvek neexistuje, a to i v prázdném rozsahu, výsledkem je last. Před dereferencováním ověřte, že výsledek není last.

Přetížení s comp hledá první prvek e, pro který platí comp(value, e). Předpokladem je rozdělení rozsahu: nejprve musí být všechny prvky splňující !comp(value, e) a za nimi ostatní. Úplné seřazení podle kompatibilního uspořádání stačí, pro jedno hledání však není nutné. Neprohledávejte libovolně neuspořádaná data: porušení předpokladu vede k nedefinovanému chování. Význam slova „větší“ závisí na komparátoru, ne nutně na číselném operátoru >.

Ve vzestupně seřazeném rozsahu najde std::lower_bound první prvek, který není menší než value, zatímco std::upper_bound najde první větší prvek. V seřazeném rozsahu tyto hranice vymezují prvky ekvivalentní podle porovnání. Všimněte si pořadí argumentů: std::upper_bound používá comp(value, element), nikoli comp(element, value).

Jsou vyžadovány alespoň forward iterátory. Počet porovnání je O(log N), ale bez náhodného přístupu může být počet kroků iterátoru O(N); u iterátorů std::vector je logaritmický. Příklad používá syntaxi kompatibilní s C++23. Odkázaný pracovní návrh se vyvíjí a může obsahovat novější deklarace.

Pří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ýsledek

index=4
value=4
at_end=true

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje