名前空間
変種
操作

std::search

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
C のライブラリ
 
ヘッダ <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; を実行します。 SearcherCopyConstructible である必要はありません。

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

標準 C++ ライブラリの検索アルゴリズムの実装
(クラステンプレート) [edit]
ボイヤー・ムーア検索アルゴリズムの実装
(クラステンプレート) [edit]
ボイヤー・ムーア・ホースプール検索アルゴリズムの実装
(クラステンプレート) [edit]
(C++17およびそれ以降)

目次

[編集] 引数

first, last - 調べる要素の範囲
s_first, s_last - 検索する要素の範囲
policy - 使用する実行ポリシー。 詳細は実行ポリシーを参照してください
searcher - 検索アルゴリズムと探すパターンをカプセル化する検索子
p - 要素が等しいと扱われるべき場合に ​true を返す二項述語。

述語関数のシグネチャは以下と同等なものであるべきです。

 bool pred(const Type1 &a, const Type2 &b);

シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなりません。
Type1 および Type2 は、 ForwardIt1 および ForwardIt2 型のオブジェクトの逆参照からType1 および Type2 にそれぞれ暗黙に変換可能なものでなければなりません。 ​

型の要件
-
ForwardIt1, ForwardIt2ForwardIterator の要件を満たさなければなりません。
-
SearcherSearcher の要件を満たさなければなりません。

[編集] 戻り値

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 が3つの標準のポリシーのいずれかの場合は、 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;
            }
        }
    }
}

[編集]

#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

[編集] 関連項目

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