【OI之路】01语法与STL-2STL

壮哉我stl!

字符串

读取整行,getline(cin,s);

1
2
3
4
5
6
7
8
9
10
11
12
#include<string>
string s1; //定义一个字符串s1,并初始化为空
string s2(s1); //用s1初始化s2
string s3("value"); //将s3初始化为"value"
string s4(n,'c'); //将s4初始化为字符'c'的n个副本,简单来说就是n个'c'字符
s.empty() //若s为空串,则返回true,否则为false
s.size() //返回s中字符的个数,s.length()与其相同
s.insert(pos,s2) //在s下标为pos的元素前插入字符串s2
s.substr(pos,len) //返回s中下标为pos起的长度为len的子串
s.replace(pos,l,s2) //替换s中下标为pos起的长度l个字符为字符串s2
s.find(s2,pos) //在s中查找s2第一次出现的位置
s.c_str() //返回一个C风格的字符串临时指针

关联式容器

map <类型1,类型2> 变量名;
在一些应用中,使用map容器来作为一个有序的映射表
对map单次操作的时间复杂度为log(n)

1
2
3
4
5
6
7
8
9
10
11
12
#include<map>
ma["abc"]=2; //将字符串"abc"映射到整数2
cout<<ma["abc"]; //输出为2
ma.begin() //返回map中第一个元素的迭代器(指针)
ma.end() //返回最后一个元素后一个的迭代器(指针)
ma.size() //返回map中元素的个数
ma.count(element) //判断元素element是否存在map中
ma.clear() //初始化map
ma.lower_bound() //返回键值大于等于给定元素的第一个位置,一旦map中的一个元素被访问,不论它之前是否已经被赋值,它都被视为存在
operator[] //访问map中的元素,若该元素不存在,则创建一个新元素,并返回类型2初始值
获得iterater:ma.find("abc")

set

返回迭代器(直接减去begin()得到下标即排名,加上*得到值)
begin()–返回指向第一个元素的迭代器
end()–返回指向最后一个元素的迭代器
find()–返回一个指向被查找到元素的迭代器,不存在则返回end()
lower_bound()–返回指向大于(或等于)某值的第一个元素的迭代器,可外面,不存在则返回end()
upper_bound()–返回大于某个值元素的迭代器,可外面,不存在则返回end()

用multiset可以完全代替优先队列,还可以同时小根、大根
支持删除(s.erase(s.find())即可,只会删一个,如果传入值删除所有)、搜索元素

1
2
得到最小值*(s.begin())
最大值*(--s.end())

Zebras

1.2.9 迭代器

1
2
3
4
5
6
map<string,int> m;
for(map<string,int>::iterator i=m.begin();i!=m.end();i++)
{
//或 cout<<i->first<<" "<<i->second<<endl;
cout<<(*i).first<<" "<<(*i).second<<endl;
}

如果要反向枚举,可以从rbegin的结尾,到rend,注意遍历的时候要用++
这样会方便很多,不用预处理st和ed
sort的时候(主要是vector)也会很方便:
sort( a.rbegin(),a.rend() )
这可以从大到小

bitset

定义、初始化与赋值

bitset<8> 表示二进制长度为8
默认初始值为0
bs[0]=1 表示将最后一位设为1,而不是首位(bin[0])

函数

返回bool
bs.any() 是否存在值为1的二进制位
bs.none() 是否不存在值为1的二进制位,也就是0
bs.count() 值为1的个数

返回bitset
bs.flip() 全部位逐位取反,等效于 ~bs

返回下标
找1
_Find_first()
_Find_next(pos)
Zebras

其他
所有位运算,除了“!”,不知道原因
赋值:set()全部1,reset()全部0

转化

bs.to_string()
bs.to_ulong() 变成 unsigned long
bs.to_ullong() 变成 unsigned long long
bs=”0001010”
bs=31

优秀的空间复杂度

长度 bitset字节 bool[]字节
16 4 16
32 4 32
64 8 64

简而言之,每8位1个字节
其实和用int存储是一样的,例如32位是4字节

时间复杂度

每次操作,位数/32

其他

nth_element(start, start+n, end)
使第n大元素处于第n位置(从0开始,其位置是下标为 n的元素)
常用于KD-Tree
原理其实就是手写二分排序一样,然后只搞某一侧

deque
与queue不同在于能任意访问其中的元素(因为是连续的空间),并且能在前面插入元素(与vector不同)
(这是手写队列也无法做到的,虽然不常用,因为oi不考stl,只是作为工具)

equal_range
参数和lower_bound等类似
能够返回容器内,等值区间,而且同样是左闭右开区间

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a012.html
转载请注明出处,谢谢!