std::search_n

Определено в заголовке `<algorithm>`
	(1)
template< class ForwardIt, class Size, class T > ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );		(до C++20)
template< class ForwardIt, class Size, class T > constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );		(с C++20)
template< class ExecutionPolicy, class ForwardIt, class Size, class T > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value );	(2)	(с C++17)
	(3)
template< class ForwardIt, class Size, class T, class BinaryPredicate > ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );		(до C++20)
template< class ForwardIt, class Size, class T, class BinaryPredicate > constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );		(с C++20)
template< class ExecutionPolicy, class ForwardIt, class Size, class T, class BinaryPredicate > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p );	(4)	(с C++17)

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

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

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

2,4) То же, что и (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Параметры

first, last	-	диапазон элементов для проверки
count	-	длина искомой последовательности
value	-	значение искомых элементов
policy	-	стратегия выполнения. Подробности см. в стратегии выполнения.
p	-	бинарный предикат, который возвращает `true`, если элементы должны рассматриваться как равные. Подпись предикатной функции должна быть эквивалентной следующей: `bool pred(const Type1 &a, const Type2 &b);` Хотя подпись не обязательно должна иметь `const &`, функция не должна модифицировать объекты, передаваемые ей, и должна быть способна принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1 &` недопустимо, а также `Type1`, если для `Type1` перемещение эквивалентно копированию(с C++11)). Тип Type1 должен быть таким, чтобы объект типа ForwardIt можно было дереференцировать, а затем неявно преобразовать в Type1. Тип Type2 должен быть таким, чтобы объект типа T можно было неявно преобразовать в Type2.
Требования к типу
-`ForwardIt` должен удовлетворять требованиям LegacyForwardIterator.
-`Size` должен быть преобразуем к целочисленному типу.

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

Если count положительно, возвращает итератор в начало первой найденной последовательности в диапазоне [first, last). Каждая итерация it в последовательности должна удовлетворять следующему условию:

1,2) *it == value равно true.

3,4) p(*it, value) != false равно true.

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

Если count равно нулю или отрицательно, возвращается first.

Сложность

Учитывая N как std::distance(first, last):

1,2) не более N сравнений со значением с использованием operator==.

3,4) не более N применений предиката p.

Исключение

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

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

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

search_n (1)
template<class ForwardIt, class Size, class T> ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value) { if (count <= 0) return first; for (; first != last; ++first) { if (!(first == value)) continue; ForwardIt candidate = first; for (Size cur_count = 1; true; ++cur_count) { if (cur_count >= count) return candidate; // success ++first; if (first == last) return last; // exhausted the list if (!(first == value)) break; // too few in a row } } return last; }
search_n (3)
template<class ForwardIt, class Size, class T, class BinaryPredicate> ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPredicate p) { if (count <= 0) return first; for (; first != last; ++first) { if (!p(first, value)) continue; ForwardIt candidate = first; for (Size cur_count = 1; true; ++cur_count) { if (cur_count >= count) return candidate; // success ++first; if (first == last) return last; // exhausted the list if (!p(first, value)) break; // too few in a row } } return last; }

search_n (1)

template<class ForwardIt, class Size, class T>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value)
{
    if (count <= 0)
        return first;
 
    for (; first != last; ++first)
    {
        if (!(*first == value))
            continue;
 
        ForwardIt candidate = first;
 
        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // success
 
            ++first;
            if (first == last)
                return last; // exhausted the list
 
            if (!(*first == value))
                break; // too few in a row
        }
    }
    return last;
}

search_n (3)

template<class ForwardIt, class Size, class T, class BinaryPredicate>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value,
                   BinaryPredicate p)
{
    if (count <= 0)
        return first;
 
    for (; first != last; ++first)
    {
        if (!p(*first, value))
            continue;
 
        ForwardIt candidate = first;
 
        for (Size cur_count = 1; true; ++cur_count)
        {
            if (cur_count >= count)
                return candidate; // success
 
            ++first;
            if (first == last)
                return last; // exhausted the list
 
            if (!p(*first, value))
                break; // too few in a row
        }
    }
    return last;
}

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
 
template<class Container, class Size, class T>
[[nodiscard]]
constexpr bool consecutive_values(const Container& c, Size count, const T& v)
{
    return std::search_n(std::begin(c), std::end(c), count, v) != std::end(c);
}
 
int main()
{
    constexpr char sequence[] = "1001010100010101001010101";
 
    static_assert(consecutive_values(sequence, 3, '0'));
 
    std::cout << std::boolalpha
              << "Has 4 consecutive zeros: "
              << consecutive_values(sequence, 4, '0') << '\n'
              << "Has 3 consecutive zeros: "
              << consecutive_values(sequence, 3, '0') << '\n';
}

Вывод:

Has 4 consecutive zeros: false
Has 3 consecutive zeros: true

Отчеты об ошибках

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

DR	Применён к	Поведение, опубликованное	Правильное поведение
LWG 283	C++98	`T` должно было быть EqualityComparable, но тип значения `InputIt` не всегда `T`	убрано требование
LWG 426	C++98	верхний предел сложности был `N·count`, он отрицательный, если `count` отрицательное	верхний предел равен `0` если `count` неположительно
LWG 714	C++98	если `count > 0`, верхний предел сложности был `N·count`, но в худшем случае количество сравнений/операций всегда равно `N`	изменено верхний предел на `N` в этом случае

См. также

find_end	находит последнюю последовательность элементов в определенном диапазоне (шаблон функции)
findfind_iffind_if_not (C++11)	находит первый элемент, удовлетворяющий определенным критериям (шаблон функции)
search	ищет диапазон элементов (шаблон функции)
ranges::search_n (C++20)	ищет заданное число последовательных копий элемента в диапазоне (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/search_n