如何在 C++ 中找到两个 std::set 的交集？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13448064/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
how to find the intersection of two std::set in C++?
提问by ILikeTacos
I have been trying to find the intersection between two std::set in C++, but I keep getting an error.
我一直试图在 C++ 中找到两个 std::set 之间的交集，但我一直收到错误消息。
I created a small sample test for this
我为此创建了一个小样本测试
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
set<int> s1;
set<int> s2;
s1.insert(1);
s1.insert(2);
s1.insert(3);
s1.insert(4);
s2.insert(1);
s2.insert(6);
s2.insert(3);
s2.insert(0);
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
return 0;
}
The latter program does not generate any output, but I expect to have a new set (let's call it s3) with the following values:
后一个程序不生成任何输出，但我希望有一个s3具有以下值的新集合（让我们称之为）：
s3 = [ 1 , 3 ]
Instead I'm getting the error:
相反，我收到了错误：
test.cpp: In function ‘int main()':
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)'
What I understand out of this error, is that there's no definition in set_intersectionthat accepts Rb_tree_const_iterator<int>as parameter.
我从这个错误中了解到，没有定义set_intersection接受Rb_tree_const_iterator<int>作为参数。
Furthermore, I suppose the std::set.begin()method returns an object of such type,
此外，我想该std::set.begin()方法返回一个这种类型的对象，
is there a better way to find the intersection of two std::setin C++? Preferably a built-in function?
有没有更好的方法可以std::set在 C++ 中找到两个的交集？最好是内置函数？
Thanks a lot!
非常感谢！
回答by Karthik T
You havent provided an output iterator for set_intersection
您还没有为set_intersection提供输出迭代器
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
Fix this by doing something like
通过做类似的事情来解决这个问题
...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
std::inserter(intersect,intersect.begin()));
You need a std::insertiterator since the set is as of now empty. We cannot use back_ or front_inserter since set doesnt support those operations.
您需要一个std::insert迭代器，因为该集合现在是空的。我们不能使用 back_ 或 front_inserter 因为 set 不支持这些操作。
回答by billz
Have a look at the sample in the link: http://en.cppreference.com/w/cpp/algorithm/set_intersection
查看链接中的示例：http: //en.cppreference.com/w/cpp/algorithm/set_intersection
You need another container to store the intersection data, below code suppose to work:
您需要另一个容器来存储交叉数据，下面的代码假设可以工作：
std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));
回答by Olaf Dietsche
See std::set_intersection. You must add an output iterator, where you will store the result:
见std::set_intersection。您必须添加一个输出迭代器，您将在其中存储结果：
#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));
See Ideonefor full listing.
有关完整列表，请参阅Ideone。
回答by Kemin Zhou
Just comment here. I think it is time to add union, intersect operation to the set interface. Let's propose this in the future standards. I have been using the std for a long time, each time I used the set operation I wished the std were better. For some complicated set operation, like intersect, you may simply (easier?) modify the following code:
只是在这里评论。我觉得是时候给set接口添加union、intersect操作了。让我们在未来的标准中提出这个建议。我用std很久了，每次用set操作都希望std好点。对于一些复杂的集合操作，比如相交，你可以简单地（更容易？）修改以下代码：
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (first1!=last1 && first2!=last2)
{
if (*first1<*first2) ++first1;
else if (*first2<*first1) ++first2;
else {
*result = *first1;
++result; ++first1; ++first2;
}
}
return result;
}
copied from http://www.cplusplus.com/reference/algorithm/set_intersection/
复制自http://www.cplusplus.com/reference/algorithm/set_intersection/
For example, if your output is a set, you can output.insert(*first1). Furthermore, you function may not be templated.If you code can be shorter than using the std set_intersection function then go ahead with it.
例如，如果您的输出是一个集合，则可以 output.insert(*first1)。此外，您的函数可能没有被模板化。如果您的代码可以比使用 std set_intersection 函数更短，那么继续使用它。
If you want to do a union of two set you can simply setA.insert(setB.begin(), setB.end()); This is much simpler than the set_union method. However, this will not work with vector.
如果你想做两个集合的并集，你可以简单地 setA.insert(setB.begin(), setB.end()); 这比 set_union 方法简单得多。但是，这不适用于矢量。
回答by Scheff
The first (well-voted) comment of the accepted answercomplains about a missing operator for the existing std set operations.
已接受答案的第一个（投票得当）评论抱怨现有标准集操作缺少运算符。
On one hand, I understand the lack of such operators in the standard library. On the other hand, it is easy to add them (for the personal joy) if desired. I overloaded
一方面，我理解标准库中缺少这样的操作符。另一方面，如果需要，很容易添加它们（为了个人乐趣）。我超载了
operator *()for intersection of setsoperator +()for union of sets.
operator *()对于集合的交集operator +()用于集合的并集。
Sample test-set-ops.cc:
样品test-set-ops.cc：
#include <algorithm>
#include <iterator>
#include <set>
template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator * (
const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
std::set<T, CMP, ALLOC> s;
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(s, s.begin()));
return s;
}
template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator + (
const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
std::set<T, CMP, ALLOC> s;
std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
std::inserter(s, s.begin()));
return s;
}
// sample code to check them out:
#include <iostream>
using namespace std;
template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
const char *sep = " ";
for (const T &value : values) {
out << sep << value; sep = ", ";
}
return out;
}
int main()
{
set<int> s1 { 1, 2, 3, 4 };
cout << "s1: {" << s1 << " }" << endl;
set<int> s2 { 0, 1, 3, 6 };
cout << "s2: {" << s2 << " }" << endl;
cout << "I: {" << s1 * s2 << " }" << endl;
cout << "U: {" << s1 + s2 << " }" << endl;
return 0;
}
Compiled and tested:
编译和测试：
$ g++ -std=c++11 -o test-set-ops test-set-ops.cc
$ ./test-set-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
I: { 1, 3 }
U: { 0, 1, 2, 3, 4, 6 }
$
What I don't like is the copy of return values in the operators. May be, this could be solved using move assignment but this is still beyond my skills.
我不喜欢的是运算符中返回值的副本。也许，这可以使用移动分配来解决，但这仍然超出了我的技能。
Due to my limited knowledge about these "new fancy" move semantics, I was concerned about the operator returns which might cause copies of the returned sets. Olaf Dietschepointed out that these concerns are unnecessary as std::setis already equipped with move constructor/assignment.
由于我对这些“新奇”移动语义的了解有限，我担心可能会导致返回集合的副本的运算符返回。Olaf Dietsche指出这些担忧是不必要的，因为std::set已经配备了移动构造函数/赋值。
Although I believed him, I was thinking how to check this out (for something like "self-convincing"). Actually, it is quite easy. As templates has to be provided in source code, you can simply step through with the debugger. Thus, I placed a break point right at the return s;of the operator *()and proceeded with single-step which leaded me immediately into std::set::set(_myt&& _Right): et voilà – the move constructor. Thanks, Olaf, for the (my) enlightment.
虽然我相信他，但我正在考虑如何检查这一点（例如“自我说服”之类的东西）。实际上，这很容易。由于模板必须在源代码中提供，您可以简单地使用调试器逐步完成。因此，我把一个破发点就在return s;的operator *()，并与单步其含铅我马上进入着手std::set::set(_myt&& _Right)：瞧等-移动的构造。谢谢，奥拉夫，为（我的）启蒙。
For the sake of completeness, I implemented the corresponding assignment operators as well
为了完整起见，我也实现了相应的赋值运算符
operator *=()for "destructive" intersection of setsoperator +=()for "destructive" union of sets.
operator *=()用于“破坏性”集合的交集operator +=()用于集合的“破坏性”并集。
Sample test-set-assign-ops.cc:
样品test-set-assign-ops.cc：
#include <iterator>
#include <set>
template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator *= (
std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
auto iter1 = s1.begin();
for (auto iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
if (*iter1 < *iter2) iter1 = s1.erase(iter1);
else {
if (!(*iter2 < *iter1)) ++iter1;
++iter2;
}
}
while (iter1 != s1.end()) iter1 = s1.erase(iter1);
return s1;
}
template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator += (
std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
s1.insert(s2.begin(), s2.end());
return s1;
}
// sample code to check them out:
#include <iostream>
using namespace std;
template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
const char *sep = " ";
for (const T &value : values) {
out << sep << value; sep = ", ";
}
return out;
}
int main()
{
set<int> s1 { 1, 2, 3, 4 };
cout << "s1: {" << s1 << " }" << endl;
set<int> s2 { 0, 1, 3, 6 };
cout << "s2: {" << s2 << " }" << endl;
set<int> s1I = s1;
s1I *= s2;
cout << "s1I: {" << s1I << " }" << endl;
set<int> s2I = s2;
s2I *= s1;
cout << "s2I: {" << s2I << " }" << endl;
set<int> s1U = s1;
s1U += s2;
cout << "s1U: {" << s1U << " }" << endl;
set<int> s2U = s2;
s2U += s1;
cout << "s2U: {" << s2U << " }" << endl;
return 0;
}
Compiled and tested:
编译和测试：
$ g++ -std=c++11 -o test-set-assign-ops test-set-assign-ops.cc
$ ./test-set-assign-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
s1I: { 1, 3 }
s2I: { 1, 3 }
s1U: { 0, 1, 2, 3, 4, 6 }
s2U: { 0, 1, 2, 3, 4, 6 }
$
