华师一附中OI组

标题: STL常用函数 [打印本页]

作者: admin 时间: 2019-10-28 11:07
标题: STL常用函数
1、sort
2、memset memcpy memmove
3、upbounder
4、kth
5、容器，迭代器 set map vector stack queue priority_queue

作者: admin 时间: 2019-10-28 11:18
在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>); ///注意

对于第三个参数，我们也可以自己定义比较模式，这样更清晰，比如

int A[100];
bool cmp(int a,int b)//int为数组数据类型
{
return a>b;//降序排列这里可千万不要用<=!!!
//return a<b;//默认的升序排列
}
sort(A,A+100,cmp);

复制代码

结构体可以这样做：

Student Stu[100];
bool cmp(Student a,Student b)
{
return a.id>b.id;//按照学号降序排列
//return a.id<b.id;//按照学号升序排列
}
sort(Stu,Stu+100,cmp);

复制代码

也可以在结构体里面重载<运算符，（只能是<，因为默认是有小到大）

typedef struct Student
{
int id;
string name;
double grade;
bool operator<(const Student& s)
{
return id>s.id;//降序排列
//return id<s.id;//升序排列
}
};
vector<Student> V;
sort(V.begin(),V.end());

复制代码

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

作者: admin 时间: 2019-10-28 11:47
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)处插入新的数值。

for (i=1; i<=10; i++)
{
cin>>x;
///找到第一个大于x的a[j]
for(j=1; (a[j]<x && j<i); j++) ;
cout<<j<<" ";
memcpy(a+j+1,a+j,(i-j)*sizeof(a[1])); ///把a[j]到a[i]的数都往后挪一格
a[j]=x;
}

复制代码

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

作者: admin 时间: 2019-11-4 00:46
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。

sort (a,a+8); // 10 10 10 20 20 20 30 30
bool b=binary_search(a,a+8,15);
cout<<b<<endl; ///没有找到
int x,y;
x=lower_bound(a,a+8,20)-a;
y=upper_bound(a,a+8,20)-a;
cout<<x<<' '<<y<<endl; ///找到了
x=lower_bound(a,a+8,15)-a;
y=upper_bound(a,a+8,15)-a;
cout<<x<<' '<<y<<endl; ///找不到

复制代码

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

作者: admin 时间: 2019-11-5 11:26
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做的三连击

#include<iostream>
#include<set>
using namespace std;
int x,xx,xxx,y;
set <int > s;
int main()
{
for (x=100; x<=1000/3; x++) ///枚举
{
xx=x+x,xxx=xx+x;///生成
/// 判断
s.clear();/// 清零，和数组一样
y=x/100%10,s.insert(y);
y=x/10%10,s.insert(y);
y=x/1%10,s.insert(y);
y=xx/100%10,s.insert(y);
y=xx/10%10,s.insert(y);
y=xx/1%10,s.insert(y);
y=xxx/100%10,s.insert(y);
y=xxx/10%10,s.insert(y);
y=xxx/1%10,s.insert(y);
s.erase(0);///0不上算
if (s.size()==9) ///数目检查
cout<<x<<' '<<xx<<' '<<xxx<<endl;
}
return 0;
}

复制代码

作者: admin 时间: 2019-11-5 11:29
map就牛逼了，一般用在非连续的数据的统计，比如广搜记录出现的最短路。可以简略类似数组那样写m[xx]=yy的样子。
比如，输入一个句子，统计其中每个单词出现的次数。

#include <bits/stdc++.h>
using namespace std;
map<string , int > M;
map<string, int>::iterator it;
int i,j,x;
string str,s;
int main ()
{
getline(cin,str);
int l=str.size();
for (i=0; i<=l-1; i++)if (str[i]>='a' && str[i]<='z') str[i]=str[i]-'a'+'A'; ///小写转大写
for (i=0,s=""; i<=l-1; i++)
if (str[i]>='A' && str[i]<='Z') s+=str[i];
else
{
M[s]++;
s="";
}
M.erase(""); ///空格可能被加入
cout<<M.size()<<endl;
for (it=M.begin(); it!=M.end(); it++)
cout<<it->first<<' '<<it->second<<endl;
return 0;
}

复制代码

与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的函数

欢迎光临华师一附中OI组 (http://hsyit.cn/)