std::ranges::upper_bound
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| (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 *größer* als value ist, oder last, wenn kein solches Element gefunden wird. Der Bereich [first, last) muss in Bezug auf den Ausdruck oder !comp(value, element) 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 Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[edit] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den partiell geordneten Bereich der zu untersuchenden Elemente definiert |
| r | - | der partiell geordnete Bereich, der untersucht werden soll |
| value | - | Wert, mit dem die Elemente verglichen werden sollen |
| pred | - | Prädikat, das auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
Iterator, der auf das erste Element zeigt, das *größer* als value ist, oder last, wenn kein solches Element gefunden wird.
[edit] Komplexität
Die Anzahl der Vergleiche und Anwendungen der Projektion ist logarithmisch zur Distanz zwischen first und last (höchstens log2(last - first) + O(1) Vergleiche und Anwendungen der Projektion). Bei einem Iterator, der kein random_access_iterator-Modell darstellt, ist die Anzahl der Iterator-Inkremente jedoch linear.
[edit] Mögliche Implementierung
struct upper_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 = ranges::distance(first, last); while (count > 0) { it = first; step = count / 2; ranges::advance(it, step, last); if (!comp(value, std::invoke(proj, *it))) { 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 upper_bound_fn upper_bound; |
[edit] Hinweise
| 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 <iterator> #include <vector> int main() { namespace ranges = std::ranges; std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6}; { auto lower = ranges::lower_bound(data.begin(), data.end(), 4); auto upper = ranges::upper_bound(data.begin(), data.end(), 4); ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; } { auto lower = ranges::lower_bound(data, 3); auto upper = ranges::upper_bound(data, 3); ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; } using CD = std::complex<double>; std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}}; auto cmpz = [](CD x, CD y) { return x.real() < y.real(); }; #ifdef __cpp_lib_algorithm_default_value_type auto it = ranges::upper_bound(nums, {2, 0}, cmpz); #else auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz); #endif assert((*it == CD{3, 0})); }
Ausgabe
4 4 4 3 3 3 3
[edit] Siehe auch
| (C++20) |
gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Teilt einen Bereich von Elementen in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| Gibt einen Iterator zum ersten Element zurück, das *größer* als ein bestimmter Wert ist (Funktionstemplate) |
