//### C++ STL
<"vector"> //倍增数组
{
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
clear() //清空
front()/back()
push_back()/pop_back() //尾插/弹出末位
begin()/end() //返回数组的第一个元素/最后一个元素的后一个
//vector的三种遍历方式
for(int i=0;i<n;i++)str.push_back(i);
{
/*1*/{for(int i=0;i<str.size();i++)cout<<str[i]<<' ';}
/*2*/{for(vector<int>::iterator i=str.begin();i!=str.end();i++)cout<<*i<<' ';}
/*3*/{for(auto x:str)cout<<x<<' ';}
}
//支持字典序比较运算
e.g.:
{
vector<int> a(4,3),b(3,4);
if(a<b) puts("a<b");
}
}
<"pair"> //存储一个二元组
{
//pair的三种声明方法:
pair<变量类型,变量类型> 变量名;
变量名= make_pair(变量,变量);
变量名={变量,变量};
e.g.:
{
pair<int,double> x;
x.first=123;
x.second=123.123;
}
//支持以first为第一关键字,second为第二关键字进行字典序比较运算,类似结构体排序
//支持嵌套声明
e.g.:{pair<int,pair<int,int>>}
}
<"string"> //字符串
{
size()/length() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
clear() //清空
str.substr(a,b) //返回str从a开始长为b的子串(a不输入则从str[0]开始截取子串;b不输入则截取从a开始后的整个子串)
str.c_str() //返回str的地址
[] //下标查找
//支持操作:
{
string a="asdf"
a+="aszx"
printf("%s\n",a.c_str());
}
}
<"queue"> //队列
{
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
push() //向队尾插入一个元素
front() //返回队头元素
back() //返回队尾元素
pop() //弹出队头元素(队尾插入,队头弹出)
//清空队列:
q=queue<int>();
}
<"priority_queue"> //优先队列(堆(完全二叉树)默认是大根堆:即堆顶元素是最大值)
{
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
push() //插入一个元素
top() //返回堆顶元素
pop() //弹出堆顶元素
//创建大根堆:
priority_queue<int> heap;
//创建小根堆:
priority_queue<int,vector<int>,greater<int>> heap;
}
<"stack"> //栈
{
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
push() //插入一个元素
top() //返回堆顶元素
pop() //弹出堆顶元素
}
<"deque"> //双端队列(加强版vector)
{
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
clear() //清空
front() //返回第一个元素
back() //返回最后一个元素
push_back()/pop_back() //插入/弹出最后一个元素
push_front()/pop_front()//插入/弹出第一个元素
//(缺点:速度慢一点)
begin()/end() //返回数组的第一个元素/最后一个元素的后一个
}
<"set,multiset"> //基于平衡二叉树(红黑树),动态维护有序序列
{
//set不支持插入重复元素,multiset支持
size() //返回元素个数 O(1)
empty() //返回是否为空 O(1)
clear() //清空
insert() //插入一个数
find() //查找一个数
count() //返回某一个数的个数
erase() //(1)输入一个数x,删除所有x O(k+logn);(2)输入一个迭代器,删除这个迭代器
lower_bound(x) //返回大于等于x的最小的数的迭代器
upper_bound(x) //返回大于x的最小的数的迭代器
++/-- //返回前驱/后继
}
<"map,multimap"> //同上
{
insert() //插入一个pair<,>
erase() //(1)输入一个pair x,删除所有x O(k+logn);(2)输入一个迭代器,删除这个迭代器
find() //查找一个数
[] //下标查找
lower_bound(x) //返回大于等于x的最小的数的迭代器
upper_bound(x) //返回大于x的最小的数的迭代器
//遍历:
<1>:迭代器遍历 for(auto it=map_name.begin();it!=map_name.end();it++)
<2>: for(auto p:map_name)
}
<"unordered_set,unordered_map,unordered_multiset,unordered_multimap">
//实现原理:哈希表
//支持O(1)的查询是否存在(map,set为O(logn)),无序插入
//同上 时间复杂度O(1)但不支持lower_bound()/upper_bound(),++,--操作
<"bitset"> //压位
{
压缩bool类型的空间(省8倍)
bitset<个数> 变量名;
//支持操作:
~,&,|,^,>>,<<,==,!=,[];
count() //返回有多少个true
any()/none()//返回是否至少有一个1/是否全为0
set() //把所有位置变成1
set(k,v) //把第k位变成v
reset() //把所有位置变成0
flip() //把所有位置取反
flip(k) //把第k位取反
}
good