std::ranges::find_end
De cppreference.com
<tbody>
</tbody>
| Definido en el archivo de encabezado <algorithm>
|
||
| Signatura de la 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) |
1) Busca la última ocurrencia de la secuencia [first2, last2) en el rango [first1, last1), después de la proyección con
proj1 y proj2, respectivamente. Los elementos proyectados se comparan usando el predicado binario pred.2) Igual que (1), pero usa
r1 como el primer rango fuente y r2 como el segundo rango fuente, como si usara ranges::begin(r1) como first1, ranges::end(r1) como last1, ranges::begin(r2) como first2, y ranges::end(r2) como last2.Las entidades similares a funciones descritas en esta página son niebloids, es decir:
- Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a cualquiera de ellas.
- Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
- Cuando alguna de ellas se encuentra mediante la búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.
En la práctica, pueden implementarse como objetos función o con extensiones de compilador especiales.
Parámetros
| first1, last1 | - | El rango de los elementos a examinar (p. ej., pajar). |
| first2, last2 | - | El rango de los elementos a buscar (p. ej., aguja). |
| r1 | - | El rango de los elementos a examinar (p. ej., pajar). |
| r2 | - | El rango de los elementos a buscar (p. ej., aguja). |
| pred | - | Predicado binario para comparar los elementos. |
| proj1 | - | Proyección a aplicar a los elementos en el primer rango. |
| proj2 | - | Proyección a aplicar a los elementos en el segundo rango. |
Valor de retorno
1) Un subrango de tipo
ranges::subrange<I1>{} inicializado por valor con la expresión {i, i + (i == last1 ? 0 : ranges::distance(first2, last2))} que denota la última ocurrencia de la secuencia [first2, last2) en el rango [first1, last1) (después de las proyecciones con proj1 y proj2). Si [first2, last2) está vacío o si no se encuentra tal secuencia, el valor de retorno efectivamente se inicializa con {last1, last1}.2) Igual que (1), excepto que el tipo de retorno es
ranges::borrowed_subrange_t<R1>.Complejidad
A lo sumo S·(N-S+1) aplicaciones del predicado correspondiente y cada proyección, donde S es ranges::distance(first2, last2) y N es ranges::distance(first1, last1) para (1), o S es ranges::distance(r2) y N es ranges::distance(r1) para (2).
Notas
Una implementación puede mejorar la eficiencia de la búsqueda si los iteradores de entrada modelan std::bidirectional_iterator buscando desde el final hacia el principio. Modelar std::random_access_iterator puede mejorar la velocidad de comparación. Sin embargo, todo esto no cambia la complejidad teórica del peor de los casos.
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::end(r1),
ranges::begin(r2), ranges::end(r2),
std::move(pred),
std::move(proj1), std::move(proj2));
}
};
inline constexpr find_end_fn find_end{};
|
Ejemplo
Ejecuta este código
#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
void imprimir(const auto pajar, const auto aguja)
{
const auto pos = std::distance(pajar.begin(), aguja.begin());
std::cout << "En \"";
for (const auto c : pajar) { std::cout << c; }
std::cout << "\" se encontró \"";
for (const auto c : aguja) { std::cout << c; }
std::cout << "\" en la posición [" << pos << ".." << pos + aguja.size() << ")\n"
<< std::string(4 + pos, ' ') << std::string(aguja.size(), '^') << '\n';
}
int main()
{
using namespace std::literals;
constexpr auto secreto{"contraseña contraseña seña..."sv};
constexpr auto deseada{"contraseña"sv};
constexpr auto encontrado1 = std::ranges::find_end(
secreto.cbegin(), secreto.cend(), deseada.cbegin(), deseada.cend());
imprimir(secreto, encontrado1);
constexpr auto encontrado2 = std::ranges::find_end(secreto, "seña"sv);
imprimir(secreto, encontrado2);
const auto encontrado3 = std::ranges::find_end(secreto, "TRA"sv,
[](const char x, const char y) { // usa un predicado binario
return std::tolower(x) == std::tolower(y);
});
imprimir(secreto, encontrado3);
const auto encontrado4 = std::ranges::find_end(secreto, "ASEÑA"sv, {}, {},
[](char c) { return std::tolower(c); }); // proyecta el segundo rango
imprimir(secreto, encontrado4);
static_assert(std::ranges::find_end(secreto, "CLAVE"sv).empty()); // => no se encontró
}
Salida:
En "contraseña contraseña contra..." se encontró "contraseña" en la posición [9..17)
^^^^^^^^^^
En "contraseña contraseña contra..." se encontró "seña" en la posición [18..22)
^^^^^^
En "contraseña contraseña contra..." se encontró "tra" en la posición [19..22)
^^^
En "contraseña contraseña contra..." se encontró "aseña" en la posición [12..17)
^^^^^
Véase también
(C++23)(C++23)(C++23) |
Encuentra el último elemento que satisfaga un criterio específico. (niebloid) |
(C++20)(C++20)(C++20) |
Encuentra el primer elemento que satisfaga un criterio específico. (niebloid) |
(C++20) |
Busca por cualquiera de un conjunto de elementos. (niebloid) |
(C++20) |
Encuentra dos primeros elementos contiguos idénticos (o que satisfagan un predicado dado). (niebloid) |
(C++20) |
Busca una subsecuencia de elementos en un rango. (niebloid) |
(C++20) |
Busca un número de copias consecutivas de un elemento en un rango. (niebloid) |
| Encuentra la última secuencia de elementos en un cierto rango. (plantilla de función) |