std::search

提供: cppreference.com

ヘッダ `<algorithm>` で定義
	(1)
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );			(C++20未満)
template< class ForwardIt1, class ForwardIt2 > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );			(C++20以上)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );		(2)	(C++17以上)
		(3)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );				(C++20未満)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );				(C++20以上)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );			(4)	(C++17以上)
			(5)
template<class ForwardIt, class Searcher> ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );					(C++17以上) (C++20未満)
template<class ForwardIt, class Searcher> constexpr ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );					(C++20以上)

1-4) 範囲 [first, last) 内から要素列 [s_first, s_last) が現れる最初の位置を検索します。

1) 要素は operator== を用いて比較されます。

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

2,4) (1,3) と同じですが、 policy に従って実行されます。これらのオーバーロードは、 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である場合にのみ、オーバーロード解決に参加します。

5) searcher のコンストラクタで指定されたパターンをシーケンス

[first, last)

から検索します。実質的に return searcher(first, last).first; を実行します。 Searcher は CopyConstructible である必要はありません。

標準ライブラリは以下の検索子を提供します。

default_searcher (C++17)	標準 C++ ライブラリの検索アルゴリズムの実装 (クラステンプレート) [edit]
boyer_moore_searcher (C++17)	ボイヤー・ムーア検索アルゴリズムの実装 (クラステンプレート) [edit]
boyer_moore_horspool_searcher (C++17)	ボイヤー・ムーア・ホースプール検索アルゴリズムの実装 (クラステンプレート) [edit]

(C++17以上)

first, last	-	調べる要素の範囲
s_first, s_last	-	検索する要素の範囲
policy	-	使用する実行ポリシー。詳細は実行ポリシーを参照してください
searcher	-	検索アルゴリズムと探すパターンをカプセル化する検索子
p	-	要素が等しいと扱われるべき場合に true を返す二項述語。述語関数のシグネチャは以下と同等なものであるべきです。 bool pred(const Type1 &a, const Type2 &b); シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず `Type1` および `Type2` 型 (およびそれらの const 修飾された型) のすべての値を受理できなければなりません (そのため Type1 & は許されません。また Type1 に対してムーブがコピーと同等でなければ Type1 も許されません (C++11以上))。型 Type1 および Type2 は、 ForwardIt1 および ForwardIt2 型のオブジェクトの逆参照からType1 および Type2 にそれぞれ暗黙に変換可能なものでなければなりません。
型の要件
- `ForwardIt1, ForwardIt2` は LegacyForwardIterator の要件を満たさなければなりません。
- `Searcher` は Searcher の要件を満たさなければなりません。

[編集] 戻り値

1-4) 範囲 [first, last) 内の要素列 [s_first, s_last) が現れる最初の位置の先頭を指すイテレータ。そのような要素列が見つからない場合は、 last が返されます。

[s_first, s_last) が空の場合は、 first が返されます。

(C++11以上)

5) searcher.operator() の結果、つまり、見つかった部分要素列の位置を指すイテレータまたは見つからなかった場合は last のコピーを返します。

[編集] 計算量

1-4) 多くとも S*N 回の比較。ただし S = std::distance(s_first, s_last)、 N = std::distance(first, last)。

5) 検索子に依存します。

[編集] 例外

テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外を投げ、 ExecutionPolicy が標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。それ以外のあらゆる ExecutionPolicy については、動作は処理系定義です。
アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。

[編集] 実装例

1つめのバージョン

template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last)
{
    for (; ; ++first) {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) {
            if (s_it == s_last) {
                return first;
            }
            if (it == last) {
                return last;
            }
            if (!(*it == *s_it)) {
                break;
            }
        }
    }
}

2つめのバージョン

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last, 
                            BinaryPredicate p)
{
    for (; ; ++first) {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) {
            if (s_it == s_last) {
                return first;
            }
            if (it == last) {
                return last;
            }
            if (!p(*it, *s_it)) {
                break;
            }
        }
    }
}

[編集] 例

Run this code

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
 
template <typename Container>
bool in_quote(const Container& cont, const std::string& s)
{
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
 
int main()
{
    std::string str = "why waste time learning, when ignorance is instantaneous?";
    // str.find() も同様に使用できます。
    std::cout << std::boolalpha << in_quote(str, "learning") << '\n'
                                << in_quote(str, "lemming")  << '\n';
 
    std::vector<char> vec(str.begin(), str.end());
    std::cout << std::boolalpha << in_quote(vec, "learning") << '\n'
                                << in_quote(vec, "lemming")  << '\n';
 
    // C++17 オーバーロードのデモ。
    std::string in = "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
                     " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
    std::string needle = "pisci";
    auto it = std::search(in.begin(), in.end(),
                   std::boyer_moore_searcher(
                      needle.begin(), needle.end()));
    if(it != in.end())
        std::cout << "The string " << needle << " found at offset "
                  << it - in.begin() << '\n';
    else
        std::cout << "The string " << needle << " not found\n";
}

出力:

true
false
true
false
The string pisci found at offset 43

[編集] 関連項目

find_end	指定された要素の並びが現れる最後の位置を探します (関数テンプレート) [edit]
includes	ある集合が別の集合の部分集合であるかどうか調べます (関数テンプレート) [edit]
equal	2つの要素集合が同じかどうか調べます (関数テンプレート) [edit]
findfind_iffind_if_not (C++11)	一定の基準を満たす最初の要素を探します (関数テンプレート) [edit]
lexicographical_compare	ある範囲が別の範囲より辞書的に小さいかどうか調べます (関数テンプレート) [edit]
mismatch	2つの範囲が異なる最初の位置を探します (関数テンプレート) [edit]
search_n	指定個数の連続する指定要素を指定範囲から検索します (関数テンプレート) [edit]
default_searcher (C++17)	標準 C++ ライブラリの検索アルゴリズムの実装 (クラステンプレート) [edit]
boyer_moore_searcher (C++17)	ボイヤー・ムーア検索アルゴリズムの実装 (クラステンプレート) [edit]
boyer_moore_horspool_searcher (C++17)	ボイヤー・ムーア・ホースプール検索アルゴリズムの実装 (クラステンプレート) [edit]

「https://ja.cppreference.com/mwiki/index.php?title=cpp/algorithm/search&oldid=42767」から取得

言語
標準ライブラリヘッダ
フリースタンディング処理系とホスト処理系
名前付き要件
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ (C++20)
アルゴリズムライブラリ
数値演算ライブラリ
ローカライゼーションライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドサポートライブラリ (C++11)
技術仕様書

cppreference.com

名前空間

変種

表示

操作