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 ) ;			(C++20以降constexpr) (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 ) 内で、指定された 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以降)

翻訳のポイント： - 「Contents」を「目次」に翻訳 - C++関連の専門用語（Parameters, Return value, Complexity, Exceptions, Possible implementation, Notes, Example, Defect reports, See also）は原文のまま保持 - HTMLタグ、属性、クラス名、ID、リンク先は一切変更せず - 番号部分はそのまま保持 - フォーマットと構造は完全に維持

パラメータ

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
                  << "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 が負の場合に問題が生じる	上限を 0 （ count が非正の場合）
LWG 714	C++98	count > 0 の場合、計算量の上限が `N·count` であったが、最悪ケースでの比較/操作回数は常に `N`	上限を `N` に変更
LWG 2150	C++98	「シーケンスの出現」の条件が不正確	修正済み

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

find_end	特定の範囲内で要素の最後のシーケンスを見つける (関数テンプレート)
find find_if find_if_not (C++11)	特定の条件を満たす最初の要素を見つける (関数テンプレート)
search	要素の範囲の最初の出現を検索する (関数テンプレート)
ranges::search_n (C++20)	範囲内で要素の連続したコピーの最初の出現を検索する (アルゴリズム関数オブジェクト)

cppreference.net

Namespaces

Variants

std:: search_n

目次

パラメータ

戻り値

計算量

例外

実装例

注記

例

不具合報告

関連項目