前言:
近来在学习STL标准库,做一份笔记并整理好,方便自己梳理知识、以后查找,也方便他人学习,两全其美,快哉快哉!
这里我会以中国大学慕课上北京大学郭炜老师的《程序设计与算法(一)C语言程序设计》中的十二章十三章为学习资料来做笔记。并且我会附上代码(只要我不偷懒的话)。若有没学习到的部分,我会继续找资料来更新学习笔记。
STL(Standard Template Library,标准模板库)
包含一些常用的算法如排序查找,和常用的数据结构如:可变长数组,链表,字典等。
优点:使用方便,(运行)效率较高。
注意:若要使用其中的算法,需要#include
一、排序(sort)
本质上是用快速排序算法实现。
用法1:对基本类型的数组(int,double,char…)从小到大排序
sort(数组名+n1, 数组名+n2);
n1和n2都是int类型表达式,可以包含变量
如果n1=0,则+n1可以不写
作用是将数组中下标范围为[n1,n2)的元素从小到大排序,下标为n2的元素不在排序区间内。
样例:
1 int main(int argc, char const *argv[])
2 {
3 int a[] = {15,4,3,8,7,2,6};
4 sort(a,a+7);//对整个数组从小到大排序
5 for (int i = 0; i < 7; i++)
6 {
7 cout<<a[i]<<' ';
8 }//结果:2 3 4 6 7 8 15
9 cout<<endl;
10 int b[] = {15,4,3,8,7,2,6};
11 sort(b,b+3);
12 for (int i = 0; i < 7; i++)
13 {
14 cout<<b[i]<<' ';
15 }//结果:3 4 15 8 7 2 6
16 cout<<endl;
17 int c[] = {15,4,3,8,7,2,6};
18 sort(c+2,c+5);
19 for (int i = 0; i < 7; i++)
20 {
21 cout<<c[i]<<' ';
22 }//结果:15 4 3 7 8 2 6
23 cout<<endl;
24 return 0;
25 }
用法1
用法2:对元素类型为T的基本类型数组从大到小排序:
sort(数组名+n1,数组名+n2,greater
样例:
1 int main(int argc, char const *argv[])
2 {
3 int a[] = {15,4,3,8,7,2,6};
4 int i;
5 sort(a,a+7,greater
6 for ( i = 0; i < 7; i++)
7 {
8 cout<<a[i]<<' ';
9 }//结果:15 8 7 6 4 3 2
10
11 return 0;
12 }
用法2
用法3:用自定义的排序规则,对任何类型T的数组排序
使用这种用法的原因:在我们自己定义了一些类/结构体的时候,自带的排序规则可能无法使用,或者说我们需要用我们自己的方法来排序,这个时候我们就要自定义排序规则了。
sort(数组名+n1,数组名+n2,排序规则结构名());
排序规则结构的定义方式:
1 struct 结构名
2 {
3 bool operator()(const T & a1,const T & a2)const
4 {
5 //若a1应该在a2前面,则返回true
6 //否则返回false
7 }
8 };
定义方式
在bool operator()(const T & a1,const T & a2)const这一句中,要记得写上const,否则可能会有奇奇怪怪的错误。
样例1(自定义规则排序):
1 struct rule1//从大到小排序
2 {
3 bool operator()(const int & a1,const int & a2)const
4 {
5 return a1 > a2;
6 }
7 };
8 struct rule2//按个位数从大到小排序
9 {
10 bool operator()(const int & a1,const int & a2)const
11 {
12 return a1%10 < a2%10;
13 }
14 };
15 void Print(int a[],int size)
16 {
17 for (int i = 0; i < size; i++)
18 {
19 cout<<a[i]<<",";
20 }
21 cout<<endl;
22 }
23 int main(int argc, char const *argv[])
24 {
25 int a[] = {12,45,3,98,21,7};
26 sort(a,a+sizeof(a)/sizeof(int));//从小到大排序
27 cout<<"1)";Print(a,sizeof(a)/sizeof(int));
28 //结果:1)3,7,12,21,45,98,
29 sort(a,a+sizeof(a)/sizeof(int),rule1());//从大到小排序
30 cout<<"2)";Print(a,sizeof(a)/sizeof(int));
31 //结果:2)98,45,21,12,7,3,
32 sort(a,a+sizeof(a)/sizeof(int),rule2());//按个位数从小到大排序
33 cout<<"3)";Print(a,sizeof(a)/sizeof(int));
34 //结果:3)21,12,3,45,7,98,
35 return 0;
36 }
用法3样例1(自定义规则排序)
样例2(结构体数组排序):
1 struct Student
2 {
3 char name[20];
4 int id;
5 double gpa;
6 };
7 Student students [] =
8 {
9 {"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},
10 {"Ala",333,3.5},{"Zero",101,4.0}
11 };
12 //排序范围是[n1,n2)的元素
13 //在使用二分查找时,查找规则必须和排序规则一致
14 struct StudentRule1//按姓名从小到大排
15 {
16 bool operator()(const Student & s1,const Student & s2)const{
17 if (stricmp(s1.name,s2.name) < 0)
18 {
19 return true;
20 }
21 return false;
22 }
23 };
24 struct StudentRule2//按id从小到大排
25 {
26 bool operator()(const Student & s1,const Student & s2)const{
27 return s1.id < s2.id;
28 }
29 };
30 struct StudentRule3//按gpa从高到低排
31 {
32 bool operator()(const Student & s1,const Student & s2)const{
33 return s1.gpa > s2.gpa;
34 }
35 };
36 void PrintStudents(Student s[],int size)
37 {
38 for (int i = 0; i < size; i++)
39 {
40 cout<<"("<<s[i].name<<","<<s[i].id<<","<<s[i].gpa<<")";
41 }
42 cout<<endl;
43 }
44 int main()
45 {
46 int n = sizeof(students)/sizeof(Student);
47
48 sort(students,students+n,StudentRule1());
49 PrintStudents(students,n);
50 //结果:(Ala,333,3.5)(Jack,112,3.4)(Mary,102,3.8)(Mary,117,3.9)(Zero,101,4)
51 sort(students,students+n,StudentRule2());
52 PrintStudents(students,n);
53 //结果:(Zero,101,4)(Mary,102,3.8)(Jack,112,3.4)(Mary,117,3.9)(Ala,333,3.5)
54 sort(students,students+n,StudentRule3());
55 PrintStudents(students,n);
56 //结果:(Zero,101,4)(Mary,117,3.9)(Mary,102,3.8)(Ala,333,3.5)(Jack,112,3.4)
57 return 0;
58 }
用法3样例2(结构体数组排序)
这些就是这次笔记的内容了,感谢大家读到这里,祝大家学习愉快,头发常驻!
手机扫一扫
移动阅读更方便
你可能感兴趣的文章