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

std::search

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека 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

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

Ищет последнее вхождение подпоследовательности элементов в диапазон
(шаблон функции) [edit]
Определяет, одинаковы ли два множества элементов
(шаблон функции) [edit]
Находит первый элемент, удовлетворяющий определенным критериям
(шаблон функции) [edit]
возвращает истину, если один диапазон лексикографически меньше, чем другой
Оригинал:
returns true if one range is lexicographically less than another
Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

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