Пространства имён
Варианты
Действия

search

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Библиотека алгоритмов
Ограниченные алгоритмы и алгоритмы над диапазонами (C++20)
Ограниченные алгоритмы, например ranges::copy, ranges::sort, ...
Политики исполнения (C++17)
Немодифицирующие операции над последовательностями
(C++11)(C++11)(C++11)
(C++17)
Модифицирующие операции над последовательностями
Операции разбиения
Операции сортировки
(C++11)
Операции двоичного поиска
Операции с наборами (в отсортированных диапазонах)
Операции с кучей
(C++11)
Операций минимума/максимума
(C++11)
(C++17)

Операции перестановки
Числовые операции
Операции с неинициализированной памятью
(C++17)
(C++17)
(C++17)
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class ForwardIt1, class ForwardIt2 >

ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,

                   ForwardIt2 s_first, ForwardIt2 s_last );
(1)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >

ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,

                   ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
(2)

Ищет первое вхождение последовательности элементов [s_first, s_last) в диапазон [first, last - (s_last - s_first)). Первый вариант использует operator== для сравнения элементов, второй вариант использует заданный бинарный предикат p.

Содержание

[править] Параметры

first, last диапазон элементов для проверки
s_first, s_last диапазон искомых элементов
p бинарный предикат, который возвращает ​true если элементы следует считать равными.

Определение функции предиката должно быть эквивалентно следующему:

 bool pred(const Type1 &a, const Type2 &b);

Определение не должно обязательно содержать const &, но функция не должна модифицировать принимаемые объекты.
Типы Type1 и Type2 должны быть таковы, что объекты типов ForwardIt1 и ForwardIt2 могут быть разыменованы и затем неявно преобразованы в Type1 и Type2 соответственно.

Требования к типам
-
ForwardIt1 должен соответствовать требованиям ForwardIterator.
-
ForwardIt2 должен соответствовать требованиям ForwardIterator.

[править] Возвращаемое значение

Итератор на начало первой подпоследовательности [s_first, s_last) в диапазоне [first, last - (s_last - s_first)). Если такая последовательность не найдена, возвращается last.

Если [s_first, s_last) пуста, возвращается first. (начиная с C++11)

[править] Сложность

Не больше S*N сравнений, где S = std::distance(s_first, s_last), N = std::distance(first, last).

[править] Возможная реализация

Первый вариант
template<class ForwardIt1, class ForwardIt2>
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 s_first, ForwardIt2 s_last)
{
    for (; ; ++first) {
        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;
            }
        }
    }
}
Второй вариант
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 s_first, ForwardIt2 s_last,
                        BinaryPredicate p)
{
    for (; ; ++first) {
        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;
            }
        }
    }
}

[править] Пример

#include <string>
#include <algorithm>
#include <iostream>
 
template<typename Container>
bool in_quote(const Container& cont, const std::string& s)
{
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
 
int main()
{
    std::string str = "Зачем тратить время на обучение, если невежество приходит мгновенно?";
    // также может использоваться str.find()
    std::cout << std::boolalpha << in_quote(str, "обучение") << '\n'
                                << in_quote(str, "обручение")  << '\n';
 
    std::vector<char> vec(str.begin(), str.end());
    std::cout << std::boolalpha << in_quote(vec, "обучение") << '\n'
                                << in_quote(vec, "обручение")  << '\n';
}

Вывод:

true
false
true
false

[править] См. также

находит последнюю последовательность элементов в определённом диапазоне
(шаблон функции) [править]
определяет, одинаковы ли два множества элементов
(шаблон функции) [править]
находит первый элемент, соответствущий определённым критериям
(шаблон функции) [править]
возвращает true, если один диапазон лексикографически меньше другого
(шаблон функции) [править]
находит первую позицию, в которой два диапазона различаются
(шаблон функции) [править]
ищет несколько последовательных копий элемента в диапазоне
(шаблон функции) [править]