c++ STL set difference

Question

Does the C++ STL set data structure have a set difference operator?

score 164 · Answer 1 · edited Oct 20 '12 at 21:15

164

Yes there is, it is in <algorithm> and is called: std::set_difference. The usage is:

#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()));

In the end, the set result will contain the s1-s2.

edited Oct 20 '12 at 21:15

answered Nov 12 '08 at 13:59

PierreBdR

42,120
10
46
62

+1. Sadly, when I needed that, I gave up and rolled my own loop :( – peterchen Nov 12 '08 at 14:52
54

BTW, if you use set_difference on a non-associative container class, say a vector, make sure the elements in both containers are sorted first... – oz10 Nov 13 '08 at 01:06
4

#include -> No such file, should be ? – stefanB Aug 07 '09 at 02:12
for set I had to qualify std::insert_iterator< set>(...) – stefanB Aug 07 '09 at 02:16
@stefanB: first comment is correct, and as to the second one: common is to use `std::inserter` instead. No qualification is needed since this is a function. – rlbond Dec 26 '09 at 19:29
3

The docs say `set_difference` requires both containers to be sorted. Is `set` really sorted? It is not obvious. – Ayrat Sep 06 '20 at 18:43
1

@Ayrat Of course std::set is sorted. For set_difference to work, you must make sure that the set and set_difference use the same comparison. – Fabian Apr 29 '21 at 09:24
with C++20 you could use the ranges variant `#include #include #include // ... std::set s1, s2; // Fill in s1 and s2 with values std::set result; std::ranges::set_difference(s1, s2, std::inserter(result, result.end()));` – Bernhard Leichtle Feb 07 '22 at 09:41

Mr Fooz · Answer 2 · 2008-11-12T14:43:14.243

11

Yes, there is a set_difference function in the algorithms header.

Edits:

FYI, the set data structure is able to efficiently use that algorithm, as stated in its documentation. The algorithm also works not just on sets but on any pair of iterators over sorted collections.

As others have mentioned, this is an external algorithm, not a method. Presumably that's fine for your application.

edited Nov 12 '08 at 14:43

answered Nov 12 '08 at 13:52

Mr Fooz

109,094
6
73
101

1

It's usable on _any_ pair of sorted containers. – xtofl Nov 12 '08 at 14:16

score 5 · Answer 3 · answered Oct 03 '13 at 20:35

Once again, boost to the rescue:

#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>

std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());

setDifference will contain set0-set1.

score 4 · Answer 4 · answered Nov 12 '08 at 13:55

Not an "operator" in the language sense, but there is the set_difference algorithm in the standard library:

http://www.cplusplus.com/reference/algorithm/set_difference.html

Of course, the other basic set operations are present too - (union etc), as suggested by the "See also" section at the end of the linked article.

score 2 · Answer 5 · answered Aug 06 '09 at 00:29

2

The chosen answer is correct, but has some syntax errors.

Instead of

#include <algorithms>

use

#include <algorithm>

Instead of

std::insert_iterator(result, result.end()));

use

std::insert_iterator<set<int> >(result, result.end()));

answered Aug 06 '09 at 00:29

9

or just use `std::inserter(result, result.end())` – rlbond Dec 26 '09 at 19:29

score 2 · Answer 6 · answered Feb 26 '18 at 18:49

C++ does not define a set difference operator but you can define your own (using code given in other responses):

template<class T>
set<T> operator -(set<T> reference, set<T> items_to_remove)
{
    set<T> result;
    std::set_difference(
        reference.begin(), reference.end(),
        items_to_remove.begin(), items_to_remove.end(),
        std::inserter(result, result.end()));
    return result;
}

score 1 · Answer 7 · answered Nov 12 '08 at 13:54

Not as a method but there's the external algorithm function set_difference

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);

http://www.sgi.com/tech/stl/set_difference.html

score 1 · Answer 8 · answered Nov 12 '08 at 13:54

1

Apparently, it does.

SGI - set_difference

answered Nov 12 '08 at 13:54

LeppyR64

5,251
2
30
35

Ben · Answer 9 · 2018-03-14T15:29:42.057

All of the answers I see here are O(n). Wouldn't this be better?:

template <class Key, class Compare, class Allocator>   
std::set<Key, Compare, Allocator> 
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
             const std::set<Key, Compare, Allocator>& rhs) {
    if (lhs.empty()) { return lhs; }
    // First narrow down the overlapping range:
    const auto rhsbeg = rhs.lower_bound(*lhs.begin());
    const auto rhsend = rhs.upper_bound(*lhs.rbegin());
    for (auto i = rhsbeg; i != rhsend; ++i) {
        lhs.erase(*i);
    }
    return std::move(lhs);
}

That seems to do the right thing. I'm not sure how to deal with the case that Compare's type doesn't fully specify its behavior, as in if Compare is a std::function<bool(int,int)>, but aside from that, this seems to work right and should be like O((num overlapping) • log(lhs.size())).

In the case that lhs doesn't contain *i, it's probably possible to optimize further by doing an O(log(rhs.size())) search for the next element of rhs that's >= the next element of lhs. That would optimize the case that lhs = {0, 1000} and rhs = {1, 2, ..., 999} to do the subtraction in log time.

score -1 · Answer 10 · answered Jan 03 '13 at 22:34

-1

can we just use

 set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).

answered Jan 03 '13 at 22:34

user1830108

195
1
15

4

`std::back_inserter` requires the `push_back()` method on the target container `result`. This will not work if `result` is a `std::set` – Attila Jan 18 '13 at 10:16
1

Please do not put questions in answers. – user650261 Oct 24 '18 at 04:01

c++ STL set difference

10 Answers10

Linked