C++ partition·stable_partition·partition_point: 조건으로 범위 나누기

작성 0xmote · 2026년 3월 20일 · 16분 읽기 · 수정 2026년 9월 24일 중급 튜토리얼

이 글의 핵심

partition은 요소를 지우지 않고 재배치만 하기 때문에 반환된 반복자를 무시하면 어디까지가 조건을 만족하는지 알 수 없습니다. stable_partition이 추가 메모리를 쓰는 이유와 성능 차이, partition_point가 전제로 삼는 조건을 짚고, 우선순위 처리나 조건부 삭제 같은 실무 패턴에 적용하는 방법을 설명합니다.

Partition이란?

Partition (분할) 은 조건에 따라 요소를 두 그룹으로 나누는 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; });

// [2, 4, 6, 1, 3, 5] (순서는 보장 안 됨)

왜 필요한가?:

필터링: 조건별로 그룹화
성능: O(n) 시간 복잡도
유연성: 커스텀 조건 지원
전처리: 정렬 전 분할

// ❌ 수동 분할: 복잡
std::vector<int> evens, odds;
for (int x : v) {
    if (x % 2 == 0) {
        evens.push_back(x);
    } else {
        odds.push_back(x);
    }
}

// ✅ partition: 간결
auto pivot = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

두 코드는 결과를 담는 방식이 다릅니다. 수동 분할은 벡터 두 개를 새로 할당하고 원소를 복사하지만, partition은 추가 메모리 없이 원래 벡터 안에서 원소를 교환해 재배치합니다. 대신 결과가 “하나의 벡터 + 경계 반복자”라는 형태가 되므로, 반환된 pivot을 반드시 받아 두어야 어디까지가 참 그룹인지 알 수 있습니다. 반환값을 버리면 원소는 재배치되었는데 경계는 모르는 상태가 되고, 다시 알려면 partition_point로 O(log n) 탐색을 한 번 더 해야 합니다.

Partition 동작 원리:

flowchart LR
    A["[1, 2, 3, 4, 5, 6]"] --> B[partition]
    B --> C["[2, 4, 6, 1, 3, 5]"]
    C --> D["true 그룹"]
    C --> E["false 그룹"]
    D -.-> |pivot| E

Partition 종류:

알고리즘	안정성	시간 복잡도	사용 시나리오
`partition`	❌ 불안정	O(n)	빠른 분할
`stable_partition`	✅ 안정	버퍼 확보 시 O(n), 아니면 O(n log n)	순서 유지
`partition_point`	-	O(log n)	분할 지점 찾기
`partition_copy`	✅ 안정	O(n)	복사하며 분할

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: 빠름, 순서 보장 안 됨
auto pivot1 = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

// stable_partition: 느림, 순서 유지
auto pivot2 = std::stable_partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

기본 사용

#include <algorithm>

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 << " ";
}

실전 예시

예시 1: 필터링

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, -2, 3, -4, 5, -6, 7, -8};
    
    // 양수를 앞으로
    auto pivot = std::partition(numbers.begin(), numbers.end(),
         [](int x) { return x > 0; });
    
    std::cout << "양수: ";
    for (auto it = numbers.begin(); it != pivot; ++it) {
        std::cout << *it << " ";
    }
}

예시 2: stable_partition

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    
    // 안정 분할 (순서 유지)
    auto pivot = 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
    }
}

예시 3: partition_point

#include <algorithm>

int main() {
    std::vector<int> v = {2, 4, 6, 1, 3, 5};
    
    // 이미 분할된 범위
    std::partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
    
    // 분할 지점 찾기
    auto pivot = std::partition_point(v.begin(), v.end(),
         [](int x) { return x % 2 == 0; });
    
    std::cout << "분할 지점: " << std::distance(v.begin(), pivot) << std::endl;
}

예시 4: 3-way 분할

#include <algorithm>

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
    }
}
// 주석의 출력은 그룹 구성이며, 그룹 안의 순서는 구현에 따라 다를 수 있음

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 log n), 추가 메모리 사용 가능
용도	퀵 정렬 피벗 단계, 순서 무관 필터	UI 목록, 타임스탬프 순 유지가 필요한 파이프라인

두 알고리즘의 비용 차이는 구현 방식에서 옵니다. partition은 양 끝에서 안쪽으로 걸어오며 “앞에 있으면 안 되는 원소”와 “뒤에 있으면 안 되는 원소”를 찾아 서로 교환합니다. 멀리 떨어진 원소끼리 바꾸므로 순서가 섞이지만, 추가 메모리가 없고 교환 횟수도 적습니다(양방향 반복자라면 최대 n/2번). 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가 거짓

즉 단조(monotonic) 한 분할입니다. 전제가 깨지면 결과는 의미가 없거나 UB입니다. partition_point는 내부적으로 이진 탐색으로 “첫 번째 false” 위치를 O(log n)에 찾습니다.

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::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 결과의 한쪽이 비어 있을 수 있다”는 점은 이 알고리즘을 응용할 때 항상 확인해야 하는 경계 조건입니다.

partition과 이진 탐색의 조합

정렬된 범위에서 “임계값 이상이 처음 나오는 위치”는 lower_bound로 구합니다. 이는 정렬에 의해 자연스럽게 pred(*it)가 앞쪽에서만 참이 되는 단조 구조와 맞닿아 있습니다.

원본 순서를 유지하며 두 그룹으로만 나누기 → stable_partition 또는 partition_copy
이미 키 기준 정렬되어 있고 경계만 필요 → lower_bound / upper_bound / partition_point류가 적합

점수 순으로 정렬된 학생 목록에서 “합격선 이상 인원”은 lower_bound로 경계를 찾고 std::distance로 개수를 구하면 됩니다.

분할 알고리즘

// partition: 불안정
auto pivot = std::partition(begin, end, pred);

// stable_partition: 안정 (순서 유지)
auto pivot = std::stable_partition(begin, end, pred);

// partition_point: 분할 지점
auto pivot = std::partition_point(begin, end, pred);

// is_partitioned: 분할 확인
bool partitioned = std::is_partitioned(begin, end, pred);

// partition_copy: 복사하며 분할
std::partition_copy(begin, end, out1, out2, pred);

자주 발생하는 문제

문제 1: 순서

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: 순서 보장 안 됨
std::partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
// 가능: [2, 6, 4, 1, 3, 5]

// stable_partition: 순서 유지
std::stable_partition(v.begin(), v.end(),  [](int x) { return x % 2 == 0; });
// 보장: [2, 4, 6, 1, 3, 5]

문제 2: partition_point

std::vector<int> v = {1, 2, 3, 4, 5};

// ❌ 분할 안 됨
// auto pivot = std::partition_point(v.begin(), v.end(), pred);  // 정의되지 않은 동작

// ✅ 분할 후
std::partition(v.begin(), v.end(), pred);
auto pivot = std::partition_point(v.begin(), v.end(), pred);

문제 3: 성능

// partition: O(n), 불안정
std::partition(v.begin(), v.end(), pred);

// stable_partition: 버퍼 확보 시 O(n), 실패 시 O(n log n), 안정
std::stable_partition(v.begin(), v.end(), pred);

// 순서 중요하지 않으면 partition 사용

문제 4: 반환값

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition 반환: 분할 지점 반복자
auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

활용 패턴

// 1. 필터링
auto pivot = std::partition(v.begin(), v.end(), pred);

// 2. 안정 분할
auto pivot = std::stable_partition(v.begin(), v.end(), pred);

// 3. 분할 지점
auto pivot = std::partition_point(v.begin(), v.end(), pred);

// 4. 복사 분할
std::partition_copy(v.begin(), v.end(), out1, out2, pred);

실무 패턴

패턴 1: 우선순위 처리

#include <algorithm>
#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로 두 목록을 새로 만드는 편이 부작용이 없습니다.

패턴 2: 조건부 삭제

#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하는 방식이 유용합니다. 순서가 필요 없고 삭제 대상을 먼저 사용해야 할 때가 이 패턴이 맞는 자리입니다.

패턴 3: 그룹별 처리

#include <algorithm>
#include <vector>
#include <string>

struct User {
    std::string name;
    bool premium;
    int age;
};

void processUsers(std::vector<User>& users) {
    // 프리미엄 사용자를 앞으로
    auto pivot = std::stable_partition(users.begin(), users.end(),
         [](const User& u) { return u.premium; });
    
    // 프리미엄 사용자 처리
    std::cout << "프리미엄 사용자:\n";
    for (auto it = users.begin(); it != pivot; ++it) {
        std::cout << "- " << it->name << '\n';
    }
    
    // 일반 사용자 처리
    std::cout << "일반 사용자:\n";
    for (auto it = pivot; it != users.end(); ++it) {
        std::cout << "- " << it->name << '\n';
    }
}

FAQ

Q1: partition은 무엇인가요?

A: 조건에 따라 요소를 두 그룹으로 나누는 알고리즘입니다.

auto pivot = std::partition(v.begin(), v.end(),
     [](int x) { return x % 2 == 0; });

Q2: 안정성은?

partition: 불안정 (순서 보장 안 됨)
stable_partition: 안정 (순서 유지)

// partition: [2, 6, 4, 1, 3, 5] (가능)
// stable_partition: [2, 4, 6, 1, 3, 5] (보장)

Q3: 반환값은?

A: 분할 지점 반복자를 반환합니다.

auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

Q4: 성능은?

partition: O(n), 추가 메모리 없음
stable_partition: 임시 버퍼를 확보하면 O(n), 확보하지 못하면 O(n log n)

// 빠름
std::partition(v.begin(), v.end(), pred);

// 느림 (순서 유지)
std::stable_partition(v.begin(), v.end(), pred);

Q5: partition_point는?

A: 이미 분할된 범위에서 분할 지점을 찾습니다. O(log n) 시간 복잡도입니다.

// 분할 후
std::partition(v.begin(), v.end(), pred);

// 분할 지점 찾기
auto pivot = std::partition_point(v.begin(), v.end(), pred);

Q6: partition_copy는?

A: 복사하며 분할합니다.

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; });

Q7: 분할 확인은?

A: std::is_partitioned 를 사용합니다.

if (std::is_partitioned(v.begin(), v.end(), pred)) {
    std::cout << "분할됨\n";
}

Q8: C++20 ranges 버전은 무엇이 다른가요?

A: std::ranges::partition(v, pred)처럼 컨테이너를 통째로 넘길 수 있고, 반환값이 반복자 하나가 아니라 false 그룹 구간(subrange)입니다. 또 프로젝션을 지원해 std::ranges::partition(tasks, std::identity{}, &Task::urgent)처럼 멤버를 직접 기준으로 삼을 수 있습니다. 자세한 동작은 cppreference의 partition 문서에 정리되어 있습니다.

관련 글: algorithm, sort, remove_if.

Partition은 조건에 따라 요소를 두 그룹으로 나누는 STL 알고리즘입니다.