简介:
algorithm头文件是C++的标准算法库,它主要应用在容器上。
因为所有的算法都是通过迭代器进行操作的,所以算法的运算实际上是和具体的数据结构相分离的
,也就是说,具有低耦合性。
因此,任何数据结构都能使用这套算法库,只要它具有相应的迭代器类型。
常用函数:
一、max()、min()、abs()函数
max():求两个数最大值 min():求两个数最小值 abs():求一个数的绝对值
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a = 3 , b = 4 ; int Max = max (a,b); int Min = min (a,b); int Abs = abs (-3 ); cout << Max << Min << Abs; return 0 ; }
输出:433 注意:
1、max()和min()函数中的参数只能是两个,如果想求3个数的最大值,需要嵌套一下
同理:如果想求数组中的最大值,需要在循环中写。
2、写了algorithm头文件后,
max就变成了函数名,在自己定义变量时,要避免使用max,min等。
3、abs()函数只能用于求整型变量的绝对值,而##include<cmath>
中的fabs()函数还可用于求浮点型变量的绝对值,不要搞混~
2、交换函数:swap()
用来交换x和y的值
代码:
1 2 3 4 5 6 7 8 9 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a = 3 , b = 4 ; swap (a,b); cout << a << b; return 0 ; }
输出:43
3、翻转函数:reverse()
翻转x-y区间的数组、容器的值。
1、翻转整个数组
翻转整个数组:
1 2 3 4 5 6 7 8 9 10 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {11 ,22 ,33 ,44 ,55 }; reverse (a,a+5 ); for (int i = 0 ; i < 5 ; i++) cout << a[i] << ' ' ; return 0 ; }
输出:55 44 33 22 11
2、也可以实现对部分值的翻转,像这样:
翻转部分数组:
1 2 3 4 5 6 7 8 9 10 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {11 ,22 ,33 ,44 ,55 }; reverse (a+3 ,a+5 ); for (int i = 0 ; i < 5 ; i++) cout << a[i] << ' ' ; return 0 ; }
输出:11 22 33 55 44
3、翻转容器:若想对容器中所有的数进行翻转,则需要用到begin()、end()函数,像这样:
翻转整个容器:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ##include <iostream> ##include <algorithm> ##include <vector> using namespace std;int main () { vector<int >v; for (int i = 0 ; i < 5 ; i++) v.push_back (i); reverse (v.begin (), v.end ()); for (int i = 0 ; i < v.size (); i++) { cout << v[i] << ' ' ; } return 0 ; }
输出:4 3 2 1 0
4、翻转容器:容器的翻转也可以用迭代器,来实现指定位数的翻转,像这样:
翻转部分容器:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ##include <iostream> ##include <algorithm> ##include <vector> using namespace std;int main () { vector<int >v; vector<int >::iterator it; for (int i = 0 ; i < 5 ; i++) v.push_back (i); it = v.begin (); reverse (it, it+3 ); for (int i = 0 ; i < v.size (); i++) { cout << v[i] << ' ' ; } return 0 ; }
输出:2 1 0 3 4
注意: 如果想在翻转时指定位数,则其为半开半闭区间。 如reserve(a+2,
a+4);翻转数组中第2-4之间的数,不包括第二个,但包括第四个。
四、排序函数:sort()
1、对x-y区间的数组、容器进行排序。默认升序排列。
数组升序排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {55 ,44 ,33 ,22 ,11 }; sort (a,a+5 ); for (int i = 0 ; i < 5 ; i++) cout << a[i] << ' ' ; return 0 ; }
输出:11 22 33 44 55
2、如果想将数组降序排序,就需要写一个简单的函数,改变默认的排序功能,像这样:
数组降序排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ##include <iostream> ##include <algorithm> bool cmp (int a, int b) { return a > b; } using namespace std;int main () { int a[5 ] = {55 ,44 ,33 ,22 ,11 }; sort (a,a+5 ,cmp); for (int i = 0 ; i < 5 ; i++) cout << a[i] << ' ' ; return 0 ; }
输出:55 44 33 22 11
3、同理,如果想对结构体排序,也需要自定义优先级。像这样:
结构体排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ##include <iostream> ##include <algorithm> using namespace std;struct Student { int high; int weigh; }student[10 ]; bool cmp (Student a, Student b) { return a.high < b.high; } int main () { for (int i = 0 ; i < 10 ; i++) { student[i].high = i ; } sort (student, student+10 , cmp); for (int i = 0 ; i < 10 ; i++) { cout << student[i].high << ' ' ; } return 0 ; }
输出:0 1 2 3 4 5 6 7 8 9
4、如果想对容器排序,就需要使用迭代器,或begin(),end()函数。像这样:
容器升序排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ##include <iostream> ##include <algorithm> ##include <vector> using namespace std;int main () { vector<int >v; vector<int >::iterator it; for (int i = 5 ; i > 0 ; i--) v.push_back (i); it = v.begin (); sort (it, it+3 ); for (int i = 0 ; i < v.size (); i++) { cout << v[i] << ' ' ; } return 0 ; }
输出:3 4 5 2 1
5、同理,如果想对容器降序排序,或对容器结构体排序,向数组那样操作就可以了。
注意:
1、sort()排序函数的时间复杂度大概在o(nlogn),比冒泡、简单排序等效率高 。
2、和reverse()函数一样,可以自由指定排序范围,也是半开半闭区间(左闭右开)。
五、查找函数:find()
查找某数组指定区间x-y内是否有x,若有,则返回该位置的地址,若没有,则返回该数组第n+1个值的地址。(好烦有木有,为啥要返回地址。还要转化o(╥﹏╥)o)
1、数组中查找是否有某值:一定一定一定要满足代码中这两个条件。
第一个条件是:p-a != 数组的长度。p是查找数值的地址,a是a[0]的地址。
第二个条件是:*p == x; 也就是该地址指向的值等于我们要查找的值。
最后输出p-a+1; p-a相当于x所在位置的地址-a[0]所在位置的地址,
但因为是从0开始算, 所以最后需要+1。
1、对数组查找:
1 2 3 4 5 6 7 8 9 10 11 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {11 ,22 ,33 ,44 ,55 } int *p = find (a,a+5 ,33 ); if (((p-a) != 5 ) && (*p == x)) cout << (p-a+1 ); return 0 ; }
输出:3
2、对容器进行查找同理:也要满足这两个条件:
对容器查找:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ##include <iostream> ##include <algorithm> ##include <vector> using namespace std;int main () { vector<int >v; vector<int >::iterator it, it1; for (int i = 0 ; i < 5 ; i++) v.push_back (i); int size = v.size (); it = find (v.begin (), v.end (), 3 ); it1 = v.begin (); if (((it-it1)!=size)&&(*it==3 )) cout << (it-it1+1 ) << endl; return 0 ; }
输出:4
六、查找函数:upper_bound()、lower_bound()
1、upper_bound():查找第一个大于x的值的位置
2、lower_bound():查找第一个大于等于x的值的位置
同样是返回地址,用法和find()函数一毛一样,限制条件也一毛一样,照着扒就行了。
七、填充函数:fill()
在区间内填充某一个值。同样适用所有类型数组,容器。
1、举例:在数组中未赋值的地方填充9999
代码:
1 2 3 4 5 6 7 8 9 10 11 12 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {11 ,33 ,22 }; fill (a+3 ,a+5 ,9999 ); for (int i = 0 ; i < 5 ; i++) cout << a[i] << ' ' ; return 0 ; }
输出:11 33 22 9999 9999
应用:
常用在大数加法中,因为数太大,需要用字符串保存,如果在运算时需要填充0,就要用这个函数。
八、查找某值出现的次数:count()
1、在数组中查找x 在某区间出现的次数:
代码:
1 2 3 4 5 6 7 8 9 10 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[5 ] = {11 ,22 ,33 ,44 ,44 }; cout << count (a, a+5 , 44 ); return 0 ; }
输出:2
2、在容器中查找同理,只是需要用iterator迭代器或begin()、end()函数。
注意:
和前几个函数一样,如果需要指定区间查询,注意是半开半闭区间(左闭右开区间)。
八、求最大公因数:__gcd()
震惊把!在我最开始知道竟然有这个函数时,我也是震惊的!
另外,用二者乘积除以最大公因数即可得到最小公倍数。
因此没有求最小公倍数的函数。
代码:
1 2 3 4 5 6 7 8 9 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a = 12 , b = 4 ; int Gcd = __gcd(a,b); cout << Gcd; return 0 ; }
注意: __gcd() 需要写两个下划线!
九、求交集、并集、差集:set_intersection()、set_union()、set_difference()
1、求交集:
(1):将两个数组的交集赋给一个容器(为什么不能赋给数组呢?因为数组不能动态开辟,且inserter()函数中的参数必须是指向容器的迭代器。):
代码:
1 2 3 4 5 6 7 8 9 10 11 12 ##include <algorithm> ##include <iostream> ##include <vector> using namespace std;int main () { int a[5 ] = {1 ,2 ,3 ,4 ,5 }, b[5 ] = {1 ,2 ,33 ,44 ,55 }; vector<int >::iterator it; vector<int >v4; set_intersection (a, a+5 , b, b+5 , inserter (v4,v4. begin ())); for (int i = 0 ; i < v4. size (); i++) { cout << v4[i] << ' ' ; }
输出:1 2
(2):将两个容器的交集赋给另一个容器: 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ##include <algorithm> ##include <iostream> ##include <vector> using namespace std;int main () { vector<int > v1, v2, v3; for (int i = 0 ; i < 5 ; i++) v1. push_back (i); for (int i = 3 ; i < 8 ; i++) v2. push_back (i); set_intersection (v1. begin (), v1. end (), v2. begin (), v2. end (), inserter (v3,v3. begin ())); for (int i = 0 ; i < v3. size (); i++) { cout << v3[i] << ' ' ; } return 0 ; }
输出:3 4
2、求并集:
(1):将两个数组的并集赋给一个容器(为什么不能赋给数组呢?因为数组不能动态开辟,且inserter()函数中的参数必须是指向容器的迭代器。):
代码:
1 2 3 4 5 6 7 8 9 10 11 12 ##include <algorithm> ##include <iostream> ##include <vector> using namespace std;int main () { int a[5 ] = {1 ,2 ,3 ,4 ,5 }, b[5 ] = {1 ,2 ,33 ,44 ,55 }; vector<int >::iterator it; vector<int >v4; set_union (a, a+5 , b, b+5 , inserter (v4,v4. begin ())); for (int i = 0 ; i < v4. size (); i++) { cout << v4[i] << ' ' ; }
输出:1 2 3 4 5 33 44 55 (2):将两个容器的并集赋给另一个容器:
代码: ##include<algorithm>
##include<iostream>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ##include <vector> using namespace std;int main () { vector<int > v1, v2, v3; for (int i = 0 ; i < 5 ; i++) v1. push_back (i); for (int i = 3 ; i < 8 ; i++) v2. push_back (i); set_union (v1. begin (), v1. end (), v2. begin (), v2. end (), inserter (v3,v3. begin ())); for (int i = 0 ; i < v3. size (); i++) { cout << v3[i] << ' ' ; } return 0 ; }
输出:0 1 2 3 4 5 6 7
3、差集完全同理。
注意: inserter(c,c.begin())为插入迭代器
此函数接受第二个参数,这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。
十、全排列:next_permutation()
将给定区间的数组、容器全排列
1、将给定区间的数组全排列:
代码:
1 2 3 4 5 6 7 8 9 10 11 ##include <iostream> ##include <algorithm> using namespace std;int main () { int a[3 ] = {1 ,2 ,3 }; do { cout<<a[0 ]<<a[1 ]<<a[2 ]<<endl; }while (next_permutation (a,a+3 )); return 0 ; }
输出: 123 132 213 231 312 321
2、容器全排列同理:只不过将参数换成iterator迭代器或begin()、end()函数。
注意:
和之前的一样,如果指定全排列区间,则该区间是半开半闭区间(左闭右开)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
————————————————
版权声明:本文为CSDN博主「来老铁干了这碗代码」的原创文章,遵循CC 4.0
BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_43899069/article/details/104450000