引言
我看了一下，到目前为止好像没有一篇日报来整理C++的STL，那鄙人就稍微的来整理一下2333~
并且这篇文章基本不是针对大佬的……大佬可直接无视，去看看紫荆花之恋啥的……
开始
本文同步发表于 李嘉安的博客（我是可以点的）
小声BB：我这整篇文章都是手打的……去我的博客给刷个访问量吧……
一 set系列
set——集合，是一个自带排序，去重的STL（multiset不去重，前加unordered_不排序）
所以为啥要有unordered_multiset这玩意呢？我也不知道……
1.set
a.定义
定义set的基本格式为
set<type_name> set_name;如：
set<int> s;//定义一个存储int的set但是set中的元素必须定义小于号，所以往里面可以放结构体，但是需重载运算符，如：
struct st{
int x,y;
bool operator<(const test a)const{
return x<a.x;//按照x来比较
}
};这样就可以定义一个存储结构体的set了，如:
set<st> s;b.插入
使用insert函数
如:
s.insert(233);如果是结构体的话就把它先转为结构体
s.insert((st){1,1});c.迭代器
这玩意就像一个指针一样～
下面给出定义方法
set<int>::iterator it;
set<int>::reverse_iterator rit;这玩意的用处就是遍历set中的元素，而reverse_iterator则是反向遍历其中的元素，如：
for(it=s.begin();it!=s.end();it++) cout<<*it;
for(rit=s.rbegin();rit!=s.rend();rit++) cout<<*rit;如果是结构体的话则写成：
for(it=s.begin();it!=s.end();it++) cout<<it->x;
for(rit=s.rbegin();rit!=s.rend();rit++) cout<<rit->x;或：
for(it=s.begin();it!=s.end();it++) cout<<(*it).x;
for(rit=s.rbegin();rit!=s.rend();rit++) cout<<(*rit).x;d.删除
使用erase函数，它既可以删除一个迭代器上的值，也可以删除set中的某个数，如：
s.erase(4);
s.erase(it);如果是结构体的话：
s.insert((st){4,5});e.寻找
使用find函数，如：
it=s.find(4)如果是结构体的话：
it=s.find((st){4,5})f.其他
清空:
s.clear();判断是否为空：
if(s.empty()) printf("set为空");总元素个数：
printf("set有%d个元素",s.size());寻找该元素（找不到返回s.end()）
it=s.find(1);2.multiset
a.定义
multiset和set唯一区别就是multiset不自动去重，且multiset和set的操作都是差不多的，定义只要将set改为multiset即可：
multiset<int> s;//定义一个存储int的multisetb.其他
multiset多了一个函数可用（其实set也可用，但作用就只限于判断是否有这个数了）：
特定元素个数：
printf("multiset中有%d个1",s.count(1));3.unordered_set/multiset(仅限C++11或以上)
这就是不排序的set/multiset……函数都差不多
二 map系列
(虽然有multimap,但我觉得没用，就不写了)
map——映射，是的，妈妈再也不用担心我不会写哈希啦~它自动按键值排序，unordered_则不排序。
1.map
a.定义
定义map的基本格式为
map<type_name,type_name> map_name;如：
map<int,int> m;//定义一个用int映射int的map但是map中的元素必须定义小于号，所以往里面可以放结构体，但是需重载运算符，如：
struct st{
int x,y;
bool operator<(const test a)const{
return x<a.x;//按照x来比较
}
};这样就可以定义一个存储结构体的set了，如:
map<int,st> m;b.读取和删改
map的读取和删改只需想数组一样使用即可，如：
读取,修改（自动添加）：
m[0]=1;//修改
int k=m[0];//读取删除要用函数erase：
m.erase(0);//删除m[0]c.其他
清空:
m.clear();判断是否为空：
if(m.empty()) printf("map为空");总元素个数：
printf("map有%d个元素",m.size());寻找该元素（找不到返回m.end()）
it=m.find(1);2.unordered_map(仅限C++11或以上)
a.定义
只要把map改为unordered_map即可~
这个unordered_map就是不排序的map啦~能加快速度，因为一般写哈希时不需排序。如果你被卡的话可以试试这个，但是这玩意会被大量哈希碰撞卡死，比如说CF670C Cinema，最坏可以被卡到$O(n^2)$，但是也别慌，基本只有CF才有这种毒瘤数据。如果你是毒瘤出题人，那么具体怎么卡可以去看以前的日报。
三 stack/queue系列
stack——栈，当然，你知道栈是LIFO的，不用解释
queue——队列，当然，你知道栈是FIFO的，不用解释
deque——双向队列……这玩意就是一个容器上下都可pop和push
1.queue与stack
a.定义
与其他STL同理，如：
queue<int> q;
stack<int> s;b.插入弹出
使用pop与push函数，如：
q.pop();
s.pop();
q.push(1);
s.push(1);c.访问
stack是使用top
queue是使用front和back
int t=s.top(),f=q.front(),b=q.front();d. 其他
清空:
s.clear();
q.clear();判断是否为空：
if(s.empty()) printf("stack为空");
if(q.empty()) printf("queue为空");总元素个数：
printf("stack有%d个元素",s.size());
printf("queue有%d个元素",q.size());2.priority_queue
1.定义
只需将queue改为priority_queue即可
其他都差不多，就是它多了一个自动排序的功能
3.deque
a.定义
只需将queue改为deque即可
deque<int> dq;b.插入弹出
使用pop与push函数，如：
dq.push_back(1);
dq.push_front(1);
dq.pop_back();
dq.pop_front();c.访问
同queue是使用front和back
int b=dq.back(),b=dq.front();d.其他
清空:
dq.clear();判断是否为空：
if(dq.empty()) printf("deque为空");总元素个数：
printf("deque有%d个元素",dq.size());四 vector
vector——矢量，其实你可以理解为一个动态长度的数组……
附：vector有bool优化，如8个bool只需1字节
a.定义
与set等同理，如
vector<int> v;//定义一个存储int的vector这个不用定义小于号，因为它不排序啊
b.插入
如果要在末尾新增函数的话，使用push_back()
v.push_back(1)如果要在中间插入的话，则使用insert。注：这个函数是线性复杂度的
这个有两种写法，第一个是插入一个，第二个则是多个
v.insert(v.begin(),233);//在第一个元素后插入一个233，第一个值是一个指针(也可使用迭代器)，第二个元素的话改为v.begin()+1即可
v.insert(v.begin(),2,233)//在第一个元素后插入两个233c.删改
修改只需像普通数组使用即可：
v[0]=233;删除使用erase函数，也有两种写法，第一个是删除一个，第二个则是多个：
v.erase(v.begin());//删除第一个元素
v.erase(v.begin(),v.begin()+1);//删除前两个元素删除末尾元素则使用pop_back：
v.pop_back();d.其他
返回是否为空：
if(v.empty()) printf("vector为空");返回元素个数：
printf("vector有%d个元素",v.size());五.排序系列
1.sort
这玩意大家都知道吧……从小到大排序
sort(a,a+n);cmp自定义比较函数:
bool cmp(const int &a,const int &b){
return a>b;
}
sort(a,a+n,cmp)即可实现从大到小排序
但旧版C++标准要求这玩意平均时间复杂度是$nlogn$
而C++11或以上则要求最坏$nlogn$
2. stable_sort
这是个稳定的$nlogn$排序，用法和sort一样
七 String
string——字符串，其实这玩意有很多函数，下面进行介绍。
1. 定义
如：
string s; 2. 字符串赋值
众所周知，scanf是不支持string的！（但是scanf和printf其实是支持字符数组的）
只能用cin2333
赋值语句:
s="23333";3. 转char数组
在C语言里，也有很多字符串的函数，但是它们的参数都是char指针类型的，所以在C++里有两个函数能够转换string为char指针——data()/c_str()（它们是一样的）如：
printf("%s",s);//编译错误printf("%s",s.data())//通过4. 大小
好多函数可以返回string的长度：
printf("string的长度为%d",s.size());
printf("string的长度为%d",strlen(s.data()));
printf("string的长度为%d",s.length());5. 其他
a. 寻找某字符第一次出现的位置：
printf("字符a在%d位置出现",s.find('a'));b. 截取子串:
注意这个函数的参数是从哪个位置后面截几个
printf("这个字符串第1位开始的2个字符构成的子串是%s",s.substr(0,2).data());六 时间复杂度系列
这里说明一下各个结构的时间复杂度：
1. 基于红黑树实现的STL
有：map,set,mutiset,mutimap
它们大部分的操作均是O($logn$)的
2. 基于哈希表的STL
有: unordered_map,unordered_set,unordered_multimap,unordered_multiset
它们大部分操作均是O($1$)的(包括 "[ ]" 操作符)
但是有大量哈希碰撞时则可被卡到O($n^2$)
3.vector
vector总是另当别论……
在中间插入:O($n$)
在末尾插入:O($1$)
在中间删除:O($n$)
在末尾删除:O($1$)
其他基本是:O($1$)
0 条评论