本文归纳总结刷题常用到STL容器以及一些标准算法，主要包括：

string、vector、map、pair、unordered_map、set、queue、priority_queue、stack，以及这些容器的常用操作，如插入、删除、查找、访问方式（迭代器or下标，C++11关键字auto了解吗？顺序访问or随机访问）、初始化等。最后介绍头文件<algorithm>下的几个常用函数，尤其是sort。

【string】C++字符串类型

1.插入操作 str.insert(pos,str);//在下标pos处插入字符串str 

2.删除操作

(1)删除单个元素 

str.erase(iter);//删除迭代器iter指定的元素 

(2)删除区间元素 

1)str.erase(first_iter, last_iter)//删除迭代器[first,second)之间的元素

                   　 

2)str.erase(pos,length)//删除下标pos开始的长度为length的区间元素 

3.截取字符串 string newstr = str.substr(pos,length)//截取从下标pos开始的长度为length的子串 

4.查找操作 

1)str.find(str2)//如果str2是str的子串，则返回str2在str中首次出现的位置；否则，返回string::npos，这个值是-1 

　　　　　 

2)str.find(str2,pos)//从str下标为pos的位置开始匹配sr2 

注意，如果我在字符串str="3.1415"中查询小数点出现的位置，应该写成 

str.find(".") 而不是 

str.find('.') ，后者查找的是char型字符，而不是string型，是没有这种写法的！

5.字符串转数字函数 stoi() ， 如string str="123"，可以int val=stoi(str); 

6.string类型支持下标访问和迭代器访问，不过一般就用下标[]访问，和C的写法一样，不说了。另外，C++11之后，如果要完整遍历一个string，还可以用下面的写法。

简单示例：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int main(){    //string对象的创建    string str1("aaa");    string str2="bbb";    char buf[10]="hello";    string str3(buf);//这种初始化方法我一开始还以为不可以的呢。    cout<
           
            <<' '<
            
             <<' '<
             
              <
              
               <
              
             
            
           
          
         
        
       

此外，可以通过sstream流把非string型的数据转换成string型，即实现一种将各种不同的类型变量拼接成字符串的功能（同sprintf()函数）。功能强大，比如下面的示例，把int型，空格，string型，和char型写进了ostringstream流里，最终拼接成了string型输出。

#include 
       
        #include 
        
         #include 
         
          //string流using namespace std;int main(){    ostringstream oss;    int a = 23;    string str = "James";    char ch = 'X';    oss << a <<" "<< str << ch;    string newStr = oss.str();    cout << newStr << '\n';//23 JamesX    return 0;}
         
        
       

 

但是在刷题时，用string流的写法来进行字符串拼接是不明智的，如有必要应该选用sprintf()，

1.该函数包含在stdio.h的头文件中；

2.sprintf与printf函数二者功能相似，但是sprintf函数打印到字符串中，而printf函数打印输出到屏幕上。sprintf函数在把其他数据类型转换成字符串类型的操作中应用广泛。

3.sprintf函数的格式： 

int sprintf( char *buffer, const char *format [, argument,...] ); 

其基本写法如下：

#include 
       
        int main(){    char buf[100];    int a=422,b=100;    double pi=3.1415926;    int len=sprintf(buf,"%d %d %.2f",a,b,pi);//将不同数值进行拼接，返回的len相当于strlen(buf)    printf("len:%d, %s\n",len,buf);    const char* str1="kill";    const char* str2="the fucking PAT";    sprintf(buf,"%s %s",str1,str2);//将两个字符串进行拼接    printf("%s\n",buf);    char ch='A';    sprintf(buf,"I got %d in %s %c",b,str2,ch);//同时将多种不同类型的数据进行拼接    printf("%s\n",buf);    return 0;}
       

 

【vector】这个是用的最多的，基本就拿来当数组来用。不过要稍微讲一下二维数组的提前申请空间，如下：

int main(){    vector
       
        
         > matrix;//假设这是一个4*3的矩阵    int row=4,col=3;    matrix.resize(row);    for(int i=0;i
        
       

 

【map &&unordered_map】分别在头文件<map>和<unordered_map>中，别混了。

这两个刷题时用的也非常多，其中map的底层实现是RB-Tree，因此会根据键值自动进行排序，默认是字典序。而unordered_map的底层实现是哈希。因此，如果只是单纯的用来创建某种映射关系的话，推荐用unordered_map，效率会高一些。不过在PAT中，我试了一下，两者耗时没什么差别，如果某道题用map会超时，那么用unordered_map也会超时，这个时候要想想字符串哈希了！这里只讲一下我不熟悉的写法，如下：

#include 
       
        #include 
        
         #include 
         
        
       

 

【set】常用于自动排序，去重。当容器内存放的元素是结构体时，要自定义排序规则。

#include 
       
        #include 
        
         using namespace std;struct Node{    int id;    int score;    //构造函数    Node(int id_,int score_):id(id_),score(score_){}    //重载运算符    //按照成绩从高到低排序，若成绩相同，则按学号升序排列    bool operator <(const Node rhs) const {
     //必须加上这两个const        if(this->score != rhs.score) return this->score > rhs.score;        else return this->id < rhs.id;    }};int main(){    Node node1(1012,90);    Node node2(1005,90);    Node node3(1010,79);    Node node4(1001,96);    Node node5(1017,86);    set
         
           mySet={node1,node2,node3,node4,node5};    //迭代器遍历            for(set
          
           ::iterator it=mySet.begin();it!=mySet.end();it++)        cout<
           
            id<<' '<<(*it).score<<'\n';//迭代器it就是个指针，所以可以用->，或先解引用*再用.    //auto 遍历        for(auto it:mySet)        cout<
            
             <<' '<
             
              <<'\n'; return 0;}
             
            
           
          
         
        
       

 

【priority_queue】优先队列常用在需要动态的找到某个序列的最大/小值，比如贪心问题；也可以对Dijkstra算法进行优化。使用优先队列需要知道，队列内元素的优先级是如何定义的。

(1).基本数据类型的优先级设置

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int main(){    //默认情况按降序排列(大顶堆)，较大的数优先级较高    //下面两种方式等价    //priority_queue
           
            
             ,less
             
               > q1; priority_queue
              
                q1; q1.push(3); q1.push(1); q1.push(3); q1.push(5); while(!q1.empty()){ cout<
               
                <<' ';//5 3 3 1 q1.pop(); } cout<<"\n"<<"\n"; //greater 让较小的数优先级较大 priority_queue
                
                 
                  ,greater
                  
                    > q2; q2.push(3); q2.push(1); q2.push(3); q2.push(5); while(!q2.empty()){ cout<
                   
                    <<' ';// 1 3 3 5 q2.pop(); } return 0; }
                   
                  
                 
                
               
              
             
            
           
          
         
        
       

(2).结构体类型的优先级设置

#include 
       
        #include 
        
         #include 
         
          using namespace std;struct Node{    int id;    int score;    //构造函数    Node(int id_,int score_):id(id_),score(score_){}    //重载运算符    //按照成绩从高到低排序，若成绩相同，则按学号升序排列    //注意，这里的"<",">"符号和前面set自定义排序的时候相反！        bool operator <(const Node rhs) const {        if(this->score != rhs.score) return this->score < rhs.score;        else return this->id > rhs.id;    }};int main(){    Node node1(1012,90);    Node node2(1005,90);    Node node3(1010,79);    Node node4(1001,96);    Node node5(1017,86);    vector
          
            vec={node1,node2,node3,node4,node5};    priority_queue
           
             q;    for(int i=0;i