partition_point
partition_point (분할 경계 지점)
분할된 범위에서 술어가 거짓이 되는 첫 지점을 찾는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
partition_point는 분할된(partitioned) 범위 [first, last)에서 술어 p가 처음으로 거짓이 되는 위치를 반환해요. 범위는 p 기준으로 분할되어 있어야 해요.
template< class ForwardIt, class UnaryPred >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPred p ); // (1)
- 반환 값:
p가 참인 구간의 끝(즉 첫 거짓 원소). 범위 전체가 참이면last. - 복잡도:
last - first에 로그적(std::distance대비O(log N)의p호출).
std::partition으로 만든 분할된 범위에서 "참 그룹이 어디까지인지"를 찾을 때, std::find_if-not을 쓰는 대신 로그 시간으로 효율적으로 찾아줘요.
std::vector<int> v{2, 4, 6, 1, 3, 5}; // 짝수 먼저 분할됨
auto it = std::partition_point(v.begin(), v.end(),
[](int x){ return x % 2 == 0; });
// 첫 홀수(1)를 가리킴
lower_bound가 정렬 범위에서 이진 탐색이라면, partition_point는 분할 범위에서 경계를 찾는 셈이에요.