C++ partition·stable_partition·partition_point: 조건으로 범위 나누기
이 글의 핵심
partition은 요소를 지우지 않고 재배치만 하기 때문에 반환된 반복자를 무시하면 어디까지가 조건을 만족하는지 알 수 없습니다. stable_partition이 추가 메모리를 쓰는 이유와 성능 차이, partition_point가 전제로 삼는 조건을 짚고, 우선순위 처리나 조건부 삭제 같은 실무 패턴에 적용하는 방법을 설명합니다.
Partition이란?
std::partition은 조건(predicate)을 만족하는 요소를 범위 앞쪽으로, 만족하지 않는 요소를 뒤쪽으로 재배치하는 STL 알고리즘입니다. 요소를 지우거나 새로 만들지 않고 범위 안에서 위치만 바꾸며, 두 그룹의 경계를 가리키는 반복자를 돌려줍니다.
#include <algorithm>
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6};
// 짝수를 앞으로
auto pivot = std::partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
// 예: [6, 2, 4, 3, 5, 1] (libstdc++ 결과, 그룹 안의 순서는 구현에 따라 다름)
// pivot은 3을 가리킴: [begin, pivot)은 짝수, [pivot, end)는 홀수같은 일을 두 벡터로 나누어 할 수도 있습니다.
std::vector<int> evens, odds;
for (int x : v) {
if (x % 2 == 0) {
evens.push_back(x);
} else {
odds.push_back(x);
}
}두 코드는 결과를 담는 방식이 다릅니다. 수동 분할은 벡터 두 개를 새로 할당하고 원소를 복사하지만, partition은 추가 메모리 없이 원래 벡터 안에서 원소를 교환해 재배치합니다. 대신 결과가 “하나의 벡터와 경계 반복자”라는 형태가 되므로, 반환된 pivot을 반드시 받아 두어야 어디까지가 참 그룹인지 알 수 있습니다. 반환값을 버리면 원소는 재배치되었는데 경계는 모르는 상태가 되고, 다시 알려면 partition_point로 O(log n) 탐색을 한 번 더 해야 합니다.
flowchart LR
A["[1, 2, 3, 4, 5, 6]"] --> B[partition]
B --> C["[6, 2, 4, 3, 5, 1]"]
C --> D["true 그룹"]
C --> E["false 그룹"]
D -.-> |pivot| E
<algorithm>에는 분할과 관련된 함수가 다섯 개 있습니다.
| 알고리즘 | 그룹 안 순서 | 시간 복잡도 | 용도 |
|---|---|---|---|
partition | 유지 안 됨 | O(n) | 제자리 분할 |
stable_partition | 유지 | 버퍼 확보 시 O(n), 아니면 O(n log n) | 순서를 지키는 제자리 분할 |
partition_copy | 유지 | O(n) | 두 출력 범위로 복사하며 분할 |
partition_point | - | O(log n) 조건 호출 | 분할된 범위의 경계 찾기 |
is_partitioned | - | O(n) | 범위가 분할되어 있는지 확인 |
기본 사용
그림: 실제 실행 결과 — 값을 3으로 나눈 나머지에 따라 9 6 3 / 4 1 7 / 2 8 5의 세 묶음으로 나뉜다.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto pivot = std::partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
std::cout << "짝수: ";
for (auto it = v.begin(); it != pivot; ++it) {
std::cout << *it << " ";
}
std::cout << "\n홀수: ";
for (auto it = pivot; it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
}stable_partition
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::stable_partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
for (int x : v) {
std::cout << x << " "; // 2 4 6 1 3 5 (각 그룹 안에서 원래 순서 유지)
}
std::cout << "\n";
}partition_copy
원본을 그대로 두고 두 그룹을 각각 다른 컨테이너로 받고 싶다면 partition_copy를 씁니다. 각 출력 안에서는 원래 순서가 유지됩니다.
#include <algorithm>
#include <iterator>
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> evens, odds;
std::partition_copy(v.begin(), v.end(),
std::back_inserter(evens),
std::back_inserter(odds),
[](int x) { return x % 2 == 0; });
// evens: 2 4 6, odds: 1 3 53-way 분할
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 3으로 나눈 나머지로 세 그룹 만들기
auto pivot1 = std::partition(v.begin(), v.end(),
[](int x) { return x % 3 == 0; });
auto pivot2 = std::partition(pivot1, v.end(),
[](int x) { return x % 3 == 1; });
std::cout << "3의 배수: ";
for (auto it = v.begin(); it != pivot1; ++it) {
std::cout << *it << " "; // 3 6 9
}
std::cout << "\n나머지 1: ";
for (auto it = pivot1; it != pivot2; ++it) {
std::cout << *it << " "; // 1 4 7
}
std::cout << "\n나머지 2: ";
for (auto it = pivot2; it != v.end(); ++it) {
std::cout << *it << " "; // 2 5 8
}
std::cout << "\n";
}
// 주석의 출력은 그룹 구성이며, 그룹 안의 순서는 구현에 따라 다를 수 있음3-way 분할의 요령은 두 번째 partition을 전체가 아니라 [pivot1, end)에만 적용하는 것입니다. 첫 번째 호출로 3의 배수를 앞으로 모은 뒤 남은 구간만 다시 나누므로, 전체 비용은 두 번의 선형 탐색입니다. 같은 방식으로 k개 그룹이 필요하면 k-1번 분할하면 되지만, 그룹이 많아지면 std::sort에 그룹 번호를 키로 주는 편이 코드가 단순할 수 있습니다. 퀵 정렬에서 중복 값이 많은 배열을 빠르게 처리하는 “Dutch National Flag”(피벗보다 작음·같음·큼) 분할도 이 아이디어의 변형이며, 한 번의 순회로 세 그룹을 만드는 전용 구현이 따로 있습니다.
partition vs stable_partition
| 항목 | partition | stable_partition |
|---|---|---|
| 같은 그룹 안의 상대 순서 | 보장하지 않음 | 유지 |
| 시간 | O(n) | 버퍼 확보 시 O(n), 아니면 O(n log n) 교환 |
| 추가 메모리 | 없음 | 임시 버퍼 할당 시도 |
| 반복자 요구 | forward iterator | bidirectional iterator |
두 알고리즘의 비용 차이는 구현 방식에서 옵니다. partition은 양방향 반복자가 주어지면 양 끝에서 안쪽으로 걸어오며 “앞에 있으면 안 되는 원소”와 “뒤에 있으면 안 되는 원소”를 찾아 서로 교환합니다. 멀리 떨어진 원소끼리 바꾸므로 순서가 섞이지만, 추가 메모리가 없고 교환 횟수도 최대 n/2번입니다(forward 반복자만 있으면 최대 n번). stable_partition은 순서를 지키기 위해 임시 버퍼를 할당해 한쪽 그룹을 옮겨 두었다가 다시 채우며, 버퍼를 할당하지 못하면 분할 정복과 회전(rotate)으로 대신하느라 O(n log n)이 됩니다. 즉 stable_partition은 힙 할당이 일어날 수 있는 알고리즘이라, 실시간 루프나 할당을 금지한 코드에서는 주의가 필요합니다.
같은 그룹 안에서의 순서가 중요하지 않다면 partition이 더 싸고 빠릅니다. 원래 순서를 유지한 채 두 덩이로 나누고 싶다면 stable_partition이 맞습니다. 결과를 어차피 두 컨테이너로 따로 다룬다면 partition_copy가 의도를 가장 잘 드러냅니다.
partition_point: 전제와 이진 탐색
partition_point(first, last, pred)는 범위가 이미 다음 조건을 만족할 때만 올바른 결과를 줍니다.
[first, mid)의 모든 요소에pred가 참입니다.[mid, last)의 모든 요소에pred가 거짓입니다.
이 전제는 함수의 사전 조건이라, 깨진 범위에 호출하면 동작이 정의되지 않습니다. 실제로는 크래시보다 엉뚱한 위치를 돌려주는 경우가 대부분이라 더 찾기 어렵습니다. 확신이 없으면 디버그 빌드에서 assert(std::is_partitioned(first, last, pred))로 확인하는 것이 좋습니다. partition_point는 이진 탐색으로 첫 번째 거짓 위치를 찾으며, 조건 호출은 O(log n)번입니다. 다만 std::list 같은 random access가 아닌 반복자에서는 중간 지점까지 이동하는 데 O(n)이 들기 때문에 전체 시간은 선형입니다.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> v = {2, 4, 6, 1, 3, 5}; // 이미 짝수 | 홀수로 분할된 범위
auto pivot = std::partition_point(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
std::cout << "분할 지점: " << std::distance(v.begin(), pivot) << "\n"; // 3
}정렬된 범위는 “기준값보다 작다”는 조건에 대해 자연스럽게 분할되어 있으므로, partition_point는 lower_bound와 같은 위치를 찾습니다.
std::vector<int> sorted = {1, 3, 5, 7, 9};
auto it = std::partition_point(sorted.begin(), sorted.end(),
[](int x) { return x < 6; });
// it는 처음으로 6 이상인 원소(7)를 가리킴
// std::lower_bound(sorted.begin(), sorted.end(), 6)과 같은 결과점수 순으로 정렬된 학생 목록에서 합격선 이상인 인원을 세는 경우처럼 키 기준으로 정렬된 데이터에서 경계만 필요하다면 lower_bound/upper_bound나 partition_point가 적합합니다. 조건이 “점수가 기준 이상이면서 출석률이 80% 이상”처럼 비교자로 표현하기 어색할 때 partition_point가 특히 편합니다. 물론 그 조건에 대해서도 범위가 분할되어 있어야 합니다.
퀵 정렬 한 단계 스케치
퀵 정렬의 핵심은 피벗을 기준으로 범위를 “작은 그룹 | 큰 그룹”으로 한 번에 나누는 것이며, 이것이 곧 std::partition입니다. 교육용으로 “피벗보다 작은 값을 앞으로”만 보여 주면 다음과 같습니다.
#include <algorithm>
#include <vector>
void partition_step(std::vector<int>& a, int pivot) {
std::partition(a.begin(), a.end(), [pivot](int x) { return x < pivot; });
}완전한 퀵 정렬은 피벗을 구간 안에 확정시키고 양쪽 부분 구간을 재귀하는 등 추가 로직이 필요하며, 실무에서는 std::sort(인트로소트 계열)를 쓰는 것이 일반적입니다. 여기서 기억할 점은 partition 한 번이 선형이라는 것입니다.
이 스케치를 그대로 재귀에 쓰면 흔한 함정에 빠집니다. 조건이 x < pivot이고 피벗 값 자체는 오른쪽 그룹에 남으므로, 배열에 피벗과 같은 값이 여러 개 있거나 피벗이 최솟값이면 왼쪽 그룹이 비어 버립니다. 그러면 오른쪽 구간의 크기가 줄지 않아 무한 재귀가 되고 결국 스택 오버플로우로 끝납니다. 교재의 퀵 정렬이 피벗을 따로 빼 두었다가 분할 뒤 경계 위치로 옮겨 “확정”시키는 이유가 이것입니다. 직접 구현할 일은 거의 없지만, “partition 결과의 한쪽이 비어 있을 수 있다”는 점은 이 알고리즘을 응용할 때 항상 확인해야 하는 경계 조건입니다.
실무 패턴
우선순위 처리
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
std::string name;
int priority;
bool urgent;
};
void processTasks(std::vector<Task>& tasks) {
// 긴급 작업을 앞으로
auto pivot = std::stable_partition(tasks.begin(), tasks.end(),
[](const Task& t) { return t.urgent; });
for (auto it = tasks.begin(); it != pivot; ++it) {
std::cout << "긴급: " << it->name << '\n';
}
for (auto it = pivot; it != tasks.end(); ++it) {
std::cout << "일반: " << it->name << '\n';
}
}여기서 stable_partition을 쓴 이유는 작업 목록이 보통 도착 순서나 우선순위 순으로 이미 정렬되어 있기 때문입니다. partition을 쓰면 긴급 작업끼리의 순서가 섞여 먼저 들어온 긴급 작업이 뒤로 밀릴 수 있습니다. 다만 이 함수는 인자로 받은 tasks 자체를 재배치한다는 점을 호출자가 알아야 합니다. 원본 순서를 유지해야 한다면 인덱스나 포인터 배열을 분할하거나, partition_copy로 두 목록을 새로 만드는 편이 부작용이 없습니다. 같은 방식으로 프리미엄 사용자와 일반 사용자, 실패한 요청과 성공한 요청처럼 두 그룹을 순서대로 처리하는 코드에 그대로 적용할 수 있습니다.
조건부 삭제
#include <algorithm>
#include <vector>
template<typename T, typename Pred>
void removeIf(std::vector<T>& vec, Pred pred) {
// 남길 요소를 앞으로, 삭제할 요소를 뒤로
auto pivot = std::partition(vec.begin(), vec.end(),
[&pred](const T& item) { return !pred(item); });
vec.erase(pivot, vec.end());
}
// 사용
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
removeIf(numbers, [](int x) { return x % 2 == 0; });
// 결과: 1, 3, 5 (남은 원소의 순서는 보장되지 않음)이 패턴은 동작하지만 표준 관용구와 비교하면 차이가 있습니다. partition은 불안정하므로 남은 원소의 순서가 바뀔 수 있습니다. 표준의 erase-remove 관용구(vec.erase(std::remove_if(...), vec.end()))나 C++20의 std::erase_if(vec, pred)는 남는 원소의 순서를 유지하면서 같은 O(n)으로 동작합니다. 반면 remove_if는 뒤쪽 원소를 “이동된 뒤 남은 상태”로 두기 때문에, 삭제할 원소를 지우기 전에 사용해야 하는 경우(예: 삭제 대상에 대해 정리 작업 실행)에는 쓸 수 없습니다. 이때는 partition이나 stable_partition으로 삭제 대상을 뒤로 모아 처리한 뒤 erase하는 방식이 유용합니다. 순서가 필요 없고 삭제 대상을 먼저 사용해야 할 때가 이 패턴이 맞는 자리입니다.
C++20 ranges 버전
std::ranges::partition(v, pred)처럼 컨테이너를 통째로 넘길 수 있고, 반환값이 반복자 하나가 아니라 false 그룹 구간(subrange)입니다. 또 프로젝션을 지원해 std::ranges::partition(tasks, std::identity{}, &Task::urgent)처럼 멤버를 직접 기준으로 삼을 수 있습니다. 자세한 동작은 cppreference의 partition 문서에 정리되어 있습니다.
#include <algorithm>
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6};
auto odd_part = std::ranges::partition(v, [](int x) { return x % 2 == 0; });
// odd_part.begin()이 기존 반환값(pivot)에 해당
v.erase(odd_part.begin(), odd_part.end()); // 홀수 제거