std::ranges::find_end
De es.cppreference.net
| Definido en el encabezado <algorithm>
|
||
| Signatura de llamada |
||
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) | (desde 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) | (desde 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) | (desde 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) | (desde C++26) |
Para la definición de /*execution-policy*/, véase esta página; para la definición de /*sized-random-access-range*/, véase esta página.
Busca la última aparición del rango objetivo en el rango fuente. Los elementos (proyectados por proj1 y proj2 respectivamente) se comparan utilizando el predicado binario pred.
1) El rango fuente es
[first1, last1), y el rango objetivo es [first2, last2).2) El rango fuente es
r1, y el rango objetivo es r2.3,4) Igual que (1,2), pero ejecutado de acuerdo a
policy.Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (conocidos informalmente como niebloids), es decir:
- No se pueden especificar listas de argumentos de plantilla explícitas al llamar a cualquiera de ellos.
- Ninguno de ellos es visible para la búsqueda dependiente de argumentos.
- Cuando cualquiera de ellos se encuentra mediante búsqueda no cualificada normal como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.
Parámetros
| first1, last1 | - | el par iterador-centinela que define el origen rango |
| first2, last2 | - | el par iterador-centinela que define el destino rango |
| r1 | - | el rango de origen |
| r2 | - | el rango de destino |
| pred | - | el predicado a aplicar a los elementos (proyectados) |
| proj1 | - | la proyección a aplicar a los elementos del rango de origen |
| proj2 | - | la proyección a aplicar a los elementos del rango de destino |
| policy | - | la política de ejecución a utilizar |
Valor de retorno
Un subrango correspondiente a la última aparición del rango objetivo en el rango fuente.
Si el rango objetivo está vacío o no aparece en el rango fuente, se devuelve un rango vacío.
Complejidad
Dados N1 como ranges::distance(first1, last1) o ranges::distance(r1), y N2 como ranges::distance(first2, last2) o ranges::distance(r2):
1,2) Como máximo N2⋅(N1-N2+1) aplicaciones de
pred y proj.3,4) 𝓞(N2⋅(N1-N2+1)) aplicaciones de
pred y proj.Excepciones
3,4) Durante el proceso de ejecución:
- Si los recursos de memoria temporal necesarios para la paralelización no están disponibles, std::bad_alloc se lanza.
- Si se lanza una excepción no capturada al acceder a objetos a través de un argumento de algoritmo, el comportamiento está determinado por la política de ejecución (para políticas estándar, se invoca std::terminate).
Notas
Una implementación puede mejorar la eficiencia de la búsqueda si los tipos de iterador modelan bidirectional_iterator buscando desde el final hacia el inicio. Modelar random_access_iterator puede mejorar la velocidad de comparación. Sin embargo, todo esto no cambia la complejidad teórica del peor caso.
Posible implementación
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{};
|
Ejemplo
Ejecutar este código
#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
}
Salida:
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)
^^^^^
Véase también
| encuentra la última secuencia de elementos en un rango determinado (plantilla de función) | |
(C++23)(C++23)(C++23) |
encuentra el último elemento que satisface criterios específicos (objeto función de algoritmo) |
(C++20)(C++20)(C++20) |
encuentra el primer elemento que satisface criterios específicos (objeto función de algoritmo) |
(C++20) |
busca cualquiera de un conjunto de elementos (objeto función de algoritmo) |
(C++20) |
encuentra los dos primeros elementos adyacentes que son iguales (o satisfacen un predicado dado) (objeto función de algoritmo) |
(C++20) |
busca la primera aparición de un rango de elementos (objeto función de algoritmo) |
(C++20) |
busca la primera aparición de un número de copias consecutivas de un elemento en un rango (objeto función de algoritmo) |