C++进阶-STL 常用算法列举

STL 常用算法列举

概述
- 常用遍历算法
- - `for_each` 遍历容器
  - `transfrom` 搬运容器到另一个容器中
- 常用查找函数
- - `find` 查找元素
  - `find_if` 按条件查找元素
  - `adjacent_find` 查找相邻重复元素
  - `binary_search` 二分查找法
  - `count` 统计元素个数
  - `count_if` 按条件统计元素个数
- 常用排序算法
- - `sort` 对元素内内容进行排序
  - `random_shuffle` 洗牌指定范围内的元素随机调整次序
  - `merge` 容器元素合并，并存储到另一个容器中
  - `reverse` 反转指定范围的元素
- 常用拷贝和替换算法
- - `copy` 容器内指定范围的元素拷贝到另一个容器中
  - `replace` 将容器内指定范围的旧元素修改为新元素
  - `replace_if` 容器内指定范围满足条件的元素替换为新元素
  - `swap` 互换两个容器中的元素
- 常用算数生成算法
- - `accumulate` 计算容器元素累计总和
  - `fill` 向容器中填充元素
- 常用集合算法
- - `set_intersection` 求两个容器的交集
  - `set_union` 求两个容器的并集
  - `set_difference` 求两个容器的差集

概述

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

常用遍历算法

`for_each` 遍历容器

函数原型
for_each(iterator beg, iterator end, _func);
- 遍历算法，实现遍历容器元素
- beg开始迭代器
- end结束迭代器
- _func函数或者函数对象

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

void print(int val)
{
	std::cout << val << " ";
}

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

int main()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), print);
	std::cout << std::endl;
	for_each(v.begin(), v.end(), Print());
}

运行结果

`transfrom` 搬运容器到另一个容器中

功能描述：搬运容器到另一个容器中
函数原型：
transfrom(iterator beg1, iterator end1, iterator beg2, _func);
- beg1 源容器开始迭代器
- end1 源容器结束迭代器
- beg2 目标容器开始迭代器
- _func 函数或者函数对象

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

class Transfrom
{
public:
	int operator()(int val)
	{
		return val * 3;
	}
};

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

int main()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	std::cout << "调用transform前的原verctor:" << std::endl;
	for_each(v.begin(), v.end(), Print());
	std::cout << std::endl;

	vector<int> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(), v2.begin(), Transfrom());
	std::cout << "调用transform后的原verctor2:" << std::endl;
	for_each(v2.begin(), v2.end(), Print());
	std::cout << std::endl;
}

执行结果

常用查找函数

`find` 查找元素

功能描述：查找指定的元素，返回找到指定元素的迭代器，找不到返回结束迭代器 end()
函数原型：
find(iterator beg, iterator end, value);
- 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素

案例一：查找内置数据类型

vector<int> vt;
for (int i = 0; i < 10; i++)
{
	vt.push_back(i);
}
vector<int>::iterator it = find(vt.begin(), vt.end(), 3);
if (it == vt.end())
{
	std::cout << "not find!" << std::endl;
}
else
{
	std::cout << "find result" << std::endl;
}

案例二：查找自定义数据类型

class Demo
{
public:
	string name;
public:
	Demo(string name)
	{
		this->name = name;
	}
	bool operator== (const Demo& d1)
	{
		return this->name == d1.name;
	}
};

void findCustomDemo()
{
	vector<Demo> vt;
	for (int i = 0; i < 10; i++)
	{
		Demo demo(i+"");
		vt.push_back(demo);
	}
	Demo demo2(1 + "");
	vector<Demo>::iterator it = find(vt.begin(), vt.end(), demo2);
	if (it == vt.end())
	{
		std::cout << "not find!" << std::endl;
	}
	else
	{
		std::cout << "find result" << std::endl;
	}
}

查找自定义数据类型需要重载操作符 ==

`find_if` 按条件查找元素

功能描述：按照条件查找元素
函数原型：
find_if(iterator beg, iterator end, _Pred);
- 按照值查找元素，找到返回指定位置迭代器，找不到返回迭代器结束位置
- beg: 开始迭代器
- end: 结束迭代器
- _Pred函数或者谓词（返回bool类型的仿函数）

案例一：查找内置数据类型

class FindFive
{
public:
	bool operator()(int val)
	{
		return val == 5;
	}
};

void findDemo()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	vector<int>::iterator it = find_if(vt.begin(), vt.end(), FindFive());
	if (it == vt.end())
	{
		std::cout << "not find!" << std::endl;
	}
	else
	{
		std::cout << "find result" << std::endl;
	}
}

案例二：查找自定义数据类型

class Demo
{
public:
	string name;
public:
	Demo(string name)
	{
		this->name = name;
	}
};

class Find
{
public:
	bool operator()(Demo d)
	{
		return d.name == "1";
	}
};


void findCustomDemo()
{
	vector<Demo> vt;
	for (int i = 0; i < 10; i++)
	{
		Demo demo(i+"");
		vt.push_back(demo);
	}
	Demo demo2(1 + "");
	vector<Demo>::iterator it = find_if(vt.begin(), vt.end(), Find());
	if (it == vt.end())
	{
		std::cout << "not find!" << std::endl;
	}
	else
	{
		std::cout << "find result" << std::endl;
	}
}

`adjacent_find` 查找相邻重复元素

功能描述：查找相邻重复元素
函数原型：
iterator adjacent_find(iterator beg, iterator end);
- 查找相邻重复元素，返回相邻元素的第一个位置的迭代器
- beg 开始迭代器
- end 结束迭代器

int main()
{
	vector<int> vt;
	vt.push_back(1);
	vt.push_back(2);
	vt.push_back(3);
	vt.push_back(3);
	vt.push_back(1);
	vt.push_back(5);
	vector<int>::iterator it = adjacent_find(vt.begin(), vt.end());
	if (it == vt.end())
	{
		std::cout << "未找到相邻重复元素" << std::endl;
	}
	else
	{
		std::cout << "找到了相邻重复元素" << std::endl;
		for (; it != vt.end(); it++)
		{
			std::cout << *it << " ";
		}
		std::cout << std::endl;
	}
}

`binary_search` 二分查找法

功能描述：查找指定元素是否存在
函数原型：
bool binary_search(iterator beg, iterator end, value);
- 查找指定的元素，查找到返回true，否则false
- 注意：在无序序列中不可用
- beg: 开始迭代器
- end: 结束迭代器
- value: 查找的元素

int main()
{
	vector<int> vt;
	vt.push_back(1);
	vt.push_back(2);
	vt.push_back(3);
	vt.push_back(4);
	vt.push_back(5);
	vt.push_back(6);
	bool isFind = binary_search(vt.begin(), vt.end(), 3);
	if (!isFind)
	{
		std::cout << "未找到指定元素" << std::endl;
	}
	else
	{
		std::cout << "找到了指定元素" << std::endl;
	}
}

查找元素无序可能会查找不到值信息

`count` 统计元素个数

功能描述：统计元素个数
函数原型：
count(iterator beg, iterator end, value);
- 统计元素出现次数
- beg 开始迭代器
- end 结束迭代器
- value 统计的元素

int main()
{
	vector<int> vt;
	vt.push_back(1);
	vt.push_back(2);
	vt.push_back(3);
	vt.push_back(4);
	vt.push_back(5);
	vt.push_back(3);
	int num_count = count(vt.begin(), vt.end(), 3);
	std::cout << "元素3共有 " << num_count << " 个" << std::endl;
}

`count_if` 按条件统计元素个数

功能描述：统计元素个数
函数原型：
count_if(iterator beg, iterator end, _Pred);
- 按条件统计元素出现次数
- beg 开始迭代器
- end 结束迭代器
- Pred 谓词

class CountFive
{
public:
	bool operator()(int val)
	{
		return val == 5;
	}
};

int main()
{
	vector<int> vt;
	vt.push_back(1);
	vt.push_back(2);
	vt.push_back(3);
	vt.push_back(4);
	vt.push_back(5);
	vt.push_back(3);
	int num_count = count_if(vt.begin(), vt.end(), CountFive());
	std::cout << "元素5共有 " << num_count << " 个" << std::endl;
}

常用排序算法

`sort` 对元素内内容进行排序

功能描述：对元素内内容进行排序
函数原型：
sort(iterator beg, iterator end, _Pred);
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	srand((unsigned int)time(NULL));
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(rand() % 60 + 40);
	}
	std::cout << "排序前：" << std::endl;
	print(vt);
	sort(vt.begin(), vt.end());
	std::cout << "排序后：" << std::endl;
	print(vt);
	sort(vt.begin(), vt.end(), greater<>());
	std::cout << "降序排序后：" << std::endl;
	print(vt);
}

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

功能描述：洗牌指定范围内的元素随机调整次序
函数原型：
random_shuffle(iterator beg, iterator end);
- 指定范围内元素随机调整次序
- beg 开始迭代器
- end 结束迭代器

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	std::cout << "排序前：" << std::endl;
	print(vt);
	random_shuffle(vt.begin(), vt.end());
	std::cout << "打乱顺序后：" << std::endl;
	print(vt);
}

为了让每次打乱的顺序更加的真实，需要加入随机数种子：
srand((unsigned int)time(NULL));

`merge` 容器元素合并，并存储到另一个容器中

功能描述：容器元素合并，并存储到另一个容器中
函数原型：
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 容器元素合并，并存储到另一个容器中
- 注意：两个容器必须是有序的
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	srand((unsigned int)time(NULL));
	vector<int> vt;
	vector<int> vt2;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(rand() % 60 + 40);
		vt2.push_back(rand() % 60 + 40);
	}
	sort(vt.begin(), vt.end());
	sort(vt2.begin(), vt2.end());
	std::cout << "合并前：" << std::endl;
	print(vt);
	print(vt2);
	vector<int> vt3;
	vt3.resize(vt.size() + vt2.size());
	merge(vt.begin(), vt.end(), vt2.begin(), vt2.end(), vt3.begin());
	std::cout << "合并后：" << std::endl;
	print(vt3);
}

执行结果

`reverse` 反转指定范围的元素

功能描述：反转指定范围的元素
函数原型：
reverse(iterator beg, iterator end);
- 反转指定范围的元素
- beg 开始迭代器
- end 结束迭代器

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	srand((unsigned int)time(NULL));
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(rand() % 60 + 40);
	}
	sort(vt.begin(), vt.end());
	std::cout << "反转前：" << std::endl;
	print(vt);
	reverse(vt.begin(), vt.end());
	std::cout << "反转后：" << std::endl;
	print(vt);
}

运行结果

常用拷贝和替换算法

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

功能描述：容器内指定范围的元素拷贝到另一个容器中
函数原型：
copy(iterator beg, iterator end, iterator dest);
- beg 开始迭代器
- end 结束迭代器
- dest 目标起始迭代器

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	srand((unsigned int)time(NULL));
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(rand() % 60 + 40);
	}
	sort(vt.begin(), vt.end());
	std::cout << "copy前：" << std::endl;
	print(vt);
	vector<int> vt2;
	vt2.resize(vt.size());
	copy(vt.begin(), vt.end(), vt2.begin());
	std::cout << "copy后：" << std::endl;
	print(vt2);
}

`replace` 将容器内指定范围的旧元素修改为新元素

功能描述：将容器内指定范围的旧元素修改为新元素
函数原型：
replace(iterator beg, iterator end, oldvalue, newvalue);
- 将区间内就元素替换成新元素
- beg 开始迭代器
- end 结束迭代器
- oldvalue 旧元素
- newvalue 新元素

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	sort(vt.begin(), vt.end());
	std::cout << "替换元素前：" << std::endl;
	print(vt);
	//3替换为10
	replace(vt.begin(), vt.end(), 3, 10);
	std::cout << "替换元素后：" << std::endl;
	print(vt);
}

执行结果

`replace_if` 容器内指定范围满足条件的元素替换为新元素

功能描述：容器内指定范围满足条件的元素替换为新元素
函数原型：
replace_if(iterator beg, iterator end, _Pred, newvalue);
- 按条件替换元素，满足条件的替换成指定元素
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词
- newvalue 替换的新元素

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

class LessEqual3
{
public:
	bool operator()(int val)
	{
		return val <= 3;
	}
};

int main()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	sort(vt.begin(), vt.end());
	std::cout << "替换元素前：" << std::endl;
	print(vt);
	//小于等于3的元素替换为10
	replace_if(vt.begin(), vt.end(), LessEqual3(), 10);
	std::cout << "替换元素后：" << std::endl;
	print(vt);
}

执行结果

`swap` 互换两个容器中的元素

功能描述：互换两个容器中的元素
函数原型：
swap(container c1, container c2);
- 互换两个容器的元素
- c1 容器1
- c2 容器2

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	vector<int> vt;
	vector<int> vt2;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
		vt2.push_back(10 + i);
	}
	sort(vt.begin(), vt.end());
	std::cout << "交换容器元素前：" << std::endl;
	print(vt);
	print(vt2);
	swap(vt, vt2);
	std::cout << "交换容器元素后：" << std::endl;
	print(vt);
	print(vt2);
}

执行结果
两个交换的容器必须要同一种类型

常用算数生成算法

算数生成算法属于小型算法，使用时包含的头文件 #include <numeric>

`accumulate` 计算容器元素累计总和

功能描述：计算容器元素累计总和
函数原型：
accumulate(iterator beg, iterator end, value);
- 计算容器的元素总和
- beg 开始迭代器
- end 结束迭代器
- value 起始值

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	std::cout << "容器所有值信息：" << std::endl;
	print(vt);
	std::cout << "容器所有值之和等于：" << accumulate(vt.begin(), vt.end(), 0) << std::endl;
}

运行结果

`fill` 向容器中填充元素

功能描述：向容器中填充元素
函数原型：
fill(iterator beg, iterator end, value);
- 向容器中填充元素
- beg 开始迭代器
- end 结束迭代器
- value 填充的值

void print(const vector<int>& vt)
{
	for (vector<int>::const_iterator it = vt.begin(); it != vt.end(); it++)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main()
{
	vector<int> vt;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
	}
	std::cout << "容器所有值信息：" << std::endl;
	print(vt);
	fill(vt.begin(), vt.end(), 3);
	std::cout << "填充容器所有值为3后：" << std::endl;
	print(vt);
}

执行结果

常用集合算法

`set_intersection` 求两个容器的交集

功能描述：求两个容器的交集
函数原型：
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 求两个集合的交集
- 两个容器必须是有序的
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器


void Myprintf(int val)
{
	std::cout << val << " ";
}

int main()
{
	vector<int> vt;
	vector<int> vt2;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
		vt2.push_back(i+1);
	}
	std::cout << "容器所有值信息：" << std::endl;
	for_each(vt.begin(), vt.end(), Myprintf);
	std::cout << std::endl;
	for_each(vt2.begin(), vt2.end(), Myprintf);
	std::cout << std::endl;
	vector<int> vt3;
	vt3.resize(min(vt.size(), vt2.size()));
	vector<int>::iterator it_end = set_intersection(vt.begin(), vt.end(), vt2.begin(), vt2.end(), vt3.begin());
	std::cout << "两个容器的交集为：" << std::endl;
	for_each(vt3.begin(), it_end, Myprintf);
	std::cout << std::endl;
}

结果信息

`set_union` 求两个容器的并集

功能描述：求两个容器的并集
函数原型：
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 求两个集合的并集
- 两个容器必须是有序的
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器

void Myprintf(int val)
{
	std::cout << val << " ";
}

int main()
{
	vector<int> vt;
	vector<int> vt2;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
		vt2.push_back(i+1);
	}
	std::cout << "容器所有值信息：" << std::endl;
	for_each(vt.begin(), vt.end(), Myprintf);
	std::cout << std::endl;
	for_each(vt2.begin(), vt2.end(), Myprintf);
	std::cout << std::endl;
	vector<int> vt3;
	vt3.resize(vt.size() + vt2.size());
	vector<int>::iterator it_end = set_union(vt.begin(), vt.end(), vt2.begin(), vt2.end(), vt3.begin());
	std::cout << "两个容器的并集为：" << std::endl;
	for_each(vt3.begin(), it_end, Myprintf);
	std::cout << std::endl;
}

执行结果

`set_difference` 求两个容器的差集

功能描述：求两个容器的差集
函数原型：
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 求两个集合的差集
- 两个容器必须是有序的
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器

void Myprintf(int val)
{
	std::cout << val << " ";
}

int main()
{
	vector<int> vt;
	vector<int> vt2;
	for (int i = 0; i < 10; i++)
	{
		vt.push_back(i);
		vt2.push_back(i+1);
	}
	std::cout << "容器所有值信息：" << std::endl;
	for_each(vt.begin(), vt.end(), Myprintf);
	std::cout << std::endl;
	for_each(vt2.begin(), vt2.end(), Myprintf);
	std::cout << std::endl;
	vector<int> vt3;
	vt3.resize(max(vt.size(),vt2.size()));
	vector<int>::iterator it_end = set_difference(vt.begin(), vt.end(), vt2.begin(), vt2.end(), vt3.begin());
	std::cout << "两个容器的差集为：" << std::endl;
	for_each(vt3.begin(), it_end, Myprintf);
	std::cout << std::endl;
}