std::search

Материал из cppreference.com

Заголовочный файл `<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;
            }
        }
    }
}

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

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


find_end	находит последний последовательности элементов в определенном диапазоне Original: finds the last sequence of elements in a certain range The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

equal	определяет, будет ли два множества элементов одинаковы Original: determines if two sets of elements are the same The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

find find_if find_if_not (C++11)	находит первый элемент, удовлетворяющий определенным критериям Original: finds the first element satisfying specific criteria The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

lexicographical_compare	возвращает истину, если один диапазон лексикографически меньше, чем другой Original: returns true if one range is lexicographically less than another The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

mismatch	находит первое положение, в котором два диапазона отличаются Original: finds the first position where two ranges differ The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

search_n	поиск в течение ряда последовательных копий элемента в диапазоне Original: searches for a number consecutive copies of an element in a range The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

Язык
Понятия (концепции)
Утилиты
Строки
Контейнеры
Алгоритмы
Итераторы
Работа с числами
Ввод / вывод
Локализация
Регулярные выражения (C++11)
Атомарные примитивы (C++11)
Потоки (C++11)

cppreference.com

Поиск

Пространства имён

Варианты

Просмотры

Действия