algorithm_search
algorithm_search (부분 수열 탐색)
std::search는 소스 범위에서 대상 부분 수열이 처음으로 나타나는 위치를 찾아요. std::find_end와 달리 가장 앞쪽의 일치를 찾아요.
출처: cppreference
본문
std::search는 소스 범위 [first1, last1)에서 대상 범위 [first2, last2)가 처음으로 나타나는 곳을 찾아요. <algorithm> 헤더에 정의되어 있어요.
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
template< class ForwardIt1, class ForwardIt2, class BinaryPred >
ForwardIt1 search( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
BinaryPred p );
- 1번 오버로드 — 요소를
operator==로 비교해요. - 2번 오버로드 — 요소를 이진 술어
p로 비교해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
반환값 (Return value)
소스 범위에서 대상 부분 수열이 처음 나타나는 위치의 시작 반복자예요. 대상 범위가 비어 있으면 first1을 돌려줘요. 대상 범위가 소스 범위에 나타나지 않으면 last1을 돌려줘요.
복잡도 (Complexity)
S를 std::distance(first1, last1), N을 std::distance(first2, last2)라고 하면 최대 S·N번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3, 4, 1, 2, 5};
std::vector<int> t{1, 2};
auto it = std::search(v.begin(), v.end(), t.begin(), t.end());
if (it != v.end())
std::cout << "Found at index " << std::distance(v.begin(), it) << '\n';
}
출력:
Found at index 0