In this lesson, you will learn how to reorganize elements within an existing memory block based on a predicate without requiring additional heap allocations.
The Problem with Standard Filtering
When you typically filter a collection—such as using vec.into_iter().filter(...).collect()—you create a new collection on the heap. This causes unnecessary pressure on the allocator and involves copying data to a new location. In high-performance systems, we want to perform this "partitioning" in-place, reusing the existing buffer.
Leveraging partition_in_place
Rust provides a powerful tool for this: the partition_in_place method available on slices. It rearranges the elements of a slice such that all elements satisfying a given predicate are moved to the front, and those that don't are moved to the back. Crucially, it does this using only the space already provided by the slice.
Consider an example where we want to separate "active" tasks from "completed" tasks in a buffer without reallocating:
let mut tasks = vec![1, 0, 1, 1, 0, 0, 1]; // 1 = Active, 0 = Completed
// Reorder in-place: all 1s move to the start
let pivot = tasks.partition_in_place(|&x| x == 1);
let (active, completed) = tasks.split_at_mut(pivot);
// active is now [1, 1, 1, 1], completed is [0, 0, 0]
How It Works
partition_in_place utilizes a two-pointer approach internally. It starts one pointer at the beginning and one at the end, swapping elements that violate the predicate until the pointers meet. This maintains the "zero-copy" philosophy we’ve been building toward.
Because this happens in-place, the original order of the elements is not guaranteed to be stable (it is not a stable sort). If the relative order of your items is strictly required, you would need to use stable_partition logic, though that often requires extra buffer space. In most systems-level partitioning tasks, however, the primary goal is grouping for cache-friendly processing or workload balancing, making the unstable partition_in_place the ideal alloc-free choice.
Key Takeaway: Use partition_in_place to reorganize collection segments without heap allocation by leveraging existing buffer memory and pointer-based swaps.