c++ STL set difference

问题:

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

回答1:

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.

回答2:

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.

回答3:

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.

回答4:

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

回答5:

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

回答6:

Apparently, it does.

SGI - set_difference

回答7:

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.

回答8:

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

回答9:

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.

回答10:

can we just use

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