CODEWITHSUNDEEP
vectorfilterrust
Luiz Martins
Luiz Martins

Reputation: 1724

Idiomatic and efficient way to get a vector filter and its complement

Suppose I have a vector, a filter over it, and I want to deconstruct it into two vectors: A filtered vector, and its complement. I see two ways to do this. The first is with a for loop:

let vct: Vec<u32> = vec![1, 3, 4, 7, 9, 10, 12];
let filter = |x| x % 3 == 0;

let mut filtered: Vec<u32> = Vec::new();
let mut complement: Vec<u32> = Vec::new();
for v in vct {
    if filter(v) {
        filtered.push(v);
    } else {
        complement.push(v);
    }
}

println!("{:?}", filtered);   //[3, 9, 12]
println!("{:?}", complement); //[1, 4, 7, 10]

This seems efficient, but unnecessarily verbose (and adds unnecessary mutability to the vectors). The other one is a naive way with iterators:

let vct: Vec<u32> = vec![1, 3, 4, 7, 9, 10, 12];
let filter = |x:&&u32| *x % 3 == 0;

let filtered: Vec<u32> = vct.iter().filter(filter).cloned().collect();
let complement: Vec<u32> = vct.into_iter().filter(|x| !filter(&x)).collect();

println!("{:?}", filtered);   //[3, 9, 12]
println!("{:?}", complement); //[1, 4, 7, 10]

Which has a clearer intent and is less verbose (save the filter definition/usage, which is a bit uglier), but iterates twice over the array, which seems unnecessary.

Both of these solutions seem sub-optimal.

Is there an idiomatic and efficient way (without re-iteration) to split a vector into a filter and its complement?

Upvotes: 3

Views: 63

Answers (1)

Vincent Savard
Vincent Savard

Reputation: 35927

The operation you are attempting to do is called partitioning. You can use Iterator.partition():

let vct: Vec<u32> = vec![1, 3, 4, 7, 9, 10, 12];
let filter: fn(u32) -> bool = |x| x % 3 == 0;

let (filtered, complement): (Vec<u32>, Vec<u32>) = vct.iter().partition(|x| filter(**x));

assert_eq!(&[3, 9, 12], filtered.as_slice());
assert_eq!(&[1, 4, 7, 10], complement.as_slice());

Playground

Upvotes: 6

Related Questions