来者可追，往之不谏

努力提升自己

0%

C++ STL常用算法

发表于 更新于 分类于
本文字数： 9.7k 阅读时长 ≈ 18 分钟

标准模板库 STL（Standard Template Library）是C++标准库的一部分，是借助模板把常用的数据结构及算法封装在其中。掌握STL对于刷算法题有很大的帮助。写此文来记录总结下STL中的常用函数

常用遍历算法

以下算法都在头文件<algorithm>中

for_each 实现遍历容器

1
for_each(iterator beg, iterator end, _func);//beg 开始迭代器	end 结束迭代器  _func 函数或者函数对象

_func传入普通函数

1
2
3
4
5
6
7
void vecPrint(int val) {			//定义普通函数
	cout << val << " ";
}
void test() {
	vector<int>v = { 2,3,43,324,234,123,2345,435,34 };
	for_each(v.begin(), v.end(), vecPrint);//遍历输出v容器中的元素
}

运行结果

​ 2 3 43 324 234 123 2345 435 34

_func传入仿函数

1
2
3
4
5
6
7
8
9
10
class printFunctor{		//创造仿函数,打印数据
public:
	void operator()(int val) {
		cout << val << " ";
	}
};
void test() {
	vector<int>v = { 2,3,43,324,234,123,2345,435,34 };
	for_each(v.begin(), v.end(), printFunctor());//遍历输出v容器中的元素
}

运行结果

2 3 43 324 234 123 2345 435 34

transform搬运容器到另一个容器

1
transform(iterator beg1, iterator end1, iterator beg2, _func);//beg1 源容器开始迭代器	end1 源容器结束迭代器 beg2 目标容器开始迭代器 _func 函数或者函数对象
1
2
3
4
5
6
7
8
9
10
11
12
13
class Trans {//仿函数实现将数据元素+10操作
public:
	int operator()(int val) {
		return val+10;
	}
};
void test() {
	vector<int>v = { 1,2,3,4,5,6,7,8,9 };
	vector<int>vTarget;
	vTarget.resize(v.size());//为vTraget容器开辟与v容器等大的空间，否则程序运行会被中止
	transform(v.begin(), v.end(),vTarget.begin(), Trans());//将v容器中的数据+10后搬运到vTarget中
	for_each(vTarget.begin(), vTarget.end(), printFunctor());//打印vTarget容器
}

运行结果

11 12 13 14 15 16 17 18 19

常用查找算法

find查找指定元素

1
find(iterator beg.iterator end,value)//value为查找的元素，找到返回指定元素的迭代器，否则返回end()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void test() {
	vector<int>v = { 1,2,3,4,5,6,7,8,9 };
	vector<int>::iterator it; //定义一个迭代器
	int toFind=1; //待查找的数据
	cout << "原始数据展示:" << endl;
	for_each(v.begin(), v.end(), printFunctor());
	cout << endl;
	cout << endl;
	while (toFind) {
		cout << "待查找值:";
		cin >> toFind;
		it = find(v.begin(), v.end(), toFind);
		if (it != v.end()) {
			cout << "找到" << toFind << "了" << endl;
		}
		else
			cout << "找不着" << endl;
	}
}

运行结果

原始数据展示:
1 2 3 4 5 6 7 8 9

待查找值:2
找到2了
待查找值:0
找不着

以上是对常用数据类型查找的示例演示，但试想以下，如果数据类型不是常用的int，char，string之类的，而是自己定义的结构体类型，我们知道如果要判定自己定义的数据类型是否相等要写重载函数的，编译器是不支持自定义数据类型的判等之类的操作的，所以对于自定义数据类型，find函数自然也不会执行成功，该如何修改程序呢？

首先把自定义数据类型与重载函数设计好

1
2
3
4
5
6
7
8
9
class Person {
public:
	string p_name;
	int p_age;
	Person(string name, int age) {
		this->p_age = age;
		this->p_name = name;
	}
};

接下来就以查找成功的案例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test() {
	vector<Person>v;
	//创建数据
	Person p1("吴京", 45);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	vector<Person>::iterator it;//定义一个迭代器
	it=find(v.begin(), v.end(), p1);//查找p1,it返回查找指定值的迭代器
	if (it != v.end()) {
		cout << "找着" << it->p_name << "了  " <<"年龄:"<<it->p_age<<endl;
	}
}

运行结果

找着吴京了 年龄:45

find_if 按条件查找元素

1
find_if(iterator beg,iterator end, _Pred);//_Pred 函数或者谓词

以在1-10数值查找大于5的数为例，来看一看 find_if 的效果

写一个判定大于5的谓词

1
2
3
4
5
6
class GT5 {
public:
	bool operator()(int val) {
		return val>5;
	}
};

接下来展示一下 find_if 的效果

1
2
3
4
5
void test() {
	vector<int>v = { 1,2,3,4,5,6,7,8,9,10 };
	vector<int>::iterator it= find_if(v.begin(), v.end(), GT5());
	cout << *it;
}

运行结果

6

可以看到，函数返回的是查找到的第一个符合条件的元素的迭代器。

对于自定义类型的数据，需要在写谓词的时候写出适合该数据类型的合适方法。比如拿之前写好的Person类，你需要比较年龄，就写关于年龄比较的仿函数。

adjacent_find 查找相邻重复元素

1
adjacent_find(iterator beg, iterator end);

很简单，返回第一个相邻的重复元素

对于自定义的数据类型需要单独写函数或者仿函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void showPerson(const Person& p) {
	cout << p.p_name << " : " << p.p_age << endl;

}
void test() {
	vector<Person>v;
	//创建数据
	Person p1("吴京", 45);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	vector<Person>::iterator it;//定义一个迭代器
	it=adjacent_find(v.begin(), v.end());//查找p1,it返回查找指定值的迭代器
	for_each(v.begin(), v.end(), showPerson);
	if (it != v.end()) {
		cout <<"相邻重复元素" << it->p_name << " 的年龄:" << it->p_age << endl;
	}
}

运行结果

吴京 : 45
吴京 : 45
郭帆 : 40
郭帆 : 40
吴孟达 : 60
李雪健 : 71
相邻重复元素吴京 的年龄:45

binary_search 二分查找

返回的是布尔类型

适用于有序数列

1
bool binary_search(iterator beg, iterator end, value);
1
2
3
4
void test() {
	vector<int>v = { 2,2,3,3,4,4,7,8,9,10 };
	cout<<"查找7找到没？"<<binary_search(v.begin(), v.end(), 7);
}

运行结果

查找7找到没？1

count 统计元素个数

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

统计自定义数据类型要实现==的重载

count_if 按条件统计元素个数

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

方法同样是分内建数据类型和自定义数据类型两种实现方式，归根到底的区别在于谓词的设计上的不同

1
2
3
4
5
6
7
8
9
10
11
12
class FindByAge {
public:
	bool operator()(const Person &P) {
		return P.p_age ==40;//查找年龄等于40的Person数据
	}
};
class GT5 {
public:
	bool operator()(int val) {
		return val > 5;//查找值大于5的数据
	}
};

常见排序算法

sort 容器内数据排序

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

将容器内的数据逆序案例:

1
2
3
4
5
6
7
8
9
10
11
12
class decrease { 	//递减仿函数
public:
	bool operator()(int val1, int val2) { 
		return val1 > val2;
	}
};
void test() {
	vector<int>v = { 2,2,3,3,4,4,7,8,9,10 };
	sort(v.begin(), v.end(),decrease());
	for_each(v.begin(), v.end(), printFunctor());

}

运行结果

10 9 8 7 4 4 3 3 2 2

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

使用时加随机数种子，使数据更有随机性

1
random_shuffle(iterator beg, iterator end);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void showPerson(const Person& p) {
	cout << "   " << p.p_name << " : " << p.p_age;

}//打印输出Person
void test() {
	vector<Person>v;
    srand((unsigned int)time(NULL));//创建随机数种子
	//创建数据
	Person p1("吴京", 40);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p4);
	vector<Person>::iterator it;//定义一个迭代器
	cout << "原始数据：";
	for_each(v.begin(), v.end(), showPerson);
	random_shuffle(v.begin(), v.end());
	cout <<endl<< "洗牌后的数据: ";
	for_each(v.begin(), v.end(), showPerson);
}


运行结果

原始数据： 吴京 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71
洗牌后的数据: 吴孟达 : 60 郭帆 : 40 李雪健 : 71 郭帆 : 40 吴京 : 40 李雪健 : 71 吴孟达 : 60

merge 合并两个容器，并存储到另一个容器

1
2
3
4
5
6
7
8
9
10
11
12
13
void test() {
	vector<int>v1;
	vector<int>v2;
	vector<int>v3;
	for (int i = 10;i >0;i--) {//两个降序序列
		v1.push_back(i);
		v2.push_back(i+3);
	}
	v3.resize(v1.size() + v2.size());//为v3分配容量
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin(),decrease());//设置谓词，实现降序排列
	for_each(v3.begin(), v3.end(), printFunctor());

}

运行结果_

13 12 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 2 1

默认是按升序排列，如果升序排列需要排序的两个数列皆为升序；如是自定义数据类型或者如案例中非默认方式排列，就需要自己写相关的谓词。注意升序则都升序，降序都降序，否则运行会中止

__reverse __反转

1
reverse(iterator beg, iterator end);

常用拷贝和替换算法

copy

1
copy(iterator beg, iterator end,iterator dest)//dest目标容器起始迭代器

下面的案例是拷贝一个自定义数据类型容器的案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Person {
public:
	string p_name;
	int p_age;
	Person(string name="", int age = 0) {
		this->p_age = age;
		this->p_name = name;
	}
	bool operator==(const Person& p) {
		if (this->p_name == p.p_name && this->p_age == p.p_age)return true;
		else return false;
	}

};
void test() {
	vector<Person>v;
	vector<Person>v1;

	//创建数据
	Person p1("吴京", 40);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p4);
	v1.resize(v.size());//为v1开辟与v相等的空间
	vector<Person>::iterator it;//定义一个迭代器，此时Person类一定要有默认构造函数
	cout << "原始数据：";
	for_each(v.begin(), v.end(), showPerson);
	copy(v.begin(), v.end(), v1.begin());
	cout <<endl<< "拷贝后的数据: ";
	for_each(v1.begin(), v1.end(), showPerson);
}

运行结果

原始数据： 吴京 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71
拷贝后的数据: 吴京 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71

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

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

下列案例将吴京的数据替换成郭帆的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void test1() {
	vector<Person>v;
	vector<Person>v1;

	//创建数据
	Person p1("吴京", 40);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p4);
	vector<Person>::iterator it;//定义一个迭代器
	cout << "原始数据：";
	for_each(v.begin(), v.end(), showPerson);
	replace(v.begin(), v.end(), p1,p2);//将吴京替换成郭帆
	cout <<endl<< "替换后的数据: ";
	for_each(v.begin(), v.end(), showPerson);
}

运行结果

原始数据： 吴京 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71
替换后的数据: 郭帆 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71

replace 是将所有的吴京都替换成郭帆

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

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

将年龄大于40人的数据都替换成郭帆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class ageG40 {
public:
	bool operator()(const Person &P) {
		return P.p_age > 40;
	}
};
void test1() {
	vector<Person>v;
	vector<Person>v1;

	//创建数据
	Person p1("吴京", 40);
	Person p2("郭帆", 40);
	Person p3("吴孟达", 60);
	Person p4("李雪健", 71);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p4);
	vector<Person>::iterator it;//定义一个迭代器
	cout << "原始数据：";
	for_each(v.begin(), v.end(), showPerson);
	replace_if(v.begin(), v.end(),ageG40(), p2);//将年龄大于40的都替换成郭帆数据
	cout <<endl<< "替换后的数据: ";
	for_each(v.begin(), v.end(), showPerson);
}

运行结果

原始数据： 吴京 : 40 郭帆 : 40 郭帆 : 40 吴孟达 : 60 吴孟达 : 60 李雪健 : 71 李雪健 : 71
替换后的数据: 吴京 : 40 郭帆 : 40 郭帆 : 40 郭帆 : 40 郭帆 : 40 郭帆 : 40 郭帆 : 40

swap

互换两个容器的元素

1
swap(container c1, container c2);//c1, c2两个同种类型的容器

算术生成算法

#include <numeric>

accumulate 计算容器元素累计总和

1
accumulate(iterator beg,iterator end, value);//计算容器元素累计总和 value起始值

fill 容器填充

1
fill (iterator beg.iterator end, value);//向容器填充value

集合算法

交集 set_intersection

1
set_intersection(iterator beg1, iterator end1,iterator beg2, iterator end2,iterator dest)//dest目标容器起始迭代器

并集 set_union

差集 set_difference