CODEWITHSUNDEEP
c++subsetset-intersection
deworde
deworde

Reputation: 2799

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

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?

Upvotes: 20

Views: 21829

Answers (2)

Rishabh Deep Singh
Rishabh Deep Singh

Reputation: 914

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

Upvotes: 0

Klark
Klark

Reputation: 8300

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.

Upvotes: 46

Related Questions