C++STL
1.vector
向量，长度可变的数组
头文件
#include<vector>
1.1vector的定义
vector<typename> name;
例如：
vector<int> name;
如果typename是vector
vector<vector<int>>name;
相当于二维数组
vector<typename> ArrayName[arraySize];
例如：
vector<int> vi[100];
1.2vector容器内元素的访问
（1）通过下标访问
vi[index];
（2）通过迭代器访问
vector<typename>：：iterator it;
例如：
vector<int>::iterator it;
有上下文环境时，可以直接用 auto it=vi.begin();
例如：
for(auto it=vi.begin();it!=vi.end();it++)
printf(“%d”,*it);
注：vi.begin()和vi.end()左闭右开。
1.3vector常用函数
（1）push_back()
在末尾添加一个元素。
vi.push_back(i);
（2）pop_back()
删除一个尾元素。
vi.pop_back();
（3）size()
返回vector元素的个数，注意是unsigned类型。
vi.size();
（4）clear()
清空vector中所有的元素。
vi.clear();
（5）insert()
insert(it,x)在迭代器it前插入一个元素x。
vi: 1 2 3 4 5
vi.insert(vi.begin()+2,-1);
vi:1 2 -1 3 4 5
（6）erase()
1.删除单个元素
vi:5 6 7 8 9
vi.erase(vi.begin()+3)
vi:5 6 7 9
2.删除一个区间内的所有元素
erase[first,last); 左闭右开
vi:5 6 7 8 9
vi.erase(vi.begin()+1,vi.begin+4)
vi:5 9
2.set
集合，一个内部自动有序且不含重复元素的容器
头文件
#include<set>
2.1 set的定义
set<typename> name;
例如：
set<int> name;
set数组
set<typename>ArrayName[arraySize];
例如：
set<int> a[100];
2.2set容器内 元素的访问
set只能用迭代器访问
set<typename>::iterator it;
例如：
set<int>::iterator it;
set<int> st;
for(auto it=st.begin();it!=st.end();it++)
print(“%d”,*it);
st:2 3 5
set元素自动递增排序，且自动去除重复元素。
注意：不能用it<st.end();
除了vector和string容器外不能用*(it+i)
2.3set常用函数
（1）insert()
insert(x)将x插入set容器中，并自动递增排序和去重。
st.insert(x)
（2）find()
find(value)返回set中对应值为value的迭代器。
set<int>::iterator it = st.find(2);
（3）erase()
1.删除单个元素
st.erase(it); //it 为迭代器
st.erase(find(100));
st.erase(value)，value 为所要删除元素的值。
st.erase(100);
2.删除区间内所有元素
erase[first,last); 左闭右开
st.erase(first,last);
st.erase(it,st.end());
（4）size()
返回set内元素的个数，unsigned类型
（5）clear()
清空set内所有的元素
3.string
字符串数组
3.1 string 的定义
string str=”abcd”;
3.2string容器内元素的访问
（1）通过下标访问
str[index];
输出str
cout<<str;
printf(“%s”,str.c_str());
（2）通过迭代器访问
string迭代器不需要参数
string::iterator it;
for(it=str.begin();it!=str.end();it++)
printf(“%c”,*it);
3.3string 常用函数
（1）operator+=
str1+=str2;
（2）compare operator
可直接使用 == ,!=,<=,<,>,>=比较大小，比较规则是字典序
（3）length()/size()
返回字符串长度，两者基本相同。
（4）insert()
1.insert(pos.string);
在pos号位置插入字符串string
string str1=”abcxyz”;
string str2=”opq”;
str1.insert(3,str2);
str1:abcopqxyz
2.insert(it,it2,it3); //it为原字符串待插入位置，it2，it3位待插入字符串首尾迭代器。[it2,it3) 左开右闭
string str1=”abcxyz”;
string str2=”opq”;
str1.insert(str1.begin()+3,str2.begin(),str2.end())
str1:abcopqxyz
（5）erase()
1.删除单个元素
str.erase(it) //it为所要删除元素位置的迭代器
2.删除一个区间内的所有元素
(1)str.erase(first,last); [first,last)左开右闭
string str=”abcdefg”;
str.erase(str.begin()+2,str.end()-1);
str:abg
(2)str.erase(pos,length);
pos为起始位置，删除后面长度为length的字符串。
string str=”abcdefg”;
str.erase(3,2);
str:abcfg
（6）clear()
str.clear(); 清空字符串
（7）substr()
substr(pos,len); 返回从pos号位开始、长度为len的子串。
string str=”Thank you for your smile”;
str.substr(0,5);
Thank
str.substr(14,4);
your
str.substr(19,5);
smile
（8）string::npos
string::npos是一个常数，其本身值为-1，unsigned_int类型，作为find函数失配时的返回值。
（9）find()
str1.find(str2); 当str2是str1的子串时，返回str2在str1中第一次出现的位置；如果str2不是str1的子串，返回string：：npos。
str1.find(str2,pos); 从str1的pos号位开始匹配str2，返回值与上文相同。
string str1=”Thank you for your smile”;
string str2=”you”;
string str3=”me”;
cout<<str1.find(str2);
6
cout<<str1.find(str2,7);
14
（10）replace()
1.str1.replace(pos,len,str2); 把str1从pos号位开始、长度为len的子串替换为str2.
2.str1.replace(it1,it2,str2); 把str1的迭代器[it1,it2)范围的子串替换成str2.
string str1=”Maybe you will turn around”;
string str2=”will not”;
striing str3=”surely”;
cout<<str1.replace(10,4,str2);
Maybe you will not turn around
cout<<str1.replace(str1.begin(),str1.begin()+5,str3);
surely you will not turn around
4.map
映射，map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。
例如：
字符串-->页码。
头文件
#include<map>
4.1 map的定义
map<typename1,typename2> mp;
map<key,value> mp;
map<int,int> mp 相当于普通的int型数组。
如果是字符串到整型的映射，必须用string，不能用char数组。
map<string,int> mp;
map的键和值也可以是STL容器。
例如:
map<set<int>,string> mp;
4.2 map容器内元素的访问
1.通过下标访问
与访问普通数组一样，例如
map<char,int> mp;
mp[‘c’]来访问它对应的整数。
mp[‘c’]=20;
注：map的键值是唯一的。
2.通过迭代器访问
map<typename1,typename2>::iterator it;
用it->first访问键
用it->second访问值
map<char,int>mp;
mp[‘m’]=20;
mp[‘r’]=30;
mp[‘a’]=40;
for(auto it=mp.begin();it!=mp.end();it++)
printf(“%c %d\n”,it->first,it->second);
map会按键值从小到大自动排序。
4.3 map常用函数
（1）find()
find(key)返回键值为key的映射的迭代器。
auto it = mp.find(‘c’);
（2）erase()
1.删除单个元素。
mp.erase(it); it为迭代器。
mp.erase(key); key为欲删除的映射的键。
2.删除一个区间内的所有元素。
map.erase(first，last) [first,last) 删除迭代器区间，左闭右开。
（3）size()
返回map中映射的对数。
（4）clear()
清空map中所有的元素。
5.queue
队列，一个先进先出的容器。
头文件
#include<queue>
5.1 queue的定义
queue<typename> name;
5.2 queue 容器内元素的访问
queue是一种先进先出的限制访问的数据结构。
只能front()访问队首元素，back()访问队尾元素。
queue<int> q;
q.front();
q.back();
//
5.3 queue 常用函数
（1）push()
q.push(x)将x进行入队
（2）front() / back()
访问队首和队尾元素。
（3）pop()
q.pop()令队首元素出队。
（4）empty()
检测queue是否为空，返回true为空，返回false则非空。
（5）size()
返回queue内元素的个数。
5.4 queue常见用途
例如广度优先搜索。
6.priority_queue
优先队列，底层用堆来实现。在优先队列中，队首元素是当前队列中优先级最高的一个。
头文件
#include<queue>
6.1 priority_queue的定义
priority_queue<typename> name;
6.2 priority_queue 容器内元素的访问
只能用q.top()函数访问。
6.3 priority_queue 常用函数
（1）push()
q.push(x)将x入队。
（2）top()
q.top()可以获得队首元素。
（3）pop()
令队首元素（堆顶元素）出队。
q.pop();
（4）empty()
检测优先队列是否为空，为空则返回true，返回false为空。
（5）size()
返回优先队列内元素的个数。
6.4 priority_queue内元素优先级的设置
1.基本数据类型的优先级设置
基本数据类型指int、double、char型等数据类型。
下面两种优先队列的定义是等价的。
priority_queue<int> q;
priority_queue<int,vector<int>,less<int> > q;
vector<int> 是来承载底层数据结构堆（heap）的容器，而less<int>是比较类。
less<int> 表示数字大的优先级越大，而greater<int>表示数字小的优先级越大。char类型按字典序。
2.结构体的优先级设置
需要重载比较符号。
例如：
struct fruit{
string name;
int price;
friend bool operator<(fruit f1,fruit f2){
return f1.price<f2.price;
}
};
判断f1==f2,则相当于!(f1<f2)&&!(f2<f1)。
所以 priority_queue<fruit> q; 内部以价格高的水果优先级高。
同理，如果想以价格低的水果为优先级高，那么把<改成>。
struct fruit{
string name;
int price;
friend bool operator<(fruit f1,fruit f2){
return f1.price>f2.price;
}
};
注：只能重载<,重载>会编译错误。
不用greater<typename>,不重载<,不用friend函数
用cmp。
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct fruit{
string name;
int price;
}f1,f2,f3;
struct cmp{
bool operator () (fruit f1,fruit f2){
return f1.price>f2.price;
}
};
int main()
{
priority_queue<fruit,vector<fruit>,cmp> q;
f1.name="a";
f1.price=3;
f2.name="b";
f2.price=2;
f3.name="c";
f3.price=1;
q.push(f1);
q.push(f2);
q.push(f3);
cout<<q.top().name<<" "<<q.top().price;
return 0;
}
结果： c 1
即便是基本数据类型或其他STL容器（如set），也可以用同样的方式定义优先级。如果结构体内数据较庞大，前面加const & 引用来提高效率。
friend bool operator<(const & fruit f1,const & fruit f2){
return f1.price>f2.price;
}
struct cmp{
bool operator () (const & fruit f1,const & fruit f2){
return f1.price>f2.price;
}
};
priority_queue的本质是堆。
7.stack
栈，一个后进先出的容器。
头文件
#include<stack>
7.1stack的定义
stack<typename> name;
7.2stack容器内元素的访问
由于栈是一种后进先出的数据结构，所以只能用top()来访问栈顶元素。
st.top();
7.3 stack常用函数
（1）push()
st.push(x)将x入栈
（2）top()
st.top()访问栈顶元素。
（3）pop()
st.pop()删除栈顶元素。
（4）empty()
st.empty()检测是否为空，为空返回true，否则返回false。
（5）size()
st.size()返回栈中元素的个数。
8.pair
当想要将两个元素绑在一起作为一个合成元素，又不想定义结构体时，可以使用pair。
头文件
#include<utility>
map实现用了pair，所以#include<map>包含#include<utility>，用map不需要再包含utility头文件。
pair 相当于
struct pair{
typeName1 first;
typeName2 second;
};
8.1 pair的定义
pair<typeName1,typeName2> name;
例如：
pair<string ,int> p;
初始化：
pair<string ,int> p(“haha”,5);
pair<string,int> p=make_pair(“haha”,5);
8.2 pair中元素的访问
用p.first和p.second访问。
8.3 pair常用函数
（1）比较操作数，pair可以直接使用==,!=,<,<=,>,>=比较大 小。
比较规则是先以first的大小作为标准，只有当first相等时才 去比较second的大小。
8.4 pair常见用途
例如：
#include<iostream>
#include<map>
using namespace std;
int main(){
map<string,int>mp;
mp.insert(make_pair("heihei",5));
mp.insert(pair<string,int>("haha",10));
//auto it ==map<string,int>::iterator it
for(auto it = mp.begin();it!=mp.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
}
9.algorithm头文件
（1）max() /min()/abs()
max和min返回两个数x、y中的最大最小值。abs(x)中x必须为整数，浮点数用math头文件下的fabs()。
（2）swap()
swap(x,y)交换x和y的值。
（3）reverse()
reverse(it,it2)可以将数组指针在[it1,it2)之间的元素或容器的迭代器[it1,it2)范围内的元素进行反转。
例如：
int a[10]={10,11,12,13,14,15};
reverse(a,a+4); //将a[0]~a[3} 4个元素反转。
13 12 11 10 14 15
string str =“abcdefghi”
reverse(str.begin()+2,str.begin()+6);
abfedcghi
（4）next_permutation()
next_permutation()给出一个序列在全排列中的下一个序列。
例如：
n=3的全排列为
123 132 213 231 312 321
231的下一个序列为312。
int a[10]={1,2,3};
do{
cout<<a[0]<<a[1]<<a[2]<<” ”;
}while(next_permutation(a,a+3));
输出：123 132 213 231 312 321
（5）fill()
fill()可以把数组或某容器的某一段区间赋为某个相同的值，与memset不同，这里的赋值可以是数组类型对应范围中的任意值。
int a[5];
fill(a,a+5,233);
（6）sort()
sort(a,a+4); //默认递增排序
cmp函数
bool cmp(int a,int b){
return a>b; //从大到小排序 与priority_queue相反。
}
结构体
struct node{
int x;
int y;
}
bool cmp(node a,node b){
if(a.x!=b.x)
return a.x>b.x; //按x从大到小排序 与priority_queue相反。
else
return a.y<b.y; //若x相等，则按y从小到大排序。
}
STL中，只有vector，string，deque是可以用sort的，像set、map容器是用红黑树实现的，元素本身有序，不允许用sort排序。
（7）lower_bound()/upper_bound()
lower_bound(first,last,val)用来寻找在数组或容器中的[first,last)范围内第一个值大于等于val的元素的位置，如果是数组，返回该位置指针；如果是容器，返回该位置的迭代器。
upper_bound(first,last,val)用来寻找数组或容器的[first，last)范围第一个值大于val的元素的位置，如果是数组，返回该位置指针；如果是容器，返回该位置的迭代器。
如果数组或容器中没有寻找到该元素，则lower_bound()和upper_bound()返回可以插入该元素的位置的指针或迭代器。