In-place C++ set intersection

Question

The standard way of intersecting two sets in C++ is to do the following:

std::set<int> set_1;  // With some elements std::set<int> set_2;  // With some other elements std::set<int> the_intersection;  // Destination of intersect std::set_intersection(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(the_intersection, the_intersection.end())); 

How would I go about doing an in-place set intersection? That is, I want set_1 to have the results of the call to set_intersection. Obviously, I can just do a set_1.swap(the_intersection), but this is a lot less efficient than intersecting in-place.

Answer 1

I think I've got it:

std::set<int>::iterator it1 = set_1.begin(); std::set<int>::iterator it2 = set_2.begin(); while ( (it1 != set_1.end()) && (it2 != set_2.end()) ) {     if (*it1 < *it2) {         set_1.erase(it1++);     } else if (*it2 < *it1) {         ++it2;     } else { // *it1 == *it2             ++it1;             ++it2;     } } // Anything left in set_1 from here on did not appear in set_2, // so we remove it. set_1.erase(it1, set_1.end()); 

Anyone see any problems? Seems to be O(n) on the size of the two sets. According to cplusplus.com, std::set erase(position) is amortized constant while erase(first,last) is O(log n).