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

c++ subset set-intersection
deworde picture deworde · Nov 1, 2010 · Viewed 14.3k times · Source

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?

Answer

Klark picture Klark · Nov 1, 2010

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.

Related questions

Finding all the subsets of a set

I need an algorithm to find all of the subsets of a set where the number of elements in a set is n. S={1,2,3,4...n} Edit: I am having trouble understanding the answers provided so far. I would like to …

Read More
Easiest way to convert int to string in C++

What is the easiest way to convert from int to equivalent string in C++. I am aware of two methods. Is there any easier way? (1) int a = 10; char *intStr = itoa(a); string str = string(intStr); (2) int a = 10; stringstream ss; ss &…

Read More
The Definitive C++ Book Guide and List

This question attempts to collect the few pearls among the dozens of bad C++ books that are published every year. Unlike many other programming languages, which are often picked up on the go from tutorials found on the Internet, few …

Read More