std::ranges:: lower_bound
|
Definiert im Header
<algorithm>
|
||
|
Aufrufsignatur
|
||
| (1) | ||
|
template
<
std::
forward_iterator
I,
std::
sentinel_for
<
I
>
S,
class
T,
class
Proj
=
std::
identity
,
|
(seit C++20)
(bis C++26) |
|
|
template
<
std::
forward_iterator
I,
std::
sentinel_for
<
I
>
S,
class
Proj
=
std::
identity
,
|
(seit C++26) | |
| (2) | ||
|
template
<
ranges::
forward_range
R,
class
T,
class
Proj
=
std::
identity
,
|
(seit C++20)
(bis C++26) |
|
|
template
<
ranges::
forward_range
R,
class
Proj
=
std::
identity
,
|
(seit C++26) | |
[
first
,
last
)
zeigt, das
nicht kleiner
als (d.h. größer oder gleich)
value
ist, oder
last
, falls 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.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:
- Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
- Keiner von ihnen ist sichtbar für argument-dependent lookup .
- Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.
Inhaltsverzeichnis |
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
#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)
|
gibt den Bereich der Elemente zurück, die einem bestimmten Schlüssel entsprechen
(Algorithmus-Funktionsobjekt) |
|
(C++20)
|
unterteilt einen Elementbereich in zwei Gruppen
(Algorithmus-Funktionsobjekt) |
|
(C++20)
|
lokalisiert den Partitionierungspunkt eines partitionierten Bereichs
(Algorithmus-Funktionsobjekt) |
|
(C++20)
|
gibt einen Iterator zum ersten Element zurück, das
größer
als ein bestimmter Wert ist
(Algorithmus-Funktionsobjekt) |
|
gibt einen Iterator zum ersten Element zurück, das
nicht kleiner
als der gegebene Wert ist
(Funktionstemplate) |