Namespaces
Variants

std::ranges::search

ja.cppreference.net より
 
 
アルゴリズムライブラリ
制約付きアルゴリズムと ranges 上のアルゴリズム (C++20)
制約付きアルゴリズム、例 ranges::copy、 ranges::sort、...
ソートと関連操作
分割操作
(C++11)    

ソート操作
二分探索操作
(分割された範囲に対する)
集合操作 (ソート済み範囲に対する)
マージ操作 (ソート済み範囲に対する)
ヒープ操作
最小/最大操作
(C++11)
(C++17)
辞書順比較操作
順列操作


 
制約付きアルゴリズム
このメニュー内のすべての名前は名前空間 std::ranges
非変更シーケンス操作
変更シーケンス操作
分割操作
ソート操作
二分探索操作 (ソート済み範囲に対する)
       
       
集合操作 (ソート済み範囲に対する)
ヒープ操作
最小/最大操作
       
       
順列操作
畳み込み操作
数値操作
(C++23)            
未初期化記憶域に対する操作
戻り値型
 
ヘッダ <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) 範囲 内の要素列 の[first2, last2)最初の[first1, last1)出現位置を検索します。要素は、それぞれ pred と proj2 で射影された後、二項述語 proj1 を使用して比較されます。
2) (1) と同じですが、最初のソース範囲として r1 を、2 番目のソース範囲として r2 を使用する点が異なります。あたかも 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}

関連項目

最初の2つの隣接要素で等しい (または指定された述語を満たす) ものを発見する
(アルゴリズム関数オブジェクト)
特定の基準を満たす最初の要素を発見する
(アルゴリズム関数オブジェクト)
特定の範囲内の要素の最後の並びを発見する
(アルゴリズム関数オブジェクト)
要素の集合のいずれかを検索する
(アルゴリズム関数オブジェクト)
範囲が指定された要素または部分範囲を含むかどうかを調べる
(アルゴリズム関数オブジェクト)
あるシーケンスが別のシーケンスの部分列であるかどうかを判定する
(アルゴリズム関数オブジェクト)
2つの範囲が異なる最初の位置を発見する
(アルゴリズム関数オブジェクト)
範囲内で要素の連続したコピーが最初に現れる位置を検索する
(アルゴリズム関数オブジェクト)
要素の範囲が最初に現れる位置を検索する
(関数テンプレート)