17.C++常用的算法_集合算法

遍历算法

1. set_intersection()

代码工程

/*1.求交集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要从两个容器中取较小值*/
/*3.set_intersection返回值是交集中最后一个元素的位置*/
1
2
3

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

using namespace std;

/*1.求交集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要从两个容器中取较小值*/
/*3.set_intersection返回值是交集中最后一个元素的位置*/
 
class print
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i); //0 1 2 3 4 5 6 7 8 9
		v2.push_back(i + 5);//5 6 7 8 9 10 11 12 13 14
	}
	//两个容器的交集为 5 6 7 8 9

	//目标容器
	vector<int>vTarget;
	//交集开辟的空间为两个容器较小的空间
	vTarget.resize(min(v1.size(), v2.size()));

	//求两个容器的交集
	vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	cout << "交集为：";

	//这里如果不用迭代器itEnd，使用vTarget.end()，会把容器后边的5个0打印出来
	for_each(vTarget.begin(), itEnd, print());

	cout << endl;

	return;
}

int main()
{
	test01();

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

运行结果

2. set_union()

/*1.求并集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要两个容器相加*/
/*3.set_union返回值是并集中最后一个元素的位置*/
1
2
3

代码工程

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

using namespace std;

/*1.求并集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要两个容器相加*/
/*3.set_union返回值是并集中最后一个元素的位置*/

class print
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i); //0 1 2 3 4 5 6 7 8 9
		v2.push_back(i + 5);//5 6 7 8 9 10 11 12 13 14
	}
	//两个容器的并集为 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

	//目标容器
	vector<int>vTarget;
	//并集开辟的空间为两个容器相加的空间大小
	vTarget.resize(v1.size() + v2.size());

	//求两个容器的并集
	vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	cout << "并集为：";

	//这里如果不用迭代器itEnd，使用vTarget.end()，会把容器后边的5个0打印出来
	for_each(vTarget.begin(), itEnd, print());

	cout << endl;

	return;
}

int main()
{
	test01();

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

运行结果

3. set_difference()

/*1.求差集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要从两个容器取较大值*/
/*3.set_difference返回值是并集中最后一个元素的位置*/
1
2
3

代码工程

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

using namespace std;

/*1.求差集的两个集合必须是有序序列*/
/*2.目标容器开辟空间需要从两个容器取较大值*/
/*3.set_difference返回值是并集中最后一个元素的位置*/

class print
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};

void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i); //0 1 2 3 4 5 6 7 8 9
		v2.push_back(i + 5);//5 6 7 8 9 10 11 12 13 14
	}
	
	//目标容器
	vector<int>vTarget;
	//差集 最特殊的情况 两个容器没有交集 取两个容器中较大的size作为目标容器开辟空间
	vTarget.resize(max(v1.size(), v2.size()));

	cout << "v1和v2的差集为：";

	//v1和v2的差集为 0 1 2 3 4
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, print());

	cout << endl;

	cout << "v2和v1的差集为：";

	//v2和v1的差集为 10 11 12 13 14
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, print());

	cout << endl;

	return;
}

int main()
{
	test01();

	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

运行结果