std::search - cppreference.com

De cppreference.com

</tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody>

Definido en el archivo de encabezado `<algorithm>`
	(1)
`template< class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );`			(hasta C++20)
`template< class ForwardIt1, class ForwardIt2 > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );`			(desde C++20)
`template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );`		(2)	(desde C++17)
		(3)
`template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );`				(hasta C++20)
`template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );`				(desde C++20)
`template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );`			(4)	(desde C++17)
			(5)
`template< class ForwardIt, class Searcher > ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );`					(desde C++17) (hasta C++20)
`template< class ForwardIt, class Searcher > constexpr ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );`					(desde C++20)

1-4) Busca la primera ocurrencia de la secuencia de elementos [s_first, s_last) en el rango [first, last).

1) Los elementos se comparan usando operator==.

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

2,4) Igual que (1,3), pero ejecutado de acuerdo a la política de ejecución policy. Estas sobrecargas no participan en la resolución de sobrecarga a menos que 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) sea verdadera.

5) Busca la secuencia [first, last) por el patrón especificado en el constructor de searcher. Efectivamente ejecuta return searcher(first, last).first;. Searcher no tiene que ser CopyConstructible.

La biblioteca estándar proporciona los siguientes buscadores:

(desde C++17)

Parámetros

first, last	-	El rango de los elementos a examinar.
s_first, s_last	-	El rango de la secuencia de elementos a buscar.
policy	-	La política de ejecución a usar. Véase política de ejecución para más detalles.
searcher	-	El buscador que encapsula el algoritmo de búsqueda y el patrón a buscar.
p	-	Predicado binario que devuelve `true` si los elementos deben tratarse como iguales. La signatura de la función predicado deberá ser equivalente a la siguiente: `bool pred(const Tipo1 &a, const Tipo2 &b);` Mientras que la signatura no necesita tener `const &`, la función no debe modificar los objetos que se le han pasado y debe ser capaz de aceptar todos los valores de tipo (posiblemente `const`) `Tipo1` y `Tipo2` independientemente de la categoría de valor (por lo tanto, no se permite `Tipo1 &`, ni `Tipo1` a menos que para `Tipo1` un movimiento sea equivalente a una copia (desde C++11)). Los tipos `Tipo1` y `Tipo2` deben ser tales que objetos de tipo `ForwardIt1` y `ForwardIt2` pueden ser desreferenciados y luego convertidos implícitamente a `Tipo1` and `Tipo2` respectively.
Requisitos de tipo
-`ForwardIt1, ForwardIt2` debe satisfacer los requisitos de ForwardIterator.
-`Searcher` debe satisfacer los requisitos de Searcher.

Valor de retorno

1-4) Iterador al comienzo de la primera ocurrencia de la secuencia [s_first, s_last) en el rango [first, last). Si no se encuentra tal ocurrencia, se devuelve last.

Si [s_first, s_last) está vacío, se devuelve first. (desde C++11)

5) Devuelve el resultado de searcher.operator(), es decir, un iterador a la ubicación en la que se encuentra la subcadena, o una copia de last si no se encontró.

Complejidad

1-4) A lo sumo S * N comparaciones, donde S = std::distance(s_first, s_last) y N = std::distance(first, last).

5) Depende del buscador.

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy (política de ejecución) reportan errores tales que:

Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y la política de ejecución es una de las tres políticas estándar, se llama a std::terminate. Para cualquier otra política de ejecución, el comportamiento está definido por la implementación.
Si el algoritmo falla al asignar memoria, se lanza std::bad_alloc.

Posible implementación

search (1)
template<class ForwardIt1, class ForwardIt2> constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last) { while (true) { ForwardIt1 it = first; for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) { if (s_it == s_last) return first; if (it == last) return last; if (!(it == s_it)) break; } ++first; } }
search (3)
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate> constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p) { while (true) { ForwardIt1 it = first; for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) { if (s_it == s_last) return first; if (it == last) return last; if (!p(it, s_it)) break; } ++first; } }

search (1)

template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!(*it == *s_it))
                break;
        }
        ++first;
    }
}

search (3)

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last,
                            BinaryPredicate p)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!p(*it, *s_it))
                break;
        }
        ++first;
    }
}

Ejemplo

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <vector>
using namespace std::literals;

bool contains(const auto& cont, std::string_view s)
{
    // str.find() (o str.contains(), desde C++23) también se puede usar
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}

int main()
{
    const auto str {"¿Por qué perder el tiempo aprendiendo, cuando la ignorancia es instantánea?"sv};

    std::cout << std::boolalpha
              << contains(str, "aprendiendo") << '\n'     // true
              << contains(str, "aprehendiendo")  << '\n'; // false

    const std::vector vec(str.begin(), str.end());
    std::cout << contains(vec, "aprendiendo") << '\n'     // true
              << contains(vec, "aprehendiendo")  << '\n'; // false

    // La sobrecarga de C++17 con demo de buscadores:
    constexpr auto pajar
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };

    for (const auto aguja : {"piscis"sv, "Piscis"sv})
    {
        const std::boyer_moore_searcher searcher(aguja.begin(), aguja.end());
        const auto it = std::search(pajar.begin(), pajar.end(), searcher);
        std::cout << "La cadena " << std::quoted(aguja) << ' ';
        if (it == pajar.end())
            std::cout << "no se encontró\n";
        else
            std::cout << "se encontró en el desplazamiento " << it - pajar.begin() << '\n';
    }
}

Salida:

true
false
true
false
La cadena "piscis" se encontró en el desplazamiento 43
La cadena "Piscis" no se encontró

Véase también

find_end	Encuentra la última secuencia de elementos en un cierto rango. (plantilla de función) [editar]
includes	Devuelve `true` si una secuencia es una subsecuencia de otra. (plantilla de función) [editar]
equal	Determina si dos conjuntos de elementos son iguales. (plantilla de función) [editar]
findfind_iffind_if_not (C++11)	Encuentra el primer elemento que satisfaga un criterio específico. (plantilla de función) [editar]
lexicographical_compare	Devuelve `true` si un rango es lexicográficamente menor que otro. (plantilla de función) [editar]
mismatch	Encuentra la primera posición donde dos rangos difieren. (plantilla de función) [editar]
search_n	Busca un número de copias consecutivas de un elemento en un rango. (plantilla de función) [editar]
default_searcher (C++17)	Implementación del algoritmo de búsqueda de la biblioteca estándar de C++. (plantilla de clase) [editar]
boyer_moore_searcher (C++17)	Implementación del algoritmo de búsqueda Boyer-Moore. (plantilla de clase) [editar]
boyer_moore_horspool_searcher (C++17)	Implementación del algoritmo de búsqueda Boyer-Moore-Horspool. (plantilla de clase) [editar]
ranges::search (C++20)	Busca una subsecuencia de elementos en un rango. (niebloid) [editar]