std::search_n

ヘッダ `<algorithm>`
template< class ForwardIt, class Size, class T > ForwardIt search_n( ForwardIt first, ForwardIt last, Size count, const T& value );	で定義 (1)	(C++26まで) (C++20からconstexpr)
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 ExecutionPolicy, class ForwardIt, class Size, class T > ForwardIt search_n( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Size count, const T& value );	(2)	(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 );	(2)		(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 );	(3)	{{mark constexpr since (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 );	(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== を使用して比較されます。

3) 要素は指定された二項述語 p を使用して比較されます。

2,4) (1,3) と同じですが、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 を返す二項述語。述語関数のシグネチャは以下と同等であるべきです： 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	「シーケンスの出現」の条件が不正確	修正済み

コンパイラサポート
フリースタンディングとホスト環境
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
レンジライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日時ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行処理サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様書
シンボル索引
外部ライブラリ

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)	特定の基準を満たす最初の要素を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
search	ある要素範囲が最初に現れる位置を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::search (C++20)	ある要素範囲が最初に現れる位置を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::search_n (C++20)	ある範囲内で、指定された要素が連続して指定個数分現れる最初の位置を検索する (アルゴリズム関数オブジェクト)

ja.cppreference.net

Namespaces

Variants

std::search_n

目次

パラメータ

戻り値

計算量

例外

実装例

注記

例

不具合報告

関連項目