std::ranges::search
Von cppreference.com
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, |
(1) | (seit C++20) |
| template< ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, |
(2) | (seit C++20) |
1) Sucht nach dem ersten Vorkommen der Elementsequenz
[first2, last2) im Bereich [first1, last1). Elemente werden mit dem binären Prädikat pred verglichen, nachdem sie jeweils mit proj2 und proj1 projiziert wurden.2) Dasselbe wie (1), verwendet jedoch r1 als ersten Quellbereich und r2 als zweiten Quellbereich, als ob ranges::begin(r1) als first1, ranges::end(r1) als last1, ranges::begin(r2) als first2 und ranges::end(r2) als last2 verwendet würden.
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
| first1, last1 | - | das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente definiert (auch Haystack genannt) |
| first2, last2 | - | das Iterator-Sentinel-Paar, das den Bereich der zu suchenden Elemente definiert (auch Needle genannt) |
| r1 | - | der Bereich der zu untersuchenden Elemente (auch Haystack genannt) |
| r2 | - | der Bereich der zu suchenden Elemente (auch Needle genannt) |
| pred | - | binäres Prädikat, das auf die projizierten Elemente angewendet wird |
| proj1 | - | Projektion, die auf die Elemente im ersten Bereich angewendet wird |
| proj2 | - | Projektion, die auf die Elemente im zweiten Bereich angewendet wird |
[edit] Rückgabewert
1) Gibt einen ranges::subrange-Wert zurück, der das erste Vorkommen der Sequenz
[first2, last2) (auch Needle genannt) im Bereich [first1, last1) (auch Haystack genannt) darstellt, nach Anwendung der Projektionen proj1 und proj2 auf die Elemente beider Sequenzen, gefolgt von der Anwendung des binären Prädikats pred zum Vergleichen der projizierten Elemente.Wenn kein solches Vorkommen gefunden wird, wird ranges::subrange{last1, last1} zurückgegeben.
Wenn der zu durchsuchende Bereich (auch Needle genannt) leer ist, d. h. first2 == last2, wird ranges::subrange{first1, first1} zurückgegeben.[edit] Komplexität
Höchstens S * N Anwendungen des entsprechenden Prädikats und jeder Projektion, wobei
(1) S = ranges::distance(first2, last2) und N = ranges::distance(first1, last1);
(2) S = ranges::distance(r2) und N = ranges::distance(r1).
[edit] Mögliche Implementierung
struct search_fn { template<std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2> constexpr ranges::subrange<I1> operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (;; ++first1) { I1 it1 = first1; for (I2 it2 = first2;; ++it1, ++it2) { if (it2 == last2) return {first1, it1}; if (it1 == last1) return {it1, it1}; if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) break; } } } template<ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity> requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2> constexpr ranges::borrowed_subrange_t<R1> operator()(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(pred), std::move(proj1), std::move(proj2)); } }; inline constexpr search_fn search {}; |
[edit] Beispiel
Führen Sie diesen Code aus
#include <algorithm> #include <cctype> #include <iostream> #include <iterator> #include <string_view> using namespace std::literals; void print(int id, const auto& haystack, const auto& needle, const auto& found) { std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); "; const auto first = std::distance(haystack.begin(), found.begin()); const auto last = std::distance(haystack.begin(), found.end()); if (found.empty()) std::cout << "not found;"; else { std::cout << "found: \""; for (const auto x : found) std::cout << x; std::cout << "\";"; } std::cout << " subrange: {" << first << ", " << last << "}\n"; } int main() { constexpr auto haystack {"abcd abcd"sv}; constexpr auto needle {"bcd"sv}; // the search uses iterator pairs begin()/end(): constexpr auto found1 = std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // the search uses ranges r1, r2: constexpr auto found2 = std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // 'needle' range is empty: constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' will not be found: constexpr auto awl {"efg"sv}; constexpr auto found4 = std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // the search uses custom comparator and projections: constexpr auto bodkin {"234"sv}; auto found5 = std::ranges::search(haystack, bodkin, [](const int x, const int y) { return x == y; }, // pred [](const int x) { return std::toupper(x); }, // proj1 [](const int y) { return y + 'A' - '1'; }); // proj2 print(5, haystack, bodkin, found5); }
Ausgabe
1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}[edit] Siehe auch
| (C++20) |
Findet die ersten beiden benachbarten Elemente, die gleich sind (oder eine gegebene Bedingung erfüllen) (Algorithmus-Funktionsobjekt) |
| (C++20)(C++20)(C++20) |
Findet das erste Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt) |
| (C++20) |
Findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sucht nach einem der Elemente aus einer Menge von Elementen (Algorithmus-Funktionsobjekt) |
| (C++23)(C++23) |
Prüft, ob der Bereich das gegebene Element oder den gegebenen Teilbereich enthält (Algorithmus-Funktionsobjekt) |
| (C++20) |
Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Findet die erste Position, an der sich zwei Bereiche unterscheiden (Algorithmus-Funktionsobjekt) |
| (C++20) |
Sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt) |
| Sucht nach dem ersten Vorkommen eines Elementbereichs (Funktionstempelat) |
