std::ranges::equal_range
| 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) sind.Der Bereich [first, last) muss mindestens teilweise in Bezug auf value geordnet sein, d.h. er muss alle folgenden Anforderungen erfüllen:
- partitioniert in Bezug auf element < value oder comp(element, value) (d.h. alle Elemente, für die der Ausdruck true ist, gehen allen Elementen voraus, für die der Ausdruck false ist).
- partitioniert in Bezug auf !(value < element) oder !comp(value, element).
- für alle Elemente gilt: wenn element < value oder comp(element, value) true ist, dann ist auch !(value < element) oder !comp(value, element) true.
Ein vollständig sortierter Bereich erfüllt diese Kriterien.
Die zurückgegebene Sicht wird aus zwei Iteratoren gebildet: einer zeigt auf das erste Element, das nicht kleiner als value ist, und der andere zeigt auf das erste Element, das größer als value ist. Der erste Iterator kann alternativ mit std::ranges::lower_bound() erhalten werden, der zweite mit std::ranges::upper_bound().
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 |
[bearbeiten] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente definiert |
| r | - | der zu untersuchende Elementbereich |
| value | - | Wert, mit dem die Elemente verglichen werden sollen |
| comp | - | wenn das erste Argument kleiner als (d.h. davor geordnet) das zweite ist |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[bearbeiten] Rückgabewert
std::ranges::subrange, das ein Paar von Iteratoren enthält, die den gesuchten Bereich definieren. Der erste zeigt auf das erste Element, das nicht kleiner als value ist, und der zweite zeigt auf das erste Element, das größer als value ist.
Wenn es keine Elemente gibt, die nicht kleiner als value sind, wird der letzte Iterator (Iterator, der gleich last oder ranges::end(r) ist) als erstes Element zurückgegeben. Ebenso, wenn es keine Elemente gibt, die größer als value sind, wird der letzte Iterator als zweites Element zurückgegeben.
[bearbeiten] Komplexität
Die Anzahl der durchgeführten Vergleiche ist logarithmisch zur Distanz zwischen first und last (höchstens 2 * log2(last - first) + O(1) Vergleiche). Für einen Iterator, der random_access_iterator nicht modelliert, ist die Anzahl der Iterator-Inkremente jedoch linear.
[bearbeiten] Mögliche Implementierung
struct equal_range_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 ranges::subrange<I> operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const { return ranges::subrange ( ranges::lower_bound(first, last, value, std::ref(comp), std::ref(proj)), ranges::upper_bound(first, last, value, std::ref(comp), std::ref(proj)) ); } 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_subrange_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 equal_range_fn equal_range; |
[bearbeiten] Anmerkungen
| Feature-Test-Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | Listeninitialisierung für Algorithmen (1,2) |
[bearbeiten] Beispiel
#include <algorithm> #include <compare> #include <complex> #include <iostream> #include <vector> struct S { int number {}; char name {}; // note: name is ignored by these comparison operators friend bool operator== (const S s1, const S s2) { return s1.number == s2.number; } friend auto operator<=>(const S s1, const S s2) { return s1.number <=> s2.number; } friend std::ostream& operator<<(std::ostream& os, S o) { return os << '{' << o.number << ", '" << o.name << "'}"; } }; void println(auto rem, const auto& v) { for (std::cout << rem; const auto& e : v) std::cout << e << ' '; std::cout << '\n'; } int main() { // note: not ordered, only partitioned w.r.t. S defined below std::vector<S> vec { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'} }; const S value{2, '?'}; namespace ranges = std::ranges; auto a = ranges::equal_range(vec, value); println("1. ", a); auto b = ranges::equal_range(vec.begin(), vec.end(), value); println("2. ", b); auto c = ranges::equal_range(vec, 'D', ranges::less {}, &S::name); println("3. ", c); auto d = ranges::equal_range(vec.begin(), vec.end(), 'D', ranges::less {}, &S::name); println("4. ", d); 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 p3 = ranges::equal_range(nums, {2, 0}, cmpz); #else auto p3 = ranges::equal_range(nums, CD{2, 0}, cmpz); #endif println("5. ", p3); }
Ausgabe
1. {2, 'B'} {2, 'C'} {2, 'D'}
2. {2, 'B'} {2, 'C'} {2, 'D'}
3. {2, 'D'} {4, 'D'}
4. {2, 'D'} {4, 'D'}
5. (2,2) (2,1)[bearbeiten] Siehe auch
| (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++20) |
Stellt fest, ob ein Element in einem teilweise geordneten Bereich vorhanden ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Teilt einen Bereich von Elementen in zwei Gruppen auf (Algorithmus-Funktionsobjekt) |
| (C++20) |
Bestimmt, ob zwei Elementmengen gleich sind (Algorithmus-Funktionsobjekt) |
| gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen (Funktionstemplate) |
