C++ Partition Algorithms: partition, stable_partition & partition_point

What is partition?

Partition moves elements so that pred holds for an initial subrange and fails for the rest.

#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

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

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).

---

Related posts

• C++ Algorithm Sort
• C++ Algorithm Guide
• C++ Algorithm Search

Keywords

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