就地C++集合交集

Question

在C++中交叉两个集合的标准方法是执行以下操作:

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

我该怎么做一个就地设置交叉点？也就是说,我希望set_1具有对set_intersection的调用结果.显然,我可以做一个set_1.swap(the_intersection),但这比现场交叉效率要低得多.

Answer 1

我想我已经得到了它:

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

有谁看到任何问题？似乎是两组大小的O(n).根据cplusplus.com,std :: set erase(position)是摊销常数,而erase(first,last)是O(log n).