How do I check if one vector is a subset of another?

Question

Currently, I think my best option is to use std::set_intersection, and then check if the size of the smaller input is the same as the number of elements filled by set_intersection.

Is there a better solution?

Overrate

Related #6907021 – Gould

Answer 1

Try this:

if (std::includes(set_one.begin(), set_one.end(),
                  set_two.begin(), set_two.end()))
{
// ...
}

About includes().

The includes() algorithm compares two sorted sequences and returns true if every element in the range [start2, finish2) is contained in the range [start1, finish1). It returns false otherwise. includes() assumes that the sequences are sorted using operator<(), or using the predicate comp.

runs in

At most ((finish1 - start1) + (finish2 - start2)) * 2 - 1 comparisons are performed.

Plus O(nlog(n)) for sorting vectors. You won't get it any faster than that.

Outdate

I believe std::set_intersection will perform the same as above (i.e. (2 * (count1 + count2)) - 1 operations) – Ariellearies

Well worst case is the same, but if the result is false the includes will do it's job much faster. And you also use one more vector in intersection. As the names suggest set_intersection should be used for finding that intersection and includes for checking if one set is subset of another. – Outdate

if your data is in std::set you could use std::set_difference – Klondike

set_intersection and set_difference are symmetric operations, where includes is asymmetric. They cannot be substituted for each other. – Decompress

@Klark: and what about unordered_set? assuming there's no collision in the hash you can get O(n) – Quinquepartite

Answer 2

If you are using c++-20 or higher, you can use the std::ranges::includes to do the same.

assert(ranges::includes(vector<int>{2, 4, 6, 8, 10}, vector<int>{4}));
assert(ranges::includes(vector<int>{2, 4, 6, 8, 10}, vector<int>{4, 6}));

Quinte