ILi*_*cos 77 c++ std stdset stl-algorithm
我一直在尝试在C++中找到两个std :: set之间的交集,但我一直收到错误.
我为此创建了一个小样本测试
#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;
}
后一个程序不生成任何输出,但我希望有一个新的集合(让我们称之为s3)具有以下值:
s3 = [ 1 , 3 ]
相反,我得到错误:
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>)’
我从这个错误中理解的是,没有定义set_intersection接受Rb_tree_const_iterator<int>参数.
此外,我想该std::set.begin()方法返回这种类型的对象,
有没有更好的方法std::set在C++中找到两个的交集？最好是内置功能？
非常感谢!
Kar*_*k T 92
你没有为set_intersection提供输出迭代器
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
通过做类似的事情解决这个问题
...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
std::inserter(intersect,intersect.begin()));
你需要一个std::insert迭代器,因为该集合现在是空的.我们不能使用back_或front_inserter,因为set不支持这些操作.
bil*_*llz 22
请查看链接中的示例:http: //en.cppreference.com/w/cpp/algorithm/set_intersection
你需要另一个容器来存储交集数据,在代码下面假设工作:
std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));
请参见std :: set_intersection.您必须添加输出迭代器,您将在其中存储结果:
#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));
请参阅Ideone以获取完整列表
已接受答案的第一个（投票得当）评论抱怨现有标准集操作缺少运算符。
一方面，我理解标准库中缺少这样的操作符。另一方面，如果需要，很容易添加它们（为了个人乐趣）。我超载了
operator *() 对于集合的交集operator +() 用于集合的并集。样品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;
}
编译和测试：
$ 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 }
$
我不喜欢的是运算符中返回值的副本。也许，这可以使用移动分配来解决，但这仍然超出了我的技能。
由于我对这些“新奇”移动语义的了解有限，我担心可能会导致返回集合的副本的运算符返回。Olaf Dietsche指出这些担忧是不必要的，因为std::set已经配备了移动构造函数/赋值。
虽然我相信他，但我正在考虑如何检查这一点（例如“自我说服”之类的东西）。实际上，这很容易。由于模板必须在源代码中提供，您可以简单地使用调试器逐步完成。因此，我把一个破发点就在return s;的operator *()，并与单步其含铅我马上进入着手std::set::set(_myt&& _Right)：瞧等-移动的构造。谢谢，奥拉夫，为（我的）启蒙。
为了完整起见，我也实现了相应的赋值运算符
operator *=() 用于“破坏性”集合的交集operator +=() 用于集合的“破坏性”并集。样品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;
}
编译和测试：
$ 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 }
$