STL
种类较多,不用一次全部背下来,先记住有哪些东西,用的时候再查阅具体资料,多用几次就记住了。
STL算法
以下
排序
sort(a+l,a+r+1);
将数组
可以自定义排序规则,sort
的第三个参数的位置是一个函数,返回值为 bool
bool cmp(int a,int b)
{
return a>b;
};
sort(a+l,a+r+1,cmp);
2
3
4
5
其中函数包含两个参数,类型应该与 a
数组的类型保持一致,返回值为排序的规则。
注意排序规则不能双向成立,比如如果规则是 a>=b
,且恰好 a
和 b
相等,那么将产生段错误或运行超时。
排序是
二分查找
int p1=lower_bound(a+l,a+r+1,x)-a;//数组a[l]~a[r]中第一个大于等于x位置的下标
int p2=upper_bound(a+l,a+r+1,x)-a;//数组a[l]~a[r]中第一个大于x位置的下标
2
单词查找
去重
sort(a+l,a+r+1);
int pos=unique(a+l,a+r+1)-a;
2
把数组
注意 sort
。
它会把每个元素的第一份从小到大放在
比如
去重是
离散化
将数组
所谓离散化,就是把数组在大小关系不变的情况下,将数字重新赋值
比如
这样就可以将数字规模变成数字个数的数量级,从而降低某些算法的时间复杂度
for(int i=1;i<=n;++i) c[i]=a[i];
sort(c+1,c+n+1);
int pos=unique(c+1,c+n+1)-c;
for(int i=1;i<=n;++i)
{
a[i]=lower_bound(c+1,c+pos,a[i])-c;
}
2
3
4
5
6
7
全排列
do
{
for(int i=1;i<=n;++i) cout<<a[i]<<" \n"[i==n];
}next_permutation(a+1,a+n+1);//将数组a生成字典序上的下一个数组,如果字典序已经最大了结束
2
3
4
全排列是
翻转
reverse(a+1,a+n+1);//翻转数组a[1]~a[n]
翻转是
STL容器
以下
pair
二元组
将两个类型合并成一个类型
pair<int,int> q;
其中 pair<int,int>
是数据类型, q
是变量名。
二元组中的第一个元素叫 first
,第二个叫 second
。
pair<int,int> q={1,2};
cout<<q.first<<' '<<q.second<<endl;
2
pair
默认先按 first
从小到大排序, first
相等的再按 second
从小到大排序。
array
数组
array<int,5> a;
定义一个范围为 a[0]~a[4]
的数组,默认按字典序排序,数据类型是 int
。
额外设定一个数组类型的 STL
容器用处之一是方便把数组作为参数。
vector
动态数组。
vector<int> a(n+1);
其中 <int>
是类型,可以替换,a
是数组名称,(n+1)
是数组大小,正常情况下数组不能用变量大小,使用动态数组可以。
vector 是支持下标访问的有序容器。
动态数组的定义可以嵌套:
vector<vector<int> > a(n+1);//开了n+1个动态数组
vector<vector<int> > a(n+1,vector<int>(n+1));//开了n+1个n+1大小的动态数组
vector a(n+1,vector<int>(n+1));//c++17 开始支持自动类型推导
2
3
加入一个元素:
a.push_back(x);//向a数组末尾加入元素x
注意,如果你定义的时候比如规定了 vector<int> a(5)
,那么再 push_back()
,是把元素加到了
删除末尾元素:
a.pop_back();
vector
加入元素和删除末尾元素都是
删除一段元素:
a.erase(a.begin()+l,a.begin()+r+1);//删除a[l]~a[r]
重新定义动态数组大小:
a.resize(100,0);
按顺序遍历数组元素:
for(int x:a){}
上面的操作都是
迭代器:专门用来指向 STL
工具地址的一种指针类似物。
和指针一样,它指向一个 STL
的地址,如果要访问这个地址上的元素,需要用 *
。
比如 it=q.begin()
表示 it
指向 q
名字为 q
的 vector
第一个元素的地址,如果要保存 q
第一个元素,要 int x=*it
。
不同的 STL
的迭代器类型不同,如果要定义一个 vector
类型的迭代器,需要:
vector<int>::iterator it
其中 it
是迭代器的变量名,vector<int>::iterator
是迭代器的类型。
a.begin();//动态数组a中第一个元素的迭代器
a.end();//动态数组a中最后一个元素之后一个位置的迭代器。
vector<int>::iterator it=a.begin();//通过这种方式可以定义一个名字叫it的迭代器变量。
for(auto it=a.begin();it!=a.end();++it)
{
cout<<(*it)<<' ';
};
//迭代器可以通过自增运算改变数值,在多数STL中,内部元素的迭代器地址都是逻辑上连续的。(c++11之后,auto关键字可以自动定义一个迭代器类型)。
2
3
4
5
6
7
8
以下函数是本节将要介绍的不同类型
=://构造赋值
a.begin();//指向a开头元素的迭代器
a.end();//指向a最后一个元素之后一个位置的迭代器,同时也是a的结束位置
a.size();//返回容器a中元素个数
a.empty();//检查容器a是否为空,为空则返回值为1
a.swap(b);//交换a,b两个容器的内容,这样交换是O(1)的。(它实际没交换,换了一下指向两个容器的地址)
a.clear();//清空a里的元素
a.erase(元素/迭代器);//对于顺序容器,这个操作要O(n),对于无序容器要O(logn)
2
3
4
5
6
7
8
各种比较符号比较两个同类型容器大小时,默认按字典序排序。
对于vector的排序,用以下方式实现:
sort(a.begin(),a.end());//整个a数组排序
sort(a.begin()+l,a.begin()+r+1);//a[l]~a[r]排序
2
其他函数类似。
删除 vector
中的元素:
在用迭代器遍历时,如果要删除某个元素:
for(auto it=q.begin();it!=q.end();)
{
if(*it==5) q.erase(it);
++it;
}
2
3
4
5
这样是不对的,因为删除后 it
就变成了野指针(没有指向的东西了),再 ++it
也不会得到正确的结果。
正确用法是:
for(auto it=q.begin();it!=q.end();++it)
{
if(*it==5) it=q.erase(it);
else ++it;
}
2
3
4
5
删除一个元素后,会自动返回下一个位置的迭代器。
在中间删除迭代器也是
set
集合,内部是用平衡树(不用管它是啥,数据结构课会讲的)实现的。
set
会根据集合的定义,自动给元素去重。
set<int> q;//定义一个名字为 q ,类型为 int 的集合
q.insert(5);//集合中插入数字
2
放入集合中的数字将会被自动去重并从小到大排序,但是集合不能用下标进行访问,只能用迭代器。(因为它内部是数据结构)。
cout<<q.count(x)<<endl;//集合内元素x的数量
(因为是集合,所以只有 0 和 1 两种情况)。
查找元素
auto it=q.find(x);//it 指向集合里值为 x 的地址,如果找不到,返回q.end();
输出集合中最小的数字和最大的数字:
cout<<(*q.begin())<<' '<<(*prev(q.end()))<<endl;
auto it1=q.begin(),it2=prev(q.end());
cout<<(*it1)<<' '<<(*it2)endl;
2
3
按从小到大的顺序输出
set<int> q;
set<int>::iterator it;
while(it!=q.end())
{
cout<<(*it)<<'\n';
++it;
}
2
3
4
5
6
7
因为
set<int> q;
auto it=q.lower_bound(x);//返回q中第一个大于等于x的数字的迭代器,找不到则返回q.end()
2
set
的插入、删除、二分查找等操作都是
multiset
多重集合
跟 set 的区别是,不会删除重复的元素。
用 multiset 时要注意,如果使用
q.erase(x);
是删除所有值为x的元素,不管有多少个都删了,如果只想删除一个,要用迭代器
auto it=q.find(x);
q.erase(it);
2
multiset
操作复杂度与 set
相同
map
map是一个任意下标类型的数字。
通常数组下标只能是整数,map可以支持多种下标
map<类型1,类型2> q;
q[类型1]=类型2;
2
例如:
map<char,int> q;
q['a']=10;
2
遍历map
map<char,int> q;
for(pair<char,int> x:q)
{
cout<<x.first<<' '<<x.second<<'\n';
}
2
3
4
5
其中x.first
是指类型1(下标),x.second
是存的类型2(内容)
pair是一个二元组,pair<类型1,类型2>把两个类型封装成一个变量,第一个通过.first调用,第二个通过.second调用。
map
的插入、删除都是
queue
队列
一种先进先出的数据结构,如同排队。
queue<int> q;
创建一个 int
类型的队列。
q.push(x);//在队列 q 尾部加入元素 x
q.push(y);
q.push(z);
q.pop();//删除队首(第一个)元素
cout<<q.front()<<endl;//输出队列中的第一个元素
2
3
4
5
队列插入、删除、取队首是
stack
栈
一种后进先出的数据结构,如同坐电梯,最后一个上的第一个下。
因为栈实现起来过于简单,所以一般直接用 vector
来模拟了
vector<int> sta;
sta.push_back(x);//栈顶插入元素
sta.pop_back();//删除栈顶元素。
2
3
链表
这并不是 STL
,只是顺便介绍一下链表怎么用
有
val[x]//节点 x 里的值
pre[x]//节点 x 的上一个节点
nxt[x]//节点 x 的下一个节点
2
3
在某个节点
void insert(int x,int p,int v)//在 x 后面插入一个编号为 p,值为 v 的节点
{
int y=nxt[x];//x的下一个节点
val[p]=v;
nxt[x]=p;//x的下一个变成p
pre[p]=x;//p的上一个变成x
if(y!=0)
{
nxt[p]=y;//p的下一个变成y
pre[y]=p;//y的上一个变成p
}
}
2
3
4
5
6
7
8
9
10
11
12
删除编号为 p
的节点:
void del(int p)
{
int x=pre[p],y=nxt[p];
nxt[x]=y;
pre[y]=x;
}
2
3
4
5
6
这样就相当于把 p
隐藏了,不管从前往后找还是从后往前找,都不会经过 p
了。
priority_queue
优先队列
名字叫队列,但其实和队列关系并不大(雾)
实际上这种数据结构是堆
priority_queue<int> q;
定义了一个大根堆,名字叫 q
,存储的数据类型是 int
。
q.push(5);
q.push(6);//将5 6插入堆
q.top();//返回堆中的最大值
q.pop();//删除堆中的最大值
q.size();//返回堆中数字个数
q.empty();//返回堆中是否为空
2
3
4
5
6
如果想定义一个每次取最小数字的堆,可以:
priority_queue<int,vector<int>,greater<int> > q1;
堆中的数据类型需要有 <
的定义,比如数字、浮点数、字符串等,数组和结构体这种自己本身没用的需要先定义 <
的含义。
一般堆的插入、删除、取堆首都先认为是
string
字符串
string s;//定义一个类型为 s 的字符串
cin>>s;
2
字符串可以直接当一种普通的数据类型,它也具有一些 stl
容器的特性
int n=s.length();//求字符串的长度
s.begin()//字符串首个字符
s.end()//字符串最后一个字符之后一个位置
reverse(s.begin(),s.end()); //翻转字符串
2
3
4
vector
中的大部分函数,在 string
中同样适用。
string
同样是变长的,所以和 vector
有很多相似的性质。
bitset
一位表示一个
那么理论上一个 int
就能存 32
位信息了。
bitset
就是这种工具:
存储
bitset<1000> b;
其中 <1000>
是bitset
的位数, b
是变量名。
bitset
可以看作是一个位数比较多的二进制数字。
bitset
支持用 []
进行下标访问,上面的 b
的范围是 b[0]~b[999]
,其中 b[0]
是最低位。
bitset<1000> b;//超时
bitset<1000> p(10);//以10的二进制为初始值初始化p
q.count()//q 中 1 的数量
q.any()// 若存在某一位是 1 则返回 true
q.all()// 若所有位都是 1 则返回 true
q.none()// 若所有位都是 0 则返回 true
q.set()//将所有位设置成 1
q.set(pos,1/0)// 将第 pos 位设置成 1/0
q.reset()//将所有位设置成 0
q.filp()// 翻转所有位
q.filp(pos)// 翻转第 pos 位
q.to_string()//返回字符串类型的该二进制数,最低位在右边。
q.to_ulong()//返回转化成 unsigned long 类型的数字
q.to_ullong()// 转化成 unsigned long long 类型
2
3
4
5
6
7
8
9
10
11
12
13
14
bitset
支持二进制下的各种位运算,当 bitset
作为一个整体运算时,各种位运算的时间复杂度都是正常 int
运算的
例如:
bitset<5> a(5),b(7);
a^=b;
cout<<a.to_ulong()<<endl;
2
3
输出为 2
。
一些涉及到位运算的题目,用 bitset
实现可以在原来的复杂度基础上,让时间和空间都变为原来的 long long
实现的则变为