【万字总结篇】C++STL常用算法详解（错等年系列）

admin • 2021-11-30 20:33 • C/C++

写在前面

本小菜鸟是一名热爱编程的大二在校生，目前主要精力放在学习C++、数据结构和算法上。

我最近两个月才开始学算法(鬼知道我大一干嘛去了)，被算法折磨的死去活来(太难了吧…)，这两个月来在力扣刷了200多题，还是能感觉到一些进步的，继续保持，争取在年末刷到500题！这是我的力扣主页—>我的力扣主页

回到正题，目前C++这个专栏的博客我已经总结完了C++常用的容器、内置函数对象(仿函数)、还有此篇常用的内置算法，都是一些C++STL的内容，因为这部分内容不难，并且需要记忆的内容偏多(也就是需要多看多运用)，所以就先总结出来了。之后我还会总结一些C++基础知识和C++面向对象的内容，也会有一些C++项目实战分析总结。

欢迎小伙伴们关注我，私信和我交流讨论关于C/C++和算法的一些东西呀。知无不答！

以下是正文部分，若有笔误，还请大佬批评指出。

STL常用算法

C++STL中的内置算法主要在头文件<algorithm>、<functional>、<numeric>中

<algorithm>是所有STL头文件中最大的一个，也是包含算法最多，最常用的一个头文件，其中包含比较、交换、查找、遍历、复制、修改等算法
<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数
<functional>定义了一些模板类，用以声明函数对象(仿函数)

注意：本文除了最后的两个算术生成算法在头文件#include<numeric>中以外，其余算法都在头文件#include<algorithm>中

下面将详细介绍一些常用的内置算法，以及会用一些简单的实例帮助大家理解其如何使用。

最大值/最小值

我们先来看两个非常简单并且使用起来非常方便算法

max(a,b)返回a,b中较大的数
min(a,b) 返回a,b中较小的数

注意：

使用这两个函数时，不能使用与其同名的变量(max、min)，比如 max = max(a, b)、min = min(min, b)等。
这两个算法只能比较两个数的大小，如果想比较两个以上数的大小可以嵌套使用，比如求三个数中的最大值m = max(a, max(b, c))

示例：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int arr[10] = { 5,8,2,4,6,9,7,0,1,3 };
	int m1=arr[0];
	int m2 = arr[0];
	for (int i = 0; i < 10; ++i) {
		m1 = max(m1, arr[i]);
		m2 = min(m2, arr[i]);
	}
	cout << "最大值为: " << m1 
		 << "n最小值为: " << m2 << endl;
}

输出如下：

最大值为: 9
最小值为: 0

头文件基本就是例子中那几个，此后的例子中如果没有特殊的头文件需要包含，就省去这一部分了

常用遍历算法

for_each

功能： 遍历容器，进行某种自定义操作。
这个自定义操作就是自己写的一个函数，具体你想干啥自己决定。

函数原型：
for_each(iterator beg,iterator end,_func); 遍历容器

第一个参数beg可以传入容器的起始迭代器，也可以传入数组内第一个元素的地址
第二个参数end可以传入容器的结束迭代器，或者传入数组最后一个元素的下一个位置的地址
最后一个参数_func可以传入一个函数或者函数对象

有一点必须要强调一下，对于一个数组而言，数组内第一个元素的地址相当于起始迭代器，数组最后一个元素的下一个位置的地址相当于结束迭代器，之后的例子中传入容器迭代器的参数部分(beg,end)，有时也会传入数组的地址，不必惊讶，这就是这方面的运用。

transform

功能： 按照某种自定义规则搬运容器(或数组)内元素到另一个容器(或数组)中。

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

beg1传入原容器的起始迭代器，或数组的首地址
end1传入原容器的结束迭代器，或者数组最后一个元素的下一个位置的地址
beg2传入目标容器的起始迭代器，或者目标数组的首地址
_func传入搬运规则函数或函数对象

下面同过一个简单的例子，练习一下这两种遍历算法的使用：

void printArr(int val)//自定义操作：打印
{
	cout << val << " ";
}
int targetArr(int val)//搬运规则函数，在原数据基础上加100
{
	return val + 100;
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };//原数组
	int target[15];//目标数组,目标数组的长度必须不小于原数组
	transform(arr, arr + 10, target, targetArr);
	cout << "原数组打印：";
	for_each(arr, arr + 10, printArr);
	cout << "n目标数组打印：";
	for_each(target, target + 10, printArr);
}

输出如下：

原数组打印：0 1 2 3 4 5 6 7 8 9
目标数组打印：100 101 102 103 104 105 106 107 108 109

常用查找算法

简介：

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

find

功能： 按值查找元素

函数原型：

find(iterator beg,iterator end,value);

beg起始迭代器
end结束迭代器
value是要查找的元素，如果其是自定义数据类型，如类的对象、结构体类型的元素,查找时需要重载==运算符
找到返回指定位置的迭代器，找不到返回结束迭代器

下面通过两个例子练习find的使用

对于内置数据类型的使用：

#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);
	}
	auto it = find(v.begin(), v.end(), 5);//查找元素5
	if (it != v.end()) {
		cout << "找到元素" << *it << endl;
	}
	else {
		cout << "未找到元素";
	}
}

输出如下：

找到元素5

对于自定义数据类型的使用：

class Person
{
public:
	string m_name;
	int m_age;
	Person(string name,int age):m_name(name),m_age(age){}
	//重载==运算符,否则find不知道按什么规则比较
	bool operator==(const Person& p)
	{
		if (m_name == p.m_name && m_age == p.m_age) {
			return true;
		}
		return false;
	}
};
int main()
{
	vector<Person> v;
	v.push_back(Person("张三", 20));
	v.push_back(Person("李四", 25));
	v.push_back(Person("王五", 30));
	v.push_back(Person("赵六", 40));

	Person p("王五",30);

	auto it = find(v.begin(), v.end(), p);//查找元素5
	if (it != v.end()) {
		cout << "找到此人:" << it->m_name << it->m_age << endl;
	}
	else {
		cout << "未找到此人";
	}
}

输入如下：

找到此人:王五30

find_if

功能： 按指定规则查找元素

函数原型：

find_if(iterator beg,iterator end,_Pred);

beg起始迭代器
end结束迭代器
_Pred称为谓词(返回值是bool类型的函数或仿函数称为谓词),在这里用做查找规则。 谓词这个概念很重要，此后会经常见到
找到返回指定位置的迭代器，找不到返回结束迭代器

示例：

bool greaterFive(int val)//查找规则
{
	return val > 5;
}
int main()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
		v.push_back(i);
	}
	auto it = find_if(v.begin(), v.end(), greaterFive);
	if (it != v.end()) {
		cout << "找到大于5的元素：" << *it << endl;
	}
	else {
		cout << "未找到" << endl;
	}
}

输出如下：

找到大于5的元素：6

adjacent_find

功能： 查找相邻且重复的元素

函数原型：

adjacent_find(iterator beg,iterator end);

beg起始迭代器
end结束迭代器
找到返回相邻元素第一个元素位置的迭代器，没找到返回容器结束迭代器

示例：

int main()
{
	vector<int> v;
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(3);
	v.push_back(3);
	auto it = adjacent_find(v.begin(), v.end());
	if (it != v.end()) {
		cout << "相邻重复的元素为：" << *it << endl;
	}
	else {
		cout << "不存在相邻重复的元素" << endl;
	}
}

输出如下：

相邻重复的元素为：3

binary_find

功能： 查找指定元素value，找到返回true，否则返回false

特点：

查找速度比一般查找算法快的多，因为一般查找算法的时间复杂度为O(n),而二分查找算法的时间复杂度为O(log(n))
但二分查找也有局限性，它不能用于查找无序序列，也就是说只能利用二分查找查升序排序或降序排序序列中指定的元素

函数原型：

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

beg起始迭代器
end结束迭代器
只能在有序序列中使用，如果用于无序序列，函数返回的结果将不准确

示例：

int main()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
		v.push_back(i);
	}
	bool flag = binary_search(v.begin(), v.end(), 5);
	if (flag == 1) {
		cout << "找到指定元素" << endl;
	}
	else {
		cout << "未找到" << endl;
	}
}

输出如下：

找到指定元素

count

功能： 统计相同元素出现次数

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

统计元素value的个数
beg起始迭代器
end结束迭代器

示例：

我们重点看一下count在自定义数据类型中的使用

class Person
{
public:
	string m_name;
	int m_age;
	Person(string name,int age):m_name(name),m_age(age) {}
	bool operator==(const Person& p)//重载==，作为统计元素规则
	{
		if (m_age == p.m_age) {
			return true;//统计年龄相同的元素
		}
		return false;
	}
};
int main()
{
	vector<Person> v;
	v.push_back(Person("张三", 30));
	v.push_back(Person("李四", 25));
	v.push_back(Person("王五", 35));
	v.push_back(Person("赵六", 25));
	v.push_back(Person("熊大", 25));
	v.push_back(Person("熊二", 20));

	Person p("光头强", 25);
	int num = count(v.begin(), v.end(), p);
	cout << "年龄为25的生物的个数：" << num << endl;
}

输出如下：

年龄为25的生物的个数：3

count_if

功能： 按照指定条件统计元素个数

函数原型：

count_if(iteraotr beg,iterator end,_Pred);

beg起始迭代器
end结束迭代器
_Pred 谓词，在这里用作统计的条件

示例：

bool greater5(int val)
{
	return val > 5;
}
int main()
{
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
		v.push_back(i);
	}
	int num = count_if(v.begin(), v.end(), greater5);
	cout << "大于5的元素的个数为：" << num << endl;
}

输出如下：

大于5的元素的个数为：4

常用排序算法

简介：

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

sort

功能： 对容器或数组内元素进行排序

特点：

sort是C++STL中最常用的算法了，没有之一！
sort排序是最快的排序，时间复杂度O(n*log(n))，因为其内部主要由快速排序+插入排序+堆排序实现的。
当排序的序列数据量大时采用快排算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免快排的递归调用带来过大的额外负荷，就改用插入排序。如果递归层次过深，还会改用堆排序。

函数原型：

sort(iterator beg,iterator end,_Pred);

默认对容器内元素升序排序(从小到大)
beg起始迭代器
end结束迭代器
_Pred 谓词，可以不填这个参数(默认升序排序)，如果想按照其他规则排序，如降序排序，这个参数就必须填入
这个算法只有随机存取迭代器可以使用，如普通数组、vector容器、deque容器等等

下面的一个例子将会把前面的算法for_each、transform和sort结合在一起使用

void myPrint(int val)
{
	cout << val << " ";
}
int targetVector(int val)
{
	return val;
}
bool myComepare(int v1,int v2)
{
	return v1 > v2;
}
int main()
{
	int a[10] = { 1,4,7,2,5,8,3,6,9 };//乱序数组
	vector<int> v(10);
	transform(a, a + 10, v.begin(), targetVector);

	cout << "排序前打印数组a: ";
	for_each(a, a + 10, myPrint);
	cout << "n排序前打印容器v: ";
	for_each(v.begin(), v.end(), myPrint);

	sort(a, a + 10);//默认升序排序
	cout << "n升序排序后打印数组a: ";
	for_each(a, a + 10, myPrint);

	sort(v.begin(), v.end(), myComepare);//降序排序
	cout << "n降序排序后打印容器v: ";
	for_each(v.begin(), v.end(), myPrint);
}

输出如下：

排序前打印数组a: 1 4 7 2 5 8 3 6 9 0
排序前打印容器v: 1 4 7 2 5 8 3 6 9 0
升序排序后打印数组a: 0 1 2 3 4 5 6 7 8 9
降序排序后打印容器v: 9 8 7 6 5 4 3 2 1 0

random_shuffle

功能： 指定范围内元素随机调整次序

函数原型：

random_shuffle(iterator beg,iterator end);

beg起始迭代器
end结束迭代器
指定范围[beg,end)内元素随机打乱

注意： 在使用random_shuffle之前最好先撒下随机数种子srand((unsigned)time(NULL))，否则每次随机的结果都是一样的。srand函数在头文件#include<ctime>中。

示例：

void myPrint(int val)
{
	cout << val << " ";
}
int main()
{
	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	srand((unsigned)time(NULL));//随机数种子
	random_shuffle(a, a + 10);
	cout << "随机打乱后：";
	for_each(a, a + 10, myPrint);
}

打印如下(每个人打印的结果可能不同，因为是随机打乱的)：

随机打乱后：0 5 4 6 7 1 8 3 9 2

merge

功能： 将两个有序的容器合并到另一个目标容器中，合并后该目标容器仍然有序

函数原型：

merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg);

beg1第一个容器或数组起始迭代器
end1第一个容器或数组结束迭代器
beg2第一个容器或数组起始迭代器
end2第一个容器或数组结束迭代器
target_beg目标容器或数组起始迭代器

注意：

两个容器必须是有序的并且是同一种顺序，不能一个升序一个降序
目标容器的大小必须提前指定，并且其大小不小于合并的那两个容器的大小之和

示例：

void myPrint(int val)
{
	cout << val << " ";
}
int main()
{
	vector<int> v;
	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	
	for (int i = 0; i < 10; ++i) {
		v.push_back(i + 5);
	}
	vector<int> target(10 + v.size());
	cout << "打印a: ";
	for_each(a,a+10, myPrint);
	cout << "n打印打印v2: ";
	for_each(v.begin(), v.end(), myPrint);

	merge(a, a + 10, v.begin(), v.end(), target.begin());
	cout << "n打印合并后容器target: ";
	for_each(target.begin(), target.end(), myPrint);
}

打印如下：

打印a: 0 1 2 3 4 5 6 7 8 9
打印打印v2: 5 6 7 8 9 10 11 12 13 14
打印合并后容器target: 0 1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 11 12 13 14

reverse

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

函数原型：

reverse(iterator beg,iterator end);

beg起始迭代器
end结束迭代器

示例：

int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	reverse(arr, arr + 10);
	cout << "反转后输出：";
	for (int i = 0; i < 10; ++i) {
		cout << arr[i] << " ";
	}
}

输出如下：

反转后输出：9 8 7 6 5 4 3 2 1 0

常用的替换算法

简介：

swap 交换两个容器的元素，或者仅仅交换两个元素
replace 将容器内指定范围的旧元素替换为新元素
replace_if 按条件将替换元素，满足条件的替换成指定元素

swap

功能： 交换两个容器内的元素，或者仅仅交换两个元素

函数原型：

swap(container c1,container c2);

c1容器1或元素1
c2容器2或元素2

注意： c1和c2必须是同种类型的容器或元素，否则换不了，编译器报错。

示例：

void myPrint(int val)
{
	cout << val << " ";
}
int main()
{
	int a=1, b=2;
	vector<int> v1,v2;
	for (int i = 0; i < 10; ++i) {
		v1.push_back(i);     //v1: 0,1,2,3,4,5,6,7,8,9
		v2.push_back(9 - i); //v2: 9,8,7,6,5,4,3,2,1,0
	}
	swap(a, b);
	cout << "a = " << a << "， b = " << b << endl;
	swap(v1, v2);
	cout << "输出v1: ";
	for_each(v1.begin(), v1.end(), myPrint);
	cout << "n输出v2: ";
	for_each(v2.begin(), v2.end(), myPrint);
}

输出如下：

a = 2， b = 1
输出v1: 9 8 7 6 5 4 3 2 1 0
输出v2: 0 1 2 3 4 5 6 7 8 9

replace

功能： 将容器内指定范围的旧元素替换为新元素

函数原型：

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

beg起始迭代器
end结束迭代器
将容器[beg,end)内元素oldvalue全部换成newvalue

示例：

int main()
{
	int arr[10] = { 6,3,1,4,8,6,6,7,6,5 };
	replace(arr + 1, arr + 10, 6, 60);
	cout << "替换后：";
	for (int i = 0; i < 10; ++i) {
		cout << arr[i] << " ";
	}
}

输入如下：

替换后：6 3 1 4 8 60 60 7 60 5

replace_if

功能： 按条件将替换元素，满足条件的替换成指定元素

函数原型：

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

beg起始迭代器
end结束迭代器
_Pred是谓词，将满足谓词条件的元素替换成newvalue

示例：

bool lessFive(int val)//谓词，条件是小于5的数
{
	return val < 5;
}
int main()
{
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	replace_if(arr, arr + 10, lessFive, 0);
	cout << "替换后：";
	for (int i = 0; i < 10; ++i) {
		cout << arr[i] << " ";
	}
}

输出如下：

替换后：0 0 0 0 0 5 6 7 8 9

常用集合算法

简介：

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

set_intersection

功能： 求两个容器内元素的交集，并把这个交集传给另一个容器

函数原型：

set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

beg1第一个容器起始迭代器
end1第一个容器结束迭代器
beg2第一个容器起始迭代器
end2第一个容器结束迭代器
target_beg目标容器的起始迭代器
函数返回值为目标容器最后一个元素的下一个地址处的迭代器

注意：求交集的两个容器必须是有序序列，而且同序（同升或同降），否则报错。

示例：

int main()
{
	vector<int> v1, v2;
	for (int i = 0; i < 10; ++i) {
		v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9
		v2.push_back(i + 5);      //v2: 5,6,7,8,9,10,11,12,13,14
	}
	vector<int> target;
	//设置目标容器大小
	target.resize(min(v1.size(), v2.size()));

	auto target_end = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
	cout << "打印存储交集的目标容器：";
	for (auto it = target.begin(); it != target_end; ++it) {
		cout << *it << " ";
	}
}

输出如下：

打印存储交集的目标容器：5 6 7 8 9

set_ union

功能： 求两个容器内元素的并集，并把这个并集传给另一个容器

函数原型：

set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

beg1第一个容器起始迭代器
end1第一个容器结束迭代器
beg2第一个容器起始迭代器
end2第一个容器结束迭代器
target_beg目标容器的起始迭代器
函数返回值为目标容器最后一个元素的下一个地址处的迭代器

注意：求并集的两个容器必须是有序序列，而且同序（同升或同降），否则报错。

示例：

int main()
{
	vector<int> v1, v2;
	for (int i = 0; i < 10; ++i) {
		v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9
		v2.push_back(i+5);        //v2: 5,6,7,8,9,10,11,12,13,14
	}
	vector<int> target;
	//设置目标容器大小
	target.resize(v1.size()+ v2.size());

	auto target_end = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
	cout << "打印存储并集的目标容器：";
	for (auto it = target.begin(); it != target_end; ++it) {
		cout << *it << " ";
	}
}

输出如下：

打印存储并集的目标容器：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

set_ difference

功能： 求两个容器内元素的差集，并把这个差集传给另一个容器
所谓差集：容器v1相对于v2的差集是，v1内元素去除v1和v2交集部分所剩余的元素

函数原型：

set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

beg1第一个容器起始迭代器
end1第一个容器结束迭代器
beg2第一个容器起始迭代器
end2第一个容器结束迭代器
target_beg目标容器的起始迭代器
函数返回值为目标容器最后一个元素的下一个地址处的迭代器

注意：求并集的两个容器必须是有序序列，而且同序（同升或同降），否则报错。

示例：

int main()
{
	vector<int> v1, v2;
	for (int i = 0; i < 10; ++i) {
		v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9
		v2.push_back(i + 5);      //v2: 5,6,7,8,9,10,11,12,13,14
	}
	vector<int> target;
	//设置目标容器大小
	target.resize(max(v1.size(), v2.size()));

	auto target_end = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
	cout << "打印v1和v2的差集：";
	for (auto it = target.begin(); it != target_end; ++it) {
		cout << *it << " ";
	}
	target_end = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), target.begin());
	cout << "n打印v2和v1的差集：";
	for (auto it = target.begin(); it != target_end; ++it) {
		cout << *it << " ";
	}
}

输出如下：

打印v1和v2的差集：0 1 2 3 4
打印v2和v1的差集：10 11 12 13 14

常用的算术生成算法

注意：本文之前介绍的所有算法都在头文件#include<algorithm>中，现在将介绍两个在#include<numeric>中的算法

简介：

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

accumulate

功能： 计算容器内元素累计总和

函数原型：

accumulate(iterator beg,iterator end,value);

beg起始迭代器
end结束迭代器
value是起始值，如果不需要把它设为0
函数返回容器内元素累计总和

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}
	int sum = accumulate(v.begin(), v.end(), 0);
	cout << "容器内元素和为：" << sum << endl;
}

输出如下：

容器内元素和为：5050

fill

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

函数原型：

fill(iterator beg,iterator end,value);

beg起始迭代器
end结束迭代器
向容器中填充value

示例：

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main()
{
	vector<int> v(10);
	fill(v.begin(), v.end(), 1);
	for (int i = 0; i < 10; ++i) {
		cout << v[i] << " ";
	}
}

输出如下：

1 1 1 1 1 1 1 1 1 1

结束语

本篇到此结束，共一万两千多字，你的点赞、评论、关注、收藏都是对我最大的支持，谢谢啦！(悄咪咪说一声，本篇可能是C站最详细的C++STL常用算法总结哦)。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c++STL 后端开发语言算法

二维码

数据结构-图的实现以及基础算法-C语言实现

< <上一篇

数组分区—荷兰国旗问题？

下一篇>>

搜索内容

【万字总结篇】C++STL常用算法详解（错等年系列）

写在前面

目录索引

STL常用算法

最大值/最小值

常用遍历算法

for_each

transform

常用查找算法

find

find_if

adjacent_find

binary_find

count

count_if

常用排序算法

sort

random_shuffle

merge

reverse

常用的替换算法

swap

replace

replace_if

常用集合算法

set_intersection

set_ union

set_ difference

常用的算术生成算法

accumulate

fill

结束语

最新文章

分类

标签云