STL常用算法-C++

概述：

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

1. 常用的遍历算法

学习目标：

• 掌握常用的遍历算法

算法简介：

• for_each // 遍历容器
• transform // 搬运容器到另一个容器中

1.1 for_each

功能描述：

• 实现遍历容器

函数原型：

• for_each(iterator beg, iterator end, _func);
  // 遍历算法 遍历容器元素
  // beg 开始迭代器
  // end 结束迭代器
  // _func 函数或者函数对象

示例：

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

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

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

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

	for_each(v.begin(), v.end(), print01);//普通函数
	cout << endl;

	for_each(v.begin(), v.end(), print02());//仿函数的函数对象
	cout << endl;
	
	return 0;
}

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

1.2 transform

功能描述：

• 搬运容器到另一个容器中

函数原型：

• transform(iterator beg1, iterator end1, iterator beg2, _func);
  // beg1 源容器开始迭代器
  // end1 源容器结束迭代器
  // beg2 目标容器开始迭代器
  // _func 函数或者函数对象（可以在搬运过程中对源容器中的元素做一些逻辑运算等操作）

示例：

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

//仿函数
class Transform
{
public:
	int operator()(int val) {//搬运过程中需要把元素返回回去，所以返回类型为搬运的元素类型
		return val;
	}
};

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

int main() {
	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;
	
	return 0;
}

总结：

• 搬运的目标容器必须要提前开辟预定大小的空间，否则无法正常搬运
• 搬运过程中需要把元素返回回去，所以仿函数的返回类型为 搬运的元素的类型

2. 常用查找算法

学习目标：

• 掌握常用的查找算法

算法简介：

• find // 查找元素
• find_if // 按条件查找元素
• adjacent_find // 查找相邻重复元素
• binary_search // 二分查找法
• count // 统计元素个数
• count_if // 按条件统计元素个数

2.1 find

功能描述：

• 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器（end）

函数原型：

• find(iterator beg, iterator end, value);
  // 以迭代器的方式按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  // beg 开始迭代器
  // end 结束迭代器
  // value 查找的元素

示例：

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

class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	
	bool operator==(const Person& p) {
		if (this->name == p.name && this->age == p.age) {
			return true;
		} else {
			return false;
		}
	}

public:
	string name;
	int age;
};

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

	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) {
		cout << "没有找到！" << endl;
	}
	else {
		cout << "找到:" << *it << endl;
	}
	

//查找自定义数据类型
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	vp.push_back(p4);

	Person pp("bbb", 20);
	//当使用 find 查找自定义数据类型时，要在自定义数据类型内部重载 == 运算符，让底层 find 知道如何对比自定义数据类型
	vector<Person>::iterator it = find(vp.begin(), vp.end(), pp);
	if (it == vp.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到：" << it->name << " " << it.age << endl;
	}
	
	return 0;
}

总结：

• 利用 find 可以在容器中找指定的元素，返回值是迭代器
• 当使用 find 查找自定义数据类型时，要在自定义数据类型内部重载 == 运算符，让底层 find 知道如何对比自定义数据类型

2.2 find_if

功能描述：

• 按条件查找元素

函数原型：

• find_if(iterator beg, iterator end, _Pred);
  // 按值查找元素，找到返回指定元素迭代器位置，找不到返回结束迭代器位置
  // beg 开始迭代器
  // end 结束迭代器
  // _Pred 函数或者谓词（返回 bool 类型的仿函数）

示例：

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

//内置数据类型仿函数
class GreaterFive
{
public:
	bool operator()(int val) {
		return val > 5;
	}
};

class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	
	bool operator==(const Person& p) {
		if (this->name == p.name && this->age == p.age) {
			return true;
		} else {
			return false;
		}
	}

public:
	string name;
	int age;
};

//自定义数据类型仿函数
class Greater20
{
public:
	bool operator()(Person& p) {
		return p.age > 20;
	}
};

int main() {
//查找内置数据类型
	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;
	}

//查找自定义数据类型
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	vp.push_back(p4);

	Person pp("bbb", 20);
	vector<Person>::iterator it = find(vp.begin(), vp.end(), Greater20());
	if (it == vp.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到：" << it->name << " " << it.age << endl;
	}
	
	return 0;
}

2.3 adjacent_find

功能描述：

• 查找相邻重复元素

函数原型：

• adjacent_find(iterator beg, iterator end);
  // 查找相邻重复元素，返回相邻元素的第一个位置的迭代器；找不到返回结束迭代器位置。
  // beg 开始迭代器
  // end 结束迭代器

示例：

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

int main() {
//查找内置数据类型
	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 it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "没有找到相邻重复元素！" << endl;
	}
	else {
		cout << "找到相邻重复元素:" << *it << endl;
	}

	return 0;
}

2.4 binary_search

功能描述：

• 查找指定元素是否存在

函数原型：

• bool binary_search(iterator beg, iterator end, val);
  // 查找指定的元素，查到返回 true，否则 false
  // beg 开始迭代器
  // end 结束迭代器
  // value 查找的元素

注意：容器必须是有序的序列，在无序序列中不可用。（如果是无序的序列，结果未知！）

示例：

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

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

	bool ret= binary_search(v.begin(), v.end(), 9);
	if (ret) {
		cout << "找到了元素!" << endl;
	}
	else {
		cout << "未找到!" << endl;
	}

	return 0;
}

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

2.5 count

功能描述：

• 统计元素个数

函数原型：

• count(iterator beg, iterator end, val);
  // 统计元素出现次数
  // beg 开始迭代器
  // end 结束迭代器
  // value 统计的元素

示例：

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

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

	bool operator==(const Person& p) {//底层要求必须加上 const，否则会报错
		if (this->age == p.age) {
			return true;
		} else {
			return false;
		}
	}

public:
	string name;
	int age;
};

int main() {
//统计内置数据类型
	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);

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

//统计自定义数据类型
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 20);
	Person p4("ddd", 40);
	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	vp.push_back(p4);
	
	Person pp("eee", 20);
	
	//当使用 count 查找自定义数据类型时，要在自定义数据类型内部重载 == 运算符，让底层 count 知道如何对比自定义数据类型
	num = count(vp.begin(), vp.end(), pp);
	cout << "和 eee 的年龄相同 的元素个数为：" << num << endl;
	
	return 0;
}

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

2.5 count_if

功能描述：

• 按条件统计元素个数

函数原型：

• count_if(iterator beg, iterator end, _Pred);
  // 按条件统计元素出现次数
  // beg 开始迭代器
  // end 结束迭代器
  // _Pred 谓词

示例：

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

class Greater2
{
public:
	bool operator()(int val) {
		return val > 2;
	}
};

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

	bool operator==(const Person& p) {//底层要求必须加上 const，否则会报错
		if (this->age == p.age) {
			return true;
		} else {
			return false;
		}
	}

public:
	string name;
	int age;
};

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

int main() {
//统计内置数据类型
	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);

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

//统计自定义数据类型
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 20);
	Person p4("ddd", 40);
	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	vp.push_back(p4);
	
	num = count(vp.begin(), vp.end(), AgeGreater20());
	cout << "age >= 20 的元素个数为：" << num << endl;
	
	return 0;
}

3. 常用排序算法

学习目标：

• 掌握常用的排序算法

算法简介：

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

3.1 sort

功能描述：

• 对容器内元素进行排序

函数原型：

• sort(iterator beg, iterator end, _Pred);
  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  // beg 开始迭代器
  // end 结束迭代器
  // _Pred 谓词，可以选择填或不填，不填的话默认是一个从小到大的排序；如果填的话会按照指定的排序规则进行排序
  // 返回值是 bool 类型

示例：

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

class Greater2
{
public:
	bool operator()(int val) {
		return val > 2;
	}
};

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

int main() {

	vector<int> v;
	v.push_back(0);
	v.push_back(2);
	v.push_back(3);
	v.push_back(1);
	v.push_back(4);

	sort(v.begin(), v.end());//1.默认升序排列
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	sort(v.begin(), v.end(), greater<int>());//2.使用内建函数对象降序排列
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	
	return 0;
}

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

3.2 random_shuffle

功能描述：

• 洗牌：对指定范围内的元素随机调整次序

函数原型：

• random_shuffle(iterator beg, iterator end);
  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  // beg 开始迭代器
  // end 结束迭代器

示例：

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

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

int main() {

	vector<int> v;
	for (int i = 0 ; i < 10; i++) {
		v.push_back(i);
	}
	//1.利用洗牌算法打乱顺序，但每次打乱顺序是一样的
	//random_shuffle(v.begin(), v.end());
	//2.利用洗牌算法打乱顺序，加入随机种子真实打乱
	srand((unsigned int)time(NULL));
	random_shuffle(v.begin(), v.end());

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

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

3.3 merge

功能描述：

• 两个容器元素合并，并存储到另一个容器中

函数原型：

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

注意：默认情况下两个容器必须都是升序序列，合并后依然是一个升序序列；如果都是降序序列的话，需要在参数列表中第 6 个形参的位置填写 谓词参数 指定规则。

示例：

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

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

int main() {

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

	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;
	
	return 0;
}

总结：

• 默认情况下 merge 合并的两个容器必须都是升序序列，合并后依然是一个升序序列。
• 必须提前给目标容器分配空间

3.3 reverse

功能描述：

• 将容器内元素进行反转

函数原型：

• reverse(iterator beg, iterator end);
  // 反转指定范围内的元素
  // beg 开始迭代器
  // end 结束迭代器

示例：

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

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

int main() {

	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());//1.
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	
	return 0;
}

总结：

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

4. 常用拷贝和替换算法

学习目标：

• 掌握常用的拷贝和替换算法

算法简介：

• copy // 容器内指定范围的元素拷贝到另一个容器中
• replace // 将容器内指定范围的旧元素修改为新元素
• replace_if // 容器内指定范围满足条件的元素替换为新元素
• swap // 互换两个容器的元素

4.1 copy

功能描述：

• 容器内指定范围的元素拷贝到另一个容器中

函数原型：

• copy(iterator beg, iterator end, iterator dest);
  // 将源容器中的数据拷贝到目标容器中
  // beg 源容器的起始迭代器
  // end 源容器的结束迭代器
  // dest 目标容器的起始迭代器

示例：

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

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

int main() {

	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

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

	vector<int> v2;
	v2.resize(v.size());//提前开辟空间
	copy(v.begin(), v.end(), v2.begin());//1.

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

	
	return 0;
}

总结：

• 利用 copy 算法在拷贝时，目标容器记得提前开辟空间。
• 在实际工程中以容器直接赋值为主，copy 算法拷贝使用较少。

4.2 replace

功能描述：

• 容器内指定范围的旧元素修改为新元素

函数原型：

• replace(iterator beg, iterator end, oldvalue, newvalue);
  // 将区间内旧元素替换成新元素
  // beg 开始迭代器
  // end 结束迭代器
  // oldvalue 旧元素
  // newvalue 新元素

示例：

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

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

int main() {

	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

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

	replace(v.begin(), v.end(), 20, 2000);//1.

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

	
	return 0;
}

总结：

• replace 会替换区间内满足条件的元素

4.3 replace_if

功能描述：

• 将区间内满足条件的元素，替换成指定元素

函数原型：

• replace_if(iterator beg, iterator end, _pred, newvalue);
  // 按条件替换元素，将区间内满足条件的旧元素替换成新元素
  // beg 开始迭代器
  // end 结束迭代器
  // _pred 谓词
  // newvalue 替换的新元素

示例：

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

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

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

int main() {

	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

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

	replace_if(v.begin(), v.end(), Greater30(), 3000);//1.

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

	
	return 0;
}

总结：

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

4.4 swap

功能描述：

• 互换两个容器

函数原型：

• swap(container c1, container c2);
  // 互换两个容器
  // c1：容器 1
  // c2：容器 2

同种类型的容器才可以做交换。

示例：

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

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

int main() {

	vector<int> v1;
	v1.push_back(10);
	v1.push_back(30);
	v1.push_back(50);
	v1.push_back(20);
	v1.push_back(40);
	
	vector<int> v2;
	v2.push_back(300);
	v2.push_back(500);
	v2.push_back(200);
	v2.push_back(400);

	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;
	
	swap(v1, v2);//1.

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

	
	return 0;
}

总结：

• swap 交换容器时，注意交换的容器要同种类型

5. 常用的算术生成算法

学习目标：

• 掌握常用的算术生成算法

注意：

• 算术生成算法属于小型算法，使用是包含的头文件为 #include <numeric>

算法简介：

• accumulate // 计算容器元素累积总和
• fill // 往容器中添加元素

5.1 accumulate

功能描述：

• 计算区间内的容器元素累计总和

函数原型：

• accumulate(iterator beg, iterator end, value);
  // 计算容器元素累积总和
  // beg 开始迭代器
  // end 结束迭代器
  // value 初始的累加值

示例：

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

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

int main() {

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

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

	int total = accumulate(v.begin(), v.end(), 0);//1.
	cout << "total = " << total << endl;
	
	return 0;
}

总结：

• accumulate 使用时头文件注意是 numeric，这个算法很实用

5.2 fill

功能描述：

• 向容器中填充指定的元素

函数原型：

• fill(iterator beg, iterator end, value);
  // 向容器中填充元素
  // beg 开始迭代器
  // end 结束迭代器
  // value 填充的值

示例：

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

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

int main() {

	vector<int> v;
	v.resize(10);
	fill(v.begin(), v.end(), 100);

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

总结：

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

6. 常用集合算法

学习目标：

• 掌握常用的集合算法

算法简介：

• set_intersection //求两个容器的交集
• set_union //求两个容器的并集
• set_difference //求两个容器的差集

6.1 set_intersection

功能描述：

• 求两个容器的交集

函数原型：

• set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求两个容器的交集
  // beg1 容器1开始迭代器
  // end1 容器1结束迭代器
  // beg2 容器2开始迭代器
  // end2 容器2结束迭代器
  // dest 目标容器开始迭代器
  // 返回目标容器中交集结束的迭代器

注意：两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。

示例：

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

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

int main() {

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

	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());//1.返回值是目标容器中交集结束的迭代器
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
	
	return 0;
}

总结：

• 求交集的两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。
• 目标容器开辟空间需要从两个容器中取小值
• set_intersection 返回值 是交集中最后一个元素的下一个位置，在遍历交集的时候使用返回值的迭代器。

6.2 set_union

功能描述：

• 求两个容器的并集

函数原型：

• set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求两个容器的并集
  // beg1 容器1开始迭代器
  // end1 容器1结束迭代器
  // beg2 容器2开始迭代器
  // end2 容器2结束迭代器
  // dest 目标容器开始迭代器
  // 返回目标容器中并集结束的迭代器

注意：两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。

示例：

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

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

int main() {

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

	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());//1.返回值是目标容器中并集结束的迭代器
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
	
	return 0;
}

总结：

• 求并集的两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。
• 目标容器开辟空间需要两个容器相加
• set_union 返回值 是并集中最后一个元素的下一个位置，在遍历并集的时候使用返回值的迭代器。

6.3 set_difference

功能描述：

• 求两个容器的差集

v1 和 v2 容器的差集：v1 - v1 ∩ v2
v2 和 v1 容器的差集：v2 - v1 ∩ v2

函数原型：

• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // 求两个容器的差集
  // beg1 容器1开始迭代器
  // end1 容器1结束迭代器
  // beg2 容器2开始迭代器
  // end2 容器2结束迭代器
  // dest 目标容器开始迭代器
  // 返回目标容器中差集结束的迭代器

注意：两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。

示例：

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

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

int main() {

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

	vector<int> vTarget;
	vTarget.resize(max(v1.size(), v2.size()));//提前给目标容器分配空间
	cout << "v1 和 v2 的差集是：" << endl;
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());//1.返回值是目标容器中差集结束的迭代器
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;

	cout << "v2 和 v1 的差集是：" << endl;
	vector<int>::iterator itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());//2.返回值是目标容器中差集结束的迭代器
	for_each(vTarget.begin(), itEnd, myPrint);
	cout << endl;
	
	return 0;
}

总结：

• 求差集的两个集合（两个源容器）必须是有序序列（默认升序，降序谓词）。
• 目标容器开辟空间需要从两个容器中取较大值
• set_difference 返回值 是差集中最后一个元素的下一个位置，在遍历差集的时候使用返回值的迭代器。