详解c++STL—常用算法

概述:

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

1、常用遍历算法

1.1、for_each

功能描述：

• 实现容器的遍历

函数原型：

• for_each(iterator beg, iterator end, _func);

// beg 开始迭代器

// end 结束迭代器

// _func 函数或者函数对象

示例：

#include<vector>
#include<algorithm>
//常用遍历算法 for_each
void print01(int val) {
	cout << val << " ";
}

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

void test01() {
	int a[] = { 1,2,4,5,6,7,8,0,9 };
	vector<int> v(a,a+9);
	
	//用函数名，作为第三个参数
	for_each(v.begin(), v.end(),print01);
	cout << endl;

	//用仿函数，作为第三个参数
	//Print02() 匿名对象
	for_each(v.begin(), v.end(),Print02());
	cout << endl;
}

int main() {
	test01();
	system("pause");
	return 0;
}

1.2、transform

功能描述：

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

函数原型：

• transform(iterator beg1, iterator end1, iterator beg2, _func);

//beg1 源容器开始迭代器

//end1 源容器结束迭代器

//beg2 目标容器开始迭代器

//_func 函数或者函数对象

示例：

//常用遍历算法 transform
class Print02 {
public:
	int operator()(int val) const {
		cout << val << " ";
		return val;
	}
};

int func(int val)  {
	return val;
}

void test01() {
	int a[] = { 1,2,4,5,6,7,8,0,9 };
	//1、源容器
	vector<int> vS(a, a + 9);
	for_each(vS.begin(), vS.end(), Print02());
	cout << endl;

	//2、目标容器
	vector<int> vT;
	vT.resize(vS.size());//开辟空间，不开辟报错、

	//搬运
	transform(vS.begin(),vS.end(),vT.begin(),func);
	for_each(vT.begin(),vT.end(),Print02());
	cout << endl;

	//搬运时，对_func赋予功能——打印输出
	transform(vS.begin(),vS.end(),vT.begin(),Print02());
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}

注意事项：

1、目标容器需要提前开辟空间（resize），否则无法搬运！

2、第四个参数（_func），用于对数据进行一定的变换或输出，如果不变换或输出，直接return

3、第四个参数（_func），需要返回值，不可以是void

2、常用查找算法

2.1、find

功能描述：

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

函数原型：

• find(iterator beg, iterator end, value);
• // beg 开始迭代器
• // end 结束迭代器
• // value 查找的元素

示例：

//常用的查找算法 find
class Print01 {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

//1、查找内置数据类型
void test01() {
	int a[] = { 1,2,6,7,8,3,4,5,9 };
	vector<int> v(a,a+(sizeof(a)/sizeof(a[0])));
	for_each(v.begin(),v.end(),Print01());
	cout << endl;

	vector<int>::iterator it = find(v.begin(),v.end(),10);
	if (it == v.end()) {
		cout << "内置数据类型 未找到" << endl;
	}
	else {
		cout << "内置数据类型 找到了 : " <<*it<< endl;
	}
	
}

//2、查找自定义数据类型
class Person {
public:
	//初始化列表，构造函数
	Person(string name, int age) :m_name(name), m_age(age) {}

	//重载 == ，让底层find知道怎么去比较
	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;
};

class Print02 {
public:
	void operator()(Person p) {
		cout << "姓名：" << p.m_name << " 年龄：" << p.m_age << endl;
	}
};


void test02() {
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);

	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	for_each(vp.begin(), vp.end(), Print02());
	
	Person pp("aaa",10);

	vector<Person>::iterator it1 =  find(vp.begin(),vp.end(),pp);
	if (it1 == vp.end()) {
		cout << "自定义数据类型 未找到" << endl;
	}
	else {
		cout << "自定义数据类型 找到了 : " << endl;
		cout << "姓名：" << it1->m_name << " 年龄：" << it1->m_age << endl;
	}

}


int main() {
	test01();
	cout << endl;
	test02();
	system("pause");
	return 0;
}

注意事项：

1、查找自定义数据类型时，需要重载==，让底层find知道如何去比较数据是否相等

2、利用find可以在容器中找指定的元素，返回值是迭代器

2.2、find_if

功能描述：

• 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

函数原型：

• find_if(iterator beg, iterator end, _Pred);

// beg 开始迭代器

// end 结束迭代器

// _Pred 函数或者谓词（返回bool类型的仿函数）

示例：

//常用的查找算法 find_if
class Print01 {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

class greater5 {
public:
	bool operator()(int val) {
		return val > 5;
	}
};

//1、查找内置数据类型
void test01() {
	int a[] = { 1,2,6,7,8,3,4,5,9 };
	vector<int> v(a, a + (sizeof(a) / sizeof(a[0])));
	for_each(v.begin(), v.end(), Print01());
	cout << endl;

	vector<int>::iterator it = find_if(v.begin(), v.end(), greater5());
	if (it == v.end()) {
		cout << "内置数据类型 未找到" << endl;
	}
	else {
		cout << "内置数据类型 找到了 : " << *it << endl;
	}

}

//2、查找自定义数据类型
class Person {
public:
	//初始化列表，构造函数
	Person(string name, int age) :m_name(name), m_age(age) {}

	string m_name;
	int m_age;
};

class Print02 {
public:
	void operator()(Person p) {
		cout << "姓名：" << p.m_name << " 年龄：" << p.m_age << endl;
	}
};

class greater20 {
public:
	bool operator()(Person p) {
		return p.m_age > 20;
	}
};

void test02() {
	vector<Person> vp;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);

	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	for_each(vp.begin(), vp.end(), Print02());

	vector<Person>::iterator it1 = find_if(vp.begin(), vp.end(), greater20());
	if (it1 == vp.end()) {
		cout << "自定义数据类型 未找到" << endl;
	}
	else {
		cout << "自定义数据类型 找到了 : " << endl;
		cout << "姓名：" << it1->m_name << " 年龄：" << it1->m_age << endl;
	}

}

int main() {
	test01();
	cout << endl;
	test02();
	system("pause");
	return 0;
}

2.3、adjacent_find

功能描述：

• 查找相邻重复元素,返回相邻元素的第一个位置的迭代器

函数原型：

• adjacent_find(iterator beg, iterator end);

// beg 开始迭代器

// end 结束迭代器

示例：

//常用查找算法 adjacent_find
class printVector {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(10);
	v.push_back(10);

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

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

}

int main() {
	test01();
	system("pause");
}

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

2.4、binary_search

功能描述：

• 二分查找法，查找指定的元素，查到 返回true 否则false

函数原型：

• bool binary_search(iterator beg, iterator end, value);

// beg 开始迭代器

// end 结束迭代器

// value 查找的元素

示例：

//常用的查找算法 binary_search
void test01() {
	vector<int> v;
	for (int i = 0; i < 10;i++) {
		v.push_back(i);
	}
	
	for (vector<int>::iterator it = v.begin(); it != v.end();it++) {
		cout << *it << " ";
	}
	cout << endl;

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

}
int main(){
	test01();
	system("pause");
}

注意事项：

1、二分查找， 仅在有序序列中可用，如果是无序序列，结果未知

2、二分查找法的查找效率很高

2.5、count

功能描述：

• 统计元素出现次数

函数原型：

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

示例：

//常用查找算法 count（统计）
//1、内置数据类型
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);

	for (int i = 0; i < v.size();i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	int ret = count(v.begin(),v.end(),10);
	cout << "自定义数据类型—10 的个数：" << ret << endl;

}

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


	string m_name;
	int m_age;
};

void test02() {
	vector<Person> vp;
	
	Person p1("刘备",30);
	Person p2("关羽",30);
	Person p3("张飞",30);
	Person p4("小乔",20);
	Person p5("周瑜",40);

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

	Person p9("诸葛",30);
	vector<Person>::iterator it = vp.begin();
	for (int i = 0; i < vp.size();i++) {
		cout << "姓名：" << it->m_name << " 年龄：" << it->m_age << endl;
		it++;
	}

	int ret1 = count(vp.begin(),vp.end(),p9);
	cout << "和诸葛年龄相同的人个数：" << ret1 << endl;

}


int main() {
	test01();
	cout << endl;
	test02();
	system("pause");
}

注意事项：对于统计自定义数据类型的时候，需要配合重载operator==

2.6、count_if

功能描述：

• 按条件统计元素出现次数

函数原型：

• count_if(iterator beg, iterator end, _Pred);

// beg 开始迭代器

// end 结束迭代器

// _Pred 谓词

示例：

//常用查找算法 count_if（条件统计）
class greater5 {
public:
	bool operator()(int val) {
		return val > 10;
	}
};

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

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	int ret = count_if(v.begin(), v.end(),greater5());
	cout << "内置数据类型—大于5的个数：" << ret << 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()(const Person& p) {
		return p.m_age > 20;
	}
};

void test02() {
	vector<Person> vp;

	Person p1("刘备", 30);
	Person p2("关羽", 30);
	Person p3("张飞", 30);
	Person p4("小乔", 20);
	Person p5("周瑜", 40);

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

	vector<Person>::iterator it = vp.begin();
	for (int i = 0; i < vp.size(); i++) {
		cout << "姓名：" << it->m_name << " 年龄：" << it->m_age << endl;
		it++;
	}

	int ret1 = count_if(vp.begin(), vp.end(), greater20());
	cout << "自定义数据类型—年龄大于20：" << ret1 << endl;

}


int main() {
	test01();
	cout << endl;
	test02();
	system("pause");
}

3、常用排序算法

3.1、sort

功能描述：

• 对容器内元素进行排序

函数原型：

• sort(iterator beg, iterator end, _Pred);

// beg 开始迭代器

// end 结束迭代器

// _Pred 谓词

示例：

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

class myCompera {
public:
	bool operator()(int val1,int val2) {
		return val1 > val2;
	}
};


void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(50);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	for_each(v.begin(),v.end(), print01);
	cout << endl;

	//1、默认升序
	sort(v.begin(),v.end());
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	//2、使用内置函数对象，改变规则为降序
	sort(v.begin(),v.end(),greater<int>());
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	//3、自定义谓词，改变排序规则
	sort(v.begin(), v.end(),myCompera());
	for_each(v.begin(), v.end(), print01);
	cout << endl;

}


int main() {
	test01();
	system("pause");
	return 0;
}

3.2、random_shuffle

功能描述：

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

函数原型：

• random_shuffle(iterator beg, iterator end);

// beg 开始迭代器

// end 结束迭代器

示例：

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

class myCompera {
public:
	bool operator()(int val1, int val2) {
		return val1 > val2;
	}

};

void test01() {

	//随机数的种子
	srand((unsigned int)time(NULL));
	vector<int> v;
	for (int i = 0; i < 10;i++) {
		v.push_back(i);
	}

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

	//洗牌，打乱顺序
	random_shuffle(v.begin(),v.end());
	for_each(v.begin(), v.end(), print01);
	cout << endl;

}

int main() {
	test01();
	system("pause");
	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 目标容器开始迭代器

示例：

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

void test01() {
	//1、准备两个原容器
	vector<int> v1;
	vector<int> v2;

	for (int i = 10; i > 0; i--) {
		v1.push_back(i);
		v2.push_back(i-1);
	}
	for_each(v1.begin(),v1.end(),print01);
	cout << endl;
	for_each(v2.begin(), v2.end(), print01);
	cout << endl;
	
	//2、准备一个目标容器
	vector<int> vt;
	//3、提前分配空间，否则无法执行
	vt.resize(v1.size() + v2.size());

	//5、默认升序，可设置为，降序
	//注意，两个原容器的排序规则必须和merge的排序规则一致，否则无法执行
	merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vt.begin(),greater<int>());
	for_each(vt.begin(), vt.end(), print01);
	cout << endl;

}

int main() {
	test01();
	system("pause");
}

注意事项：

1、 两个容器必须是有序的

2、两个原容器的排序规则必须和merge的排序规则一致，否则无法执行（都是less<T>，或者greater<T>）

3.4、reverse

功能描述：

• 将容器内元素进行反转

函数原型：

• reverse(iterator beg, iterator end);

// beg 开始迭代器

// end 结束迭代器

示例：

//常用排序算法 reverse
void test01() {
	vector<char> v;
	v.push_back('a');
	v.push_back('b');
	v.push_back('c');
	v.push_back('d');
	v.push_back('e');

	cout << "反转前：" << endl;
	for (int i = 0; i < v.size();i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	//反转
	reverse(v.begin(),v.end());
	cout << "反转后：" << endl;
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

}

int main() {
	test01();
	system("pause");
}

4、常用拷贝和替换算法

4.1、copy

功能描述：

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

函数原型：

• copy(iterator beg, iterator end, iterator dest);

// beg 开始迭代器

// end 结束迭代器

// dest 目标起始迭代器

示例：

//常用的拷贝算法 copy
void myPrint(int val) {
	cout << val << " ";
}
void test01() {
	vector<int> v;
	for (int i = 0; i < 5;i++) {
		v.push_back(i);
	}

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

	vector<int> v2;
	v2.push_back(6);
	v2.push_back(7);
	v2.resize(v.size() + 2);

	//拷贝
	copy(v.begin(), v.end(),v2.begin()+2);
	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}

注意事项：

1、拷贝前，目标容器需要提前分配好空间

2、利用copy，可以实现拼接

4.2、replace

功能描述：

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

函数原型：

• replace(iterator beg, iterator end, oldvalue, newvalue);

// beg 开始迭代器

// end 结束迭代器

// oldvalue 旧元素

// newvalue 新元素

示例:

//常用的替换算法 replace
class myPrint {
public:
	void operator()(int val){
		cout << val << " ";
	}
};

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	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();
	system("pause");
	return 0;
}

4.3、replace_if

功能描述:

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

函数原型：

• replace_if(iterator beg, iterator end, _pred, newvalue);

// beg 开始迭代器

// end 结束迭代器

// _pred 谓词

// newvalue 替换的新元素

示例：

////常用的替换算法 replace_if
class myPrint {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

class greater10 {
public:
	bool operator()(int val) {
		return val > 10;
	}
};

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(10);
	v.push_back(20);
	v.push_back(40);
	v.push_back(10);

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

	//将大于10的，替换为 666
	replace_if(v.begin(), v.end(), greater10(), 666);

	cout << "替换后" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}
class myPrint {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

class greater10 {
public:
	bool operator()(int val) {
		return val > 10;
	}
};

void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(10);
	v.push_back(20);
	v.push_back(40);
	v.push_back(10);

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

	//将大于10的，替换为 666
	replace_if(v.begin(), v.end(), greater10(), 666);

	cout << "替换后" << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}

4.4、swap

功能描述：

• 互换两个容器的元素

函数原型：

• swap(container c1, container c2);

// c1 容器1

// c2 容器2

示例：

//常用的替换算法 swap
class myPrint {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};


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

	cout << "交换前：" << endl;
	cout << "v的地址：" << &v[0] << endl;
	for_each(v.begin(),v.end(),myPrint());
	cout << endl;
	cout << "v1的地址：" << &v1[0] << endl;
	for_each(v1.begin(),v1.end(),myPrint());
	cout << endl;

	cout << "交换后：" << endl;

	//实现v和v1的交换
	swap(v,v1);

	cout << "v的地址：" << &v[0] << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
	cout << "v1的地址：" << &v1[0] << endl;
	for_each(v1.begin(), v1.end(), myPrint());
	cout << endl;


}

int main() {
	test01();
	system("pause");
	return 0;
}

注意事项：

1、swap交换时，发生的是地址交换

2、swap交换时，两个容器需要同种数据类型

5、常用算术生成算法

5.1、accumulate

功能描述：

• 计算区间内 元素累计总和，并将其返回

函数原型：

• accumulate(iterator beg, iterator end, value);

// beg 开始迭代器

// end 结束迭代器

// value 起始值

示例：

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

	int sum = accumulate(v.begin(),v.end(),0);
	cout << "vector容器元素之和：" << sum << endl;
}

int main() {
	test01();
	system("pause");
	return 0;
}

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

5.2、fill

功能描述：

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

函数原型：

• fill(iterator beg, iterator end, value);

// beg 开始迭代器

// end 结束迭代器

// value 填充的值

示例：

//常用的算术生成算法 fill
void myPrint(int val) {
	cout << val << " ";
}

void test01() {
	vector<int> v;
	v.resize(10);
	for_each(v.begin(),v.end(),myPrint);
	cout << endl;

	//重新填充为 100
	fill(v.begin(),v.end(),100);
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}

6、常用集合算法

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<vector>
#include<numeric>
#include<algorithm>
//常用的集合算法 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+1);
		v2.push_back(i+6);
	}

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

	vector<int> vt;
	//需要分配空间，空间大小为两个集合的最小值
	vt.resize(min(v1.size(),v2.size()));

	//返回值是交集的最后一个元素迭代器
	vector<int>::iterator itEnd =  
		set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),vt.begin());
	//1、下界迭代器为：v.end()
	for_each(vt.begin(),vt.end(),myPrint);
	cout << endl;
	//2、下界迭代器为：itEnd
	for_each(vt.begin(), itEnd, myPrint);
	cout << endl;

}

int main() {
	test01();
	system("pause");
	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 目标容器开始迭代器

示例：

//常用的集合算法 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 + 1);
		v2.push_back(i + 6);
	}

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

	vector<int> vt;
	//需要分配空间，空间大小为两个集合大小之和
	vt.resize(v1.size()+v2.size());

	//返回值是并集的最后一个元素迭代器
	vector<int>::iterator itEnd =
		set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vt.begin());
	//1、下界迭代器为：v.end()
	for_each(vt.begin(), vt.end(), myPrint);
	cout << endl;
	//2、下界迭代器为：itEnd
	for_each(vt.begin(), itEnd, myPrint);
	cout << endl;

}

int main() {
	test01();
	system("pause");
	return 0;
}

注意事项：

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

6.3、set_difference

功能描述：

• 求两个集合的差集

函数原型：

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

//beg1 容器1开始迭代器

// end1 容器1结束迭代器

// beg2 容器2开始迭代器

// end2 容器2结束迭代器

// dest 目标容器开始迭代器

示例：

//常用的集合算法 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 + 1);
		v2.push_back(i + 6);
	}

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

	vector<int> vt;
	//需要分配空间，空间大小为两个集合的最大值
	vt.resize(max(v1.size(),v2.size()));

	// 1、v1 和 v2 的差集 
	//返回值是并集的最后一个元素迭代器
	vector<int>::iterator itEnd =
		set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vt.begin());
	cout << endl;

	//下界迭代器为：itEnd
	cout << "v1 和 v2 的差集:" << endl;
	for_each(vt.begin(), itEnd, myPrint);
	cout << endl;

	//1、 v2 和 v1 的差集 
	itEnd =set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vt.begin());
	cout << endl;

	//下界迭代器为：itEnd
	cout << "v2 和 v1 的差集:" << endl;
	for_each(vt.begin(), itEnd, myPrint);
	cout << endl;
	
}

int main() {
	test01();
	system("pause");
	return 0;
}

注意事项：

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