STL常用函数

admin

1、sort
2、memset memcpy memmove
3、upbounder
4、kth
5、容器，迭代器  set  map vector stack queue priority_queue

admin

在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. 
   
7.         bool operator<(const Student& s)
   
8.         {
   
9.                 return id>s.id;//降序排列
   
10.         //return id<s.id;//升序排列
    
11.         }
    
12. };
    
13. vector<Student> V;
    
14. sort(V.begin(),V.end());

复制代码

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

admin

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库里面，注意要加上相应的头文件。

admin

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;  ///找不到

复制代码

admin

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

admin

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. }

复制代码

admin

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