Is there a built in function to compute the difference of two sets?

user_10499008 0
Viewed 2463

New to Rust. Pretty simple question, I searched for a while and couldn't find an answer

Basically I want something like this

let mut v1 = vec![0, 1, 2, 3, 4];
let mut v2 = vec![3, 4];
assert_eq!(v1 - v2, &[0, 1, 2]);

let mut v1 = vec![0, 1, 2, 3, 4, 5, 6];
let mut v2 = vec![3, 4];
assert_eq!(v1 - v2, &[0, 1, 2, 5, 6]);

let mut v1 = vec![0, 1, 2, 3, 4, 5, 6];
let mut v2 = vec![7];
assert_eq!(v1 - v2, &[0, 1, 2, 3, 4, 5, 6]);
rust set
2 Answers

Based on your examples, it seems that you're looking for vectors where the elements are unique.

Vectors don't actually guarantee this property (items don't have to be unique or ordered, indeed, they don't even have to support comparison), but Sets do (HashSet or BTreeSet). And HashSet indeed supports the - operator:

(playground link)

use std::collections::HashSet;

fn main() {
    let s1: HashSet<i32> = [0, 1, 2, 3, 4].iter().cloned().collect();
    let s2: HashSet<i32> = [3, 4].iter().cloned().collect();
    let expected: HashSet<i32> = [0, 1, 2].iter().cloned().collect();
    assert_eq!(&s1 - &s2, expected);
}

If you want to perform this operation on vectors, you could convert to HashSet or BTreeSet and then create a vector from this:

fn vect_difference(v1: &Vec<i32>, v2: &Vec<i32>) -> Vec<i32> {
    let s1: HashSet<i32> = v1.iter().cloned().collect();
    let s2: HashSet<i32> = v2.iter().cloned().collect();
    (&s1 - &s2).iter().cloned().collect()
}

Or you could perform the difference directly on the vectors (keeping in mind that this is an O(N*M) algorithm and would perform poorly if both vectors are long):

fn vect_difference(v1: &Vec<i32>, v2: &Vec<i32>) -> Vec<i32> {
    v1.iter().filter(|&x| !v2.contains(x)).cloned().collect()
}
user_3465870

To remove elements from one vector that are in another:

fn subtract(a: &Vec<i32>, b: &Vec<i32>) -> Vec<i32> {
    let mut c = a.clone();
    c.retain(|x| !b.contains(x));
    c
}

or if you're okay with mutating the first vector:

fn subtract(a: &mut Vec<i32>, b: &Vec<i32>) {
    a.retain(|x| !b.contains(x));
}

Note this is an O(N*M) algorithm where N,M are the lengths of the vectors.

This is fast for a small number of elements. For larger number you might use a HashSet. The difference method provides an applicable example, building the sets from vectors initially.

Here's my version, which only makes one HashSet and is therefore faster if you start with two vectors and want to end with a vector. This is similar to what difference() does under the hood.

use std::collections::HashSet;
let b: HashSet<_> = v2.into_iter().collect();
v1.retain(|x| !b.contains(x));

This will be O(M+N): M to build the hash set from the second vector, and N to check each element in the first vector.

user_32087230
Related