欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

对于集合的交集,并集,差集的函数的理解

程序员文章站 2022-07-12 16:14:48
...
对于集合的交集,并集,差集的函数的理解

算法简介:

  • set_intersection // 求两个容器的交集(intersection==>交叉,交叉路口,十字路口,交集,交叉点)
  • set_union // 求两个容器的并集(union==>联盟,工会,联合,结合,并集)
  • set_difference // 求两个容器的差集(difference==>差异,差别,区别,差值
交集

功能:

  • 求两个容器的交集

函数原型:

  • set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  • // beg1 容器1开始迭代器
    // end1 容器1结束迭代器
    // beg2 容器2开始迭代器
    // end2 容器2结束迭代器
    // dest 目标容器开始迭代器

需要注意的是:这两个集合都必须是有序序列,也就是都排过序的

#include"head.h"


int main()
{
	vector<int>a = { 1,3,5,6,4 ,7};
	sort(a.begin(), a.end(), [](int a, int b)->bool {return a < b; });//此处只相当于复习了一下lambda表达式,因为之前只学过,没用过,在这里先试试,其实就相当于默认从小到大的排序;
		vector<int>b = { 2,3,6,2,7,9 };
		sort(b.begin(), b.end(), [](int a, int b) {return a < b; });
		vector<int>c(100);
		//cout << c.size();
	auto it=	set_intersection(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	for_each(c.begin(), it, [](int i) {cout << i << endl; });
	//3,6,7
		
}

lambda表达式

总结:

  • 求交集的两个集合必须是有序序列(必须是有序,否则一定会出错)求交集(以及并集差集)的时候其实很容易想到需要排序,如果是自己编写,只有排序才会加快时间复杂度,
  • 目标容器开辟空间需要从两个容器中求最小值(不是必要的,目的就是为了减少空间的浪费)
  • set_intersection的返回值时交集中最后一个元素的迭代器
set_union

功能描述:

  • 求两个集合的并集

函数原型:

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

#include"head.h"


int main()
{
	vector<int>a = { 1,2,3,4,5,6 };
	vector<int>b = {0,1,3,5,6,9 };
	vector<int>c(60);

	auto it=set_union(a.begin(), a.end(), b.begin(), b.end(), c.begin());//事实证明必须要排序,否则一定会出错,错误提示无效参数的传递,不过上述数组有序,所以不用排序;
	for_each(c.begin(), it, [](int i) {cout << i << " "; });
		
}

总结

  • 求并集的两个集合必须为有序序列
  • 目标容器开辟空间需要两个容器相加(不是必须的,是为了节省空间)
  • set_union返回值时并集中最后一个元素的迭代器
set_difference

功能描述:

  • 求两个集合的差集

函数原型:

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// 注意:两个集合必须是有序序列

// beg1 容器1开始迭代器
// end1 容器1结束迭代器
// beg2 容器2开始迭代器
// end2 容器2结束迭代器
// dest 目标容器开始迭代器

#include"head.h"


int main()
{
	vector<int>a = {1,7,5,3,6 };
	vector<int>b = {4,7,5,3 };
	vector<int>c(60);
	sort(a.begin(), a.end(), [](int a, int b) {return a < b; });//一定要排序
	sort(b.begin(), b.end(), [](int a, int b) {return a < b; });
	auto it=set_difference(a.begin(), a.end(), b.begin(), b.end(), c.begin());//相当于数学中集合a-b;
	for_each(c.begin(), it, [](int i) {cout << i << endl; });
}

**总结 **:

  • 求差集的两个集合必须是有序序列
  • 目标容器开辟空间需要从两个容器中取较大值(非必要,只是为了减少空间的浪费)
  • set_difference的返回值是差集中最后一个元素的位置的迭代器;
相关标签: 理解