CKTIS / C++
std::lower_bound — erste Position, die nicht kleiner als ein Schlüssel ist
std::lower_bound sucht in einem passend partitionierten Bereich die Grenze: das erste Element, das nicht kleiner als der Schlüssel ist, oder das Ende des Bereichs. Zurückgegeben wird ein Iterator, keine Bestätigung, dass ein gleicher Wert vorhanden ist.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)std::lower_bound aus <algorithm> durchsucht [first, last) und gibt den ersten Iterator zurück, für den comp(*it, value) falsch ist, oder last, falls es kein solches Element gibt. Ohne comp wird der standardmäßige Kleiner-Vergleich verwendet. In einem aufsteigend sortierten Zahlenbereich zeigt das Ergebnis auf das erste Element >= value, also auch auf das erste Duplikat.
Voraussetzung ist, dass der Bereich für den jeweiligen Schlüssel partitioniert ist: Alle Elemente, für die comp(element, value) gilt, müssen vor den übrigen Elementen stehen. Eine vollständige Sortierung nach demselben Vergleich genügt, ist aber nicht erforderlich. Wird diese Bedingung verletzt, ist das Verhalten undefiniert; die Funktion sortiert die Daten nicht.
Das Ergebnis bestätigt nicht, dass der Schlüssel vorhanden ist. Prüfe it != last, bevor du *it verwendest. Im Beispiel mit Ganzzahlen prüft der Code vor der Ausgabe des gefundenen Werts nur it != values.end(); er vergleicht den Wert nicht mit dem Schlüssel. Wenn der Iterator nicht auf das Ende des Bereichs zeigt, kannst du die Gleichheit separat mit *it == key prüfen. Bei einer benutzerdefinierten Ordnung bedeutet Äquivalenz !comp(a, b) && !comp(b, a) und nicht zwingend a == b.
Mindestens Forward-Iteratoren sind erforderlich. Bei N Elementen beträgt die Zahl der Vergleiche O(log N), aber ohne Random-Access-Iteratoren kann die Zahl der Iteratorschritte linear sein. Das Beispiel zielt auf C++23; das verlinkte Dokument ist ein fortlaufend bearbeiteter Entwurf und keine unveränderliche C++23-Ausgabe.
Beispiele
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 3, 3, 7};
for (int key : {3, 4, 9}) {
const auto it = std::lower_bound(values.begin(), values.end(), key);
std::cout << key << ": index=" << (it - values.begin());
if (it != values.end()) {
std::cout << ", value=" << *it;
} else {
std::cout << ", end";
}
std::cout << '\n';
}
}
Ergebnis
3: index=1, value=3 4: index=3, value=7 9: index=4, end
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.