Is the following code using std::set "legal"?

Question

I have this code:

set<int>::iterator new_end = 
                   set_difference(set1.begin(), set1.end(),
                                  set2.begin(), set2.end(),
                                  set1.begin());
set1.erase(new_end, set1.end);

It compiles and runs fine in visual studio. However, in a previous question, people stated that a set's iterators are supposed to be const. I don't see anything like that in the standard. Can someone tell me where it says that, or if this is well-defined behavior?

If it's not, please provide code that does what I need. Is there a way to do this without creating a temporary set?

Answer 1

The fifth argument to set_difference is supposed to be an OutputIterator, see documentation.

Answer 2

No, it's not. From the SGI STL Reference

1. [first1, last1) and [result, result + n) do not overlap.
2. [first2, last2) and [result, result + n) do not overlap.

Also, I'm not sure that begin() can be used as an OutputIterator, as Nikolai N Fetissov pointed out.

Answer 3

One suggestion to solve it:

std::set<int> tmp;
std::set_difference(set1.begin(), set1.end(),
                    set2.begin(), set2.end(),
                    std::inserter(tmp, tmp.begin()));
std::swap(tmp, set1);

I can't think of a way to do it without using a temporary set (apart from iterating through the containers and doing erase on individual elements).

Answer 4

Your code violates a couple of the invariants for set_difference. From page 420 of the Josuttis Book:

• The caller must ensure that the destination range is big enough or that insert iterators are used.
• The destination range should not overlap the source ranges.

You're trying to write back over the first set, which is not allowed. You need to write someplace other than the source ranges - for that we can use a third set:

std::set<int> set3;
std::set_difference(set1.begin(), set1.end(),
                    set2.begin(), set2.end(),
                    std::inserter(set3, set3.begin()));

The second argument to std::inserter is a hint for where the elements should be inserted. It's only a hint, however, rest assured that the elements will end up in the right place. set3 is initially empty, so begin() is about the only hint we can give.

After the call to set_difference, set3 will contain what you tried to make set1 contain in your original code. You can go on using set3 or swap it with set1 if you prefer.

Update:

I'm not sure about the performance of this, but if you just want to remove all elements from set1 that appear in set2, you can try:

for (std::set<int>::iterator i = set2.begin(); i != set2.end(); ++i)
{
    set1.erase(*i);
}

Answer 5

The C++ standard doesn't explicitly say that assigning to set iterators is disallowed, but it does specify for set_difference that "the resulting range shall not overlap with either of the original ranges" (25.3.5.3).

It may have worked for you so far just because you got lucky with the contents of set1 and set2.