c++ STL set difference

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

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.

Yes, there is a http://www.sgi.com/tech/stl/set_difference.html">set_difference</a> function in the algorithms header.

Edits:

FYI, the set data structure is able to efficiently use that algorithm, as stated in its http://www.sgi.com/tech/stl/set.html">documentation</a>;. 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.

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.

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.

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;
}

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

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

Apparently, it does.

SGI - set_difference

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.

can we just use

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