华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1694|回复: 6
打印 上一主题 下一主题

STL常用函数

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2019-10-28 11:07:30 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
1、sort
2、memset memcpy memmove
3、upbounder
4、kth
5、容器,迭代器  set  map vector stack queue priority_queue
回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2019-10-28 11:18:47 | 只看该作者
在STL中最常用的可能是sort了,sort函数在algorithm库中,标准的格式是sort(a,a+n,cmp)

该函数可以给数组,或者链表list、向量排序。它对普通的快速排序进行了优化,此外,它还结合了插入排序和推排序。系统会根据你的数据形式和数据量自动选择合适的排序方法,平均情况下很快的。

此函数有3个参数:

参数1:第一个参数是数组的首地址,一般写上数组名就可以,因为数组名是一个指针常量。

参数2:第二个参数相对较好理解,即首地址加上数组的长度n(代表尾地址的下一地址)。

参数3:默认可以不填,如果不填sort会默认按数组升序排序。也就是1,2,3,4排序。也可以自定义一个排序函数,改排序方式为降序什么的,也就是4,3,2,1这样。

典型应用:
把int数组a里面的a[0]-a[n-1]升序排列 : sort(a,a+n);  省略了第三个参数
把int数组a里面的a[1]-a[n]升序排列 : sort(a+1,a+n+1);  
把int数组a里面的a[1]-a[n]降序排列 : sort(a+1,a+n+1,great<int>);
把long long 数组a里面的a[1]-a[n]降序排列 : sort(a+1,a+n+1,great<long long>); ///注意

对于第三个参数,我们也可以自己定义比较模式,这样更清晰,比如
  1. int A[100];
  2. bool cmp(int a,int b)//int为数组数据类型
  3. {
  4.   return a>b;//降序排列  这里可千万不要用<=!!!
  5.   //return a<b;//默认的升序排列
  6. }
  7. sort(A,A+100,cmp);
复制代码


结构体可以这样做:
  1. Student Stu[100];
  2. bool cmp(Student a,Student b)
  3. {
  4.   return a.id>b.id;//按照学号降序排列
  5.   //return a.id<b.id;//按照学号升序排列
  6. }
  7. sort(Stu,Stu+100,cmp);
复制代码


也可以在结构体里面重载<运算符,(只能是<,因为默认是有小到大)
  1. typedef struct Student
  2. {
  3.         int id;
  4.         string name;
  5.         double grade;

  6.         bool operator<(const Student& s)
  7.         {
  8.                 return id>s.id;//降序排列
  9.         //return id<s.id;//升序排列
  10.         }
  11. };
  12. vector<Student> V;
  13. sort(V.begin(),V.end());
复制代码



sort是不稳定的排序,要是想稳定的排序,可以使用stable_sort 或者在结构体里面加上第二第三关键字的比较。
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
 楼主| 发表于 2019-10-28 11:47:21 | 只看该作者
memset:在一块内存块中按字节填充某个给定的值,它是对较大的结构体或数组进行清零操作的一种最快方法。
格式memset(a,b,c)  其中a是数组名或者是指针值表示填充的首地址,b是要填充的字节值,c是填充的数量。
比如要把int a数组a[0]-a[n-1],全部填上0:memset(a,0,sizeof(a));
比如要把int a数组a[0]-a[n-1],全部填上1:memset(a,1,sizeof(a)); 想一想,现在要是输出a数组,里面的元素会是几?
比如要把int a数组a[0]-a[n-1],全部填上很大的数:memset(a,0X7F,sizeof(a)); 也有人喜欢用0X3F,避免相加之后溢出。
比如要把int a数组a[0]-a[n-1],全部填上很小的数:memset(a,0XFF,sizeof(a));
填充主要是1,3,4三种模式,其他模式要千万小心。


memcpy:从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。格式memcpy(dest,src,n)注意地址不要重叠,否则会有莫名问题。要是有部分重叠的话,可以改用memmove。int a[100],b[100];
memcpy(a,b,sizeof(a))   把a数组复制给b数组,相当于PASCAL中的b=a;
插入排序中把a(i)到a(j)的数整体右挪一格然后在a(i)处插入新的数值。
  1.         for (i=1; i<=10; i++)
  2.                 {
  3.                         cin>>x;
  4.                         ///找到第一个大于x的a[j]
  5.                         for(j=1; (a[j]<x && j<i); j++) ;
  6.                         cout<<j<<"   ";
  7.                         memcpy(a+j+1,a+j,(i-j)*sizeof(a[1])); ///把a[j]到a[i]的数都往后挪一格
  8.                         a[j]=x;
  9.                 }
复制代码

这三个函数都在cstring库里面,注意要加上相应的头文件。

回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
地板
 楼主| 发表于 2019-11-4 00:46:28 | 只看该作者
upper_bound(),lower_bound(),equal_range(),binary_search()四个函数都是二分查找相关的,必须在容器元素有序的情况下使用,默认cmp由小到大。

binary_search(first,last,key,cmp):返回值是一个布尔值,如果返回true,那么就说明在某个容器中出现了键值等于key的元素,false则反之。;若你想获得更多的信息(例如该元素在容器中的位置),那么你可以使用lower_ bound或upper_bound实现该功能。cmp指定了比较方式,first和last是上下界,key是待查的关键字。

upper_bound(first,last,key,cmp) 得到a[x]和a[y-1]中>=k的第一个元素的指针,如果不存在这样的元素,则得到y。

lower_bound:重点要说的一个函数。这个函数的返回值是键值>=的第一个元素,其实这个函数可以在查找某个值的时候用,效率是很高的。lower_bound(first,last,key,compare)。

equal_range:查找等于key的键值的范围,例如有序列:1 3 4 4 4 5 7 7 9,假如我们调用equal_range查找4出现的范围,那么函数的返回值就是:3 5(在位置3到位置5出现了3个4)。不过要注意一点,equal_range的返回值是一个pair。


  1.     sort (a,a+8); // 10 10 10 20 20 20 30 30
  2.     bool b=binary_search(a,a+8,15);
  3.     cout<<b<<endl;  ///没有找到
  4.     int x,y;
  5.         x=lower_bound(a,a+8,20)-a;
  6.     y=upper_bound(a,a+8,20)-a;
  7.     cout<<x<<' '<<y<<endl;  ///找到了
  8.          
  9.         x=lower_bound(a,a+8,15)-a;
  10.     y=upper_bound(a,a+8,15)-a;
  11.     cout<<x<<' '<<y<<endl;  ///找不到
复制代码


回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
5#
 楼主| 发表于 2019-11-5 11:04:38 | 只看该作者
在C++里组织大规模数据一般首选数组,很是直观,但是对于某些操作来说,效率很低,比如插入,查找,删除等。C++为此提供了丰富的容器来装数据,常用的有vector list dequeue string stack set等。这里先介绍下vector
vector是顺序存放数据的,所以在前面和后面插入都很快,
list是双向链表,
dequeue是双端队列,
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
6#
 楼主| 发表于 2019-11-5 11:26:25 | 只看该作者
set是集合类型,里面数据是按红黑树结构存放的,所以查找删除的效率都很高。

begin()        ,返回set容器的第一个元素
end()      ,返回set容器的最后一个元素
clear()          ,删除set容器中的所有的元素
empty()    ,判断set容器是否为空
max_size()   ,返回set容器可能包含的元素最大个数
size()      ,返回当前set容器中的元素个数
rbegin     ,返回的值和end()相同
rend()     ,返回的值和rbegin()相同

insert(key_value); 将key_value插入到set中 ,返回值是pair<set<int>::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。

erase(iterator)  ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值

find()  ,返回给定值值得定位器,如果没找到则返回end()。


inset(first,second);将定位器first到second之间的元素插入到set中,返回值是void.


lower_bound(key_value) ,返回第一个大于等于key_value的定位器
upper_bound(key_value),返回最后一个大于key_value的定位器


set一般用来判断重复,看看set做的三连击
  1. #include<iostream>
  2. #include<set>
  3. using namespace std;
  4. int x,xx,xxx,y;
  5. set <int > s;
  6. int main()
  7. {
  8.         for (x=100; x<=1000/3; x++)  ///枚举
  9.                 {
  10.                         xx=x+x,xxx=xx+x;///生成
  11.                         /// 判断
  12.                         s.clear();/// 清零,和数组一样
  13.                         y=x/100%10,s.insert(y);
  14.                         y=x/10%10,s.insert(y);
  15.                         y=x/1%10,s.insert(y);
  16.                         y=xx/100%10,s.insert(y);
  17.                         y=xx/10%10,s.insert(y);
  18.                         y=xx/1%10,s.insert(y);
  19.                         y=xxx/100%10,s.insert(y);
  20.                         y=xxx/10%10,s.insert(y);
  21.                         y=xxx/1%10,s.insert(y);
  22.                         s.erase(0);///0不上算
  23.                         if (s.size()==9)  ///数目检查
  24.                                 cout<<x<<' '<<xx<<' '<<xxx<<endl;
  25.                 }
  26.         return 0;
  27. }
复制代码


回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
7#
 楼主| 发表于 2019-11-5 11:29:36 | 只看该作者
map就牛逼了,一般用在非连续的数据的统计,比如广搜记录出现的最短路。可以简略类似数组那样写m[xx]=yy的样子。
比如,输入一个句子,统计其中每个单词出现的次数。
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. map<string , int > M;
  4. map<string, int>::iterator it;
  5. int i,j,x;
  6. string str,s;
  7. int main ()
  8. {
  9.         getline(cin,str);
  10.         int l=str.size();
  11.         for (i=0; i<=l-1; i++)if (str[i]>='a' && str[i]<='z') str[i]=str[i]-'a'+'A'; ///小写转大写
  12.         for (i=0,s=""; i<=l-1; i++)
  13.                 if (str[i]>='A' && str[i]<='Z')  s+=str[i];
  14.                 else
  15.                         {
  16.                                 M[s]++;
  17.                                 s="";
  18.                         }
  19.         M.erase(""); ///空格可能被加入
  20.         cout<<M.size()<<endl;
  21.         for (it=M.begin(); it!=M.end(); it++)
  22.                 cout<<it->first<<' '<<it->second<<endl;
  23.         return 0;
  24. }
复制代码

与set相关的那些函数map基本也都能用    
       begin()          返回指向map头部的迭代器
  clear()         删除所有元素
      count()          返回指定元素出现的次数
      empty()          如果map为空则返回true
      end()            返回指向map末尾的迭代器
      equal_range()    返回特殊条目的迭代器对
      erase()          删除一个元素
      find()           查找一个元素
      insert()         插入元素
      key_comp()       返回比较元素key的函数
      lower_bound()    返回键值>=给定元素的第一个位置
      max_size()       返回可以容纳的最大元素个数
      rbegin()         返回一个指向map尾部的逆向迭代器
      rend()           返回一个指向map头部的逆向迭代器
      size()           返回map中元素的个数
      swap()            交换两个map
      upper_bound()     返回键值>给定元素的第一个位置
      value_comp()      返回比较元素value的函数



回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 12:30 , Processed in 0.145768 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表