Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ Splitting a vector in two groups

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.

C++ partition_copy and partition_point

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

C++
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. Use stable_partition when order matters.
  • Complexity: partition does O(n) predicate calls and at most n/2 swaps. stable_partition is O(n) if extra memory can be allocated and O(n log n) otherwise, so it may allocate.
  • Iterator requirements: partition works with forward iterators, which also makes it usable on std::list. stable_partition needs bidirectional iterators.
  • partition_point uses binary search, so it takes O(log n) predicate calls on random-access ranges. It is the generalization of lower_bound.
  • Quicksort and selection: std::nth_element is implemented with the same idea; use it if you only need the k-th element or the top k.
  • Ranges: std::ranges::partition, stable_partition and partition_copy (C++20) take a range and a projection.
  • Parallel: the non-ranges overloads accept an execution policy; see execution policies.