adjacent_find

adjacent_find (인접한 같은/조건 만족 원소 찾기)

범위에서 서로 이웃하면서 특정 조건을 만족하는 첫 번째 쌍을 찾는 알고리즘이에요. 기본적으로는 같은 값이 두 번 연속으로 나오는 위치를 찾아줘요. <algorithm> 헤더에 있어요.

출처: cppreference

본문

adjacent_find의 기본 형태는 범위 [first, last)를 순회하면서 인접한 두 원소가 같은 첫 번째 위치를 찾는 거예요. 같음의 판정은 operator==로 해요.

template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );

직접 만든 이진 술어를 쓰는 버전도 있어요. 이 경우엔 p(*it, *(it+1))이 참이 되는 첫 지점을 찾아요.

template< class ForwardIt, class BinaryPred >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last,
                         BinaryPred p );

C++17부터는 실행 정책을 받는 오버로드가 추가됐어요. 그 버전은 ExecutionPolicy가 유효한 실행 정책인 경우에만 오버로드 해석에 참여해요.

동작 정리해요.

• 1. 인접한 두 원소가 같은 첫 쌍을 찾아요. operator==로 판정.
• 2. 이진 술어 p를 만족하는 첫 쌍을 찾아요.
• 3,4) 1,2와 같지만 policy에 따라 실행돼요.

조건을 만족하는 쌍이 없으면 last를 반환해요. 찾으면 그 첫 번째 원소를 가리키는 반복자를 돌려주고요. 계산 복잡도는 last - first에 비례하는데, 최악의 경우 비교 횟수가 (last - first) - 1번이에요.

std::find가 단일 원소를 찾는다면, adjacent_find는 이웃 관계까지 고려해 쌍을 찾는다고 기억하면 돼요.

더 알아보기 (Learn more)

cppreference