Set difference in C++

Question

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}

what would you like? difference or intersection? make your mind up! ;) — Nim, Apr 18 '11 at 12:51
http://www.cplusplus.com/reference/algorithm/set_difference/ — , Apr 18 '11 at 12:51
possible duplicate of [c++ STL set difference](http://stackoverflow.com/questions/283977/c-stl-set-difference) — Sebastian Mach, Jul 20 '12 at 15:02

score 30 · Accepted Answer · edited May 23 '17 at 11:54

30

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

edited May 23 '17 at 11:54

Community

1
1

answered Apr 18 '11 at 12:50

orlp

106,415
33
201
300

1

How do you know this works? It is not infers from documentation, stating elements should be sorted. – Dims Jan 31 '20 at 16:42
@Dims std::set is always sorted. – Olof Hedman Jan 18 '21 at 17:29

score 11 · Answer 2 · answered Apr 18 '11 at 12:49

11

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

answered Apr 18 '11 at 12:49

Oliver Charlesworth

260,367
30
546
667

`which runs in O(n) time` depends on implementation. – orlp Apr 18 '11 at 12:51
4

@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

score 0 · Answer 3 · answered Apr 18 '11 at 12:51

0

set_symmetric_difference

answered Apr 18 '11 at 12:51

Pete

10,459
9
51
73

{1 2 3 4 5 6 7 8 9 10} - { 5 6 7 11} would include 11? – Will Apr 18 '11 at 12:55
Yes, it will because it's not in the first set. I see now that the OP wanted to subtract a subset (which would not include any numbers not in the original) of the set. I got excited and assumed he just wanted what was different between any two sets. – Pete Apr 18 '11 at 13:12

Will · Answer 4 · 2011-04-18T12:59:01.500

0

You can use std::set_difference function.

the output range contains a copy of every element that is contained in [first1, last1) and not contained in [first2, last2).

edited Apr 18 '11 at 12:59

answered Apr 18 '11 at 12:51

Will

71,757
38
162
237

Set difference in C++

4 Answers4

Linked