引言

我看了一下,到目前为止好像没有一篇日报来整理C++的STL,那鄙人就稍微的来整理一下2333~

并且这篇文章基本不是针对大佬的……大佬可直接无视,去看看紫荆花之恋啥的……

开始

本文同步发表于 李嘉安的博客(我是可以点的)

小声BB:我这整篇文章都是手打的……去我的博客给刷个访问量吧……

一 set系列

set——集合,是一个自带排序,去重的STL(multiset不去重,前加unordered_不排序)

所以为啥要有unordered_multiset这玩意呢?我也不知道……

1.set

a.定义

定义set的基本格式为

1
set<type_name> set_name;

如:

1
set<int> s;//定义一个存储int的set

但是set中的元素必须定义小于号,所以往里面可以放结构体,但是需重载运算符,如:

1
2
3
4
5
6
struct st{
int x,y;
bool operator<(const test a)const{
return x<a.x;//按照x来比较
}
};

这样就可以定义一个存储结构体的set了,如:

1
set<st> s;

b.插入

使用insert函数

如:

1
s.insert(233);

如果是结构体的话就把它先转为结构体

1
s.insert((st){1,1});

c.迭代器

这玩意就像一个指针一样~

下面给出定义方法

1
2
set<int>::iterator it;
set<int>::reverse_iterator rit;

这玩意的用处就是遍历set中的元素,而reverse_iterator则是反向遍历其中的元素,如:

1
2
for(it=s.begin();it!=s.end();it++) cout<<*it;
for(rit=s.rbegin();rit!=s.rend();rit++) cout<<*rit;

如果是结构体的话则写成:

1
2
for(it=s.begin();it!=s.end();it++) cout<<it->x;
for(rit=s.rbegin();rit!=s.rend();rit++) cout<<rit->x;

或:

1
2
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中的某个数,如:

1
2
s.erase(4);
s.erase(it);

如果是结构体的话:

1
s.insert((st){4,5});

e.寻找

使用find函数,如:

1
it=s.find(4)

如果是结构体的话:

1
it=s.find((st){4,5})

f.其他

清空:

1
s.clear();

判断是否为空:

1
if(s.empty()) printf("set为空");

总元素个数:

1
printf("set有%d个元素",s.size());

寻找该元素(找不到返回s.end())

1
it=s.find(1);

2.multiset

a.定义

multiset和set唯一区别就是multiset不自动去重,且multiset和set的操作都是差不多的,定义只要将set改为multiset即可:

1
multiset<int> s;//定义一个存储int的multiset

b.其他

multiset多了一个函数可用(其实set也可用,但作用就只限于判断是否有这个数了):

特定元素个数:

1
printf("multiset中有%d个1",s.count(1));

3.unordered_set/multiset(仅限C++11或以上)

这就是不排序的set/multiset……函数都差不多

二 map系列(虽然有multimap,但我觉得没用,就不写了)

map——映射,是的,妈妈再也不用担心我不会写哈希啦~它自动按键值排序,unordered_则不排序。

1.map

a.定义
定义map的基本格式为

1
map<type_name,type_name> map_name;

如:

1
map<int,int> m;//定义一个用int映射int的map

但是map中的元素必须定义小于号,所以往里面可以放结构体,但是需重载运算符,如:

1
2
3
4
5
6
struct st{
int x,y;
bool operator<(const test a)const{
return x<a.x;//按照x来比较
}
};

这样就可以定义一个存储结构体的set了,如:

1
map<int,st> m;

b.读取和删改

map的读取和删改只需想数组一样使用即可,如:

读取,修改(自动添加):

1
2
m[0]=1;//修改
int k=m[0];//读取

删除要用函数erase:

1
m.erase(0);//删除m[0]

c.其他

清空:

1
m.clear();

判断是否为空:

1
if(m.empty()) printf("map为空");

总元素个数:

1
printf("map有%d个元素",m.size());

寻找该元素(找不到返回m.end())

1
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同理,如:

1
2
queue<int> q;
stack<int> s;

b.插入弹出

使用pop与push函数,如:

1
2
3
4
q.pop();
s.pop();
q.push(1);
s.push(1);

c.访问

stack是使用top

queue是使用front和back

1
int t=s.top(),f=q.front(),b=q.front();

d.其他

清空:

1
2
s.clear();
q.clear();

判断是否为空:

1
2
if(s.empty()) printf("stack为空");
if(q.empty()) printf("queue为空");

总元素个数:

1
2
printf("stack有%d个元素",s.size());
printf("queue有%d个元素",q.size());

2.priority_queue

1.定义

只需将queue改为priority_queue即可

其他都差不多,就是它多了一个自动排序的功能

3.deque

a.定义

只需将queue改为deque即可

1
deque<int> dq;

b.插入弹出

使用pop与push函数,如:

1
2
3
4
dq.push_back(1);
dq.push_front(1);
dq.pop_back();
dq.pop_front();

c.访问

同queue是使用front和back

1
int b=dq.back(),b=dq.front();

d.其他

清空:

1
dq.clear();

判断是否为空:

1
if(dq.empty()) printf("deque为空");

总元素个数:

1
printf("deque有%d个元素",dq.size());

四 vector

vector——矢量,其实你可以理解为一个动态长度的数组……

附:vector有bool优化,如8个bool只需1字节

a.定义

与set等同理,如

1
vector<int> v;//定义一个存储int的vector

这个不用定义小于号,因为它不排序啊

b.插入

如果要在末尾新增函数的话,使用push_back()

1
v.push_back(1)

如果要在中间插入的话,则使用insert。注:这个函数是线性复杂度的

这个有两种写法,第一个是插入一个,第二个则是多个

1
2
v.insert(v.begin(),233);//在第一个元素后插入一个233,第一个值是一个指针(也可使用迭代器),第二个元素的话改为v.begin()+1即可
v.insert(v.begin(),2,233)//在第一个元素后插入两个233

c.删改

修改只需像普通数组使用即可:

1
v[0]=233;

删除使用erase函数,也有两种写法,第一个是删除一个,第二个则是多个:

1
2
v.erase(v.begin());//删除第一个元素
v.erase(v.begin(),v.begin()+1);//删除前两个元素

删除末尾元素则使用pop_back:

1
v.pop_back();

d.其他

返回是否为空:

1
if(v.empty()) printf("vector为空");

返回元素个数:

1
printf("vector有%d个元素",v.size());

五.排序系列

1.sort

这玩意大家都知道吧……从小到大排序

1
sort(a,a+n);

cmp自定义比较函数:

1
2
3
4
5
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. 定义

如:

1
string s;

2. 字符串赋值

众所周知,scanf是不支持string的!(但是scanf和printf其实是支持字符数组的)

只能用cin2333

赋值语句:

1
s="23333";

3. 转char数组

在C语言里,也有很多字符串的函数,但是它们的参数都是char指针类型的,所以在C++里有两个函数能够转换string为char指针——data()/c_str()(它们是一样的)如:

1
printf("%s",s);//编译错误
1
printf("%s",s.data())//通过

4. 大小

好多函数可以返回string的长度:

1
2
3
printf("string的长度为%d",s.size());
printf("string的长度为%d",strlen(s.data()));
printf("string的长度为%d",s.length());

5.其他

a. 寻找某字符第一次出现的位置

1
printf("字符a在%d位置出现",s.find('a'));

b. 截取子串:

注意这个函数的参数是从哪个位置后面截几个

1
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$)

谢谢你看到这里!