CKTIS / C++
std::stable_partition — stable range partitioning
std::stable_partition rearranges a range so that elements satisfying a predicate precede the others. It preserves relative order within both groups and returns an iterator to the partition boundary.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
// Usage:
auto boundary = std::stable_partition(first, last, pred);std::stable_partition, declared in <algorithm>, modifies [first, last): elements for which pred yields true precede the others. Relative order is preserved separately within both groups. This is not sorting; std::partition does not guarantee this stability.
The returned iterator boundary points to the first element of the second group. It equals last when all elements satisfy the predicate and first when none do. For an empty range, the function returns first, and first == last. Bidirectional iterators are required, together with swappable, move-constructible, move-assignable elements. The predicate must not modify the elements it examines.
For the illustrated overload without an execution policy, a range of N elements requires exactly N predicate applications. There are at most N log₂ N swaps, reduced to O(N) with sufficient extra memory. Rearranging the existing range therefore does not imply a constant auxiliary-memory guarantee.
The example preserves the order of even numbers 2, 4, 6 and odd numbers 5, 7, 1; the second output line is the size of the first group. The displayed declaration targets C++23. The source is an evolving working draft that also includes later changes; its constexpr annotations must not automatically be applied to C++23.
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> values{5, 2, 7, 4, 1, 6};
const auto boundary = std::stable_partition(
values.begin(), values.end(),
[](int value) { return value % 2 == 0; });
for (auto it = values.begin(); it != values.end(); ++it) {
if (it != values.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n' << std::distance(values.begin(), boundary) << '\n';
}
Result
2 4 6 5 7 1 3
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.