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

std::search_n

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class ForwardIt, class Size, class T >
ForwardIt1 search_n( ForwardIt first, ForwardIt last, Size count, const T& value );
(1)
template< class ForwardIt, class Size, class T, class BinaryPredicate >

ForwardIt1 search_n( ForwardIt first, ForwardIt last, Size count, const T& value,

                     BinaryPredicate p );
(2)

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

Содержание

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

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

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

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

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

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

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

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

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

Не больше last - first применений предиката.

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

Первый вариант
template<class ForwardIt, class Size, class T>
ForwardIt1 search_n(ForwardIt first, ForwardIt last,
                          Size count, const T& value)
{
    Size curr_count = 0;
    ForwardIt result, t_last = first;
    std::advance(t_last, std::distance(first, last) - count + 1);
 
    for (; first != t_last; first++) {
        curr_count = 0;
        result = first;
        while (*first == value) {
            curr_count++;
            if (curr_count == count) {
                return result;
            }
            ++first;
        }
    }
    return last;
}
Второй вариант
template<class ForwardIt, class Size, class T, class BinaryPredicate>
ForwardIt1 search_n(ForwardIt first, ForwardIt last,
                          Size count, const T& value, BinaryPredicate p)
{
    Size curr_count = 0;
    ForwardIt result, t_last = first;
    std::advance(t_last, std::distance(first, last) - count + 1);
 
    for (; first != t_last; first++) {
        curr_count = 0;
        result = first;
        while (p(*first == value)) {
            curr_count++;
            if (curr_count == count) {
                return result;
            }
            ++first;
        }
    }
    return last;
}

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

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

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