Split vec by filter

  1. I have a v: Vec<T> and a f: T -> bool

  2. I want as output two vectors, one containing elements that make f true, and one that makes f false.

  3. T does not have Clone, but it is okay to consume v in the process.

  4. What is the simplest way to do this?

Here is an example of partitioning a vector by evenness of elements.

pub fn main() {
    let list=vec![0,1,2,3,4,5];
    
    let (even,odd):(_,Vec<_>)=list
        .into_iter()
        .partition(|x|(x%2)==0);
    
    assert_eq!(even,vec![0,2,4]);
    assert_eq!(odd,vec![1,3,5]);
    
    println!("even={:?}",even);
    println!("odd={:?}",odd);
    
}
5 Likes

@matt1992 : Nice, thanks! I keep on forgetting to look up iter::Iterator docs.

1 Like

To reuse the initial vec allocation you also have the (not yet stable) .drain_filter(), with an example showing your exact use case.

3 Likes

Is it possible that drain_filter approach takes O(n^2) time if we make n calls to remove, half of which atkes > n/2 time ?

No, drain_filter uses careful unsafe code to be O(n).

(That's why it exists, really -- if it was just remove a bunch of times, it wouldn't need to be in std at all.)

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.