std::ranges::binary_search
| 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) vorkommt.Damit ranges::binary_search erfolgreich ist, muss der Bereich [first, last) zumindest teilweise in Bezug auf value geordnet sein, d. h. er muss alle folgenden Anforderungen erfüllen:
- partitioniert in Bezug auf std::invoke(comp, std::invoke(proj, element), value) (d. h. alle projizierten Elemente, für die der Ausdruck true ist, stehen vor allen Elementen, für die der Ausdruck false ist).
- partitioniert in Bezug auf !std::invoke(comp, value, std::invoke(proj, element)).
- Für alle Elemente gilt: Wenn std::invoke(comp, std::invoke(proj, element), value) true ist, dann ist auch !std::invoke(comp, value, std::invoke(proj, element)) true.
Ein vollständig sortierter Bereich erfüllt diese Kriterien.
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 Bereich der zu untersuchenden Elemente definiert |
| r | - | der Bereich der zu untersuchenden Elemente |
| value | - | Wert, mit dem die Elemente verglichen werden sollen |
| comp | - | Vergleichsfunktion, die auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
true, wenn ein Element gleich value gefunden wird, andernfalls false.
[edit] Komplexität
Die Anzahl der Vergleiche und Projektionen ist logarithmisch zur Distanz zwischen first und last (maximal log2(last - first) + O(1) Vergleiche und Projektionen). Für ein Iterator-Sentinel-Paar, das std::random_access_iterator nicht modelliert, ist die Anzahl der Iterator-Inkremente jedoch linear.
[edit] Anmerkungen
std::ranges::binary_search gibt keinen Iterator zu dem gefundenen Element zurück, wenn ein Element gefunden wird, dessen Projektion gleich value ist. Wenn ein Iterator benötigt wird, sollte stattdessen std::ranges::lower_bound verwendet werden.
| 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 binary_search_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 bool operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const { auto x = ranges::lower_bound(first, last, value, comp, proj); return (!(x == last) && !(std::invoke(comp, value, std::invoke(proj, *x)))); } 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 bool operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), value, std::move(comp), std::move(proj)); } }; inline constexpr binary_search_fn binary_search; |
[edit] Beispiel
#include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <ranges> #include <vector> int main() { constexpr static auto haystack = {1, 3, 4, 5, 9}; static_assert(std::ranges::is_sorted(haystack)); for (const int needle : std::views::iota(1) | std::views::take(3)) { std::cout << "Searching for " << needle << ": "; std::ranges::binary_search(haystack, needle) ? std::cout << "found " << needle << '\n' : std::cout << "no dice!\n"; } using CD = std::complex<double>; std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}}; auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); }; #ifdef __cpp_lib_algorithm_default_value_type assert(std::ranges::binary_search(nums, {4, 2}, cmpz)); #else assert(std::ranges::binary_search(nums, CD{4, 2}, cmpz)); #endif }
Ausgabe
Searching for 1: found 1 Searching for 2: no dice! Searching for 3: found 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) |
Gibt einen Iterator zum ersten Element zurück, das *größer* als ein bestimmter Wert ist (Algorithmus-Funktionsobjekt) |
| (C++23)(C++23) |
Prüft, ob der Bereich das gegebene Element oder den gegebenen Teilbereich enthält (Algorithmus-Funktionsobjekt) |
| Stellt fest, ob ein Element in einem teilweise geordneten Bereich vorhanden ist (Funktionstemplate) |
