std::find_end

Definido en el encabezado `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(1)	(constexpr desde C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(constexpr desde C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(desde C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(4)	(desde C++17)

Busca la última aparición del rango objetivo [first2, last2) en el rango fuente [first1, last1).

1) Los elementos se comparan usando operator==.

2) Los elementos se comparan usando el predicado binario dado p.

3,4) Igual que (1,2), pero ejecutado de acuerdo con policy.

Estas sobrecargas participan en la resolución de sobrecargas solo si el valor de la siguiente expresión es true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(hasta C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(desde C++20)

Parámetros

first1, last1	-	el par de iteradores que definen el rango
fuente first2, last2	-	el par de iteradores que definen el rango
objetivo p	-	predicado binario que devuelve `true` si los elementos deben considerarse iguales. La firma de la función predicado debe ser equivalente a la siguiente: `bool pred(const Type1 &a, const Type2 &b);` Mientras que la firma no necesita tener `const &`, la función no debe modificar los objetos que se le pasan y debe ser capaz de aceptar todos los valores de tipo (posiblemente const) `Type1` y `Type2` independientemente de la categoría de valor (por lo tanto, `Type1 &` no está permitido, ni tampoco `Type1` a menos que para `Type1` un movimiento sea equivalente a una copia(desde C++11)). Los tipos `Type1` y `Type2` deben ser tales que los objetos de tipos `ForwardIt1` y `ForwardIt2` puedan ser desreferenciados y luego convertidos implícitamente a `Type1` y `Type2` respectivamente.
policy	-	la política de ejecución a utilizar
Requisitos de tipo
- `ForwardIt1` debe cumplir los requisitos de LegacyForwardIterator.
- `ForwardIt2` debe cumplir los requisitos de LegacyForwardIterator.

Valor de retorno

Iterador al inicio de 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 last1.

Complejidad

Dado $\scriptsize N_1$ $N 1$ como std::distance(first1, last1) y $\scriptsize N_2$ $N 2$ como std::distance(first2, last2):

1) Como máximo

N 2 \cdot(N 1 -N 2 +1)

comparaciones usando operator==.

2) Como máximo

N 2 \cdot(N 1 -N 2 +1)

aplicaciones de p.

3)

𝓞(N 2 \cdot(N 1 -N 2 +1))

comparaciones usando operator==.

4)

𝓞(N 2 \cdot(N 1 -N 2 +1))

aplicaciones de p.

Excepciones

3,4) Durante el proceso de ejecución:

Si los recursos de memoria temporal necesarios para la paralelización no están disponibles, se lanza std::bad_alloc.
Si se lanza una excepción no capturada mientras se accede 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).

Posible implementación

find_end (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2)
{
    if (first2 == last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, last2);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
{
    if (first2== last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, first2, p);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

Ejemplo

Ejecutar este código

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>

auto print_result = [](auto result, const auto& v)
{
    result == v.end()
        ? std::cout << "Sequence not found\n"
        : std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
                    << '\n';
};

int main()
{
    const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    
    for (const auto& x : {std::array{1, 2, 3}, {4, 5, 6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
        print_result(iter, v);
    }
    
    for (const auto& x : {std::array{-1, -2, -3}, {-4, -5, -6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
                                  [](int x, int y)
                                  {
                                      return std::abs(x) == std::abs(y);
                                  });
        print_result(iter, v);
    }
}

Salida:

Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found

Informes de defectos

Los siguientes informes de defectos que cambian el comportamiento se aplicaron retroactivamente a los estándares C++ previamente publicados.

DR	Aplicado a	Comportamiento como se publicó	Comportamiento correcto
LWG 1205	C++98	el valor de retorno no estaba claro si el rango objetivo está vacío	devuelve `last1` en este caso
LWG 2150	C++98	la condición de "aparición" era incorrecta	corregida

Véase también

ranges::find_end (C++20)	encuentra la última secuencia de elementos en un rango determinado (objeto función de algoritmo)
search	busca la primera aparición de un rango de elementos (plantilla de función & objeto función de algoritmo)
ranges::search (C++20)
includes	determina si una secuencia es una subsecuencia de otra (plantilla de función & objeto función de algoritmo)
ranges::includes (C++20)
adjacent_find	encuentra los dos primeros elementos adyacentes que son iguales (o satisfacen un predicado dado) (plantilla de función & objeto función de algoritmo)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	encuentra el primer elemento que satisface criterios específicos (plantilla de función & objeto función de algoritmo)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
find_first_of	busca cualquiera de un conjunto de elementos (plantilla de función & objeto función de algoritmo)
ranges::find_first_of (C++20)
search_n	busca la primera aparición de un número de copias consecutivas de un elemento en un rango (plantilla de función & objeto función de algoritmo)
ranges::search_n (C++20)

Soporte del compilador
Freestanding y hosted
Lenguaje
Biblioteca estándar
Encabezados de la biblioteca estándar
Requisitos nombrados
Macros de prueba de características (C++20)
Biblioteca de soporte del lenguaje
Biblioteca de conceptos (C++20)
Biblioteca de diagnóstico
Biblioteca de gestión de memoria
Biblioteca de metaprogramación (C++11)
Biblioteca de utilidades generales
Biblioteca de contenedores
Biblioteca de iteradores
Biblioteca de rangos (C++20)
Biblioteca de algoritmos
Biblioteca de cadenas
Biblioteca de procesamiento de texto
Biblioteca numérica
Biblioteca de fecha y hora
Biblioteca de entrada/salida
Biblioteca del sistema de archivos (C++17)
Biblioteca de soporte de concurrencia (C++11)
Biblioteca de control de ejecución (C++26)
Especificaciones técnicas
Índice de símbolos
Bibliotecas externas

es.cppreference.net

Namespaces

Variants