集合一般操作、
集合的一般操作有交,并,补,差,对称差等等。。。STL提供了集合的交,差,并,对称差运算,没有提供补集运算,但是补集运算可以转化。假设我有两个集合A和B,A在B中的补集就是 B - (A ∩ B) 。
集合(set)在数学上允许重复元素且未经过排序,但是STL的容器set则要求元素不得重复且是有序的,不然会出现运算错误!!!
下面的四个STL集合算法所接受的集合必须是有序区间,元素可以重复出现。
set_union(并)、
template<class InputIterator1,class InputIterator2,class OuputIterator>
OuputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OuputIterator result);
上述是函数原型,接受两个集合S1和S2的首尾范围迭代器,将合并后的内容写到迭代器result开始往后的地方,返回合并后的内容的尾迭代器。
注意的是由于两个集合S1和S2的每一个元素都不唯一,因此如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间中会出现max(n,m)次,其中n个来自S1,其余来自S2。
set_intersection(交)、
template<class InputIterator1,class InputIterator2,class OuputIterator>
OuputIterator set_intersection(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OuputIterator result);
该算法构造两个集合S1和S2的交集,将交集的内容写入到迭代器result往后的地方,返回交集后的内容的尾迭代器。
注意的是由于两个集合S1和S2的每一个元素都不唯一,因此如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间中会出现min(n,m)次,并且全部来自S1。
set_difference(差)、
template<class InputIterator1,class InputIterator2,class OuputIterator>
OuputIterator set_difference(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OuputIterator result);
该算法构造两个集合S1和S2的差集,将差集的内容写入到迭代器result往后的地方,返回差集后的内容的尾迭代器。
注意的是由于两个集合S1和S2的每一个元素都不唯一,因此如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间中会出现max(n - m,0)次,并且全部来自S1。
set_symmetric_difference(对称差)、
所谓对称差也就是 (S1 - S2) ∪ (S2 - S1),可以由前面的算法来实现,当然也有现成的。
template<class InputIterator1,class InputIterator2,class OuputIterator>
OuputIterator set_symmetric_difference(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OuputIterator result);
对称差意思是出现在S1且不出现在S2的元素并上出现在S2且不出现在S1的元素。该算法构造两个集合S1和S2的对称差集,将对称差集的内容写入到迭代器result往后的地方,返回对称差集后的内容的尾迭代器。
补、
这个没有专门的算法,但是可以通过转化得到。S1在S2的补集是 S2 - (S1 ∩ S2)。
/* std::unique该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素,注意!!!
(1) 这里的去除并非真正意义的erase,而是将重复的元素放到容器的末尾,返回值是去重之后的尾地址。
(2) unique针对的是相邻元素,所以对于顺序顺序错乱的数组成员,或者容器成员,需要先进行排序,可以调用std::sort()函数 */
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
//打印函数
struct print
{
void operator()(const int& a)
{
cout << a << " ";
}
};
int main()
{
//建立两个集合,其中元素无序且有重复
vector<int> array = {-1,0,1,8,33,9,4,5,4,1,8,7};
vector<int> array2 = {8,8,8,89,1,0,99};
//必须进行排序!!!
sort(array.begin(),array.end());
sort(array2.begin(),array2.end());
//这里可以选择去重复也可以不去
auto it1 = unique(array.begin(),array.end());
auto it2 = unique(array2.begin(),array2.end());
//输出集合S1的元素
cout << "S1 = ";
for_each(begin(array),it1,print());
cout << endl;
//输出集合S2的元素
cout << "S2 = ";
for_each(begin(array2),it2,print());
cout << endl;
//输出容器
size_t siz = static_cast<size_t>(it1 - begin(array)) + static_cast<size_t>(it2 - begin(array2));
vector<int> array3(siz);
//求S1并S2
cout << "S1 并 S2 = ";
auto it = set_union(begin(array),it1,begin(array2),it2,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
//求S1交S2
cout << "S1 交 S2 = ";
it = set_intersection(begin(array),it1,begin(array2),it2,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
//求S1 - S2
cout << "S1 与 S2 的差 = ";
it = set_difference(begin(array),it1,begin(array2),it2,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
//求S2 - S1
cout << "S2 与 S1 的差 = ";
it = set_difference(begin(array2),it2,begin(array),it1,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
//求(S1 - S2) U (S2 - S1)
cout << "S1 与 S2 的对称差 = ";
it = set_symmetric_difference(begin(array),it1,begin(array2),it2,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
//求 S2 - (S1 ∩ S2)
cout << "S1 在 S2 内的补集 = ";
vector<int> array4(siz);
auto iter = set_intersection(begin(array),it1,begin(array2),it2,array4.begin());
it = set_difference(begin(array2),it2,array4.begin(),iter,array3.begin());
for_each(array3.begin(),it,print());
cout << endl;
return 0;
}
Comments NOTHING