C++ Reference ยท Algorithms
The std::partition algorithm
Reference for C++ std::partition, stable_partition, partition_point and partition_copy: split a range by a predicate, order guarantees and complexity.
std::partition rearranges a range so that every element for which a predicate returns true comes before every element for which it returns false. It returns an iterator to the first element of the second group (the partition point). It is the building block of quicksort and a cheap way to split data without allocating.
std::partition does not preserve the relative order inside each group. If you need the original order, use std::stable_partition. To keep the input intact and write both groups to different outputs, use std::partition_copy.
auto mid = std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; }); // [v.begin(), mid) are even, [mid, v.end()) are odd
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class BidirIt, class Pred> BidirIt partition(BidirIt first, BidirIt last, Pred pred); // ForwardIt is enough template<class BidirIt, class Pred> BidirIt stable_partition(BidirIt first, BidirIt last, Pred pred); template<class InputIt, class OutIt1, class OutIt2, class Pred> std::pair<OutIt1, OutIt2> partition_copy(InputIt first, InputIt last, OutIt1 out_true, OutIt2 out_false, Pred pred); template<class ForwardIt, class Pred> ForwardIt partition_point(ForwardIt first, ForwardIt last, Pred pred); template<class InputIt, class Pred> bool is_partitioned(InputIt first, InputIt last, Pred pred);
| Name | Description |
|---|---|
first, last |
The half-open range [first, last). |
pred |
Called with an element; true sends it to the first group. |
out_true, out_false |
Output iterators for partition_copy. |
Returns: partition and stable_partition return the iterator to the first element of the false group (or last if all satisfy the predicate). partition_copy returns a pair of the two output iterators. partition_point returns the first element that does not satisfy the predicate. is_partitioned returns a bool.
Errors / undefined behavior: partition_point requires the range to be already partitioned, otherwise the result is meaningless. The predicate must not modify the elements.
Usage notes
- Order is not stable for
std::partition: elements within each group may be shuffled. Usestable_partitionwhen order matters. - Complexity:
partitiondoes O(n) predicate calls and at most n/2 swaps.stable_partitionis O(n) if extra memory can be allocated and O(n log n) otherwise, so it may allocate. - Iterator requirements:
partitionworks with forward iterators, which also makes it usable onstd::list.stable_partitionneeds bidirectional iterators. partition_pointuses binary search, so it takes O(log n) predicate calls on random-access ranges. It is the generalization oflower_bound.- Quicksort and selection:
std::nth_elementis implemented with the same idea; use it if you only need the k-th element or the top k. - Ranges:
std::ranges::partition,stable_partitionandpartition_copy(C++20) take a range and a projection. - Parallel: the non-ranges overloads accept an execution policy; see execution policies.