WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::upper_bound — die Grenze hinter gleichwertigen Elementen

`std::upper_bound` findet die Partitionsgrenze für den Suchwert: Die Funktion liefert einen Iterator auf das erste Element, für das `value` nach dem verwendeten Vergleich kleiner ist als dieses Element, oder `last`, wenn es kein solches Element gibt. Bei aufsteigend sortierten Zahlen und dem Standardvergleich ist dies die erste Zahl, die größer als `value` ist.

Version: 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 aus <algorithm> durchsucht den halboffenen Bereich [first, last). Bei der Standardvergleichsoperation und aufsteigender Reihenfolge liefert die Funktion das erste Element, das größer als value ist; alle Duplikate dieses Werts werden übersprungen. Das Ergebnis ist ein Iterator, kein Index und keine Aussage darüber, ob der Wert vorhanden ist. Gibt es kein passendes Element, auch bei einem leeren Bereich, ist das Ergebnis last. Prüfe das Ergebnis vor dem Dereferenzieren auf Gleichheit mit last.

Die Überladung mit comp sucht das erste Element e, für das comp(value, e) wahr ist. Voraussetzung ist, dass der Bereich partitioniert ist: Zuerst müssen alle Elemente stehen, für die !comp(value, e) gilt, danach die übrigen. Eine vollständige Sortierung nach einer passenden Ordnung reicht aus, ist für eine einzelne Abfrage aber nicht erforderlich. Durchsuche keine beliebig ungeordneten Daten: Bei Verletzung der Voraussetzung ist das Verhalten undefiniert. Was „größer“ bedeutet, hängt vom Komparator ab und nicht unbedingt vom numerischen >.

In einem aufsteigend sortierten Bereich findet std::lower_bound das erste Element, das nicht kleiner als value ist, während std::upper_bound das erste größere Element findet. In einem sortierten Bereich begrenzen diese beiden Positionen die nach dem Vergleich gleichwertigen Elemente. Achte auf die Argumentreihenfolge: std::upper_bound verwendet comp(value, element), nicht comp(element, value).

Erforderlich sind mindestens Forward-Iteratoren. Die Anzahl der Vergleiche beträgt O(log N), doch ohne wahlfreien Zugriff kann die Anzahl der Iteratorschritte O(N) betragen; bei Iteratoren von std::vector ist sie logarithmisch. Das Beispiel verwendet mit C++23 kompatible Syntax. Der verlinkte Arbeitsentwurf wird weiterentwickelt und kann neuere Deklarationen enthalten.

Beispiele

#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';
}

Ergebnis

index=4
value=4
at_end=true

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen