std:: search_n

From cppreference.net

(원문에 번역할 텍스트가 없으므로 동일한 HTML 구조를 유지합니다)

헤더 파일에 정의됨 `<algorithm>`
	(1)
template < class ForwardIt, class Size, class T > ForwardIt search_n ( ForwardIt first, ForwardIt last, Size count, const T & value ) ;			(constexpr since C++20) (until 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 ) ;			(since 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 ) ;					(C++20부터 constexpr) (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 ) 내에서 주어진 value 와 동일한 count 개의 연속된 동일 요소로 구성된 첫 번째 시퀀스를 검색합니다.

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 를 반환하는 이항 predicate. predicate 함수의 시그니처는 다음과 동등해야 함: 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 가 0이거나 음수이면, first 가 반환됩니다.

복잡도

주어진 $\scriptsize N$ $N$ 이 std:: distance ( first, last ) 인 경우:

1,2) 최대

N

번의 비교를 operator == 를 사용하여 수행합니다.

3,4) 최대

N

번의 predicate p 적용.

예외

ExecutionPolicy 라는 템플릿 매개변수를 사용하는 오버로드는 다음과 같이 오류를 보고합니다:

알고리즘의 일부로 호출된 함수 실행 중 예외가 발생하고 ExecutionPolicy 가 표준 정책 중 하나인 경우, std::terminate 가 호출됩니다. 다른 ExecutionPolicy 의 경우 동작은 구현에 따라 정의됩니다.
알고리즘이 메모리 할당에 실패하는 경우, std::bad_alloc 이 throw됩니다.

가능한 구현

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)	목록 초기화 for algorithms ( 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++ 표준에 소급 적용되었습니다.

DR	적용 대상	게시된 동작	올바른 동작
LWG 283	C++98	`T` 가 EqualityComparable 요구사항을 만족해야 했으나, `InputIt` 의 값 타입이 항상 `T` 가 아님	해당 요구사항 제거
LWG 426	C++98	복잡도 상한이 `N·count` 였으나, count 가 음수일 경우 음수값이 됨	count 가 양수가 아닐 경우 상한을 0 으로 변경
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

std:: search_n

목차

매개변수

반환값

복잡도

예외

가능한 구현

참고 사항

예제

결함 보고서

참고 항목