Check if Vec contains all elements from another Vec

user_8990329 0
Viewed 4762

There is a method contains that can be used to check if a particular element exists in a Vec. How to check if all elements from a Vec are contained in another Vec? Is there something more concise than iterating manually and checking all elements explicitly?

rust vector collections
3 Answers

You have two main choices:

  • naively check each element from one vector to see if it's in the other. This has time complexity O(n^2) but it's also very simple and has low overhead:

    assert!(b.iter().all(|item| a.contains(item)));

  • create a set of all of elements of one of the vectors, and then check if elements of the other are contained it it. This has O(n) time complexity, but higher overhead including an extra heap allocation:

    let a_set: HashSet<_> = a.iter().copied().collect();
assert!(b.iter().all(|item| a_set.contains(item)));

Which one is "better" will depend on your requirements. If you only care about speed, the better choice will still depend on the number of elements in your vectors, so you should test both with realistic data. You could also test with a BTreeSet, which has different performance characteristics from HashSet.

Here are some rough benchmarks (source) for how the implementations vary with the size of the input. In all tests, b is half the size of a and contains a random subset of a's elements:

Size of a Vec::contains HashSet::contains BtreeSet::contains
10 14 386 327
100 1,754 3,187 5,371
1000 112,306 31,233 88,340
10000 2,821,867 254,801 728,268
100000 29,207,999 2,645,703 6,611,666

Times in nanoseconds.

The naive O(n^2) solution is fastest when the number of elements is small. The overhead of allocating a HashSet or BTreeSet is overshadowed by the impact of the number of comparisons when the size is more than about 200. BTreeSet is mostly a lot slower than HashSet, but is slightly faster when the number of elements is very small.

user_4937290

If you have sorted vectors, you can do the search in linear time:

    let mut vec = vec![0, 2, 4, 3, 6, 3, 5, 1, 0];
    let mut v = vec![1, 4, 3, 3, 1];

    vec.sort_unstable();
    v.sort_unstable();

    // Remove duplicates elements in v
    v.dedup();

    let mut vec_iter = vec.iter();
    assert!(v.iter().all(|&x| vec_iter.any(|&item| item == x)));

Reference: C++ has std::includes which does exactly that.

user_57997210

You could also sort the vectors and then test them for equality:

fn main() {
    let mut v1 = vec![2, 3, 1];
    let mut v2 = vec![3, 1, 2];
    
    v1.sort();
    v2.sort();

    assert_eq!(v1, v2);
}
user_39654280
Related