C++ equivalent of Python difference_update?

Question

s1 and s2 are sets (Python set or C++ std::set)
To add the elements of s2 to s1 (set union), you can do

Python: s1.update(s2)

C++: s1.insert(s2.begin(), s2.end());

To remove the elements of s2 from s1 (set difference), you can do

Python: s1.difference_update(s2)

What is the C++ equivalent of this? The code

s1.erase(s2.begin(), s2.end());

does not work, for s1.erase() requires iterators from s1.The code

std::set<T> s3;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.end());
s1.swap(s3);

works, but seems overly complex, at least compared with Python.

Is there a simpler way?

Answer 1

Using std::set_difference is the idiomatic way to do this in C++. You have stumbled across one of the primary differences (pun intended) between C++/STL and many other languages. STL does not bundle operations directly with the data structures. This is why std::set does not implement a difference routine.

Basically, algorithms such as std::set_difference write the result of the operation to another object. It is interesting to note that the algorithm does not require that either or both of the operands are actually std::set. The definition of the algorithm is:

Effects: Copies the elements of the range [first1, last1) which are not present in the range [first2, last2) to the range beginning at result. The elements in the constructed range are sorted.

Requires: The resulting range shall not overlap with either of the original ranges. Input ranges are required to be order by the same operator<.

Returns: The end of the constructed range.

Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons

The interesting difference is that the C++ version is applicable to any two sorted ranges. In most languages, you are forced to coerce or translate the calling object (left-hand operand) into a set before you have access to the set difference algorithm.

This is not really pertinent to your question, but this is the reason that the various set algorithms are modeled as free-standing algorithms instead of member methods.

Answer 2

You should iterate through the second set:

for( set< T >::iterator iter = s2.begin(); iter != s2.end(); ++iter )
{
    s1.erase( *iter );
}

This will could be cheaper than using std::set_difference - set_difference copies the unique objects into a new container, but it takes linear time, while .erase will not copy anything, but is O(n * log( n ) ).

In other words, depends on the container, you could choose the way, that will be faster for your case.

Thanks David Rodríguez - dribeas for the remark! (:

---

EDIT: Doh! I thought about BOOST_FOREACH at the very beginning, but I was wrong that it could not be used.. - you don't need the iterator, but just the value.. As user763305 said by himself/herself.