std::ranges::lower_bound
Von de.cppreference.net
| Definiert in Header <algorithm>
|
||
| Aufrufsignatur |
||
template< std::forward_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr I lower_bound( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
|
(1) | (seit C++20) (bis C++26) |
template< std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr I lower_bound( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
|
(seit C++26) | |
template< ranges::forward_range R,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
|
(2) | (seit C++20) (bis C++26) |
template< ranges::forward_range R,
class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_iterator_t<R>
lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
|
(seit C++26) | |
1) Gibt einen Iterator zurück, der auf das erste Element im Bereich
[first, last) zeigt, das nicht kleiner als (d.h. größer oder gleich) value ist, oder last wenn kein solches Element gefunden wird.
Der Bereich [first, last) muss bezüglich des Ausdrucks std::invoke(comp, std::invoke(proj, element), value) partitioniert sein, d.h., alle Elemente, für die der Ausdruck true ist, müssen allen Elementen vorausgehen, für die der Ausdruck false ist. Ein vollständig sortierter Bereich erfüllt dieses Kriterium.2) Wie (1), verwendet aber
r als Quellbereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:
- Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
- Keine von ihnen ist für argumentabhängige Suche sichtbar.
- Wenn eine von ihnen durch normale unqualifizierte Suche als Name links des Funktionsaufrufoperators gefunden wird, wird argumentabhängige Suche unterdrückt.
Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den teilweise geordneten Bereich der zu untersuchenden Elemente definiert |
| r | - | der teilweise geordnete zu untersuchende Bereich |
| value | - | Wert, mit dem die projizierten Elemente verglichen werden |
| comp | - | Vergleichsprädikat, das auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
Rückgabewert
Iterator, der auf das erste Element zeigt, das nicht kleiner als value ist, oder last , falls kein solches Element gefunden wird.
Komplexität
Die Anzahl der Vergleiche und Anwendungen der Projektion ist logarithmisch im Abstand zwischen
first
und
last
(höchstens
log
2
(last - first) + O(1)
Vergleiche und Anwendungen der Projektion). Für einen Iterator, der nicht
random_access_iterator
modelliert, ist die Anzahl der Iterator-Inkremente jedoch linear.
Hinweise
In einem vollständig sortierten Bereich (oder allgemeiner, teilweise geordnet bezüglich
value
) nach der Projektion implementiert
std::ranges::lower_bound
den binären Suchalgorithmus. Daher kann
std::ranges::binary_search
mithilfe davon implementiert werden.
| Feature-Test Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type
|
202403
|
(C++26) | Listeninitialisierung für Algorithmen ( 1,2 ) |
Mögliche Implementierung
struct lower_bound_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, class T = std::projected_value_t<I, Proj>, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less> constexpr I operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const { I it; std::iter_difference_t<I> count, step; count = std::ranges::distance(first, last); while (count > 0) { it = first; step = count / 2; ranges::advance(it, step, last); if (comp(std::invoke(proj, *it), value)) { first = ++it; count -= step + 1; } else count = step; } return first; } template<ranges::forward_range R, class Proj = std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj>, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), value, std::ref(comp), std::ref(proj)); } }; inline constexpr lower_bound_fn lower_bound; |
Beispiel
Diesen Code ausführen
#include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <iterator> #include <vector> namespace ranges = std::ranges; template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less> constexpr I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) { first = ranges::lower_bound(first, last, value, comp, proj); return first != last && !comp(value, proj(*first)) ? first : last; } int main() { std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}; // ^^^^^^^^^^ auto lower = ranges::lower_bound(data, 4); auto upper = ranges::upper_bound(data, 4); std::cout << "found a range [" << ranges::distance(data.cbegin(), lower) << ", " << ranges::distance(data.cbegin(), upper) << ") = { "; ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); std::cout << "}\n"; // klassische binäre Suche, die nur einen Wert zurückgibt, wenn er vorhanden ist data = {1, 2, 4, 8, 16}; // ^ auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' würde end() zurückgeben if (it != data.cend()) std::cout << *it << " found at index " << ranges::distance(data.cbegin(), it); 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 it2 = ranges::lower_bound(nums, {2, 0}, cmpz); #else auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz); #endif assert((*it2 == CD{2, 2})); }
Ausgabe:
found a range [6, 10) = { 4 4 4 4 }
8 found at index 3
Siehe auch
(C++20) |
findet den Bereich von Elementen, die dem gegebenen Wert entsprechen, mittels binärer Suche (Algorithmus-Funktionsobjekt) |
(C++20) |
teilt einen Bereich von Elementen in zwei Gruppen (Algorithmus-Funktionsobjekt) |
(C++20) |
ermittelt den Teilungspunkt eines partitionierten Bereichs (Algorithmus-Funktionsobjekt) |
(C++20) |
findet das erste Element, das größer als der gegebene Wert ist, mittels binärer Suche (Algorithmus-Funktionsobjekt) |
| findet das erste Element, das nicht kleiner als der gegebene Wert ist, mittels binärer Suche (Funktionsschablone) |