就地 C++ 设置交集 [英] In-place C++ set intersection

问题描述

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

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

我将如何进行就地设置的交叉点?也就是说，我希望 set_1 有调用 set_intersection 的结果.显然，我可以只做一个 set_1.swap(the_intersection)，但这比就地相交效率低很多.

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.

推荐答案

我想我明白了:

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) 时的摊销常数.

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).

这篇关于就地 C++ 设置交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！