std::ranges:: search

From cppreference.net

ヘッダーで定義 `<algorithm>`
呼び出しシグネチャ
template < std:: forward_iterator I1, std:: sentinel_for < I1 > S1, std:: forward_iterator I2, std:: sentinel_for < I2 > S2, class Pred = ranges:: equal_to , class Proj1 = std:: identity , class Proj2 = std:: identity > requires std:: indirectly_comparable < I1, I2, Pred, Proj1, Proj2 > constexpr ranges:: subrange < I1 > search ( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(1)	(C++20以降)
template < ranges:: forward_range R1, ranges:: forward_range R2, class Pred = ranges:: equal_to , class Proj1 = std:: identity , class Proj2 = std:: identity > requires std:: indirectly_comparable < ranges:: iterator_t < R1 > , ranges:: iterator_t < R2 > , Pred, Proj1, Proj2 > constexpr ranges:: borrowed_subrange_t < R1 > search ( R1 && r1, R2 && r2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(2)	(C++20以降)

1) 範囲

first1

last1

内で、要素シーケンス

first2

last2

の最初の出現を検索します。要素はそれぞれ proj2 と proj1 で投影された後、二項述語 pred を使用して比較されます。

2) (1) と同様だが、 r1 を第1ソース範囲として、 r2 を第2ソース範囲として使用する。すなわち、 ranges:: begin ( r1 ) を first1 として、 ranges:: end ( r1 ) を last1 として、 ranges:: begin ( r2 ) を first2 として、 ranges:: end ( r2 ) を last2 として使用する場合と同等である。

このページで説明されている関数ライクなエンティティは、 アルゴリズム関数オブジェクト （非公式には niebloids として知られる）です。すなわち：

明示的なテンプレート引数リストは、いずれかを呼び出す際に指定することはできません。
いずれも実引数依存の名前探索では可視になりません。
いずれかが関数呼び出し演算子の左側の名前として通常の非修飾名前探索によって見つかった場合、実引数依存の名前探索は抑制されます。

first1, last1	-	検査対象の要素の範囲を定義するイテレータ-番兵ペア（干し草の山とも呼ばれる）
first2, last2	-	検索対象の要素の範囲を定義するイテレータ-番兵ペア（針とも呼ばれる）
r1	-	検査対象の要素の範囲（干し草の山とも呼ばれる）
r2	-	検索対象の要素の範囲（針とも呼ばれる）
pred	-	投影された要素に適用する二項述語
proj1	-	第1範囲の要素に適用する投影
proj2	-	第2範囲の要素に適用する投影

戻り値

1) 範囲

first1

last1

（別名 haystack ）内で、シーケンス

first2

last2

（別名 needle ）の最初の出現を表す ranges:: subrange 値を返す。この際、両シーケンスの要素にそれぞれ射影 proj1 と proj2 を適用した後、二項述語 pred を用いて射影された要素を比較する。

該当する出現が見つからない場合、 ranges:: subrange { last1, last1 } が返される。

検索対象の範囲（別名 needle ）が空の場合、つまり first2 == last2 の場合、 ranges:: subrange { first1, first1 } が返される。

2) (1) と同じですが、戻り値の型は ranges:: borrowed_subrange_t < R1 > です。

計算量

対応する述語と各射影の適用は最大で S * N 回であり、ここで
(1) S = ranges:: distance ( first2, last2 ) かつ N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) かつ N = ranges:: distance ( r1 ) 。

実装例

struct search_fn
{
    template<std::forward_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr ranges::subrange<I1>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (;; ++first1)
        {
            I1 it1 = first1;
            for (I2 it2 = first2;; ++it1, ++it2)
            {
                if (it2 == last2)
                    return {first1, it1};
                if (it1 == last1)
                    return {it1, it1};
                if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2)))
                    break;
            }
        }
    }
    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>, Pred, Proj1, Proj2>
    constexpr ranges::borrowed_subrange_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(pred), std::move(proj1), std::move(proj2));
    }
};
inline constexpr search_fn search {};

例

このコードを実行

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string_view>
using namespace std::literals;
void print(int id, const auto& haystack, const auto& needle, const auto& found)
{
    std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); ";
    const auto first = std::distance(haystack.begin(), found.begin());
    const auto last = std::distance(haystack.begin(), found.end());
    if (found.empty())
        std::cout << "not found;";
    else
    {
        std::cout << "found: \"";
        for (const auto x : found)
            std::cout << x;
        std::cout << "\";";
    }
    std::cout << " subrange: {" << first << ", " << last << "}\n";
}
int main()
{
    constexpr auto haystack {"abcd abcd"sv};
    constexpr auto needle {"bcd"sv};
    // 検索はイテレータペア begin()/end() を使用:
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // 検索は範囲 r1, r2 を使用:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // 'needle' 範囲が空の場合:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' は見つからない場合:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // 検索はカスタム比較関数と射影を使用:
    constexpr auto bodkin {"234"sv};
    auto found5 = std::ranges::search(haystack, bodkin,
        [](const int x, const int y) { return x == y; }, // pred
        [](const int x) { return std::toupper(x); }, // proj1
        [](const int y) { return y + 'A' - '1'; }); // proj2
    print(5, haystack, bodkin, found5);
}

出力:

1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}

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

ranges::adjacent_find (C++20)	等しい（または与えられた述語を満たす）最初の隣接する2つの要素を検索する (アルゴリズム関数オブジェクト)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	特定の基準を満たす最初の要素を検索する (アルゴリズム関数オブジェクト)
ranges::find_end (C++20)	特定の範囲内の要素シーケンスの最後を検索する (アルゴリズム関数オブジェクト)
ranges::find_first_of (C++20)	要素の集合のいずれかを検索する (アルゴリズム関数オブジェクト)
ranges::contains ranges::contains_subrange (C++23) (C++23)	範囲が指定された要素または部分範囲を含むかどうかをチェックする (アルゴリズム関数オブジェクト)
ranges::includes (C++20)	一方のシーケンスが他方の部分シーケンスである場合に true を返す (アルゴリズム関数オブジェクト)
ranges::mismatch (C++20)	2つの範囲が異なる最初の位置を検索する (アルゴリズム関数オブジェクト)
ranges::search_n (C++20)	範囲内の要素の連続する指定個数の最初の出現を検索する (アルゴリズム関数オブジェクト)
search	要素の範囲の最初の出現を検索する (関数テンプレート)

cppreference.net

Namespaces

Variants

std::ranges:: search

目次

パラメータ

戻り値

計算量

実装例

例

関連項目