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);

Quicksort Partition Scheme

std::partition is not just a standalone utility — it is the inner loop of nearly every competitive std::sort implementation. Modern introsort calls std::partition (or an inline equivalent) O(log N) times during recursive descent. Understanding this relationship explains why std::partition must be O(N) and cache-friendly: its per-call cost of O(N/level) accumulates to O(N log N) across all levels, matching the theoretical optimum for comparison sorts.

Hoare's classic scheme partitions around a pivot by scanning from both ends toward the middle, swapping elements that are on the wrong side. The following example wires std::partition directly into a recursive quicksort to make the relationship explicit:

cpp

Godbolt

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

// C++11: quicksort using std::partition as the inner partition step.
// This mirrors how introsort (used by std::sort) is structured internally.
template<class RandomIt>
void quicksort(RandomIt first, RandomIt last) {
    if (std::distance(first, last) <= 1)
        return;

    // Median-of-three pivot selection reduces worst-case probability.  // C++11
    RandomIt mid = first + std::distance(first, last) / 2;
    auto pivot_val = *mid;

    // std::partition rearranges [first, last) so that all elements < pivot
    // come first.  This single O(N) call is the "inner loop" of the sort.
    auto pivot_it = std::partition(first, last,
                                   [pivot_val](const auto& x) {
                                       return x < pivot_val;
                                   });

    // Recurse on both halves.  At depth d, each call processes N/2^d elements,
    // so each level costs O(N) total.  O(log N) levels => O(N log N) overall.
    quicksort(first, pivot_it);
    quicksort(pivot_it, last);
}

int main() {
    std::vector<int> v{5, 3, 8, 1, 9, 2, 7, 4, 6};
    quicksort(v.begin(), v.end());
    for (int x : v) std::cout << x << ' ';  // 1 2 3 4 5 6 7 8 9
}

The amortised cost of a single std::partition call at recursion depth d is O(N / 2^d). Summing across all log N levels: N + N/2 + N/4 + ... = 2N = O(N) per level × O(log N) levels = O(N log N) total. This is why std::partition benchmarks matter: a 2× slowdown in std::partition propagates directly into a 2× slowdown in std::sort.

cpp

Godbolt

// C++11: amortised cost reasoning in comments
//
//  Depth 0: 1 call, N elements   -> O(N)   work
//  Depth 1: 2 calls, N/2 each    -> O(N)   work
//  Depth 2: 4 calls, N/4 each    -> O(N)   work
//  ...
//  Depth log2(N): N calls, 1 each -> O(N)  work
//  ------------------------------------------------
//  Total: O(N log N)
//
// std::sort uses introsort: quicksort until depth > 2*log2(N),
// then falls back to heapsort to guarantee O(N log N) worst case.

`std::nth_element` as Partial Partition

When you need only the top-K elements or the median — not a fully sorted range — std::nth_element is the right tool. It places exactly one element (the one that would be at position nth in a sorted range) into its correct location, partitioning everything else into a "less than or equal" group before it and a "greater than or equal" group after it. Average complexity is O(N) — compared to O(N log N) for a full sort — making it decisive for large datasets where only a rank matters.

cpp

Godbolt

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

// C++98: find the median in O(N) average time
double median(std::vector<double> v) {           // intentional copy
    auto mid = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), mid, v.end());
    return *mid;
}

// C++98: find the top-K largest elements (unordered)
std::vector<int> top_k(std::vector<int> v, std::size_t k) {
    if (k >= v.size()) return v;
    auto boundary = v.begin() + (v.size() - k);
    std::nth_element(v.begin(), boundary, v.end());
    // [boundary, v.end()) contains the k largest elements, order unspecified
    return {boundary, v.end()};
}

int main() {
    std::vector<int> data{7, 2, 9, 1, 5, 8, 3, 6, 4};
    auto top3 = top_k(data, 3);
    // top3 contains {7, 8, 9} in some order
    for (int x : top3) std::cout << x << ' ';
}

C++20 ranges adds a projection overload, making it trivial to rank structs by a field without a wrapper lambda:

cpp

Godbolt

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

struct Student { std::string name; double gpa; };

// C++20: partition students so the top-3 GPA students are at the end
void top3_students(std::vector<Student>& students) {
    if (students.size() < 3) return;
    auto boundary = students.end() - 3;
    std::ranges::nth_element(students, boundary,
                             std::ranges::less{},
                             &Student::gpa);   // projection — no lambda needed
    // [boundary, students.end()) holds the 3 students with highest GPA
}

The O(N) average guarantee comes from introselect (the selection algorithm analogue of introsort). Worst-case is O(N) for the C++11 standard's introselect variant — most implementations use median-of-medians or a similar pivot strategy to avoid the O(N²) degenerate case of naive quickselect.

cpp

Godbolt

// Complexity comparison for finding the top-K of N elements:
//
//   std::sort then slice     O(N log N) — always                       // C++98
//   std::partial_sort        O(N log K) — sorted top-K                 // C++98
//   std::nth_element         O(N)       — unsorted top-K (average)     // C++98
//
// Rule of thumb: if you need the top-K elements and K << N,
// nth_element is the right choice.  If you also need them sorted,
// nth_element + sort([boundary, end)) costs O(N) + O(K log K).

Partition-Based In-Place Filter

The erase-remove idiom combines std::remove_if (or std::partition) with a container's erase member to delete matching elements in-place. Both std::remove_if and std::partition relocate unwanted elements to the end of the range; the subsequent erase call then shrinks the container to the new size. C++20's std::erase_if collapses both steps into one call.

cpp

Godbolt

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

struct CacheEntry {
    std::string key;
    std::chrono::steady_clock::time_point expires_at;
    bool expired() const {
        return expires_at < std::chrono::steady_clock::now();
    }
};

// C++11: erase-remove idiom with remove_if
void evict_expired_v1(std::vector<CacheEntry>& cache) {
    auto it = std::remove_if(cache.begin(), cache.end(),
                             [](const CacheEntry& e) { return e.expired(); });
    cache.erase(it, cache.end());
    // Two-step: remove_if moves expired entries to the end (O(N)),
    // erase shrinks the vector (O(erased) destructor calls).
}

// C++11: partition variant — use when you need the partition iterator
// for further processing before erasing
void evict_expired_v2(std::vector<CacheEntry>& cache) {
    auto keep_end = std::partition(cache.begin(), cache.end(),
                                   [](const CacheEntry& e) { return !e.expired(); });
    // Inspect or log cache[keep_end..end] before destroying them
    cache.erase(keep_end, cache.end());
}

// C++20: std::erase_if — same semantics, one call
void evict_expired_v3(std::vector<CacheEntry>& cache) {
    std::erase_if(cache, [](const CacheEntry& e) { return e.expired(); });
    // std::erase_if is defined for all standard containers;
    // for std::vector it performs exactly the remove_if + erase pattern.
}

The difference between std::remove_if and std::partition in this context is subtle: std::remove_if does not guarantee that the removed elements are accessible in the tail (they are in a valid but unspecified state), whereas std::partition leaves the "false" group in a valid and inspectable state. Use std::partition when you need to examine or log the elements being erased before the erase call destroys them.

cpp

Godbolt

// C++20: std::erase_if works for associative containers too,
// where the two-step idiom does not apply directly.
#include <map>
std::map<std::string, int> scores{{"alice", 42}, {"bob", 7}, {"carol", 99}};
std::erase_if(scores, [](const auto& kv) { return kv.second < 10; });
// "bob" removed; "alice" and "carol" remain

`stable_partition` Memory Analysis

std::stable_partition operates in two distinct modes depending on whether a temporary buffer can be allocated. Understanding which mode runs — and how to force the fast path on constrained systems — is essential for latency-sensitive or embedded code.

Fast path (O(N) time, O(N) space): When the implementation successfully allocates a temporary buffer of N elements from the heap, it performs a single-pass stable merge using the buffer. This is the expected path on desktop and server systems.

Slow path (O(N log N) time, O(1) extra space): When the allocation fails (or the implementation chooses not to allocate), it falls back to an in-place rotate-based algorithm. The standard permits this degradation silently — no exception is thrown, no flag is set.

cpp

Godbolt

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

// C++11: measure which path stable_partition takes
void demonstrate_stable_partition_paths() {
    // Small vector — likely fast path (buffer fits)
    std::vector<int> small(1'000);
    std::iota(small.begin(), small.end(), 0);

    auto t0 = std::chrono::high_resolution_clock::now();
    std::stable_partition(small.begin(), small.end(),
                          [](int n) { return n % 2 == 0; });
    auto t1 = std::chrono::high_resolution_clock::now();

    // Large vector — if system memory is under pressure, may take slow path
    std::vector<int> large(100'000'000);
    std::iota(large.begin(), large.end(), 0);

    auto t2 = std::chrono::high_resolution_clock::now();
    std::stable_partition(large.begin(), large.end(),
                          [](int n) { return n % 2 == 0; });
    auto t3 = std::chrono::high_resolution_clock::now();

    // If (t3-t2)/N >> (t1-t0)/N, the large case took the slow path.
    // There is no direct API to query which path was taken.
    auto small_ns = std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
    auto large_ns = std::chrono::duration_cast<std::chrono::nanoseconds>(t3 - t2).count();
    std::cout << "small ns/elem: " << small_ns / 1000 << '\n';
    std::cout << "large ns/elem: " << large_ns / 100'000'000 << '\n';
    // A ratio > ~3x suggests the large case used the O(N log N) path.
}

On embedded targets with limited heap, the mitigation is to manage the temporary buffer yourself: partition into a pre-allocated auxiliary array, then copy the two groups back in order.

cpp

Godbolt

#include <algorithm>
#include <array>
#include <vector>
#include <cstring>

// C++11: embedded-friendly stable_partition using a pre-allocated buffer.
// Avoids any dynamic allocation; uses only the caller-supplied scratch space.
template<class T, class Pred>
void stable_partition_inplace(std::vector<T>& v,
                               std::vector<T>& scratch,  // pre-allocated, size >= v.size()
                               Pred pred) {
    // Partition into scratch: true-group first, then false-group
    auto [true_end, false_end] =
        std::partition_copy(v.begin(), v.end(),
                            scratch.begin(),
                            scratch.begin() + v.size(),  // false-group starts at midpoint
                            pred);
    // Recalculate: true_end points into scratch; compute counts
    std::size_t true_count  = std::distance(scratch.begin(), true_end);
    // false-group was written starting at scratch.begin() + v.size()
    std::size_t false_count = v.size() - true_count;

    // Copy true-group back, then false-group
    std::copy(scratch.begin(), true_end, v.begin());
    std::copy(scratch.begin() + v.size(),
              scratch.begin() + v.size() + false_count,
              v.begin() + true_count);
}

The above approach uses partition_copy with two non-overlapping regions of the scratch buffer, then copies both groups back in order, achieving stable O(N) behaviour with no heap allocation beyond the caller-owned scratch vector.

`partition_copy` with Transform

std::partition_copy writes to two output iterators, and those iterators can be std::back_inserter adapters into containers of a different type than the input — enabling a filter-and-transform in a single pass without writing a hand-rolled loop. The idiom pairs naturally with std::transform_iterator (Boost, range-v3, or a hand-written wrapper) or, more commonly, a subsequent std::transform call on each output container.

The following example splits a range of LogRecord objects into warnings and errors, converting each to a summary string during the copy:

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <sstream>

// C++11
struct LogRecord {
    enum class Level { Info, Warning, Error };
    Level       level;
    int         code;
    std::string message;
};

// Transform a LogRecord to a one-line summary string
std::string summarize(const LogRecord& r) {
    std::ostringstream oss;
    oss << '[' << (r.level == LogRecord::Level::Warning ? "WARN" : "ERR ")
        << ' ' << r.code << "] " << r.message;
    return oss.str();
}

struct SummaryInserter {
    // A minimal output iterator that transforms LogRecord -> string on assignment
    std::vector<std::string>* dest;
    SummaryInserter& operator=(const LogRecord& r) {
        dest->push_back(summarize(r));
        return *this;
    }
    SummaryInserter& operator*()  { return *this; }
    SummaryInserter& operator++() { return *this; }  // no-op
    SummaryInserter  operator++(int) { return *this; }
};

void split_and_summarize(const std::vector<LogRecord>& records,
                         std::vector<std::string>&     warnings_out,
                         std::vector<std::string>&     errors_out) {
    warnings_out.reserve(records.size());
    errors_out.reserve(records.size());

    // Single pass: partition into warnings vs errors AND convert to strings  // C++11
    std::partition_copy(
        records.begin(), records.end(),
        SummaryInserter{&warnings_out},   // true  -> warnings
        SummaryInserter{&errors_out},     // false -> errors
        [](const LogRecord& r) {
            return r.level == LogRecord::Level::Warning;
        });
}

The single-pass approach avoids materialising two intermediate LogRecord vectors before converting. For records that are large or non-copyable (use std::partition instead for move-only types), the reduction in temporary storage is meaningful. An alternative that avoids the custom iterator is to call std::partition_copy into two LogRecord vectors and then std::transform each — two passes, but cleaner code:

cpp

Godbolt

// C++11: two-pass alternative — cleaner, at the cost of an extra traversal
void split_and_summarize_v2(const std::vector<LogRecord>& records,
                             std::vector<std::string>&     warnings_out,
                             std::vector<std::string>&     errors_out) {
    std::vector<LogRecord> warn_records, err_records;
    warn_records.reserve(records.size());
    err_records.reserve(records.size());

    std::partition_copy(records.begin(), records.end(),
                        std::back_inserter(warn_records),
                        std::back_inserter(err_records),
                        [](const LogRecord& r) {
                            return r.level == LogRecord::Level::Warning;
                        });

    std::transform(warn_records.begin(), warn_records.end(),
                   std::back_inserter(warnings_out), summarize);
    std::transform(err_records.begin(), err_records.end(),
                   std::back_inserter(errors_out), summarize);
}

Ranges Pipeline Integration

C++20 ranges views are lazy — they produce no output until iterated — which means they compose cleanly with the partition algorithms that do materialise output. The pattern is: partition eagerly into a std::vector (or wrap the result in a std::ranges::subrange), then apply lazy views to each group for further filtering, limiting, or transformation without additional copies.

Partition then `views::take`

cpp

Godbolt

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

struct Task { int id; int priority; bool is_ready; };

void schedule_top5_ready(std::vector<Task>& tasks) {
    // C++20: partition in-place — ready tasks move to the front
    auto [mid, end_it] = std::ranges::partition(tasks,
                                                 [](const Task& t) { return t.is_ready; });

    // Wrap the "ready" group as a subrange for further algorithm use  // C++20
    auto ready_group = std::ranges::subrange(tasks.begin(), mid);

    // Lazily take the first 5 without copying  // C++20
    auto top5 = ready_group | std::views::take(5);

    for (const Task& t : top5)
        std::cout << "Scheduling task " << t.id << '\n';
}

std::ranges::subrange is the standard vocabulary type for wrapping an iterator-sentinel pair into a range. It enables any std::ranges:: algorithm or view to consume the partition groups without copying the elements or building a new container.

Binary search within a sorted partition using `partition_point`

When a range is both sorted and partitioned (all sorted ranges satisfy the partition invariant for threshold predicates), partition_point locates the boundary in O(log N) time. Combining it with std::ranges::subrange lets you chain further algorithms on each half:

cpp

Godbolt

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

// C++20: split a sorted list of scores into "pass" (>=50) and "fail" (<50)
// groups, then apply views to each
void analyse_scores(const std::vector<int>& sorted_scores) {
    assert(std::ranges::is_sorted(sorted_scores));

    // partition_point performs binary search — O(log N)  // C++20
    auto boundary = std::ranges::partition_point(sorted_scores,
                                                  [](int s) { return s < 50; });

    auto fail_group = std::ranges::subrange(sorted_scores.begin(), boundary);
    auto pass_group = std::ranges::subrange(boundary, sorted_scores.end());

    // Apply lazy views: top-3 passing scores, bottom-3 failing scores
    auto top3_pass  = pass_group | std::views::reverse | std::views::take(3);
    auto worst3_fail = fail_group | std::views::take(3);

    std::cout << "Top 3 passing: ";
    for (int s : top3_pass) std::cout << s << ' ';

    std::cout << "\nWorst 3 failing: ";
    for (int s : worst3_fail) std::cout << s << ' ';
}

Chaining with `views::filter` for multi-predicate filtering

For complex scenarios requiring multiple predicates, partition once to separate a major group, then apply views::filter lazily on each subrange to refine further — avoiding multiple full traversals:

cpp

Godbolt

#include <algorithm>
#include <ranges>
#include <vector>

struct Packet { int src_port; int dst_port; int size_bytes; bool encrypted; };

void route_packets(std::vector<Packet>& packets) {
    // C++20: first partition — encrypted vs plain
    auto [enc_end, _] = std::ranges::partition(packets,
                                                [](const Packet& p) { return p.encrypted; });

    auto encrypted = std::ranges::subrange(packets.begin(), enc_end);
    auto plaintext  = std::ranges::subrange(enc_end, packets.end());

    // Lazily filter within each group — no additional allocation  // C++20
    auto large_encrypted = encrypted
        | std::views::filter([](const Packet& p) { return p.size_bytes > 1400; });

    auto web_plain = plaintext
        | std::views::filter([](const Packet& p) {
              return p.dst_port == 80 || p.dst_port == 8080;
          });

    // Process each view — elements evaluated lazily on iteration
    for (const Packet& p : large_encrypted) { /* forward to deep-inspection queue */ }
    for (const Packet& p : web_plain)       { /* forward to HTTP parser */ }
}

The key advantage of std::ranges::subrange over raw iterator pairs is that it satisfies the std::ranges::range concept, making it usable everywhere a range is expected — including range-for, all std::ranges:: algorithms, and the pipe operator for views composition.

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.
Prefer std::nth_element over std::sort when you only need a rank or top-K. The O(N) average cost versus O(N log N) for full sort is decisive for large N and small K.
Use std::erase_if (C++20) as the idiomatic in-place filter. It replaces the two-step erase-remove idiom with a single, readable call that works on all standard containers including associative ones.
Wrap partition results in std::ranges::subrange before passing to further algorithms. Raw iterator pairs require explicit (begin, end) overloads; subrange works with range-for, views pipes, and all std::ranges:: algorithms.
On memory-constrained targets, provide stable_partition with its own scratch buffer via partition_copy. The standard gives no way to supply an external buffer to std::stable_partition directly; the partition_copy-into-scratch pattern avoids surprise heap allocation.

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.

Using std::sort when std::nth_element suffices for top-K queries. std::sort does O(N log N) work unconditionally; if you only need the K largest elements and do not require them in order, std::nth_element + sort of the K-element tail costs O(N) + O(K log K), which is significantly faster for large N and small K.

Applying views pipelines to invalidated iterators after an in-place partition. std::partition may move elements; any iterator, pointer, or reference into the range obtained before the call is invalidated for std::vector if the call triggers a reallocation (it will not for in-place partition, but be aware that the element at a given index may have changed). Re-obtain iterators after the partition call.