std::ranges::find_end
Von de.cppreference.net
| Definiert in Header <algorithm>
|
||
| Aufrufsignatur |
||
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>
find_end( I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (seit C++20) |
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>
find_end( R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (seit C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I1, std::sized_sentinel_for<I1> S1,
std::random_access_iterator I2, std::sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
ranges::subrange<I1> find_end( Ep&& policy, I1 first1, S1 last1,
I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(3) | (seit C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R1,
/*sized-random-access-range*/ R2,
class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires std::indirectly_comparable<ranges::iterator_t<R1>,
ranges::iterator_t<R2>,
Pred, Proj1, Proj2>
ranges::borrowed_subrange_t<R1>
find_end( Ep&& policy, R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(4) | (seit C++26) |
Für die Definition von /*execution-policy*/, siehe diese Seite; für die Definition von /*sized-random-access-range*/, siehe diese Seite.
Sucht nach dem letzten Vorkommen des Zielbereichs im Quellbereich. Die Elemente (projiziert durch proj1 bzw. proj2) werden mit dem binären Prädikat pred verglichen.
1) Der Quellbereich ist
[first1, last1) und der Zielbereich ist [first2, last2).2) Der Quellbereich ist
r1 und der Zielbereich ist r2.3,4) Dasselbe wie (1,2), jedoch ausgeführt gemäß
policy.Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:
- Explizite Vorlagenargumentlisten können beim Aufruf keiner von ihnen angegeben werden.
- Keine von ihnen sind für die argumentabhängige Suche sichtbar.
- Wenn eine von ihnen durch normale unqualifizierte Suche als der Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Suche unterbunden.
Parameter
| first1, last1 | - | das Iterator-Sentinel-Paar, das den Quellbereich definiertBereich |
| first2, last2 | - | das Iterator-Sentinel-Paar, das den Zielbereich definiertBereich |
| r1 | - | der Quellbereich |
| r2 | - | der Zielbereich |
| pred | - | das Prädikat, das auf die (projizierten) Elemente angewendet wird |
| proj1 | - | die Projektion, die auf die Elemente im Quellbereich angewendet wird |
| proj2 | - | die Projektion, die auf die Elemente im Zielbereich angewendet wird |
| policy | - | die Ausführungsrichtlinie zur Verwendung |
Rückgabewert
Ein Teilbereich, der dem letzten Vorkommen des Zielbereichs im Quellbereich entspricht.
Wenn der Zielbereich leer ist oder nicht im Quellbereich vorkommt, wird ein leerer Bereich zurückgegeben.
Komplexität
Gegeben N1 als ranges::distance(first1, last1) oder ranges::distance(r1), und N2 als ranges::distance(first2, last2) oder ranges::distance(r2):
1,2) Höchstens N2⋅(N1-N2+1) Anwendungen von
pred und proj.3,4) 𝓞(N2⋅(N1-N2+1)) Anwendungen von
pred und proj.Ausnahmen
3,4) Während der Ausführung:
- Wenn die für die Parallelisierung erforderlichen temporären Speicherressourcen nicht verfügbar sind, wird std::bad_alloc ausgelöst.
- Wenn beim Zugriff auf Objekte über ein Algorithmus-Argument eine nicht abgefangene Ausnahme ausgelöst wird, wird das Verhalten durch die Ausführungsrichtlinie bestimmt (für Standardrichtlinien wird std::terminate aufgerufen).
Anmerkungen
Eine Implementierung kann die Effizienz der Suche verbessern, wenn die Iteratortypen das Konzept bidirectional_iterator erfüllen, indem sie vom Ende zum Anfang sucht. Die Erfüllung von random_access_iterator kann die Vergleichsgeschwindigkeit verbessern. Dies ändert jedoch nicht die theoretische Komplexität des schlechtesten Falls.
Mögliche Implementierung
struct find_end_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
{
if (first2 == last2)
{
auto last_it = ranges::next(first1, last1);
return {last_it, last_it};
}
auto result = ranges::search(std::move(first1), last1,
first2, last2, pred, proj1, proj2);
if (result.empty())
return result;
for (;;)
{
auto new_result = ranges::search(std::next(result.begin()), last1,
first2, last2, pred, proj1, proj2);
if (new_result.empty())
return result;
else
result = std::move(new_result);
}
}
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::next(ranges::begin(r1), ranges::end(r1)),
ranges::begin(r2),
ranges::next(ranges::begin(r2), ranges::end(r2)),
std::move(pred), std::move(proj1), std::move(proj2));
}
};
inline constexpr find_end_fn find_end{};
|
Beispiel
Diesen Code ausführen
#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
void print(const auto haystack, const auto needle)
{
const auto pos = std::distance(haystack.begin(), needle.begin());
std::cout << "In \"";
for (const auto c : haystack)
std::cout << c;
std::cout << "\" found \"";
for (const auto c : needle)
std::cout << c;
std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
<< std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
int main()
{
using namespace std::literals;
using std::ranges::find_end;
constexpr auto secret{"password password word..."sv};
constexpr auto wanted{"password"sv};
constexpr auto found1 = find_end(secret.cbegin(), secret.cend(),
wanted.cbegin(), wanted.cend());
print(secret, found1);
constexpr auto found2 = find_end(secret, "word"sv);
print(secret, found2);
const auto found3 = find_end(secret, "ORD"sv,
[](const char x, const char y)
{ // uses a binary predicate
return std::tolower(x) == std::tolower(y);
});
print(secret, found3);
const auto found4 = find_end(secret, "SWORD"sv, {}, {},
[](char c) { return std::tolower(c); }); // projects the 2nd range
print(secret, found4);
static_assert(find_end(secret, "PASS"sv).empty()); // => not found
}
Ausgabe:
In "password password word..." found "password" at position [9..17)
^^^^^^^^
In "password password word..." found "word" at position [18..22)
^^^^
In "password password word..." found "ord" at position [19..22)
^^^
In "password password word..." found "sword" at position [12..17)
^^^^^
Siehe auch
| findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktionsschablone) | |
(C++23)(C++23)(C++23) |
findet das letzte Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt) |
(C++20)(C++20)(C++20) |
findet das erste Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt) |
(C++20) |
sucht nach einem beliebigen Element aus einer Menge (Algorithmus-Funktionsobjekt) |
(C++20) |
findet die ersten zwei benachbarten Elemente, die gleich sind (oder ein gegebenes Prädikat erfüllen) (Algorithmus-Funktionsobjekt) |
(C++20) |
sucht nach dem ersten Vorkommen eines Bereichs von Elementen (Algorithmus-Funktionsobjekt) |
(C++20) |
sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt) |