What is Partitioning Algorithms in C++?

Reorder, inspect, and copy elements based on a predicate with std::partition and its companion algorithms.

Which C++ standard introduced Partitioning Algorithms?

Partitioning Algorithms was introduced in C++98.

What is the difficulty level of Partitioning Algorithms?

Partitioning Algorithms is considered Basic-level C++ material.

Partitioning Algorithms

Partitioningsince C++98

Partitioning algorithms reorder elements in a range so that all elements satisfying a unary predicate appear before all elements that do not, returning an iterator to the boundary between the two groups.

Overview

The partitioning family in <algorithm> consists of five algorithms. Each addresses a distinct use case:

Algorithm	Since	Iterator requirement	Key property
`std::partition`	C++98	ForwardIterator¹	Unstable — relative order within groups unspecified
`std::stable_partition`	C++98	BidirectionalIterator	Preserves relative order within each group
`std::is_partitioned`	C++11	InputIterator	Query only — does not modify the range
`std::partition_point`	C++11	ForwardIterator	O(log N) binary search for the boundary
`std::partition_copy`	C++11	InputIterator	Non-destructive — copies to two destinations

¹ C++11 relaxed std::partition from BidirectionalIterator to ForwardIterator.

C++17 added execution policy overloads (std::execution::par, std::execution::par_unseq) for all five. C++20 introduced std::ranges:: counterparts with projection support and sentinel-based interfaces.

The partition point — the iterator returned by std::partition and std::stable_partition, and the query target of std::partition_point — marks the boundary: [first, partition_point) satisfies the predicate; [partition_point, last) does not.

Syntax

cpp

Godbolt

#include <algorithm>

// Unstable partition — C++98; relaxed to ForwardIterator in C++11
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p);

// Stable partition — C++98; BidirectionalIterator required
template<class BidirIt, class UnaryPred>
BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPred p);

// Partition predicate check — C++11
template<class InputIt, class UnaryPred>
bool is_partitioned(InputIt first, InputIt last, UnaryPred p);

// Partition boundary via binary search — C++11; range must already be partitioned
template<class ForwardIt, class UnaryPred>
ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPred p);

// Non-destructive split — C++11
template<class InputIt, class OutputIt1, class OutputIt2, class UnaryPred>
std::pair<OutputIt1, OutputIt2>
partition_copy(InputIt first, InputIt last,
               OutputIt1 out_true, OutputIt2 out_false,
               UnaryPred p);

C++20 Ranges

cpp

Godbolt

#include <algorithm>

// All five have std::ranges:: counterparts since C++20.
// They accept sentinels, ranges, and projections directly.
auto [mid, end] = std::ranges::partition(v, pred, &Widget::priority); // projection
auto pt         = std::ranges::stable_partition(v, pred);
bool ok         = std::ranges::is_partitioned(v, pred);
auto boundary   = std::ranges::partition_point(v, pred);
auto [o1, o2]   = std::ranges::partition_copy(v, out_true, out_false, pred);

Examples

std::partition — threshold split

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<double> prices = {9.99, 45.00, 3.50, 120.00, 19.95, 5.00, 75.50};

    auto mid = std::partition(prices.begin(), prices.end(),
                              [](double p) { return p < 20.0; });

    // [prices.begin(), mid) : all satisfy p < 20.0, order unspecified
    // [mid, prices.end())   : all do not satisfy p < 20.0, order unspecified
    for (auto it = prices.begin(); it != mid; ++it)
        std::cout << "cheap: " << *it << '\n';
    for (auto it = mid; it != prices.end(); ++it)
        std::cout << "expensive: " << *it << '\n';
}

Never discard the return value of std::partition. It is the primary output; throwing it away forces a redundant O(N) scan to recover it.

std::stable_partition — order-preserving split

When the relative order of elements within each partition group must be preserved (ranked results, log lines, UI elements), use stable_partition:

cpp

Godbolt

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

struct Task { int priority; std::string name; };

void front_load_urgent(std::vector<Task>& tasks) {
    // priority == 0 tasks move to front; order within each group preserved.
    std::stable_partition(tasks.begin(), tasks.end(),
                          [](const Task& t) { return t.priority == 0; });
}

Complexity: O(N) time with O(N) auxiliary allocation, degrading silently to O(N log N) time if the allocator fails. Profile on memory-constrained targets.

std::partition_copy — non-destructive split into two containers

cpp

Godbolt

#include <algorithm>
#include <vector>

std::pair<std::vector<int>, std::vector<int>>
split_odd_even(const std::vector<int>& nums) {
    std::vector<int> evens, odds;
    evens.reserve(nums.size());
    odds.reserve(nums.size());

    std::partition_copy(nums.cbegin(), nums.cend(),
                        std::back_inserter(evens),
                        std::back_inserter(odds),
                        [](int n) { return n % 2 == 0; });
    return {std::move(evens), std::move(odds)};
}

The input range is unchanged. The two output ranges must not overlap each other or the input.

std::partition_point — O(log N) boundary lookup

For ranges that are known to be partitioned, partition_point locates the boundary via binary search in O(log N) predicate applications — much faster than a linear scan for large datasets:

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <cassert>

int main() {
    // Sorted ranges are trivially partitioned by any threshold predicate.
    std::vector<int> sorted = {1, 3, 5, 7, 9, 10, 12, 14};

    // Find first element >= 10 (same mechanics as std::lower_bound).
    auto it = std::partition_point(sorted.begin(), sorted.end(),
                                   [](int n) { return n < 10; });
    // *it == 10
    assert(*it == 10);
}

partition_point shares its precondition with std::lower_bound: calling it on an unpartitioned range is undefined behaviour with no diagnostic.

std::is_partitioned — validation and assertions

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <stdexcept>

template<class It, class Pred>
It safe_partition_point(It first, It last, Pred pred) {
    // is_partitioned is O(N); use only where correctness outweighs cost.
    assert(std::is_partitioned(first, last, pred)
           && "partition_point precondition violated");
    return std::partition_point(first, last, pred);
}

C++17 Parallel Execution

cpp

Godbolt

#include <algorithm>
#include <execution>   // C++17

std::vector<int> v = /* ... */;
auto pred = [](int n) { return n > 0; };

// C++17: parallel partition
std::partition(std::execution::par, v.begin(), v.end(), pred);

// C++17: parallel partition_copy
std::vector<int> pos, neg;
pos.resize(v.size()); neg.resize(v.size());
std::partition_copy(std::execution::par_unseq,
                    v.begin(), v.end(),
                    pos.begin(), neg.begin(), pred);

Best Practices

Prefer partition over stable_partition when order within groups is irrelevant. partition is O(N) with no extra allocation; stability has a measurable cost.
Reserve output containers before partition_copy. The algorithm cannot know the split ratio in advance; an upper bound of std::distance(first, last) avoids reallocation.
Use partition_point on pre-sorted data as a fast alternative to lower_bound. A sorted range is partitioned by any threshold predicate, and partition_point expresses the intent more directly when the predicate is not a simple comparison.
With C++20 ranges, leverage projections. std::ranges::partition(v, pred, &T::field) eliminates wrapper lambdas and is easier to read.
Gate partition_point calls with is_partitioned in debug builds. The precondition is easy to violate silently; an assert costs one O(N) scan and avoids undefined behaviour during development.

Common Pitfalls

Assuming std::partition preserves order within groups. The standard gives no guarantee. Elements satisfying the predicate will all precede those that do not, but the order within each group is implementation-defined and not stable across compiler versions or optimization levels. If order within groups matters, use stable_partition.

Calling partition_point on an unpartitioned range. This is undefined behaviour that often silently produces a wrong iterator. Tools like AddressSanitizer do not catch it. Add assert(std::is_partitioned(...)) around any call where the invariant is not statically guaranteed.

Silent O(N log N) degradation in stable_partition. When stable_partition fails to allocate its auxiliary buffer it does not throw — it silently degrades to the slower algorithm. If you're partitioning inside a tight loop on an embedded or memory-limited target, measure.

Overlapping output ranges in partition_copy. Passing iterators into the same underlying container for both out_true and out_false produces undefined behaviour unless the ranges are provably disjoint by the data. Use separate std::vector buffers.

Passing raw output iterators without reservation to partition_copy. std::back_inserter handles growth correctly, but raw iterators into an undersized container produce out-of-bounds writes.