20

If I know that one set is a subset of another set and I would like to find the difference, what's the most efficient way to do this?

ex. PSEUDO CODE

> set<int> set1 = {1 2 3 4 5 6 7 8 9 10}
> set<int> set2 = {5 6 7}

I want to subtract set2 from set1:

The answer here would be 

{1 2 3 4 8 9 10}
1201ProgramAlarm
  • 32,384
  • 7
  • 42
  • 56
user620189
  • 2,595
  • 7
  • 21
  • 19

2 Answers2

33

Use std::set_difference found in <algorithm>:

#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(result, result.end()));

Snippet source

Community
  • 1
  • 1
orlp
  • 112,504
  • 36
  • 218
  • 315
12

I would use std::set_difference, which runs in O(n) time.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • `which runs in O(n) time` depends on implementation. – orlp Apr 18 '11 at 12:51
  • 5
    @nightcracker: nope, it's guaranteed by the standard. – Yakov Galka Apr 18 '11 at 12:55
  • @nightcracker: see The ISO C++ standard section [alg.set.operations]. – Yakov Galka Apr 18 '11 at 12:58
  • 1
    @ybungalobill: Ah found it, §25.4.5.4 set_difference, Remark 4: "At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons." Indeed, `O(n)`. – orlp Apr 18 '11 at 13:09
  • @nightcracker: actually you're partially right. The standard doesn't talk in terms of O-notation because, e.g., each insertion or comparison may run in non-bounded f(n) time. So even with linear number of comparisons it may take more than O(n) time. – Yakov Galka Apr 18 '11 at 13:25
  • ybungalobill: Not true. One operation is one comparison. Whether or not that comparison is O(1) is a completely different story. – orlp Apr 18 '11 at 13:34