17

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?

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
deworde
  • 2,679
  • 5
  • 32
  • 60
  • Related https://stackoverflow.com/questions/6906521/how-to-check-whether-a-vector-is-a-subset-of-another-in-c?noredirect=1&lq=1 – luca Jan 13 '22 at 17:29

1 Answers1

46

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.

eddi
  • 49,088
  • 6
  • 104
  • 155
Klark
  • 8,162
  • 3
  • 37
  • 61
  • 1
    I believe std::set_intersection will perform the same as above (i.e. (2 * (count1 + count2)) - 1 operations) – Nim Nov 01 '10 at 11:25
  • 3
    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. – Klark Nov 01 '10 at 11:55
  • 3
    if your data is in `std::set` you could use `std::set_difference` – Krishna Oza Jan 16 '15 at 11:14
  • set_intersection and set_difference are symmetric operations, where includes is asymmetric. They cannot be substituted for each other. – dascandy Jun 02 '16 at 15:07
  • 1
    @Klark: and what about unordered_set? assuming there's no collision in the hash you can get O(n) – woockashek May 04 '22 at 08:31