C++ std::partition_point 함수란?
이 글에서는 C++ 표준 라이브러리(STL)의 partition_point 알고리즘에 대해 자세히 알아보겠습니다.
std::partition_point는 <algorithm> 헤더에 정의된 함수로, 주어진 범위에서 조건자(predicate)가 처음으로 거짓이 되는 첫 번째 요소를 가리키는 반복자(iterator)를 반환합니다. 쉽게 말해, 이미 분할된 범위에서 두 그룹의 경계 지점을 찾아주는 역할을 합니다.
단, 이 함수가 정확하게 동작하려면 대상 범위가 해당 조건자를 기준으로 미리 분할되어 있어야 합니다. 즉, 조건을 만족하는 요소들은 앞쪽에, 만족하지 않는 요소들은 뒤쪽에 배치되어 있어야 한다는 전제가 필요합니다.
예제 코드
#include <iostream>
#include <algorithm>
#include <vector>
bool IsOdd(int i) { return (i % 2) == 1; }
int main() {
std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector<int> odd, even;
// 홀수가 앞쪽에 오도록 안정 분할(stable partition) 수행
std::stable_partition(data.begin(), data.end(), IsOdd);
// 홀수와 짝수의 경계 지점(분할 지점) 탐색
auto it = std::partition_point(data.begin(), data.end(), IsOdd);
odd.assign(data.begin(), it);
even.assign(it, data.end());
std::cout << "odd:";
for (int& x : odd)
std::cout << ' ' << x;
std::cout << '\n';
std::cout << "even:";
for (int& x : even)
std::cout << ' ' << x;
std::cout << '\n';
return 0;
}
실행 결과
odd: 1 3 5 7 9 even: 2 4 6 8 10
코드 동작 원리
위 예제의 실행 흐름을 단계별로 살펴보겠습니다.
- 안정 분할:
std::stable_partition을 호출하여 홀수는 앞쪽으로, 짝수는 뒤쪽으로 이동시킵니다. 그 결과 벡터는 {1, 3, 5, 7, 9, 2, 4, 6, 8, 10} 순서로 재배열됩니다. - 분할 지점 탐색:
std::partition_point가 IsOdd 조건이 처음으로 거짓이 되는 위치, 즉 짝수 2가 시작되는 지점의 반복자를 반환합니다. - 범위 분리: 반환된 반복자를 기준으로 앞부분은 홀수 벡터에, 뒷부분은 짝수 벡터에 각각 복사하여 출력합니다.
주요 특징 및 주의 사항
partition_point는 내부적으로 이진 탐색(binary search) 방식으로 동작하므로 시간 복잡도가 O(log N)으로 매우 효율적입니다. 따라서 이미 분할된 대용량 데이터에서 경계를 빠르게 찾아야 할 때 특히 유용합니다.
다만, 범위가 실제로 조건자 기준으로 분할되어 있지 않으면 정의되지 않은 동작(undefined behavior)이 발생할 수 있습니다. 안전한 사용을 위해 호출 전에 std::is_partitioned 함수로 범위의 분할 여부를 확인하는 것이 좋습니다.