爆肝整理STL函数,助你代码实用高逼格

  • 博客主页: https://blog.csdn.net/qq_50285142
  • 欢迎点赞收藏✨关注❤留言 如有错误,敬请指正
  • 虽然生活很难,但我们也要一直走下去

STL可谓是C++的利器,深受算法竞赛选手所爱,今天我将常用函数总结了一下,他们是代码中的技巧,使用后代码层次直接提升一个档次。

废话不多说,直接开始


以下出现的描述说明:(下面函数排序按字典序排列

beg为序列的初始地址

end为序列的尾地址

1. accumulate(beg,end,init)

复杂度: O ( N ) O(N) O(N)

作用:对一个序列的元素求和

init为对序列元素求和的初始值

返回值类型:与init

  • 基础累加求和:
int a[]={
     1,3,5,9,10};

//对[0,2]区间求和,初始值为0,结果为0+1+3+5=9
int res1 = accumulate(a,a+3,0);

//对[0,3]区间求和,初始值为5,结果为5+1+3+5+9=23
int res2 = accumulate(a,a+4,5);
  • 自定义二元对象求和:

使用lamda表达式

typedef long long ll;
struct node
{
     
    ll num;
}st[10];

for(int i=1;i<=n;i++)
    st[i].num = i+10000000000;
//返回值类型与init一致,同时注意参数类型(a)也要一样
//初始值为1,累加1+10000000001+10000000002+10000000003=30000000007
ll res = accumulate(st+1,st+4,1ll,[](ll a,node b){
     
    return a+b.num;
});
    

2. fill(beg,end,num)

复杂度: O ( N ) O(N) O(N)

对一个序列进行初始化赋值

//对a数组的所有元素赋1
int a[5];
fill(a,a+5,1);
for(int i=0;i<5;i++)
    cout<<a[i]<<" ";
//1 1 1 1 1

注意区分memset:

memset()是按字节进行赋值,对于初始化赋0-1有比较好的效果.

如果赋某个特定的数会出错,赋值特定的数建议使用fill()

3. is_sorted(beg,end)

复杂度: O ( N ) O(N) O(N)

判断序列是否有序(升序),返回bool值

//如果序列有序,输出YES
if(is_sorted(a,a+n))
    cout<<"YES\n";

4. lower_bound() upper_bound()

复杂度: O ( l o g N ) O(logN) O(logN)

作用:二分查找

//在a数组中查找第一个大于等于x的元素,返回该元素的地址
lower_bound(a,a+n,x);
//在a数组中查找第一个大于x的元素,返回该元素的地址
upper_bound(a,a+n,x);

//如果未找到,返回尾地址的下一个位置的地址

5. max_element() min_element()

复杂度: O ( N ) O(N) O(N)

找最大最小值

//函数都是返回地址,需要加*取值
int mx = *max_element(a,a+n);
int mn = *min_element(a,a+n);

6. max() min()

复杂度: O ( 1 ) O(1) O(1)

找多个元素的最大值和最小值

//找a,b的最大值和最小值
mx = max(a,b);
mn = min(a,b);
//找到a,b,c,d的最大值和最小值
mx = max({
     a,b,c,d});
mn = min({
     a,b,c,d});

7. nth_element(beg,nth,end)

复杂度: 平均 O ( N ) O(N) O(N)

寻找第序列第n小的值

nth为一个迭代器,指向序列中的一个元素。第n小的值恰好在nth位置上。

执行**nth_element()**之后,序列中的元素会围绕nth进行划分:nth之前的元素都小于等于它,而之后的元素都大于等于它

实例:求序列中的第3小的元素

nth_element(a,a+2,a+n);
cout<<a[2]<<'\n';

8. next_permutation(beg,end)

复杂度: O ( N ) O(N) O(N)

求序列的下一个排列,下一个排列是字典序大一号的排列

返回truefalse

  • next_permutation(beg,end)

    如果是最后一个排列,返回false,否则求出下一个序列后,返回true

//对a序列进行重排
next_permutation(a,a+n);

应用:求所有的排列

输出a的所有排列

//数组a不一定是最小字典序序列,所以将它排序
sort(a,a+n);
do
{
     
 	for(int i=0;i<n;i++)
        printf("%d ",a[i]);
}while(next_permutation(a,a+n));
  • prev_permutation(beg,end)

求出前一个排列,如果序列为最小的排列,将其重排为最大的排列,返回false

9. partial_sort(beg,mid,end)

复杂度: 大概 O ( N l o g M ) O(N logM) O(NlogM) M为距离

部分排序,排序mid-beg个元素,mid为要排序区间元素的尾后的一个位置

从beg到mid的元素都排好序

对a数组前5个元素排序按从小到大排序

int a[] = {
     1,2,5,4,7,9,8,10,6,3};
partial_sort(a,a+5,a+10);
for(int i=0;i<10;i++) 
    cout<<a[i]<<' ';
//1 2 3 4 5 9 8 10 7 6
//前五个元素都有序

也可以添加自定义排序规则:

partial_sort(beg,mid,end,cmp)

对a的前五个元素都是降序排列

int a[] = {
     1,2,5,4,7,9,8,10,6,3};
partial_sort(a,a+5,a+10,greater<int>());
for(int i=0;i<10;i++) 
    cout<<a[i]<<' ';
//10 9 8 7 6 1 2 4 5 3
//前五个元素降序有序

10. random_shuffle()

复杂度: O ( N ) O(N) O(N)

对序列随机重排

//对a数组随机重排
random_shuffle(a,a+n);

11. reverse(beg,end)

复杂度: O ( N ) O(N) O(N)

对序列进行翻转

string s = "abcde";
reverse(s.begin(),s.end());//对s进行翻转
cout<<s<<'\n';//edcba

//对a数组进行翻转
int a[] = {
     1,2,3,4};
reverse(a,a+4);
cout<<a[0]<<a[1]<<a[2]<<a[3];//4321

12. sort()

复杂度: O ( N l o g N ) O(N logN) O(NlogN)

作用:对一个序列进行排序

//原型:
sort(beg,end);
sort(beg,end,cmp);
//对a数组的[1,n]位置进行从小到大排序
sort(a+1,a+1+n);

//对a数组的[0,n-1]位置从大到小排序
sort(a,a+n,greater<int>());
//对a数组的[0,n-1]位置从小到大排序
sort(a,a+n,less<int>());

//自定义排序,定义比较函数
bool cmp(node a,node b)
{
     
    //按结构体里面的x值降序排列
    return a.x>b.x;
}
sort(node,node+n,cmp);

13. transform()

复杂度: O ( N ) O(N) O(N)

作用:使用给定操作,将结果写到dest中

//原型:
transform(beg,end,dest,unaryOp);
//将序列开始地址beg到结束地址end大小写转换,把结果存到起始地址为dest的序列中
transform(beg,end,dest,::tolower);
transform(beg,end,dest,::toupper);

14. to_string()

将数字转化为字符串,支持小数(double)

int a = 12345678;
cout<<to_string(a)<<'\n';

15. unique(beg,end)

复杂度: O ( N ) O(N) O(N)

消除重复元素,返回消除完重复元素的下一个位置的地址

如:a[] = {1,2,3,3,4 };

unique之后a数组为{1,2,3,4,3}前面为无重复元素的数组,后面则是重复元素移到后面,返回a[4]位置的地址(不重复元素的尾后地址)

消除重复元素一般需要原序列是有序序列

运用:离散化

for(int i=0;i<n;i++)
{
     
    cin>>a[i];
    b[i] = a[i];//将a数组复制到b数组
}
sort(b,b+n);//对b数组排序
unique(b,b+n);//消除b重复元素
for(int i=0;i<n;i++)
{
     
    //因为b有序,查找到的下标就是对应的 相对大小(离散化后的值)
    int pos = lower_bound(b,b+n,a[i])-b;//在b数组中二分查找第一个大于等于a[i]的下标
    a[i] = pos;//赋值
}

16. __gcd(a,b)

求a和b的最大公约数

_ _ g c d ( 12 , 15 ) = 3 \_\_gcd(12,15) = 3 __gcd(12,15)=3

_ _ g c d ( 21 , 0 ) = 21 \_\_gcd(21,0) = 21 __gcd(21,0)=21

17.__lg(a)

求一个数二进制下最高位位于第几位(从第0位开始)(或二进制数下有几位)

_ _ l g ( 8 ) = 3 \_\_lg(8) = 3 __lg(8)=3

_ _ l g ( 15 ) = 3 \_\_lg(15) = 3 __lg(15)=3


如果你有任何想要补充的函数,欢迎评论留言补充呀!

往期优质文章推荐

  • C++ STL详解,超全总结(快速入门STL)
  • 【期末复习】c++知识点大回顾,八篇文章让你永不破防(一)
  • 区间贡献问题习题详解

如果我的文章对你有帮助,欢迎点赞+评论+关注

欢迎微信搜索『行码棋』同名公众号,点击『获取资源』领取大量资源哦。

你可能感兴趣的