std:: search

From cppreference.net

ヘッダーで定義 `<algorithm>`
template < class ForwardIt1, class ForwardIt2 > ForwardIt1 search ( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last ) ;	(1)	(constexpr since C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search ( ExecutionPolicy && policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last ) ;	(2)	(since C++17)
template < class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search ( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p ) ;	(3)	(constexpr since C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search ( ExecutionPolicy && policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p ) ;	(4)	(since C++17)
template < class ForwardIt, class Searcher > ForwardIt search ( ForwardIt first, ForwardIt last, const Searcher & searcher ) ;	(5)	(since C++17) (constexpr since 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 であること。	(C++20まで)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> が true であること。	(C++20以降)

5) コンストラクタで指定されたパターンを範囲

first

last

内で検索します。

標準ライブラリは以下のサーチャーを提供します：

default_searcher (C++17)	標準C++ライブラリの検索アルゴリズム実装 (クラステンプレート)
boyer_moore_searcher (C++17)	Boyer-Moore検索アルゴリズム実装 (クラステンプレート)
boyer_moore_horspool_searcher (C++17)	Boyer-Moore-Horspool検索アルゴリズム実装 (クラステンプレート)

(C++17以降)

first, last	-	検査する要素の範囲を定義するイテレータのペア
s_first, s_last	-	検索する要素の範囲を定義するイテレータのペア
policy	-	使用する実行ポリシー
searcher	-	検索アルゴリズムと検索パターンをカプセル化するサーチャー
p	-	要素が等しいと扱われるべき場合に true を返す二項述語。述語関数のシグネチャは以下と同等であるべきです： bool pred ( const Type1 & a, const Type2 & b ) ; シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関係なく（したがって、 Type1 & は許可されません、また Type1 も、 `Type1` に対してムーブがコピーと等価でない限り許可されません (C++11以降) ）、すべての `Type1` と `Type2` の型の値を受け入れられる必要があります。型 Type1 と Type2 は、 ForwardIt1 と ForwardIt2 の型のオブジェクトが間接参照可能であり、それぞれ Type1 と Type2 に暗黙的に変換可能である必要があります。
型要件
- `ForwardIt1, ForwardIt2` は LegacyForwardIterator の要件を満たさなければなりません。
- `BinaryPred` は BinaryPredicate の要件を満たさなければなりません。

戻り値

1-4) 範囲

first

last

内で最初に現れるシーケンス

s_first

s_last

の先頭を指すイテレータ。そのようなシーケンスが見つからない場合は、 last が返される。

もし

s_first

s_last

が空の場合、 first が返されます。

5) searcher ( first, last ) . first .

計算量

1-4) 与えられる

N

を std:: distance ( first, last ) とし、

S

を std:: distance ( s_first, s_last ) とする：

1,2) 最大で

N\cdotS

回の比較を operator == を使用して行う。

3,4) 最大で

N\cdotS

回の述語 p の適用。

5) 依存対象: searcher .

例外

ExecutionPolicy という名前のテンプレートパラメータを持つオーバーロードは、以下のようにエラーを報告します：

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

実装例

search (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last)
{
    while (true)
    {
        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;
        }
        ++first;
    }
}

search (3)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p)
{
    while (true)
    {
        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;
        }
        ++first;
    }
}

例

このコードを実行

#include <algorithm>
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>
using namespace std::literals;
bool contains(const auto& cont, std::string_view s)
{
    // str.find() (or str.contains(), since C++23) can be used as well
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
int main()
{
    const auto str{"why waste time learning, when ignorance is instantaneous?"sv};
    assert(contains(str, "learning"));
    assert(not contains(str, "lemming"));
    const std::vector vec(str.begin(), str.end());
    assert(contains(vec, "learning"));
    assert(not contains(vec, "leaning"));
    // The C++17 overload with searchers demo:
    constexpr auto quote
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };
    for (const auto word : {"pisci"sv, "Pisci"sv})
    {
        std::cout << "The string " << std::quoted(word) << ' ';
        const std::boyer_moore_searcher searcher(word.begin(), word.end());
        const auto it = std::search(quote.begin(), quote.end(), searcher);
        if (it == quote.end())
            std::cout << "not found\n";
        else
            std::cout << "found at offset " << std::distance(quote.begin(), it) << '\n';
    }
}

出力:

The string "pisci" found at offset 43
The string "Pisci" not found

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

DR	適用対象	公開時の動作	正しい動作
LWG 1205	C++98	`[` s_first `,` s_last `)` が空の場合の戻り値が不明確	この場合 first を返す
LWG 1338	C++98	LWG issue 1205 の解決策が誤って適用され、一致が見つからない場合に first を返すようになっていた	この場合 last を返す
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	特定の範囲内で要素の最後のシーケンスを見つける (関数テンプレート)
includes	一方のシーケンスが他方の部分シーケンスである場合に true を返す (関数テンプレート)
equal	2つの要素の集合が同じかどうかを判定する (関数テンプレート)
find find_if find_if_not (C++11)	特定の条件を満たす最初の要素を見つける (関数テンプレート)
lexicographical_compare	一方の範囲が他方よりも辞書順で小さい場合に true を返す (関数テンプレート)
mismatch	2つの範囲が最初に異なる位置を見つける (関数テンプレート)
search_n	範囲内で要素の連続する指定個数の最初の出現を検索する (関数テンプレート)
default_searcher (C++17)	標準C++ライブラリの検索アルゴリズム実装 (クラステンプレート)
boyer_moore_searcher (C++17)	Boyer-Moore検索アルゴリズムの実装 (クラステンプレート)
boyer_moore_horspool_searcher (C++17)	Boyer-Moore-Horspool検索アルゴリズムの実装 (クラステンプレート)
ranges::search (C++20)	要素の範囲の最初の出現を検索する (アルゴリズム関数オブジェクト)

cppreference.net

Namespaces

Variants

std:: search

目次

パラメータ

戻り値

計算量

例外

実装例

例

不具合報告

関連項目