Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::partition — partition a range by a predicate

std::partition rearranges a range so that elements satisfying a predicate precede the others. It returns the boundary iterator between the groups, but does not guarantee that order within either group is preserved.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::partition(first, last, pred)

std::partition, declared in <algorithm>, modifies the range [first, last): elements for which pred yields true precede elements yielding false. It neither sorts values nor removes elements. This description covers the overload without an execution policy.

The returned iterator boundary points to the first element of the second group. The range [first, boundary) satisfies the predicate, and [boundary, last) does not. If every element matches, the result is last; if none matches, it is first. For an empty range, these iterators are equal.

At least forward iterators and the ability to swap the referenced values are required. The predicate must not modify the elements it examines. Order within either group is not guaranteed; use std::stable_partition when that order must be preserved.

For N elements, the algorithm makes exactly N predicate calls and at most N swaps, or at most N/2 swaps with bidirectional iterators. The example prints group sizes and checks the partition with std::is_partitioned, rather than assuming a particular value order.

Examples

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

int main() {
    std::array<int, 6> values{1, 2, 3, 4, 5, 6};
    const auto is_even = [](int value) { return value % 2 == 0; };

    const auto boundary = std::partition(values.begin(), values.end(), is_even);

    std::cout << "matching: " << std::distance(values.begin(), boundary) << '\n';
    std::cout << "other: " << std::distance(boundary, values.end()) << '\n';
    std::cout << "partitioned: " << std::boolalpha
              << std::is_partitioned(values.begin(), values.end(), is_even) << '\n';
}

Result

matching: 3
other: 3
partitioned: true

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources