std::search

Определён в заголовочном файле `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );	(1)	(constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );	(2)	(начиная с C++17)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p );	(3)	(constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p );	(4)	(начиная с C++17)
template< class ForwardIt, class Searcher > ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );	(5)	(начиная с C++17) (constexpr начиная с C++20)

1-4) Ищет первое вхождение последовательности элементов [s_first, s_last) в диапазоне [first, last).

1) Элементы сравниваются с помощью operator==.

3) Элементы сравниваются с помощью заданного бинарного предиката p.

2,4) То же, что и (1,3), но выполняется в соответствии с policy.

Эти перегрузки участвуют в разрешении перегрузки только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

5) Ищет в диапазоне [first, last) образец, заданный в конструкторе searcher.

Стандартная библиотека предоставляет следующие поисковые объекты:

default_searcher (C++17)	реализация алгоритма поиска стандартной библиотеки C++ (шаблон класса)
boyer_moore_searcher (C++17)	реализация алгоритма поиска Бойера-Мура (шаблон класса)
boyer_moore_horspool_searcher (C++17)	реализация алгоритма поиска Бойера-Мура-Хорспула (шаблон класса)

(начиная с C++17)

Параметры

first, last	-	пара итераторов, определяющих диапазон элементов для проверки
s_first, s_last	-	пара итераторов, определяющих диапазон элементов для поиска
policy	-	политика выполнения, которая будет использоваться
searcher	-	объект поиска, инкапсулирующий алгоритм поиска и шаблон для поиска
p	-	бинарный предикат, который возвращает true если элементы должны рассматриваться как равные. Сигнатура функции-предиката должна быть эквивалентна следующей: bool pred ( const Type1 & a, const Type2 & b ) ; Хотя сигнатура не обязана иметь const & , функция не должна модифицировать передаваемые ей объекты и должна быть способна принимать все значения типов (возможно const) `Type1` и `Type2` независимо от категории значения (следовательно, Type1 & не допускается , как и Type1 , если для `Type1` перемещение не эквивалентно копированию (начиная с C++11) ). Типы Type1 и Type2 должны быть такими, чтобы объекты типов ForwardIt1 и ForwardIt2 могли быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно.
Требования к типам
- `ForwardIt1, ForwardIt2` должны удовлетворять требованиям LegacyForwardIterator .
- `BinaryPred` должен удовлетворять требованиям BinaryPredicate .

Возвращаемое значение

1-4) Итератор на начало первого вхождения последовательности

s_first

s_last

в диапазоне

first

last

. Если такое вхождение не найдено, возвращается last .

Если

s_first

s_last

пуст, first возвращается.

5) searcher ( first, last ) . first .

Сложность

1-4) Дано

N

как std:: distance ( first, last ) и

S

как std:: distance ( s_first, s_last ) :

1,2) Не более

N\cdotS

сравнений с использованием operator == .

3,4) Максимум

N\cdotS

применений предиката p .

5) Зависит от searcher .

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной как часть алгоритма, выбрасывает исключение и ExecutionPolicy является одним из стандартных политик , std::terminate вызывается. Для любой другой ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удается выделить память, std::bad_alloc выбрасывается.

Возможная реализация

search (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
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 BinaryPred>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred 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;
    }
}

**Примечание:** Весь код C++ внутри тегов `

` и `` оставлен без изменений, как и требовалось. HTML-теги и атрибуты также сохранены в оригинальном виде. Переведены только текстовые элементы вне кодовых блоков.

Пример

Запустить этот код

#include <algorithm>
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>
using namespace std::literals;
bool contains(const auto& cont, std::string_view s)
{
    // str.find() (or str.contains(), since C++23) can be used as well
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
int main()
{
    const auto str{"why waste time learning, when ignorance is instantaneous?"sv};
    assert(contains(str, "learning"));
    assert(not contains(str, "lemming"));
    const std::vector vec(str.begin(), str.end());
    assert(contains(vec, "learning"));
    assert(not contains(vec, "leaning"));
    // The C++17 overload with searchers demo:
    constexpr auto quote
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };
    for (const auto word : {"pisci"sv, "Pisci"sv})
    {
        std::cout << "The string " << std::quoted(word) << ' ';
        const std::boyer_moore_searcher searcher(word.begin(), word.end());
        const auto it = std::search(quote.begin(), quote.end(), searcher);
        if (it == quote.end())
            std::cout << "not found\n";
        else
            std::cout << "found at offset " << std::distance(quote.begin(), it) << '\n';
    }
}

Вывод:

The string "pisci" found at offset 43
The string "Pisci" not found

Отчеты о дефектах

Следующие отчеты об изменениях в поведении, содержащие описания дефектов, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применяется к	Поведение в опубликованной версии	Корректное поведение
LWG 1205	C++98	возвращаемое значение было неясным, если `[` s_first `,` s_last `)` пусто	возвращает first в этом случае
LWG 1338	C++98	решение LWG issue 1205 было применено некорректно, приводя к возврату first если вхождение не найдено	возвращает last в этом случае
LWG 2150	C++98	условие "вхождения последовательности" было некорректным	исправлено

См. также

find_end	находит последнюю последовательность элементов в определённом диапазоне (шаблон функции & функциональный объект алгоритма)
ranges::find_end (C++20)
includes	определяет, является ли одна последовательность подпоследовательностью другой (шаблон функции & функциональный объект алгоритма)
ranges::includes (C++20)
equal	определяет, являются ли два набора элементов одинаковыми (шаблон функции & функциональный объект алгоритма)
ranges::equal (C++20)
findfind_iffind_if_not (C++11)	находит первый элемент, удовлетворяющий определённым критериям (шаблон функции & функциональный объект алгоритма)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
lexicographical_compare	сравнивает два диапазона лексикографически (шаблон функции & функциональный объект алгоритма)
ranges::lexicographical_compare (C++20)
mismatch	находит первую позицию, в которой два диапазона различаются (шаблон функции & функциональный объект алгоритма)
ranges::mismatch (C++20)
search_n	ищет первое вхождение последовательности из нескольких повторений элемента в диапазоне (шаблон функции & функциональный объект алгоритма)
ranges::search_n (C++20)
default_searcher (C++17)	реализация поискового алгоритма стандартной библиотеки C++ (шаблон класса)
boyer_moore_searcher (C++17)	реализация поискового алгоритма Бойера–Мура (шаблон класса)
boyer_moore_horspool_searcher (C++17)	реализация поискового алгоритма Бойера–Мура–Хорспула (шаблон класса)
ranges::search (C++20)	ищет первое вхождение диапазона элементов (функциональный объект алгоритма)

Поддержка компиляторов
Автономное и хостируемое окружение
Язык
Стандартная библиотека
Заголовочные файлы стандартной библиотеки
Именованные требования
Макросы проверки возможностей (C++20)
Библиотека поддержки языка
Библиотека концепций (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных методов
Библиотека даты и времени
Библиотека ввода/вывода
Библиотека файловой системы (C++17)
Библиотека поддержки параллелизма (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants