就地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) {
++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)被摊销常数,而擦除(第一,最后)是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屋!