Split vec by filter

#1
  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?

#2

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);
    
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7cfbea652d9ce9e337a2a45ffcfafce5

4 Likes
#3

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

1 Like
#4

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
#5

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 ?

#6

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