5. STL——常用算法

概述：

1. 算法主要是由头文件$<algorithm>$ $<functional>$ $<numeric>$组成
2. $<algorithm>$是所有STL头文件中最大的一个，范围涉及到比较，交换，查找，遍历操作，复制，修改等等
3. $<numeric>$体积很小，只包含几个在序列上面进行简单数学运算的模板函数
4. $<functional>$定义了一些模板类，用以声明函数对象

5.1 常用遍历算法

学习目标：掌握常用的遍历算法

算法简介：

1. for_each // 遍历容器
2. transform // 搬运容器到另一个容器中

5.1.1 for_each

功能描述：实现遍历容器

函数原型：for_each(iterator beg, iterator end, _func);

1. // 遍历算法，遍历容器元素
2. // beg 开始迭代器
3. // end 结束迭代器
4. // _func 函数或者函数对象

示例：

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>


// 常用遍历算法 for_each

// 普通函数
void pirnt01(int val)
{
	cout << val << "  ";
}

// 仿函数
class print02
{
public:
	void operator()(int val)
	{
		cout << val << "  ";
	}
};

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	for_each(v.begin(), v.end(), pirnt01);
	cout << endl;

	for_each(v.begin(), v.end(), print02());
	cout << endl;
}


int main()
{
	test01();

	system("pause");
	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

总结：for_each在实际开发中是最常用的遍历算法，需要熟练掌握

5.1.2 transform

功能描述：搬运容器到另一个容器中

函数原型：transform(iterator beg1, iterator end1, iterator beg2, _func)

1. beg1： 源容器开始迭代器
2. end1：源容器结束迭代器
3. beg2：目标容器开始迭代器
4. _func：函数或者函数对象

示例：

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>


// 常用遍历算法transform

class Transform
{
public:
	int operator()(int v)
	{
		return v+100;
	}
};

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

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>vTarget;			// 目标容器
	vTarget.resize(v.size());			// 目标容器 需要提前开辟空间

	transform(v.begin(), v.end(), vTarget.begin(), Transform());

	for_each(vTarget.begin(), vTarget.end(), MyPrint());
	cout << endl;


}

int main()
{
	test01();

	system("pause");
	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

总结：搬运的目标容器必须要提前开辟空间，否则无法正常搬运

5.1 常用查找算法

学习目标：掌握常用的查找算法

算法简介：

1. find // 查找元素
2. find_if // 按条件查找元素
3. adjacent_find // 查找相邻重复元素
4. binary_search // 二分查找法
5. count // 统计元素个数
6. count_if // 按条件统计元素个数

5.2.1 find

功能描述：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型：find(iterator beg, iterator end, value)

1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
2. beg // 开始迭代器
3. end // 结束迭代器
4. value // 查找的元素

示例：

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>
#include<string>


// 常用的查找算法
// find

// 查找 内置数据类型
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	// 查找 容器中 是否有5这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);

	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到：" << *it << endl;
	}
}


class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	// 重载 == 底层find知道如何对比Person数据类型
	bool operator==(const Person& p)
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

// 查找 自定义数据类型
void test02()
{
	vector<Person>v;
	// 创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	// 放入到容器中
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	Person pp("bbb", 20);

	vector<Person>::iterator it = find(v.begin(), v.end(), pp);
	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到：姓名：" << it->m_Name <<"\t年龄："<<it->m_Age<< endl;
	}
	

}

int main()
{
	// test01();
	test02();

	system("pause");
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

总结：利用find可以在容器中找到指定的元素，返回值是迭代器

5.2.2 find_if

功能描述：按条件查找元素

函数原型：find_if(iterator beg, iterator end, _Pred)

1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
2. beg：开始迭代器
3. end：结束迭代器
4. _Pred函数或者谓词（返回bool类型的仿函数）

示例：

#include<iostream>
using namespace std;
#include<functional>				// 内建函数对象头文件
#include<vector>
#include<algorithm>
#include<functional>
#include<string>


// 常用的查找算法 find_if

// 1. 查找内置数据类型
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());

	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找打大于5的数字为：" << *it << endl;
	}
}

// 2. 查找自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

class Greater20
{
public:
	bool operator()(Person& p)
	{
		return p.m_Age > 20;
	}
};

void test02()
{
	vector<Person>v;
	
	// 创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	Person p5("eee", 50);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	// 找年龄大于20的人
	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到姓名：" << it->m_Name << "\t年龄：" << it->m_Age << endl;
	}


}

int main()
{
	// test01();
	test02();

	system("pause");
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

5.2.3 adjacent_find

功能描述：查找相邻重复元素

函数原型：adjacent_find(iterator beg, iterator end);

1. 查找相邻重复元素，返回相邻元素的第一个位置的迭代器
2. beg：开始迭代器
3. end：结束迭代器

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>


// 常用查找算法 adjacent_find
void test01()
{
	vector<int>v;
	v.push_back(0);
	v.push_back(2);
	v.push_back(0);
	v.push_back(3);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);
	v.push_back(3);

	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
	if (pos == v.end())
	{
		cout << "未找到相邻重复元素" << endl;
	}
	else
	{
		cout << "找到相邻重复元素：" << *pos << endl;
	}

}

int main()
{
	test01();


	system("pause");
	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

总结：面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法

5.2.4 binary_search

功能描述：查找指定元素是否存在

函数原型：bool binary_search(iterator beg, iterator end, value);

1. 查找指定的元素，查到 返回true 否则返回false
2. 注意：在无序序列中不可以用
3. beg 开始迭代器
4. end 结束迭代器
5. value 查找的元素

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

// 常用查找算法 binary_search
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	// v.push_back(2);				// 如果是无序序列，结果未知
	// 查找容器中是否有9 元素
	bool ret = binary_search(v.begin(), v.end(), 9);
	if (ret)
	{
		cout << "找到了元素" << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}

}

int main()
{

	test01();

	system("pause");
	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

总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须是有序序列

5.2.5 count

统计描述：统计元素个数

函数原型：count（iterator beg， iterator end， value）;

1. 统计元素出现次数
2. beg开始迭代器
3. end结束迭代器
4. value统计的元素

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

// 常用查找算法 count

// 1. 统计内置数据类型
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);

	int num = count(v.begin(), v.end(), 40);
	cout << "40的元素个数为：" << num << endl;


}

// 2. 统计自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	bool operator==(const Person &p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person>v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 40);

	// 将人员插入到容器中
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);


	Person p("诸葛亮", 35);
	int num = count(v.begin(), v.end(), p);
	cout << "和诸葛亮同岁数的人员个数为：" << num << endl;


}


int main()
{

	//test01();
	test02();

	system("pause");
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

总结：统计自定义数据类型的时候，需要配合重载operator==

5.2.6 count_if

功能描述：按条件统计元素个数

函数原型：count_if(iterator beg, iterator end, _Pred)；

1. 按条件统计元素出现次数
2. beg：开始迭代器
3. end：结束迭代器
4. _Pred：谓词

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

// 常用查找算法 count_if

// 统计内置数据类型
class Greater20
{
public:
	bool operator()(int val)
	{
		return val > 20;
	}
};
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(20);

	int num = count_if(v.begin(), v.end(), Greater20());
	cout << "大于20的元素个数为：" << num << endl;

}

// 统计自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

class AgeGreater20
{
public:
	bool operator()(const Person & p)
	{
		return p.m_Age > 20;
	}
};


void test02()
{
	vector<Person>v;
	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 40);
	Person p5("曹操", 20);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	// 统计 大于20岁人员个数
	int num = count_if(v.begin(), v.end(), AgeGreater20());
	cout << "大于20岁的人员个数为：" << num << endl;


}


int main()
{

	//test01();  
	test02();

	system("pause");
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

5.3 常用排序算法

学习目标：掌握常用的排序算法

算法简介：

1. sort // 对容器内元素进行排序
2. random_shuffle // 洗牌 指定范围内的元素随机调整次序
3. merge // 容器元素合并，并存储到另一容器中
4. reverse // 反转指定范围的元素

5.3.1 sort

功能描述：对容器内元素进行排序

函数原型：sort（iterator beg， iterator end， _Pred）;

1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
2. beg：开始迭代器
3. end：结束迭代器
4. _Pred：谓词

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

// 常用排序算法
void MyPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	// 利用sort进行升序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), MyPrint);
	cout << endl;

	// 改变为 降序
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), MyPrint);
	cout << endl;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：sort属于开发中最常用的算法之一，需熟练掌握

5.3.2 random_shuffle

功能描述：洗牌 指定范围内的元素随机调整次序

函数原型：random_shuffle(iterator beg, iterator end);

1. 指定范围内的元素随机调整次序
2. beg：开始迭代器
3. end：结束迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>

// 常用排序算法 random_shuffle
void MyPrint(int val)
{
	cout << val << " ";
}

void test01()
{
	srand((unsigned int)time(NULL));

	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	// 利用洗牌 算法 打乱顺序
	random_shuffle(v.begin(), v.end());

	for_each(v.begin(), v.end(), MyPrint);
	cout << endl;


}




int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：random_shuffle洗牌算法比较实用，使用时记得加随机数种子

5.3.3 merge

功能描述：两个容器元素合并，并存储到另一容器中

函数原型：merge（iterator beg1， iterator end1， iterator beg2，iterator end2， iterator dest）；

1. 容器元素合并，并存储到另一容器中
2. 注意：两个容器必须是有序的
3. beg1：容器1开始迭代器
4. end1：容器1结束迭代器
5. beg2：容器2开始迭代器
6. end2：容器2结束迭代器
7. dest：目标容器开始迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>

// 常用排序算法 merge
void myPrint(int val)
{	
	cout << val << " ";
}
void test01()
{
	vector<int>v1;
	vector<int>v2;

	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i+1);
	}

	// 目标容器
	vector<int>vTarget;

	// 提前给目标容器分配空间
	vTarget.resize(v1.size() + v2.size());

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), vTarget.end(),myPrint);
	cout << endl;

}

int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：merge合并的两个容器必须是有序序列。

5.3.4 reverse

功能描述：将容器内元素进行反转

函数原型：reverse（iterator beg， iterator end）;

1. 反抓指定范围的元素
2. beg：开始迭代器
3. end：结束迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>


void myPrint(int val)
{
	cout << val << "  ";
}

// 常用排序算法 reverse
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反转前：" << endl;
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	cout << "反转后：" << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：reverse反转区间内元素，面试题可能涉及到

5.4 常用拷贝和替换方法

学习目标：掌握常用的拷贝和替换算法

算法简介：

1. copy：容器内只当范围的元素拷贝到另一容器中
2. replace：将容器中指定范围的旧元素修改为新元素
3. replace_if：容器内指定范围满足条件的元素替换为新元素
4. swap：互换两个容器的元素

5.4.1 copy

功能描述：容器内指定范围的元素拷贝到另一容器中

函数原型：copy（iterator beg， iterator end， iterator dest）；

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>


// 常用拷贝和替换算法 copy

void myPrint(int val)
{
	cout << val << " ";

}
void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	vector<int>v2;
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;  


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

利用copy算法在拷贝时，目标容器记得提前开辟空间

5.4.2 replace

功能描述：将容器内指定范围的旧元素修改为新元素

函数原型：replace(iterator beg, iterator end, oldvalue, newvalue)；

1. 将区间内旧元素 替换成 新元素
2. beg 开始迭代器
3. end 结束迭代器
4. oldvalue 旧元素
5. newvalue 新元素

示例；

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>


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

// 常用拷贝和替换方法 replace
void test01()
{
	vector<int>v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(10);
	v.push_back(20);

	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	// 将20 替换成 2000
	replace(v.begin(), v.end(), 20, 2000);
	cout << "替换后：" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;


}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：replace会替换区间内满足条件的元素

5.4.3 replace_if

功能描述：将区间内满足条件的元素，替换成指定元素

函数原型：replace_if（iterator beg, iterator end, _pred, newvalue）;

1. 按条件替换元素，满足条件的替换成指定元素
2. beg：开始迭代器
   3 end：结束迭代器
3. _pred：谓词
4. newvalue：替换的新元素

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>



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

class Greater30
{
public:
	bool operator()(int val)
	{
		return val >= 30;
	}
};

// 常用的拷贝和替换算法 replace_if
void test01()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(30);

	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	// 将大于等于30 替换为 3000
	replace_if(v.begin(), v.end(), Greater30(), 3000);
	cout << "替换后：" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;



}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：replace_if按条件查找，可以利用仿函数灵活筛选满足的条件

5.4.4 swap

功能描述：互换两个容器的元素

函数原型：swap（container c1， container c2）；

1. 互换两个容器的元素
2. c1容器1
3. c2容器2

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>


// 常用拷贝和替换方法 swap
void myPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v1;
	vector<int>v2;

	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(100 + i);
	}

	cout << "交换前：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;

	swap(v1, v2);

	cout << "交换后：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;

	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;

}

int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：swap交换容器时，注意交换的容器要同种类型

5.5 常用算术生成算法

学习目标：掌握常用的算术生成算法

注意：算术生成算法属于小型算法，使用时包含的头文件为KaTeX parse error: Expected 'EOF', got '#' at position 1: #̲include<numeric…

算法简介：

1. accumulate：计算容器元素累计总和
2. fill：向容器中添加元素

5.5.1 accumulate

功能描述：计算区间内容器元素累计总和

函数原型：accumulate(iterator beg, iterator end, value);

1. 计算容器元素累计总和
2. beg开始迭代器
3. end结束迭代器
4. value：起始值

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>
#include<numeric>


// 常用算术生成算法
void test01()
{
	vector<int>v;
	for (int i = 0; i <= 100; i++)
	{
		v.push_back(i);
	}

	// 参数3 起始累加值
	int total = accumulate(v.begin(), v.end(), 0);
	cout << "total = " << total << endl;

}



int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：accumulate使用时头文件注意时numeric，这个算法很实用

5.5.2 fill

功能描述：向容器中填充指定的元素

函数原型：fill(iterator beg, iterator end, value)

1. 向容器中填充元素
2. beg开始迭代器
3. end结束迭代器
4. value填充的值

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>
#include<numeric>


// 常用算术生成算法
void myPrint(int val)
{
	cout << val << "  ";
}
void test01()
{
	vector<int>v;
	v.resize(10);

	// 后期重新填充
	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：利用fill可以将容器区间内元素填充为指定的值

5.6 常用集合算法

学习目标：掌握常用的集合算法

算法简介：

1. set_intersection // 求两个容器的交集
2. set_union // 求两个容器的并集
3. set_difference // 求两个容器的差集

5.6.1 set_intersection

功能描述：求两个容器的交集

函数原型：set_intersection(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

1. 求两个集合的交集
2. 注意：两个集合必须是有序序列
3. beg1：容器1开始迭代器
4. end1：容器1结束迭代器
5. beg2：容器2开始迭代器
6. end2：容器2结束迭代器
7. dest：目标容器开始迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>
#include<numeric>


 // 常用集合算法 set_intersection
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况 大容器包含小容器 开辟空间 取小容器的size即可
	vTarget.resize(min(v1.size(), v2.size()));

	// 获取交集
	vector<int>::iterator itEnd =  set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());


	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：

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

5.6.2 set_union

功能描述：求两个集合的并集

函数原型：set_union(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

1. 求两个集合的并集
2. 注意：两个集合必须是有序序列
3. beg1：容器1开始迭代器
4. end1：容器1结束迭代器
5. beg2：容器2开始迭代器
6. end2：容器2结束迭代器
7. dest：目标容器开始迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>
#include<numeric>


 // 常用集合算法 set_union
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况  两个容器没有并集 并集就是两个容器size相加 
	vTarget.resize(v1.size()+ v2.size());

	// 获取交集
	vector<int>::iterator itEnd =  set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());


	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：

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

5.6.3 set_difference

功能描述：求两个集合的差集

函数原型： set_difference(iterator beg1, iteration end1, iteration beg2, iteration end2, iteration dest)

1. 求两个集合的差集
2. 注意：两个集合必须是有序序列
3. beg1：容器1开始迭代器
4. end1：容器1结束迭代器
5. beg2：容器2开始迭代器
6. end2：容器2结束迭代器
7. dest：目标容器开始迭代器

示例：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<ctime>
#include<numeric>


 // 常用集合算法 set_difference
void myPrint(int val)
{
	cout << val << "  ";

}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	vector<int>vTarget;
	
	// 目标容器需要提前开辟空间
	// 最特殊情况  两个容器没有交集 取两个容器中大的size作为目标容器开辟空间
	vTarget.resize(max(v1.size(),v2.size()));

	// 获取交集
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	cout << "v1和v2的差集为：" << endl;
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
}


int main()
{

	test01();  
	//test02();

	system("pause");
	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

总结：

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