C++学习笔记（二十二）

一、函数对象

1. 函数对象概念

概念：

• 重载函数调用操作符的类，其对象常称为函数对象
• 函数对象使用重载的 () 时，行为类似函数调用，也叫仿函数

本质：

函数对象(仿函数)是一个类，不是一个函数

2. 函数对象使用

特点：

• 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
• 函数对象超出普通函数的概念，函数对象可以有自己的状态
• 函数对象可以作为参数传递

1）函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值

#include <iostream>

using namespace std;

class MyAdd
{
public:
	int operator()(int num1, int num2)
	{
		return num1 + num2;
	}
};

void test01()
{
	MyAdd myAdd;
	cout << "10 + 20 = " << myAdd(10, 20) << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

2）函数对象超出普通函数的概念，函数对象可以有自己的状态

#include <iostream>

using namespace std;

class MyPrint
{
public:
	int count;
	MyPrint()
	{
		this->count = 0;
	}
	void operator()(string str)
	{
		cout << str << endl;
		this->count++;
	}
};

void test01()
{
	MyPrint myPrint;
	myPrint("hello world!");
	myPrint("hello world!");
	myPrint("hello world!");
	myPrint("hello world!");
	myPrint("hello world!");
	cout << "myPrint的调用次数为:" << myPrint.count << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

3）函数对象可以作为参数传递

#include <iostream>

using namespace std;

class MyPrint
{
public:
	int count;
	MyPrint()
	{
		this->count = 0;
	}
	void operator()(string str)
	{
		cout << str << endl;
		this->count++;
	}
};

void doPrint(MyPrint& mp, string str)
{
	mp(str);
}

void test01()
{
	MyPrint myPrint;
	doPrint(myPrint, "hello C++");
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

二、谓词

1. 谓词概念

概念：

• 返回bool类型的仿函数称为谓词
• 如果operator()接收一个参数，那么叫做一元谓词
• 如果operator()接收两个参数，那么叫做二元谓词

2. 一元谓词

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class FindGreaterFive
{
public:
	bool operator()(int num)
	{
		return num > 5;
	}
};

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

	// 查找容器中有没有大于5的数字
	vector<int>::iterator it = find_if(v.begin(), v.end(), FindGreaterFive());
	
	if (it == v.end())
	{
		cout << "未找到..." << endl;
	}
	else
	{
		cout << "找到了大于5的数字:" << *it << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

3. 二元谓词

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MyCompare
{
public:
	bool operator()(int num1,int num2)
	{
		return num1 > num2;
	}
};

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

	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	// 使用函数对象改变算法策略,变为排序规则为从大到小
	sort(v.begin(), v.end(), MyCompare());
	cout << "————————" << endl;
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

三、内建函数对象

1. 内建函数对象意义

概念：

• STL内建了一些函数对象

分类：

• 算术仿函数
• 关系仿函数
• 逻辑仿函数

用法：

• 这些仿函数所产生的的对象，用法和一般函数相同
• 使用内建函数对象，需要引入头文件 #include <functional>

2. 算术仿函数

功能描述：

• 实现四则运算
• 其中negate是一元运算，其他都是二元运算

仿函数原型：

• template<class T> T plus<T>? ? ? ? // 加法仿函数
• template<class T> T minus<T>? ? ? ? // 减法仿函数
• template<class T> T multiplies<T>? ? ? ? // 乘法仿函数
• template<class T> T divides<T>? ? ? ? // 除法仿函数
• template<class T> T modulus<T>? ? ? ? // 取模仿函数
• template<class T> T negate<T>? ? ? ? // 取反仿函数

#include <iostream>
#include <functional>

using namespace std;

void test01()
{
	// 取反
	negate<int>n;
	cout << n(50) << endl;

	// 加法
	plus<int>p;
	cout << p(10, 20) << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

3. 关系仿函数

功能描述：

• 实现关系对比

仿函数原型：

• template<class T> bool equal_to<T>? ? ? ? // 等于
• template<class T> bool not_equal_to<T>? ? ? ? // 不等于
• template<class T> bool?greater<T>? ? ? ? // 大于
• template<class T> bool?greater_equal<T>? ? ? ? // 大于等于
• template<class T> bool?less<T>? ? ? ? // 小于
• template<class T> bool?less_equal<T>? ? ? ? // 小于等于

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>

using namespace std;

class MyCompare
{
public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};

void test01()
{
	vector<int>v;
	v.push_back(40);
	v.push_back(20);
	v.push_back(50);
	v.push_back(10);
	v.push_back(30);
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	// 降序
	sort(v.begin(), v.end(),MyCompare());
	sort(v.begin(), v.end(), greater<int>());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

4. 逻辑仿函数

功能描述：

• 实现逻辑运算

仿函数原型：

• template<class T> bool logical_and<T>? ? ? ? // 与
• template<class T> bool logical_or<T>? ? ? ? // 或
• template<class T> bool?logical_not<T>? ? ? ? // 非

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>

using namespace std;

void test01()
{
	vector<bool>v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

	for (vector<bool>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

	// 利用逻辑非 将容器v搬运到容器v2中,并执行取反操作
	vector<bool>v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(), v2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = v2.begin(); it != v2.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

四、常用算法

概述：

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

1. 常用的遍历算法

for_each? ? ? ? // 遍历容器

transform? ? ? ? // 搬运容器到另一个容器中

函数原型：

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

? ? ? ? // 遍历算法 遍历容器元素

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // _func函数或者函数对象

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 普通函数
void MyPrint01(int num)
{
	cout << num << " ";
}

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

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

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

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

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

• 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 num)
	{
		return num + 100;
	}
};

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

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(int argc, char* argv[])
{
	test01();
	return 0;
}

2. 常用的查找算法

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

函数原型：

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

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

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value查找的元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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 test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it = find(v.begin(), v.end(), 4);
	if (it != v.end())
	{
		cout << "找到该元素:" << *it << endl;
	}
	else
	{
		cout << "未找到该元素..." << endl;
	}
}

// 查找自定义数据类型
void test02()
{
	vector<Person>v;
	// 创建数据
	Person p1("刘备", 50);
	Person p2("关羽", 40);
	Person p3("张飞", 30);
	Person p4("赵云", 20);

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

	Person p("赵云", 20);
	vector<Person>::iterator it = find(v.begin(), v.end(), p);
	if (it != v.end())
	{
		cout << "查找到该元素..." << endl;
		cout << "姓名:" << (*it).m_Name << " " << "年龄:" << it->m_Age << endl;
	}
	else
	{
		cout << "未找到该元素..." << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	test02();
	return 0;
}

函数原型：

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

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

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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

class GreaterFive
{
public:
	bool operator()(int num)
	{
		return num > 5;
	}
};

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

// 查找内置数据类型
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 << "找到该元素:" << *it << endl;
	}
	else
	{
		cout << "未找到该元素..." << endl;
	}
}

// 查找自定义数据类型
void test02()
{
	vector<Person>v;
	// 创建数据
	Person p1("刘备", 50);
	Person p2("关羽", 40);
	Person p3("张飞", 30);
	Person p4("赵云", 20);

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

	Person p("赵云", 20);
	vector<Person>::iterator it = find_if(v.begin(), v.end(), GreaterTwenty());
	if (it != v.end())
	{
		cout << "查找到该元素..." << endl;
		cout << "姓名:" << (*it).m_Name << " " << "年龄:" << it->m_Age << endl;
	}
	else
	{
		cout << "未找到该元素..." << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	test02();
	return 0;
}

函数原型：

• adjacent_find(iterator beg, iterator end);

? ? ? ? // 查找相邻重复元素，返回相邻元素的第一个位置的迭代器

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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 << "找到相邻重复元素:" << *pos << endl;
	}
	else
	{
		cout << "未找到相邻重复..." << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

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

函数原型：

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

? ? ? ? // 查找指定元素，查到返回true 否则返回false

? ? ? ? // 注意：在无序序列中不可用

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value查找的元素

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	// 查找容器中是否有9
	// 注意:容器必须是有序的序列
	bool result = binary_search(v.begin(), v.end(), 9);

	if (result == true)
	{
		cout << "找到该元素..." <<  endl;
	}
	else
	{
		cout << "未找到该元素..." << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

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

函数原型：

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

? ? ? ? // 统计元素出现次数

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value统计的元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 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 result = count(v.begin(), v.end(), 40);

	cout << "40出现的次数为:" << result << 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("刘备", 50);
	Person p2("关羽", 50);
	Person p3("张飞", 50);
	Person p4("赵云", 35);
	Person p5("刘备", 45);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	Person p("诸葛亮", 35);

	// 统计和诸葛亮年龄相同的人数
	int result = count(v.begin(), v.end(), p);
	cout << "和诸葛亮年龄相同的人有" << result << "个" << endl;
}

int main(int argc, char* argv[])
{
	test01();
	test02();
	return 0;
}

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

函数原型：

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

? ? ? ? // 按条件统计元素出现次数

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // _Pred谓词

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 1.统计内置数据类型
class GreaterFive
{
public:
	bool operator()(int num)
	{
		return num > 5;
	}
};

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

	int result = count_if(v.begin(), v.end(), GreaterFive());

	cout << "大于5的数有" << result << "个" << 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 LessEqual45
{
public:
	bool operator()(Person& p)
	{
		return p.m_Age <= 45;
	}
};

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

	// 统计年龄小于等于45的人数
	int result = count_if(v.begin(), v.end(), LessEqual45());
	cout << "年龄小于等于45的人数有" << result << "个" << endl;
}

int main(int argc, char* argv[])
{
	test01();
	test02();
	return 0;
}

3. 常用的排序算法

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

函数原型：

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

? ? ? ? // 排序 默认按从小到大排序

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value查找的元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

class MyPrint
{
public:
	void operator()(int num)
	{
		cout << num << " ";
	}
};
void test01()
{
	vector<int>v;
	v.push_back(4);
	v.push_back(2);
	v.push_back(5);
	v.push_back(1);
	v.push_back(3);

	// 利用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(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

• random_shuffle(iterator beg, iterator end);

? ? ? ? // 指定范围内的元素随机调整次序

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <ctime>

using namespace std;

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

void test01()
{
	srand((unsigned int)time(NULL));
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	cout << "——洗牌前——" << endl;
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;

	cout << "——洗牌前——" << endl;
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

• merge(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>
#include <functional>
#include <ctime>

using namespace std;

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

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

	cout << "合并前:" << endl;
	cout << "v1:";
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
	cout << "v2:";
	for_each(v2.begin(), v2.end(), MyPrint());
	cout << endl;

	// 目标容器
	vector<int>vTarget;
	// 提前给目标容器分配空间
	vTarget.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	cout << "合并后:" << endl;
	cout << "vTarget:";
	for_each(vTarget.begin(), vTarget.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

总结：需要给目标容器提前分配空间，两个序列必须同为升序或者降序

函数原型：

• reverse(iterator beg, iterator end);

? ? ? ? // 反转指定范围的元素

? ? ? ? // beg 开始迭代器

? ? ? ? // end 结束迭代器

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <ctime>

using namespace std;

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

void test01()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	cout << "-------反转前-------" << endl;
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;

	cout << "-------反转后-------" << endl;
	reverse(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

4. 常用的拷贝和替换算法

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

函数原型：

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

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

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

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

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(int argc, char* argv[])
{
	test01();
	return 0;
}

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

函数原型：

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

? ? ? ? // 将区间内旧元素替换为新元素

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // oldvalue旧元素

? ? ? ? // newvalue新元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

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

void test01()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(2);
	v1.push_back(1);

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

	cout << "——替换后——" << endl;
	replace(v1.begin(), v1.end(), 3, 2);
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

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

? ? ? ? // 按条件替换元素，满足条件的替换为指定元素

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // _Pred谓词

? ? ? ? // newvalue新元素

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

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

class MyReplace
{
public:
	bool operator()(int num)
	{
		return num >= 2 && num < 4;
	}
};

void test01()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(3);
	v1.push_back(2);
	v1.push_back(1);

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

	cout << "——替换后——" << endl;
	replace_if(v1.begin(), v1.end(), MyReplace(), 2);
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

• swap(container C1, container C2);

? ? ? ? // 互换两个容器的元素

? ? ? ? // C1 容器1

? ? ? ? // C2 容器2

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

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

void test01()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);
	v1.push_back(1);

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

	cout << "———互换前———" << endl;
	cout << "v1:";
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
	cout << "v2:";
	for_each(v2.begin(), v2.end(), MyPrint());
	cout << endl;

	cout << "———互换后———" << endl;
	swap(v1,v2);
	cout << "v1:";
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
	cout << "v2:";
	for_each(v2.begin(), v2.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

总结：swap交换容器时，交换的容器必须是同种类型

5. 常用的算术生成算法

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

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

函数原型：

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

? ? ? ? // 计算容器元素累计总和

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value起始累加值

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;

void test01()
{
	vector<int>v1;
	for (int i = 0; i <= 100; i++)
	{
		v1.push_back(i);
	}
	// 参数3 起始累加值
	int num = accumulate(v1.begin(), v1.end(), 99);

	cout << "total = " << num << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

函数原型：

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

? ? ? ? // 向容器中填充元素

? ? ? ? // beg开始迭代器

? ? ? ? // end结束迭代器

? ? ? ? // value填充值

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>

using namespace std;

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

void test01()
{
	vector<int>v1;
	v1.resize(10);
	
	fill(v1.begin(), v1.end(), 100);
	
	for_each(v1.begin(), v1.end(), MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

6. 常用的集合算法

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

函数原型：

• 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>
#include <functional>
#include <numeric>

using namespace std;

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

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;
	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(int argc, char* argv[])
{
	test01();
	return 0;
}

总结：

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

函数原型：

• 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>
#include <functional>
#include <numeric>

using namespace std;

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

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;
	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(int argc, char* argv[])
{
	test01();
	return 0;
}

总结：

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

函数原型：

• 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>
#include <functional>
#include <numeric>

using namespace std;

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

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;
	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());
	for_each(vTarget.begin(), itEnd, MyPrint());
	cout << endl;

	cout << "v2和v1的差集为:" << endl;
	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, MyPrint());
	cout << endl;
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

总结：

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