GeezerVison is showing cpprefjp.github.io — std::ranges::search - cpprefjp C++日本語リファレンス
最終更新日時:
2026年09月11日 13時06分31秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std::ranges:: search (C++20)
namespace std :: ranges {
template < forward_iterator I1 ,
sentinel_for < I1 > S1 ,
forward_iterator I2 ,
sentinel_for < I2 > S2 ,
class Pred = ranges::equal_to ,
class Proj1 = identity ,
class Proj2 = identity >
requires indirectly_comparable < I1 , I2 , Pred , Proj1 , Proj2 >
constexpr subrange < I1 >
search ( I1 first1 ,
S1 last1 ,
I2 first2 ,
S2 last2 ,
Pred pred = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (1) C++20
template < forward_range R1 ,
forward_range R2 ,
class Pred = ranges::equal_to ,
class Proj1 = identity ,
class Proj2 = identity >
requires indirectly_comparable < iterator_t < R1 > , iterator_t < R2 > , Pred , Proj1 , Proj2 >
constexpr borrowed_subrange_t < R1 >
search ( R1 && r1 ,
R2 && r2 ,
Pred pred = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (2) C++20
template < execution-policy Ep ,
random_access_iterator I1 ,
sized_sentinel_for < I1 > S1 ,
random_access_iterator I2 ,
sized_sentinel_for < I2 > S2 ,
class Pred = ranges::equal_to ,
class Proj1 = identity ,
class Proj2 = identity >
requires indirectly_comparable < I1 , I2 , Pred , Proj1 , Proj2 >
subrange < I1 >
search ( Ep && exec ,
I1 first1 ,
S1 last1 ,
I2 first2 ,
S2 last2 ,
Pred pred = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (3) C++26
template < execution-policy Ep ,
sized-random-access-range R1 ,
sized-random-access-range R2 ,
class Pred = ranges::equal_to ,
class Proj1 = identity ,
class Proj2 = identity >
requires indirectly_comparable < iterator_t < R1 > , iterator_t < R2 > , Pred , Proj1 , Proj2 >
borrowed_subrange_t < R1 >
search ( Ep && exec ,
R1 && r1 ,
R2 && r2 ,
Pred pred = {},
Proj1 proj1 = {},
Proj2 proj2 = {}); // (4) C++26
}
概要
あるシーケンスの中から、特定のサブシーケンスを探す
(1): イテレータ範囲を指定する
(2): Rangeを直接指定する
(3): (1)の並列アルゴリズム版。実行ポリシーを指定する
(4): (2)の並列アルゴリズム版。実行ポリシーを指定する
戻り値
(1) :
[first1,last1 - (last2 - first2)] 内のイテレータ i があるとき、0 以上 last2 - first2 未満の整数 n について、それぞれ invoke (pred, invoke (proj1, *(i + n)), invoke (proj2, *(first2 + n)))そのようなイテレータが見つからない場合は {last1, last1} を返し、[first2,last2) が空である場合には {first1, first1} を返す。
(2): first1 = begin(r1), last1 = end(r1), first2 = begin(r2), last2 = end(r2)の下で(1)と等しい。
計算量
最大で (last1 - first1) * (last2 - first2) 回の、対応する比較もしくは述語が適用される
例
基本的な使い方
出力
found: index==0
並列アルゴリズムの例 (C++26)
#include <algorithm>
#include <execution>
#include <iostream>
#include <vector>
int main () {
std::vector < int > v = { 1 , 2 , 3 , 4 , 5 , 3 , 4 };
std::vector < int > pattern = { 3 , 4 };
// 並列にサブシーケンスを検索する
auto sr = std::ranges::search ( std::execution::par , v , pattern );
if ( sr . empty ()) {
std::cout << "not found" << std::endl ;
} else {
std::cout << "found: index==" << std::distance ( v.begin() , sr . begin ()) << std::endl ;
}
}
出力
found: index==2
実装例
struct search_impl {
template < forward_iterator I1 , sentinel_for < I1 > S1 , forward_iterator I2 ,
sentinel_for < I2 > S2 , class Pred = ranges::equal_to , class Proj1 = identity , class Proj2 = identity >
requires indirectly_comparable < I1 , I2 , Pred , Proj1 , Proj2 >
constexpr subrange < I1 > operator ()( I1 first1 , S1 last1 , I2 first2 , S2 last2 , Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const {
for ( ; first1 != last1 ; ++ first1 ) {
I1 p1 = first1 ;
I2 p2 = first2 ;
while ( true ) {
if ( p2 == last2 ) return { first1 , p1 };
if ( p1 == last1 ) return { p1 , p1 };
if ( ! invoke ( pred , invoke ( proj1 , * p1 ), invoke ( proj2 , * p2 ))) break ;
++ p1 , ++ p2 ;
}
}
return { first1 , first1 };
}
template < forward_range R1 , forward_range R2 , class Pred = ranges::equal_to , class Proj1 = identity , class Proj2 = identity >
requires indirectly_comparable < iterator_t < R1 > , iterator_t < R2 > , Pred , Proj1 , Proj2 >
constexpr borrowed_subrange_t < R1 > operator ()( R1 && r1 , R2 && r2 , Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const {
return ( * this )( begin ( r1 ), end ( r1 ), begin ( r2 ), end ( r2 ), ref ( pred ), ref ( proj1 ), ref ( proj2 ));
}
};
inline constexpr search_impl search ;
バージョン
言語
処理系
参照