std::lower_bound
| Definiert in Header <algorithm> |
||
| (1) | ||
template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, |
(constexpr seit C++20) (bis C++26) |
|
| template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > |
(seit C++26) | |
| (2) | ||
template< class ForwardIt, class T, class Compare > ForwardIt lower_bound( ForwardIt first, ForwardIt last, |
(constexpr seit C++20) (bis C++26) |
|
| template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, |
(seit C++26) | |
Sucht das erste Element im partitionierten Bereich [first, last), das **nicht** vor value geordnet ist.
|
Gibt den ersten Iterator iter im Bereich Wenn die Elemente elem von |
(bis C++20) |
|
Äquivalent zu std::lower_bound(first, last, value, std::less{}). |
(seit C++20) |
[first, last) zurück, für den gilt: bool(comp(*iter, value)) **falsch** ist, oder last, falls kein solcher iter existiert.[first, last) nicht in Bezug auf den Ausdruck bool(comp(elem, value)) partitioniert sind, ist das Verhalten undefiniert.Inhalt |
[edit] Parameter
| first, last | - | das Iterator-Paar, das den partitionierten Bereich der zu untersuchenden Elemente definiert |
| value | - | Wert, mit dem die Elemente verglichen werden sollen |
| comp | - | Binäres Prädikat, das **wahr** zurückgibt, wenn das erste Argument vor dem zweiten geordnet ist. Die Signatur der Prädikatfunktion sollte äquivalent zur folgenden sein: bool pred(const Type1 &a, const Type2 &b); Obwohl die Signatur nicht zwingend const & haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (möglicherweise const) |
| Typanforderungen | ||
-ForwardIt muss die Anforderungen von LegacyForwardIterator erfüllen. | ||
-Compare muss die Anforderungen an ein Binäres Prädikat erfüllen. Es muss nicht Compare erfüllen. | ||
[edit] Rückgabewert
Iterator auf das erste Element des Bereichs [first, last), das nicht vor value geordnet ist, oder last, falls kein solches Element gefunden wird.
[edit] Komplexität
Gegeben sei N als std::distance(first, last).
Wenn jedoch ForwardIt kein LegacyRandomAccessIterator ist, ist die Anzahl der Iterator-Inkremente linear in N. Insbesondere sind Iteratoren von std::map, std::multimap, std::set und std::multiset keine Zufallszugriffsiteratoren, daher sollten ihre Memberfunktionen lower_bound bevorzugt werden.
[edit] Mögliche Implementierung
Siehe auch die Implementierungen in libstdc++ und libc++.
| lower_bound (1) |
|---|
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value) { return std::lower_bound(first, last, value, std::less{}); } |
| lower_bound (2) |
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (comp(*it, value)) { first = ++it; count -= step + 1; } else count = step; } return first; } |
[edit] Hinweise
Obwohl `std::lower_bound` nur erfordert, dass [first, last) partitioniert ist, wird dieser Algorithmus normalerweise in Fällen verwendet, in denen [first, last) sortiert ist, damit die binäre Suche für jedes value gültig ist.
Im Gegensatz zu std::binary_search erfordert `std::lower_bound` nicht, dass operator< oder comp asymmetrisch sind (d. h. a < b und b < a immer unterschiedliche Ergebnisse liefern). Tatsächlich ist nicht einmal erforderlich, dass value < *iter oder comp(value, *iter) für einen beliebigen Iterator iter in [first, last) wohlgeformt sind.
| Feature-Test-Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | Listeninitialisierung für Algorithmen (1,2) |
[edit] Beispiel
#include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <vector> struct PriceInfo { double price; }; int main() { const std::vector<int> data{1, 2, 4, 5, 5, 6}; for (int i = 0; i < 8; ++i) { // Search for first element x such that i ≤ x auto lower = std::lower_bound(data.begin(), data.end(), i); std::cout << i << " ≤ "; lower != data.end() ? std::cout << *lower << " at index " << std::distance(data.begin(), lower) : std::cout << "not found"; std::cout << '\n'; } std::vector<PriceInfo> prices{{100.0}, {101.5}, {102.5}, {102.5}, {107.3}}; for (const double to_find : {102.5, 110.2}) { auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find, [](const PriceInfo& info, double value) { return info.price < value; }); prc_info != prices.end() ? std::cout << prc_info->price << " at index " << prc_info - prices.begin() : std::cout << to_find << " not found"; std::cout << '\n'; } using CD = std::complex<double>; std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}}; auto cmpz = [](CD x, CD y) { return x.real() < y.real(); }; #ifdef __cpp_lib_algorithm_default_value_type auto it = std::lower_bound(nums.cbegin(), nums.cend(), {2, 0}, cmpz); #else auto it = std::lower_bound(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz); #endif assert((*it == CD{2, 2})); }
Ausgabe
0 ≤ 1 at index 0 1 ≤ 1 at index 0 2 ≤ 2 at index 1 3 ≤ 4 at index 2 4 ≤ 4 at index 2 5 ≤ 5 at index 3 6 ≤ 6 at index 5 7 ≤ not found 102.5 at index 2 110.2 not found
[edit] Fehlerberichte
Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.
| DR | angewendet auf | Verhalten wie veröffentlicht | Korrigiertes Verhalten |
|---|---|---|---|
| LWG 270 | C++98 | Compare musste Compare erfüllen und T mussteLessThanComparable sein (starke schwache Ordnung erforderlich) |
nur eine Partitionierung ist erforderlich; heterogene Vergleiche zulässig |
| LWG 384 | C++98 | maximal log(N)+1 Vergleiche waren zulässig | korrigiert zu log2(N)+1 |
| LWG 2150 | C++98 | wenn irgendein Iterator iter in [first, last) existiert, so dassbool(comp(*iter, value)) **falsch** ist, könnte `std::lower_bound` jeden Iterator in [iter, last) zurückgeben |
kein Iterator nach iter kann zurückgegeben werden |
[edit] Siehe auch
| gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen (Funktionstemplate) | |
| Teilt einen Bereich von Elementen in zwei Gruppen auf (Funktionstemplate) | |
| (C++11) |
Findet den Partitionierungspunkt eines partitionierten Bereichs (Funktionstemplate) |
| Gibt einen Iterator zum ersten Element zurück, das *größer* als ein bestimmter Wert ist (Funktionstemplate) | |
| gibt einen Iterator zum ersten Element zurück, das *nicht kleiner* als der gegebene Schlüssel ist (öffentliche Memberfunktion von std::set<Key,Compare,Allocator>) | |
| gibt einen Iterator zum ersten Element zurück, das *nicht kleiner* als der gegebene Schlüssel ist (öffentliche Memberfunktion von std::multiset<Key,Compare,Allocator>) | |
| (C++20) |
Gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist (Algorithmus-Funktionsobjekt) |
