std::ranges::lower_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 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.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 projizierten Elemente verglichen werden sollen |
| comp | - | Vergleichsprädikat, das auf die projizierten Elemente angewendet werden soll |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
Iterator, der auf das erste Element zeigt, das nicht kleiner als value ist, oder last, wenn kein solches Element gefunden wird.
[edit] Komplexität
Die Anzahl der Vergleiche und Projektionsanwendungen ist logarithmisch bezüglich des Abstands zwischen first und last (höchstens log2(last - first) + O(1) Vergleiche und Projektionsanwendungen). Für einen Iterator, der random_access_iterator nicht modelliert, ist die Anzahl der Iterator-Inkremente jedoch linear.
[edit] Anmerkungen
Auf einem Bereich, der nach Projektion vollständig sortiert ist (oder allgemeiner, teilweise geordnet bezüglich value), implementiert std::ranges::lower_bound den Binärsuchalgorithmus. Daher kann std::ranges::binary_search darauf aufbauen.
| Feature-Test-Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | Listeninitialisierung für Algorithmen (1,2) |
[edit] 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; |
[edit] 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"; // classic binary search, returning a value only if it is present data = {1, 2, 4, 8, 16}; // ^ auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end() 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[edit] Siehe auch
| (C++20) |
gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen (Algorithmus-Funktionsobjekt) |
| (C++20) |
Teilt einen Bereich von Elementen in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| (C++20) |
Findet 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) |
