C++ partition, stable_partition and partition_point: Splitting Ranges by a Predicate

Partitioning reorders a range so that all elements for which the predicate is true appear before those for which it is false. It runs in linear time and is not stable unless you use stable_partition (extra cost / memory). The returned iterator points to the first element that fails the predicate (or end if all pass). Typical uses: quickselect, splitting data for branchy processing, or as a step before partial_sort.

What is partition?

Partition moves “true” elements to the front and “false” elements to the back. Relative order within each group is not guaranteed for std::partition; use stable_partition when order must be preserved.

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// Move even numbers to the front
auto pivot = std::partition(v.begin(), v.end(), 
    [](int x) { return x % 2 == 0; });

// e.g. [6, 2, 4, 3, 5, 1] with libstdc++; only "evens before odds" is guaranteed

The exact output depends on the implementation. A typical std::partition for bidirectional iterators works like quick sort’s Hoare partition: one iterator moves forward past elements that already satisfy the predicate, another moves backward past elements that do not, and when both stop, the two elements are swapped. That is why 6 ends up at the front here and why the odd numbers come out reversed. The algorithm applies the predicate exactly once per element and does at most about n/2 swaps, which is as cheap as a reordering can be; the price is that neither group keeps its original order.

Why is it useful?:

• Filtering: Group elements based on a condition
• Performance: O(n) time complexity
• Flexibility: Supports custom conditions
• Preprocessing: Partitioning before sorting

// ❌ Manual partitioning: complex
std::vector<int> evens, odds;
for (int x : v) {
    if (x % 2 == 0) {
        evens.push_back(x);
    } else {
        odds.push_back(x);
    }
}

// ✅ Partition: concise
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

The two versions are not equivalent, and the difference is the real reason to choose one or the other. The manual loop keeps both groups in their original order and leaves v untouched, at the cost of two new vectors and their allocations. std::partition works in place with no allocation, but it destroys the original order. When you need the groups as separate containers anyway, std::partition_copy (shown later) expresses the loop in one call and keeps the order.

How Partition Works:

flowchart LR
    A["[1, 2, 3, 4, 5, 6]"] --> B[partition]
    B --> C["[2, 4, 6, 1, 3, 5]"]
    C --> D["true group"]
    C --> E["false group"]
    D -.-> |pivot| E

Types of Partition:

Algorithm	Stability	Time Complexity	Use Case
partition	❌ Unstable	O(n)	Fast partitioning
stable_partition	✅ Stable	O(n) with a buffer, O(n log n) without	Preserve order
partition_point	-	O(log n) predicate calls	Find partition point
partition_copy	✅ Stable	O(n)	Partition while copying

stable_partition is the one whose cost is easy to misjudge. It tries to allocate a temporary buffer (in libstdc++ and libc++ as large as the range); with the buffer it moves elements in linear time, and only when the allocation fails does it fall back to a divide-and-conquer algorithm that uses O(n log n) swaps. In practice the extra cost is the allocation and the extra moves, which matter for large ranges of expensive-to-move objects and in code that must not allocate.

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: fast, order not guaranteed
auto pivot1 = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

// stable_partition: slower, preserves order
auto pivot2 = std::stable_partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

Basic Usage

#include <algorithm>

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Partition
auto pivot = std::partition(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; });

std::cout << "Even numbers: ";
for (auto it = v.begin(); it != pivot; ++it) {
    std::cout << *it << " ";
}

std::cout << "\nOdd numbers: ";
for (auto it = pivot; it != v.end(); ++it) {
    std::cout << *it << " ";
}

The returned iterator is the whole point of the algorithm: [v.begin(), pivot) is the “true” group and [pivot, v.end()) the “false” group, so std::distance(v.begin(), pivot) is the number of matches. Discarding the return value, as people sometimes do when they think of partition as a kind of sort, forces a second scan to find the boundary. The iterator is only valid until the vector is modified again; any insertion that reallocates invalidates it.

Practical Examples

Example 1: Filtering

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, -2, 3, -4, 5, -6, 7, -8};
    
    // Move positive numbers to the front
    auto pivot = std::partition(numbers.begin(), numbers.end(),
        [](int x) { return x > 0; });
    
    std::cout << "Positive numbers: ";
    for (auto it = numbers.begin(); it != pivot; ++it) {
        std::cout << *it << " ";  // 1 3 5 7 in some order
    }
}

“Filtering” here means grouping, not removing: every element is still in numbers, just rearranged. If you only need to visit the positives once, a plain loop with an if, or std::views::filter in C++20, avoids modifying the container at all. Partitioning pays off when you will process the groups several times, pass a group to a function expecting a contiguous range, or want to remove one group afterwards.

Example 2: stable_partition

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    
    // Stable partition (preserve order)
    auto pivot = std::stable_partition(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    
    for (int x : v) {
        std::cout << x << " ";  // 2 4 6 1 3 5
    }
}

Example 3: partition_point

#include <algorithm>

int main() {
    std::vector<int> v = {2, 4, 6, 1, 3, 5};
    
    // Already partitioned range
    std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    
    // Find partition point
    auto pivot = std::partition_point(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    
    std::cout << "Partition point: " << std::distance(v.begin(), pivot) << std::endl;  // 3
}

partition_point is a binary search over the predicate: it assumes the range is already partitioned and finds the boundary with O(log n) predicate calls. Here the std::partition call is redundant because v is already partitioned, but it shows the typical order of operations: partition once, then query the boundary cheaply later, for example after storing only the container. With forward iterators (such as std::forward_list), the number of predicate calls is still logarithmic, but advancing the iterators takes O(n) steps.

The more interesting use is on sorted data. A sorted range is partitioned with respect to any predicate of the form “element is less than x”, so std::partition_point(v.begin(), v.end(), [](int e) { return e < 42; }) is equivalent to std::lower_bound(v.begin(), v.end(), 42). The predicate form is handy when the search key is not an element, such as finding the first order whose timestamp is past a cutoff in a vector sorted by timestamp.

Example 4: 3-way Partitioning

#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // Partition by remainder when divided by 3
    auto pivot1 = std::partition(v.begin(), v.end(),
        [](int x) { return x % 3 == 0; });
    
    auto pivot2 = std::partition(pivot1, v.end(),
        [](int x) { return x % 3 == 1; });
    
    std::cout << "Multiples of 3: ";
    for (auto it = v.begin(); it != pivot1; ++it) {
        std::cout << *it << " ";  // 3, 6, 9 in some order
    }
    
    std::cout << "\nRemainder 1: ";
    for (auto it = pivot1; it != pivot2; ++it) {
        std::cout << *it << " ";  // 1, 4, 7 in some order
    }
    
    std::cout << "\nRemainder 2: ";
    for (auto it = pivot2; it != v.end(); ++it) {
        std::cout << *it << " ";  // 2, 5, 8 in some order
    }
}

The second call partitions only [pivot1, end), the part the first call left behind, so the multiples of 3 at the front are not disturbed. Two passes give three groups; k passes give k + 1 groups, each pass touching a shrinking remainder. For the classic three-way split around a pivot value (less than, equal to, greater than), the Dutch national flag algorithm does it in a single pass with three indices, which is what quick sort implementations use to handle many duplicate keys efficiently.

Partition Algorithms

// partition: unstable
auto pivot = std::partition(begin, end, pred);

// stable_partition: stable (preserves order)
auto pivot = std::stable_partition(begin, end, pred);

// partition_point: find partition point
auto pivot = std::partition_point(begin, end, pred);

// is_partitioned: check if partitioned
bool partitioned = std::is_partitioned(begin, end, pred);

// partition_copy: partition while copying
std::partition_copy(begin, end, out1, out2, pred);

All of these have range versions in C++20 (std::ranges::partition(v, pred)), which take the container directly and accept a projection, so std::ranges::partition(tasks, std::identity{}, &Task::urgent) partitions by a member without writing a lambda. Note that std::ranges::partition returns a subrange (the “false” group) rather than a single iterator. C++17 parallel overloads also exist (std::partition(std::execution::par, ...)), though for anything short of very large ranges the threading overhead outweighs the gain.

Common Issues

Issue 1: Order

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition: order not guaranteed
std::partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Possible: [6, 2, 4, 3, 5, 1]

// stable_partition on the original {1, 2, 3, 4, 5, 6}: preserves order
std::stable_partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Guaranteed: [2, 4, 6, 1, 3, 5]

A test that happens to produce the “nice” order with one standard library can fail with another, or after a library upgrade. A classic way this bites is a unit test that asserts the exact output of std::partition, passes for years on one compiler, and breaks the first time the project is built with a different toolchain. Assert the property you rely on (std::is_partitioned, or the group contents compared as sets) instead of a specific arrangement, or switch to stable_partition if the order is actually part of the requirement.

Issue 2: partition_point

std::vector<int> v = {1, 2, 3, 4, 5};

// ❌ Not partitioned
// auto pivot = std::partition_point(v.begin(), v.end(), pred);  // Undefined behavior

// ✅ After partitioning
std::partition(v.begin(), v.end(), pred);
auto pivot = std::partition_point(v.begin(), v.end(), pred);

On an unpartitioned range, partition_point does not fail loudly; it performs its binary search and returns some position that looks plausible and is wrong. Debug builds of some standard libraries check the precondition (_GLIBCXX_DEBUG, MSVC’s iterator debugging), which is a good reason to run tests with them occasionally. assert(std::is_partitioned(first, last, pred)) before the call documents the assumption at an O(n) cost in debug builds only.

Issue 3: Performance

// partition: O(n), unstable
std::partition(v.begin(), v.end(), pred);

// stable_partition: O(n) with a temporary buffer, O(n log n) without; stable
std::stable_partition(v.begin(), v.end(), pred);

// Use partition if order is not important

Issue 4: Return Value

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// partition returns: iterator to partition point
auto pivot = std::partition(v.begin(), v.end(), pred);

// [begin, pivot): true
// [pivot, end): false

Practical Patterns

Pattern 1: Priority Handling

#include <algorithm>
#include <vector>

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

void processTasks(std::vector<Task>& tasks) {
    // Move urgent tasks to the front
    auto pivot = std::stable_partition(tasks.begin(), tasks.end(),
        [](const Task& t) { return t.urgent; });
    
    // Process urgent tasks
    for (auto it = tasks.begin(); it != pivot; ++it) {
        std::cout << "Urgent: " << it->name << '\n';
    }
    
    // Process regular tasks
    for (auto it = pivot; it != tasks.end(); ++it) {
        std::cout << "Regular: " << it->name << '\n';
    }
}

stable_partition is the right choice here because the tasks presumably arrive in a meaningful order (submission time), and urgent tasks should keep that order among themselves. Moving a Task moves its std::string, which is cheap, but the temporary buffer is still an allocation per call; for a queue processed often, keeping two containers (urgent and regular) from the start avoids re-partitioning at all. Note that the priority field is unused: if tasks should also be ordered by priority, a single std::stable_sort with a key of (!urgent, priority) does both in one step.

Pattern 2: Conditional Removal

#include <algorithm>
#include <vector>

template<typename T, typename Pred>
void removeIf(std::vector<T>& vec, Pred pred) {
    // Move elements to be removed to the back
    auto pivot = std::partition(vec.begin(), vec.end(),
        [&pred](const T& item) { return !pred(item); });
    
    // Erase elements from the back
    vec.erase(pivot, vec.end());
}

// Usage
std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
removeIf(numbers, [](int x) { return x % 2 == 0; });
// Result: {1, 3, 5} in some order

This works, but it is not how the standard library removes elements, and the difference is instructive. std::remove_if keeps the survivors in their original order and moves them forward, leaving the tail in a valid but unspecified state, whereas partition swaps, so the removed elements are kept intact at the back and the survivors may be reordered. Use the partition version only when you want to do something with the removed elements before erasing them (log them, move them elsewhere). For plain removal, C++20’s std::erase_if(numbers, pred) does the erase-remove idiom in one call.

Pattern 3: Group Processing

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

struct User {
    std::string name;
    bool premium;
    int age;
};

void processUsers(std::vector<User>& users) {
    // Move premium users to the front
    auto pivot = std::stable_partition(users.begin(), users.end(),
        [](const User& u) { return u.premium; });
    
    // Process premium users
    std::cout << "Premium Users:\n";
    for (auto it = users.begin(); it != pivot; ++it) {
        std::cout << "- " << it->name << '\n';
    }
    
    // Process regular users
    std::cout << "Regular Users:\n";
    for (auto it = pivot; it != users.end(); ++it) {
        std::cout << "- " << it->name << '\n';
    }
}

Troubleshooting & gotchas

• Predicate calls: std::partition and stable_partition apply the predicate exactly once per element, but in an unspecified order and on elements that may already have been moved. A predicate with side effects (counting, logging, reading external state that changes) gives results that depend on the implementation; keep predicates pure.
• Iterator invalidation: Partitioning swaps values but does not change the container’s size, so iterators stay valid; they now refer to different values, though. A pointer you saved to “the element 4” before the call may point at 6 afterwards.
• Already sorted vs partitioned: A sorted range is partitioned for monotonic predicates, but partition_point requires the range to be partitioned for that specific predicate—do not confuse with binary search preconditions.
• Parallelism: C++17 offers std::partition(std::execution::par, ...), but parallel partitioning needs extra passes and memory, so it only pays off for large ranges; measure before switching.

partition_copy

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::vector<int> evens, odds;

std::partition_copy(v.begin(), v.end(),
    std::back_inserter(evens),
    std::back_inserter(odds),
    [](int x) { return x % 2 == 0; });
// evens = {2, 4, 6}, odds = {1, 3, 5}; v is unchanged

partition_copy leaves the source alone and writes each element to one of two outputs in order, so it is stable by construction. It returns a pair of the two output iterators, which tells you where each destination ended when writing into pre-sized buffers. Calling evens.reserve(v.size()) first avoids repeated reallocations when the split is unknown.

---

Related Posts

• C++ STL algorithms — English series hub
• C++ Sorting: std::sort, stable_sort, partial_sort and nth_element
• C++ Search Algorithms: find, binary_search, lower_bound, and upper_bound
• cppreference.com - partition

---

Related Articles

• std::set_union, set_intersection and set_difference on Sorted Ranges
• C++ Algorithm Reverse

---