algorithm_adjacent_find
algorithm_adjacent_find (인접 요소 쌍 찾기)
std::adjacent_find는 범위 [first, last)에서 조건을 만족하는 인접한 두 요소의 첫 번째 쌍을 찾는 알고리즘이에요. 기본적으로 인접한 같은 값 두 개를 찾아요.
출처: cppreference
본문
std::adjacent_find는 소스 범위 [first, last)에서 지정한 조건을 만족하는 인접한 요소 쌍의 첫 번째 위치를 찾아요. <algorithm> 헤더에 정의되어 있어요.
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
template< class ForwardIt, class BinaryPred >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last,
BinaryPred p );
- 1번 오버로드 — 인접한 같은 값(
==)의 첫 번째 쌍을 찾아요. - 2번 오버로드 — 이진 술어
p를 만족하는 첫 번째 인접 쌍을 찾아요. - 병렬 실행 정책 버전도 제공돼요.
반환값 (Return value)
소스 범위에서 다음 표현식이 참이 되는 첫 번째 반복자 iter예요:
bool(*iter == *std::next(iter))또는bool(p(*iter, *std::next(iter)))
그런 반복자가 없으면 last를 돌려줘요.
복잡도 (Complexity)
M을 std::distance(first, result), N을 std::distance(first, last)라고 하면 min(M+1, N-1)번의 비교(또는 p 적용)가 필요해요. 병렬 오버로드는 𝓞(N)이에요.
예제 (Example)
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};
auto i1 = std::adjacent_find(v1.begin(), v1.end());
if (i1 == v1.end())
std::cout << "No matching adjacent elements\n";
else
std::cout << "The first adjacent pair of equal elements is at "
<< std::distance(v1.begin(), i1) << ", *i1 = " << *i1 << '\n';
auto i2 = std::adjacent_find(v1.begin(), v1.end(), std::greater<int>());
if (i2 == v1.end())
std::cout << "The entire vector is sorted in ascending order\n";
else
std::cout << "The last element in the non-decreasing subsequence is at "
<< std::distance(v1.begin(), i2) << ", *i2 = " << *i2 << '\n';
}
출력:
The first adjacent pair of equal elements is at 4, *i1 = 40
The last element in the non-decreasing subsequence is at 7, *i2 = 41
가능한 구현 (Possible implementation)
template<class ForwardIt>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last)
{
if (first == last)
return last;
ForwardIt next = first;
++next;
for (; next != last; ++next, ++first)
if (*first == *next)
return first;
return last;
}
template<class ForwardIt, class BinaryPred>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p)
{
if (first == last)
return last;
ForwardIt next = first;
++next;
for (; next != last; ++next, ++first)
if (p(*first, *next))
return first;
return last;
}