Introduction

std::partition is fundamentally an in-place sequential algorithm, so there is no trivial drop-in "parallel std::partition" in TBB that preserves the exact same behavior. In practice, the usual parallel solution is to separate the work into two phases: evaluate the predicate in parallel, then copy matching and non-matching elements into output regions. That gives you partitioned data efficiently, even if the implementation is no longer a literal in-place std::partition.

Why Parallel In-Place Partition Is Hard

Partitioning seems simple: move matching elements left and the rest right. The challenge in parallel is that many threads want to rearrange the same container at once.

That creates problems such as:

• overlapping writes
• synchronization overhead
• loss of locality
• difficulty preserving order if you need stability

So the first design question is not "how do I parallelize std::partition exactly", but "what partition property do I actually need".

A Practical TBB Strategy

A straightforward parallel design is:

1. scan the input in parallel
2. collect items that satisfy the predicate
3. collect items that do not
4. copy both groups back into one output buffer

This is not in-place, but it is often the right engineering tradeoff.

Example with tbb::concurrent_vector

Here is a simple non-stable partition using oneTBB containers and parallel_for.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5#include <oneapi/tbb/concurrent_vector.h>
6#include <oneapi/tbb/blocked_range.h>
7#include <oneapi/tbb/parallel_for.h>
8
9template <typename T, typename Pred>
10void parallel_partition(std::vector<T>& data, Pred pred) {
11    oneapi::tbb::concurrent_vector<T> left;
12    oneapi::tbb::concurrent_vector<T> right;
13
14    oneapi::tbb::parallel_for(
15        oneapi::tbb::blocked_range<std::size_t>(0, data.size()),
16        [&](const oneapi::tbb::blocked_range<std::size_t>& range) {
17            for (std::size_t i = range.begin(); i != range.end(); ++i) {
18                if (pred(data[i])) {
19                    left.push_back(data[i]);
20                } else {
21                    right.push_back(data[i]);
22                }
23            }
24        }
25    );
26
27    auto out = std::copy(left.begin(), left.end(), data.begin());
28    std::copy(right.begin(), right.end(), out);
29}
30
31int main() {
32    std::vector<int> values{1, 2, 3, 4, 5, 6, 7, 8};
33    parallel_partition(values, [](int x) { return x % 2 == 0; });
34
35    for (int v : values) {
36        std::cout << v << ' ';
37    }
38    std::cout << '\n';
39}

This guarantees the partition property, though it does not preserve original ordering within the left and right groups.

If You Need Stability

If you need stable partitioning, the problem is harder. A common approach is:

1. compute a boolean keep-mask
2. use a prefix sum or parallel scan to compute write positions
3. write each element to its final output slot

That is more complex than the concurrent_vector approach, but it gives deterministic placement and better control over memory layout.

TBB's parallel_scan is the right building block for that design, not std::partition itself.

Memory Tradeoff

The simple parallel approach uses extra memory because it collects results into temporary containers. That is often acceptable, because trying to force a fully in-place parallel partition can introduce more synchronization cost than it saves.

So your real tradeoff is usually:

• extra memory and simpler parallel logic
• less memory and much more complex coordination

For many workloads, the first option wins.

When Parallel Partition Helps

Parallel partitioning makes sense when:

• the input is large
• predicate evaluation is non-trivial
• memory bandwidth is not already the bottleneck
• the added allocation cost is acceptable

If the predicate is extremely cheap and the data set is modest, the sequential std::partition may still be faster because it avoids parallel overhead.

Benchmark Before Replacing the Sequential Version

Do not assume parallel is automatically faster. Measure:

• total runtime
• memory allocation cost
• scalability with input size
• ordering requirements

A common outcome is that the parallel version wins only after the data set crosses a certain size threshold.

Common Pitfalls

The biggest mistake is searching for a one-line TBB equivalent of std::partition and assuming the semantics should match exactly. Another is ignoring order requirements until after the implementation is written. Teams also sometimes parallelize a cheap predicate over a small container and lose performance to overhead. Finally, trying to force an in-place parallel algorithm too early usually makes the code more fragile than the workload justifies.

Summary

• There is no simple drop-in TBB version of in-place std::partition.
• A practical parallel solution is to collect matching and non-matching elements separately, then copy them back.
• Use parallel_scan if you need more control or stable placement.
• Extra memory is often the cost of a much simpler and safer parallel design.
• Benchmark before replacing the sequential algorithm, because overhead can dominate on smaller inputs.