std:: search_n

From cppreference.net

Определено в заголовке `<algorithm>`
	(1)
template < class ForwardIt, class Size, class T > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(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 ) ;			(начиная с C++26)
		(2)
template < class ExecutionPolicy, class ForwardIt, class Size, class T > ForwardIt search_n ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, Size count, const T & value ) ;				(начиная с 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 ) ;				(начиная с C++26)
			(3)
template < class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value, BinaryPred p ) ;					(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 ) ;					(начиная с C++26)
				(4)
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 ) ;						(начиная с 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 ) ;						(начиная с C++26)

Выполняет поиск в диапазоне [ 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 .
- `BinaryPred` должен удовлетворять требованиям BinaryPredicate .
- `Size` должен быть преобразуем в целочисленный тип .

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

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

1,2) * it == value является true .

3,4) p ( * it, value ) ! = false является true .

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

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

Сложность

Дано $\scriptsize N$ $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 = 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; // успех
            ++first;
            if (first == last)
                return last; // список исчерпан
            if (!(*first == value))
                break; // недостаточно подряд
        }
    }
    return last;
}

search_n (3)

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; // успех
            ++first;
            if (first == last)
                return last; // список исчерпан
            if (!p(*first, value))
                break; // недостаточно подряд
        }
    }
    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
                  << "Содержит " << n << " последовательных нулей: "
                  << 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());
}

Вывод:

Содержит 4 последовательных нулей: false
Содержит 3 последовательных нулей: true
Содержит 2 последовательных нулей: true

Отчеты о дефектах

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

DR	Applied to	Behavior as published	Correct behavior
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` в этом случае
LWG 2150	C++98	условие "последовательного вхождения" было некорректным	исправлено

Смотрите также

find_end	находит последнюю последовательность элементов в заданном диапазоне (function template)
find find_if find_if_not (C++11)	находит первый элемент, удовлетворяющий определенным критериям (function template)
search	ищет первое вхождение диапазона элементов (function template)
ranges::search_n (C++20)	ищет первое вхождение заданного количества последовательных копий элемента в диапазоне (algorithm function object)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants