algorithm_partition_point
algorithm_partition_point (파티션 지점 찾기)
std::partition_point는 파티셔닝된 소스 범위에서 파티션 지점을 찾아 이진 탐색으로 돌려줘요. p를 만족하는 요소들이 끝나는 위치예요.
출처: cppreference
본문
std::partition_point는 소스 범위 [first, last)의 파티션 지점을 가리키는 반복자 iter를 돌려줘요: iter 앞의 모든 요소는 p를 만족하고, iter부터의 모든 요소는 만족하지 않아요. <algorithm> 헤더에 정의되어 있어요. C++11부터 사용 가능해요.
template< class ForwardIt, class UnaryPred >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPred p );
복잡도 (Complexity)
std::distance(first, last)를 N이라고 할 때, 𝓞(log N)번의 p 적용이 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 3, 5, 7, 2, 4, 6}; // partitioned by odd/even
auto it = std::partition_point(v.begin(), v.end(),
[](int x) { return x % 2 == 1; });
std::cout << "partition point at index "
<< std::distance(v.begin(), it) << ": " << *it << '\n';
}
출력:
partition point at index 4: 2