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?
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With