std::search_n

Определён в заголовочном файле `<algorithm>`
template< class ForwardIt, class Size, class T > ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );	(1)	(constexpr с C++20) (до C++26)
template< class ForwardIt, class Size, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );	(1)		(начиная с C++26)
template< class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred p );	(2)	(constexpr с C++20) (до C++26)
template< class ForwardIt, class Size, class T = typename std::iterator_traits <ForwardIt>::value_type, class BinaryPred > constexpr ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred p );	(2)		(начиная с C++26)
template< class ExecutionPolicy, class ForwardIt, class Size, class T > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value );	(3)	(начиная с C++17) (до C++26)
template< class ExecutionPolicy, class ForwardIt, class Size, class T = typename std::iterator_traits <ForwardIt>::value_type > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value );	(3)		(начиная с C++26)
template< class ExecutionPolicy, class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred p );	(4)	(начиная с C++17) (до C++26)
template< class ExecutionPolicy, class ForwardIt, class Size, class T = typename std::iterator_traits <ForwardIt>::value_type, class BinaryPred > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred p );	(4)		(начиная с C++26)

Выполняет поиск в исходном диапазоне [first, last) первого вхождения count последовательных элементов, равных value.

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

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

3,4) То же, что и (1,2), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки только в том случае, если значение следующего выражения является true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

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

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

Если count положительно, возвращает итератор на начало первого вхождения в исходном диапазоне.

Если count неположительно или такого вхождения в исходном диапазоне нет, возвращает last.

Сложность

Обозначим \(\scriptsize N\)N как std::distance(first, last):

1) Не более \(\scriptsize N\)N сравнений с помощью operator==.

2) Не более \(\scriptsize N\)N вызовов предиката p.

3) \(\scriptsize \mathcal{O}(N)\)𝓞(N) сравнений с помощью operator==.

4) \(\scriptsize \mathcal{O}(N)\)𝓞(N) вызовов предиката p.

Исключения

3,4) В процессе выполнения:

Если требуемые для распараллеливания временные ресурсы памяти недоступны, выбрасывается std::bad_alloc.
Если при доступе к объектам через аргумент алгоритма возникает необработанное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается std::terminate).

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

search_n (1)
template<class ForwardIt, class Size, class T = typename std::iterator_traits<ForwardIt>::value_type> 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 (2)
template<class ForwardIt, class Size, class T = typename std::iterator_traits<ForwardIt>::value_type, class BinaryPred> ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred 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 = typename std::iterator_traits<ForwardIt>::value_type>
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 (2)

template<class ForwardIt, class Size,
         class T = typename std::iterator_traits<ForwardIt>::value_type,
         class BinaryPred>
ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value,
                   BinaryPred 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;
}

Примечания

Макрос проверки поддержки функции	Значение	Стандарт	Функция
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Инициализация списком для алгоритмов (1-4)

Пример

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>

template<class Container, class Size, class T>
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[] = ".0_0.000.0_0.";
    
    static_assert(consecutive_values(sequence, 3, '0'));
    
    for (int n : {4, 3, 2})
        std::cout << std::boolalpha
                  << "Has " << n << " consecutive zeros: "
                  << consecutive_values(sequence, n, '0') << '\n';
    
    std::vector<std::complex<double>> nums{{4, 2}, {4, 2}, {1, 3}};
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = std::search_n(nums.cbegin(), nums.cend(), 2, {4, 2});
    #else
        auto it = std::search_n(nums.cbegin(), nums.cend(), 2, std::complex<double>{4, 2});
    #endif
    assert(it == nums.begin());
}

Вывод:

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

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

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

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

См. также

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

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