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