partition

partition slices in-place by a predicate

Rust has the Iterator::partition(_) method, but this requires allocating two Vecs to hold the values. This has the benefit of preserving order, at the cost of spending time and RAM to do the allocation, which also makes this API unavailable on systems without an allocator.

This crate has a partition(..) function to partition a mutable slice of values by a predicate. It will swap around values to separate those the predicate holds for and those it doesn't and return the two mutable sub-slices.

This crate also provides partition_index(..) which operates similarly, but instead returns the index of the first element to evaluate to false. All elements before this index evaluate to true, and all elements after evaluate to false.

Warning

Note that since partition works by swapping values, the order of elements within the slice will not be preserved.

Example

let mut even_odd = [0u8, 1, 2, 3, 4, 5, 6];
let (even, odd) = partition(&mut even_odd, |x| x & 1 == 0);

let mut less_than_4 = [0u8, 3, 6, 2, 1, 5, 4];
let idx = partition_index(&mut less_than_4, |x| x < 4);

Performance

On a Core m3-6y30 with 4GB of RAM, I get the following benchmark results (in ns/iter):

So it's safe to say performance compares very favorably.

License

Licensed under either of at your discretion:

• Apache 2.0
• MIT