本文归纳总结刷题常用到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)删除区间元素 )str.erase(first_iter, last_iter)//删除迭代器[first,second)之间的元素
)str.erase(pos,length)//删除下标pos开始的长度为length的区间元素
3.截取字符串 string newstr = str.substr(pos,length)//截取从下标pos开始的长度为length的子串
4.查找操作 )str.find(str2)//如果str2是str的子串，则返回str2在str中首次出现的位置；否则，返回string::npos，这个值是-1
)str.find(str2,pos)//从str下标为pos的位置开始匹配sr2
注意，如果我在字符串str="3.1415"中查询小数点出现的位置，应该写成 str.find(".") 而不是 str.find('.') ，后者查找的是char型字符，而不是string型，是没有这种写法的！
5.字符串转数字函数 stoi() ， 如string str="，可以int val=stoi(str);
6.string类型支持下标访问和迭代器访问，不过一般就用下标[]访问，和C的写法一样，不说了。另外，C++11之后，如果要完整遍历一个string，还可以用下面的写法。
简单示例：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
//string对象的创建
string str1("aaa");
string str2="bbb";
]="hello";
string str3(buf);//这种初始化方法我一开始还以为不可以的呢。
cout<<str1<<' '<<str2<<' '<<str3<<endl<<endl;
//insert
string s="kill PAT";
cout<<"before insert: "<<s<<endl<<endl;
s.insert(,"fucking ");//在原序列s[5]处插入
cout<<"after insert: "<<s<<endl<<endl;
//遍历
for(auto ch:s)
cout<<ch;
cout<<endl<<endl;
//erase
string s2="James go to Lakers Q";
cout<<s2<<endl;
s2.erase(s2.end()-);//删除Q
cout<<s2<<endl;
s2.erase(s2.begin(),s2.begin()+);
cout<<s2<<endl;
s2.erase(,);
cout<<s2<<endl<<endl;
//substr
string s3="James go to Lakers Q";
,)+" NB";
cout<<subStr<<endl<<endl;
//find
cout<<s3.find(
cout<<s3.find()<<endl;
if(s3.find(".")==string::npos) cout<<"Not find\n";//或写成数s3.find(".")==-1
else cout<<"Found\n";
;
}
此外，可以通过sstream流把非string型的数据转换成string型，即实现一种将各种不同的类型变量拼接成字符串的功能（同sprintf()函数）。功能强大，比如下面的示例，把int型，空格，string型，和char型写进了ostringstream流里，最终拼接成了string型输出。
#include <iostream>
#include <string>
#include <sstream>//string流
using namespace std;
int main()
{
ostringstream oss;
;
string str = "James";
char ch = 'X';
oss << a <<" "<< str << ch;
string newStr = oss.str();
cout << newStr << '\n';//23 JamesX
;
}
但是在刷题时，用string流的写法来进行字符串拼接是不明智的，如有必要应该选用sprintf()，
1.该函数包含在stdio.h的头文件中；
2.sprintf与printf函数二者功能相似，但是sprintf函数打印到字符串中，而printf函数打印输出到屏幕上。sprintf函数在把其他数据类型转换成字符串类型的操作中应用广泛。
3.sprintf函数的格式： int sprintf( char *buffer, const char *format [, argument,...] );
3.sprintf函数的格式： int sprintf( char *buffer, const char *format [, argument,...] );
其基本写法如下：
#include <cstdio>
int main()
{
];
,b=;
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);
;
}
【vector】这个是用的最多的，基本就拿来当数组来用。不过要稍微讲一下二维数组的提前申请空间，如下：
int main()
{
vector<vector<int>> matrix;//假设这是一个4*3的矩阵
,col=;
matrix.resize(row);
;i<matrix.size();i++)
matrix[i].resize(col);
//接下来就可以用下标运算访问了
matrix[][]=;
matrix[][]=;
;i<matrix.size();i++){
;j<matrix[i].size();j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
;
}
【map &&unordered_map】分别在头文件<map>和<unordered_map>中，别混了。
这两个刷题时用的也非常多，其中map的底层实现是RB-Tree，因此会根据键值自动进行排序，默认是字典序。而unordered_map的底层实现是哈希。因此，如果只是单纯的用来创建某种映射关系的话，推荐用unordered_map，效率会高一些。不过在PAT中，我试了一下，两者耗时没什么差别，如果某道题用map会超时，那么用unordered_map也会超时，这个时候要想想字符串哈希了！这里只讲一下我不熟悉的写法，如下：
#include <cstdio>
#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
using namespace std;
int main()
{
//完全可以当做二维数组int matrix[a][b]来使用，表示a与b的某种映射关系。
//而且键值可正可负，没有约束
unordered_map<int,unordered_map<int,bool>> mp;
mp[][-]=true;
mp[][]=true;
printf(][-]);
printf(][]);
printf(][]);//默认值是0
map<string,int> strToInt;
//三种创建map<..,..>对象的方式
strToInt.insert({});
strToInt.insert(make_pair());
strToInt.insert(pair<));
//迭代器遍历，发现输出顺序已经根据键值自动排序了，而不是插入时的顺序
for(map<string,int>::iterator it=strToInt.begin();it!=strToInt.end();it++)
printf("%s %d\n",it->first.c_str(),it->second);//注意这里是->运算符
printf("\n");
//删除
strToInt.erase("aaa");
//C++11的写法，当然选用这种啦！
for(auto it:strToInt)
printf("%s %d\n",it.first.c_str(),it.second);//这里是.运算符
;
}
【set】常用于自动排序，去重。当容器内存放的元素是结构体时，要自定义排序规则。
#include <iostream>
#include <set>
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(,);
Node node2(,);
Node node3(,);
Node node4(,);
Node node5(,);
set<Node> mySet={node1,node2,node3,node4,node5};
//迭代器遍历
for(set<Node>::iterator it=mySet.begin();it!=mySet.end();it++)
cout<<it->id<<' '<<(*it).score<<'\n';//迭代器it就是个指针，所以可以用->，或先解引用*再用.
//auto 遍历
for(auto it:mySet)
cout<<it.id<<' '<<it.score<<'\n';
;
}
【priority_queue】优先队列常用在需要动态的找到某个序列的最大/小值，比如贪心问题；也可以对Dijkstra算法进行优化。使用优先队列需要知道，队列内元素的优先级是如何定义的。
(1).基本数据类型的优先级设置
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
//默认情况按降序排列(大顶堆)，较大的数优先级较高
//下面两种方式等价
//priority_queue<int,vector<int>,less<int> > q1;
priority_queue<int> q1;
q1.push();
q1.push();
q1.push();
q1.push();
while(!q1.empty()){
cout<<q1.top()<<' ';//5 3 3 1
q1.pop();
}
cout<<"\n"<<"\n";
//greater 让较小的数优先级较大
priority_queue<int,vector<int>,greater<int> > q2;
q2.push();
q2.push();
q2.push();
q2.push();
while(!q2.empty()){
cout<<q2.top()<<' ';// 1 3 3 5
q2.pop();
}
;
}
(2).结构体类型的优先级设置
#include <cstdio>
#include <queue>
#include <vector>
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(,);
Node node2(,);
Node node3(,);
Node node4(,);
Node node5(,);
vector<Node> vec={node1,node2,node3,node4,node5};
priority_queue<Node> q;
;i<vec.size();i++)
q.push(vec[i]);
while(!q.empty()){
Node node=q.top();
q.pop();
printf("%d %d\n",node.id,node.score);
}
;
}