When is partition_point used?

On a range already partitioned so that pred is true then false — it finds the split in O(log n) with binary search.

Relation to quicksort?

Quicksort’s partition step is the same idea with a chosen pivot policy.

How should the predicate work?

Elements satisfying pred must end up before those that do not — do not confuse with sort comparators.

[2026] C++ Partition Algorithms: partition, stable_partition & partition_point

Q: partition vs stable_partition?

partition is faster and does not preserve relative order within each partition; stable_partition keeps relative order at higher cost.

2026년 3월 12일 · 16분 읽기 · 수정 2026년 3월 30일 Intermediate tutorial

이 글의 핵심

Split ranges with std::partition and stable_partition; find boundaries with partition_point and is_partitioned — quicksort ties, binary search, and stable grouping.

What is partition?

Partition moves elements so that pred holds for an initial subrange and fails for the rest. 아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

Algorithm	Stable	Time	Notes
`partition`	No	O(n)	Fast
`stable_partition`	Yes	O(n log n) typical	Preserves order
`partition_point`	—	O(log n)	Requires existing partition + monotonic pred
아래 코드는 mermaid를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

partition vs stable_partition (deep dive)

If order inside each group does not matter, `partition` is cheaper. If original order must be kept within groups, use `stable_partition` or partition_copy to two outputs.

partition_point

Requires all elements in [first, mid) satisfy pred and none in [mid, last) do — a monotonic partition. Then partition_point finds mid in logarithmic time.

std::vector<int> sorted = {1, 3, 5, 7, 9};
auto it = std::partition_point(sorted.begin(), sorted.end(),
    [](int x) { return x < 6; });

Quicksort step (sketch)

`partition` with `x < pivot` matches one step of quicksort; production code usually calls std::sort (introsort).

Partition and binary search

On sorted data, “first position where key condition holds” links to lower_bound / upper_bound. For stable grouping without sort, use stable_partition or partition_copy.

API summary

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

auto pivot = std::partition(begin, end, pred);
auto pivot = std::stable_partition(begin, end, pred);
auto pivot = std::partition_point(begin, end, pred);
bool ok = std::is_partitioned(begin, end, pred);
std::partition_copy(begin, end, out_true, out_false, pred);

FAQ

Covers definition, stability, return iterator, performance, `partition_copy`, `is_partitioned`, and resources (Effective STL, cppreference).

Keywords

std::partition, stable_partition, partition_point, is_partitioned, partition_copy, STL