std::ranges::search
From cppreference.com
| ヘッダー <algorithm> で定義 |
||
| 呼び出しシグネチャ |
||
| template< std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, |
(1) | (C++20以降) |
| template< ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, |
(2) | (C++20以降) |
1) 範囲 `[first2, last2)` の要素のシーケンスを、範囲 `[first1, last1)` の中で **最初に** 検索します。要素は、それぞれ `proj2` と `proj1` で射影された後、二項述語 `pred` を使用して比較されます。
2) (1) と同じですが、`r1` を最初のソース範囲、`r2` を 2 番目のソース範囲として使用します。これは、`first1` として `ranges::begin(r1)`、`last1` として `ranges::end(r1)`、`first2` として `ranges::begin(r2)`、`last2` として `ranges::end(r2)` を使用するのと同等です。
このページで説明されている関数のようなエンティティは、アルゴリズム関数オブジェクト（非公式にはニーブロイドとして知られている）です。つまり、
- これらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- これらのいずれも実引数依存の名前探索には見えません。
- これらのいずれかが関数呼び出し演算子の左側の名前として通常の非修飾名探索によって見つかった場合、実引数依存の名前探索は抑制されます。
目次 |
[編集] パラメータ
| first1, last1 | - | 調べる要素の範囲を定義するイテレータ-センチネルペア（「haystack」（検索対象）とも呼ばれます） |
| first2, last2 | - | 検索する要素の範囲を定義するイテレータ-センチネルペア（「needle」（検索パターン）とも呼ばれます） |
| r1 | - | 調べる要素の範囲（「haystack」（検索対象）とも呼ばれます） |
| r2 | - | 検索する要素の範囲（「needle」（検索パターン）とも呼ばれます） |
| pred | - | 射影された要素に適用される二項述語 |
| proj1 | - | 最初の範囲の要素に適用する射影 |
| proj2 | - | 2番目の範囲の要素に適用する射影 |
[編集] 戻り値
1) `proj1` と `proj2` の射影を両方のシーケンスの要素に適用し、その結果の要素に対して二項述語 `pred` を適用して比較した後、範囲 `[first1, last1)`（「haystack」）の中で、シーケンス `[first2, last2)`（「needle」）の最初の出現箇所を表す `ranges::subrange` 値を返します。
そのような出現箇所が見つからなかった場合、`ranges::subrange{last1, last1}` が返されます。
検索する範囲（「needle」）が空の場合、つまり `first2 == last2` の場合、`ranges::subrange{first1, first1}` が返されます。2) (1) と同じですが、戻り値の型は `ranges::borrowed_subrange_t` です。
[編集] 計算量
対応する述語と各射影の適用回数は、最大で 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}; // the search uses iterator pairs begin()/end(): constexpr auto found1 = std::ranges::search( haystack.begin(), haystack.end(), needle.begin(), needle.end()); print(1, haystack, needle, found1); // the search uses ranges r1, r2: constexpr auto found2 = std::ranges::search(haystack, needle); print(2, haystack, needle, found2); // 'needle' range is empty: constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' will not be found: constexpr auto awl {"efg"sv}; constexpr auto found4 = std::ranges::search(haystack, awl); print(4, haystack, awl, found4); // the search uses custom comparator and projections: 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}[編集] 関連項目
| (C++20) |
等しい（または指定された述語を満たす）最初の2つの隣接する項目を見つける (アルゴリズム関数オブジェクト) |
| (C++20)(C++20)(C++20) |
特定の基準を満たす最初の要素を見つける (アルゴリズム関数オブジェクト) |
| (C++20) |
特定の範囲内で最後の要素のシーケンスを見つける (アルゴリズム関数オブジェクト) |
| (C++20) |
要素の集合のうちいずれか1つを検索する (アルゴリズム関数オブジェクト) |
| (C++23)(C++23) |
範囲が指定された要素または部分範囲を含むかチェックする (アルゴリズム関数オブジェクト) |
| (C++20) |
あるシーケンスが別のシーケンスの部分シーケンスである場合に true を返す (アルゴリズム関数オブジェクト) |
| (C++20) |
2つの範囲が異なる最初の位置を見つける (アルゴリズム関数オブジェクト) |
| (C++20) |
範囲内である要素が連続して出現する最初の箇所を検索する (アルゴリズム関数オブジェクト) |
| 要素の範囲の最初の出現を検索する (関数テンプレート) |
