OI教程之STL

\author{张若天}
\institute{清华大学}
\date{\today}

附属于/oi

模板(Template)

大家都会写返回两个数的最大值的函数吧。
大概类似这样:

1
2
3
4
int max(int a,int b){
if(a>b) return a;
return b;
}

如果两个变量是实数类型(float,double),我们就需要再写max(float,float)和max(double,double)。
如果再碰到其他类型(char,short,long long),还需要再写。
(ps. C++里参数类型不同的两个函数是可以重名的。)

C++里提供了模板这个东西。
你可以写一个这样的函数:

1
2
3
4
5
template<typename T>
T max(T a,T b){
if(a>b) return a;
return b;
}

这样不管什么类型,只要定义了operator > 就可以调用max函数,得到两个变量里较大的值。

能够交换两个任意类型变量的模板函数swap(T,T),注意函数参数的传递方法

1
2
3
4
5
6
7
template<typename T>
T swap(T*a,T*b){
T c;
c=*a,*a=*b,*b=c;
}

swap(&a,&b);


1
2
3
4
5
6
7
template<typename T>
T swap(T&a,T&b){
T c;
c=a,a=b,b=c;
}

swap(a,b);

STL

函数模板这种写法只是为了更好的理解后面讲的内容,不推荐日常使用。
因为平时很少出现一个函数需要支持两种不同的类型的情况,如果出现了的话复制一遍代码就好了。
下面进入正题。

C++ Standard Template Library,C++标准模板库,平时简称STL或者模板库,C++预置的一些常用算法、“容器”的代码实现。
简单的说,C++帮你写好了许多东西,你拿来用就行了。
在竞赛中非常好用。也是当前大部分选手参赛语言都是C++的原因。

Namespace

STL中的东西大部分都定义在命名空间std下。如果你原来只会c语言,你可以不理解这些,只用在你每个代码开头加上一句using namespace std;即可。

STL的代码你需要以头文件的形式引入。
下面所有涉及的区间都是左闭右开的区间。

给大家推荐一个网站: link
这个网站上可以查找到某个头文件里包含哪些内容,函数需要传递哪些参数,等等。
注意:标有C++11的项,考试时不能使用。

link:这里是目前最新的NOI系列比赛语言的限制。

这个链接是旧版的

顺序容器

Vector

vector可以实现一个可以改变长度的数组。
使用时需要#include<vector>。
用vector<int> v;形式来声明一个vector<int>类型的变量v。
STL都是用模板写的,所以你需要用vector<Type>的形式来指明vector的类型。
同理vector<double> v2; 这是一个vector<double>类型的变量v2。

Vector的声明

  • vector<int> v1;这样声明的v1是一个空数组。
  • vector<int> v2(v1);这样声明的v2是v1的一个副本。
  • vector<int> v3(n);这样声明的v3是有n个0的一个数组。
  • vector<int> v4(n,i);这样声明的v4是有n个元素的数组,每个元素初始都是i。
    int换成其他类型同理(也可以是自己定义的struct类型)。

Vector的操作

vector对象本身是一个struct/class,它提供了许多函数。

  • v.empty(); 若v为空,返回true,否则返回false。
  • v.size(); 返回v中元素的个数。
  • v.push_back(t); 在v的末尾增加一个值为t的元素。
  • v[n]; 返回v中位置为n的元素(引用,可修改)。
  • v1 = v2; 将v1中元素替换为v2中元素的副本。
  • v1 == v2; 若v1与v2中对应位置的每个元素都相等返回true,否则false。
  • v1 !=,<,<=,>,>= v2; 按照位置从前到后依次比较。

Vector的操作

读入n,和n个整数,存到一个vector里,然后输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v;
int main(){
int n,x;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
v.push_back(x);
}
for(int i=0;i<v.size();i++){
printf("%d\n",v[i]);
}
return 0;
}

迭代器iterator

除了用下标来访问vector外,STL还定义了另一种访问元素的方法:使用迭代器(iterator)。用来表示容器内元素位置与遍历容器。

STL容器都定义了迭代器类型。

比如: vector<int>::iterator it;声明了一个vector<int>容器的迭代器。
每种容器都定义了.begin()函数与.end()函数。.begin()函数返回第一个元素的迭代器,.end()返回最后一个元素后一个位置的迭代器。

注意任何添加元素或删除元素都可能会使迭代器失效。

迭代器iterator

迭代器用起来与指针类似。(或者说指针也是一种迭代器。)

  • *it; 可以取得it代表元素的值。(*v.end();这样是非法的。)
  • ++it; 使it指向下一个元素。
  • --it; 使it指向前一个元素。
  • it1-it2; 如果it1与it2是同一个容器的迭代器,并且该容器是一个顺序容器,可以得到两个位置的差值。
  • it1==it2; it1!=it2; 判断两个迭代器是否指向相同的元素。
  • it2=it1+n; 如果该容器是一个顺序容器,it2可以得到it1往后n个位置的位置。

迭代器iterator

刚才的代码可以写成这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v;
int main(){
int n,x;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
v.push_back(x);
}
for(vector<int>::iterator it=v.begin();it!=v.end();++it){
printf("%d\n",*it);
}
return 0;
}

Vector提供的另一些操作

  • v.resize(x); 把vector的size调整为x,若原来大于x,删除元素,若原来小于x,补0。
  • v.reserve(x);
  • v.pop_back(); 删除v的最后一个元素。
  • v.clear(); 清空v。
  • v.insert(it,x); v.insert(it,n,x); v.insert(it,it1,it2); 在it元素后处插入x这个元素、插入n个x元素、插入it1到it2这些元素。
    注意如果插入的位置不是最后一个元素,会导致后面的元素集体后移。复杂度达到单次O(n)。

  • v.erase(it); v.erase(it1,it2); 删除it这个元素,删除it1到it2这些元素。(删除元素,也会导致元素大量移动,单次复杂度O(n))

  • v.front(); 返回第一个元素(引用,可以修改)。
  • v.back(); 返回最后一个元素 (引用,可以修改)。返回的是引用,所以可以 v.back()=10; 这样赋值。

大家动手尝试一下上面说的那些操作。

复杂度

vector时间复杂度除了insert,erase操作都是单次O(1)的。

大家思考一下怎样才能实现。
一种想法是最初就开一个大小等于用到下标最大值的数组。显然是有问题的,因为基本不太可能预先计算出用到的下标最大值。
C++的实现是,最初开一个长度为1的数组,然后每次当当前数组满了的时候就再开一个两倍空间的数组,然后把当前的内容复制到新数组中。假设最后你得到数组的大小是n,复制数组的总代价是 n+n/2+n/4+…+1 <2n,所以均摊添加一个元素的复杂度是O(1);

利用vector存图

图的存储可以使用邻接矩阵。但是有一个缺点就是空间使用是$O(n^2)$的。如果一个图有n=1w个点,m=1w条边,你需要1wx1w个int的空间,不太好存下。

利用vector,可以使空间降到O(m)。
用n个vector来存每个点的出边。
vector<int> v[10005];
如果有一条边(x,y),可以v[x].push_back(y);

如果边上有边权。可以自己造一个struct。

1
2
3
4
5
6
7
8
9
10
11
struct N{
int x,w;
N(int xx=0,int ww=0){
x=xx;w=ww;
}
};
vector<N> v[10005];

void add(int x,int y,int w){// 添加一条x到y权值为w的边。
v[x].push_back(N(y,w));
}

List

list是STL中的链表。

需要#include<list>。
类似上面的vector。list<int> l;代表一个list<int> 类型的变量l,它是一个int类型的STL链表。
同理list<double> l2;可以声明double类型的链表。

List的声明

  • list<int> l1;这样声明的l1是一个空链表。
  • list<int> l2(l1);这样声明的l2是l1的一个副本。
  • list<int> l3(n);这样声明的l3是有n个0的一个链表。
  • list<int> l4(n,i);这样声明的l4是有n个元素的链表,每个元素初始都是i。

int换成其他类型同理(也可以是自己定义的struct类型)。

List的一些操作

  • l.empty();
  • l.size();
  • l.front();
  • l.back();
  • l.push_back();
  • l.pop_back();
  • l.clear(); 与vector定义相同。
  • l.push_front(x); 在链表头加入元素x。
  • l.pop_front(x); 在链表头删去元素x。

List 的 iterator的一些操作

  • it=l.begin();
  • it=l.end();
  • ++it;
  • --it;
  • it1 == it2;
  • it1!=it2 同vector。

注意没有it1-it2;以及it2=it1+5;

  • it=l.erase(it);在链表上删除it这个元素,返回被删除元素后一个元素的迭代器。
  • it1=l.erase(it1,it2); 在链表上删除it1到it2这一段,返回it2。
  • l.insert();同vector,但是链表指定位置插入一个元素是O(1)的。
  • l.reverse(); 翻转链表l。

Queue

queue是先进先出(FIFO)队列。

需要#include<queue>。
queue<int> q;这样来声明。
同理queue<double> q;

Queue的一些操作

  • q.empty();
  • q.size();同vector以及list。
  • q.push(x);向队尾添加元素x。
  • q.front(); 返回队首元素。
  • q.back(); 返回队尾元素。
  • q.pop(); 删除队首。

无iterator操作。

Priority_queue

priority_queue是STL中的优先队列。可以查询元素中值最大的元素和删除值最大的元素。
需要#include<queue>。
priority_queue<int> pq;这样来声明。

Priority_queue的声明

priority_queue<int> pq;来声明一个普通的priority_queue。
priority_queue<int,vector<int>,greater<int> > pq; 来声明一个元素值最小的优先级最高的priority_queue。
自己定义的struct只要定义了operator <,就可以使用priority_queue。

Priority_queue的声明

like this:

1
2
3
4
5
6
7
8
9
10
struct N{
int id,w;
friend bool operator < (N a,N b){
return a.w<b.w;
}
N(int a=0,int b=0){
id=a;w=b;
}
};
priority_queue<N> pq;

Priority_queue的操作

  • pq.empty();
  • pq.size();
  • pq.push();同queue。

  • pq.top();返回优先级最高(值最小)的元素。

  • pq.pop();删除优先级最高的元素。

Priority_queue的复杂度

priority_queue的实现用的是堆。
堆是一个保证父亲权值小于两个孩子的二叉树。
稍微讲下堆。
所以pq.top();是O(1)的。pq.push()和pq.pop()都是O(log(n))的。

Stack

stack是STL中后进先出的栈。
需要#include<stack>。
stack<int> s;来声明。

其它类型同理。

Stack的操作

  • s.empty();
  • s.size();同上面。
  • s.top(); 返回栈顶元素。
  • s.pop(); 弹出栈顶。
  • s.push(x); 将元素x压入栈中。

Deque

deque 读作”deck”,是STL中的双端队列。
需要#include<deque>。
deque<Type> dq;这样声明。
一般由块状链表实现。

Deque的操作

基本同vector。

增加了:

  • dq.push_front(); 在队头增加一个元素。
  • dq.pop_front(); 删去队头元素。

关联容器

Set

set是STL中用于维护集合的容器。

需要#include<set>。
set<int> s;这样来声明一个维护int集合的容器。
同理set<double> s;可以声明维护double集合的容器。

Set提供的操作

  • s.empty(); 如果s为空返回true,否则false。
  • s.size(); 返回s的大小。
  • s.insert(x); 把x加入s。
  • s.erase(x); 把值为x的元素删除。
  • s.erase(it); 把迭代器it所指的元素删除。

Set提供的操作

  • s.clear(); 清空s。
  • it=s.find(x); 返回x元素的迭代器。
  • s.lower_bound(x);返回大于等于x的第一个元素的迭代器。
  • s.upper_bound(x);返回大于x的第一个元素的迭代器。

set::iterator的操作

  • it=s.begin(); 得到s中最小元素的迭代器。
  • it=s.end(); 得到s中最大元素
  • ++it;--it; 得到it的下一个、上一个元素。
    (可以认为set内部元素按从小到大排好序了。)

Set

set元素不能重复。
要是可重集合可以用multiset,与set用法相同。
(注意multiset erase一个元素时会把相等的元素都删掉。)

自己定义的类型

set也可以使用自己定义的struct。需要定义小于号。
比如:

1
2
3
4
struct N{int x,w;};
bool operator < (N a,N b){
return a.w<b.w;
}

Set时间复杂度

删除、查找、插入一个元素的复杂度都是O(log(n))。内部用平衡树(红黑树)实现。

Pair

pair是STL中提供的把两个变量打包成一个变量的方法。

可以调用 x=make_pair<a,b>,来得到一个pair<Type<a>,Type<b> >类型的变量x。

  • x.first;可以访问到a的值。
  • x.second;可以访问b原来的值。

Map

map类型实际上是一个set<pair<Type A,Type B> >的类型。又叫映射
map<int,int> mp;可以造一个相当于set<pair<int,int> >的类型。
它重载了[ ]运算符。
mp[a]=b;可以这样进行赋值。
mp[a];以及这样读取某个位置的值。

map[a]=b;如果原来不存在first=a的元素,便会新建一个。否则会修改这个元素。

Algorithm库

Algorithm(算法)库包含了众多的算法实现。
首先,要熟悉algorithm单词的拼写。
使用时需要#include<algorithm>。

Sort

排序相关

算法库中与排序有关的函数有:

  • sort;
  • stable_sort;
  • partial_sort;
  • nth_element;

Sort函数

有 sort(first,last) 和 sort(first,last,cmp);
first,last为迭代器或指针,cmp为自定义比较函数。
会把[first,last)的元素从小到大排序。

一般的调用形式:
int a[105],n;

  • sort(a,a+n);// n个元素 a[0]…a[n-1]
  • sort(a+1,a+n+1);// n个元素 a[1]…a[n]
    vector<int> v;
  • sort(v.begin(),v.end());

自定义cmp函数

你需要定义一个cmp函数,接受两个要排序的类型的参数A、B,当A<B时,返回True。
比如:

1
2
3
bool cmp(int a,int b){
return a>b;
}

我们就可以调用sort(a,a+n,cmp);来把a数组从大到小排序。

1
2
3
4
5
6
7
8
9
10
struct N{
int x,y;
};
bool cmp1(N a,N b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
bool cmp2(N a,N b){
return a.x+a.y<b.x+b.y;
}
  • sort(a,a+n,cmp1);可以把a排序,x从小到大并且x相等的按y从小到大。
  • sort(b,b+n,cmp2);可以把a按照a.x+a.y从小到大排序。

Sort的时间复杂度

一般情况下,我们不用关心sort函数是如何把数组排序的。
实际上sort所用的算法根据数组长度不同而不同。
复杂度 O(nlogn)。

Stable_sort

stable_sort是稳定的排序方法。(前面的sort函数并不保证稳定。)
需要额外的O(n)的空间。(实现的是归并排序。)
用法与sort相同。

稳定的排序算法

一个排序算法稳定。指的是值相同的元素在排序后保持不变的相对顺序。

Partial_sort

partial(a,a+num,a+n);或partial(a,a+num,a+n,cmp);
将a[0]…a[n-1]的前num小排序并放在a[0]…a[num-1]。

Nth_element

若a数组从0开始:
nth_element(a,a+x,a+n);或nth_element(a,a+x,a+n,cmp);
若a数组从1开始:
nth_element(a+1,a+x,a+n+1);或nth_element(a+1,a+x,a+n+1,cmp);

作用是,调用完上述函数后,没有进行排序,但是a[x]之前的元素都比a[x]小,a[x]后面的元素都比a[x]大。
也就是求出了第x小元素,a[x]。
具体实现可以看成是快排的一半,叫快速选择算法,复杂度O(n)。

Lower_bound/upper_bound

大家会二分算法么?
整数二分,实数二分。

lower_bound/upper_bound 提供了在有序数组里二分的函数。

lower_bound(a,a+n,x);或lower_bound(a,a+n,x,cmp) (数组a从0开始)可以求出a[0]…a[n-1]中第一个大于等于x的位置,返回的是一个迭代器(或指针)。
int pos=lower_bound(a,a+n,x)-a; 这种方式可以求出那个位置的下标。
lower_bound是大于等于。upper_bound是大于。

其他

unique

unique函数可以把一个有序的数组去重,并返回不重复的结尾的迭代器。
比如a={0,0,1,1,1,2,3,5,6,6};
调用 int new_end=unique(a,a+10)-a;后数组a变成{0,1,2,3,5,6,0,1,1,6};new_end的值为6。
unique也可以自定义cmp函数,unique(a,a+n,cmp)这样调用。cmp(A,B);需要在A==B时返回true,其他情况false。

离散化

综合上面的sort,unique,lower_bound,可以这样实现离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>;
#include<algorithm>;
using namespace std;
int a[1005],n;
int c[1005],tot;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) c[i]=a[i];
sort(c+1,c+n+1);
tot=unique(c+1,c+n+1)-(c+1);
for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
for(int i=1;i<=n;i++) printf("%d\n",a[i]);
return 0;
}

Swap

swap函数可以交换两个变量的值。

例如:
int a=2,b=3;
swap(a,b);
//a==3,b==2

Reverse

reverse函数可以翻转一个数组/容器。
例如:
int a[6]={0,1,2,3,4,5};
reverse(a,a+6);
//a变成{5,4,3,2,1,0}

Random_shuffle

random_shuffle函数可以把一个数组/容器随机打乱。

例如:
int a[6]={0,1,2,3,4,5};
random_shuffle(a,a+6);
//a变成随机排列的样子..

min/max

min/max函数返回两个值的较小值。

min(a,b);或min(a,b,cmp);
max(a,b);或max(a,b,cmp);

排列

next_permutation(a,a+n) 函数求a[0]…a[n-1]这个数列的下一个排列,若没有下一个排列,返回false。

例如:
int a[3]={1,2,3};
do{…}while(next_permutation(a,a+3));
可以依次得到
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

可以有cmp函数。
prev_permutation是求上一个排列,用法与上面相同。

Bitset库

bitset是一个把bool数组压位存储的数据结构。

  • 可以理解成,它把bool数组按32个一组,压到了一个个unsigned int 中。
  • bitset<512> a;这样来声明。
  • 支持位运算操作:&,|,~,<<,>>等操作。
  • 有.count()函数,来数1的个数。以及set,reset,flip函数来操纵某一位。

详细:
link

String库

速度很慢,OI中基本没用。
link

常见的STL用法

  1. sort排序
  2. set去重
  3. bfs中的queue
  4. sort+unique+lower_bound离散化
  5. vector存图
  6. vector作可变长数组
  7. map作劣质哈希表(复杂度比哈希表多一个log,但是方便)
  8. priority_queue跑最短路。

速度

NOIP、NOI目前都是没有O2优化的。
但是STL代码中大量使用inline,效率会比较低。
一般情况下,vector比数组稍慢,set、map与手写平衡树速度相当。
基本是可以接受的。

一些高级内容

容器的嵌套。
上面讲的那些容器都是可以嵌套使用的。
比如map<string,int>,map<int,vector<int> >这类。

pb_ds

强化版的STL,内容升级,门槛更高,有兴趣的可以研究。
参考saffah在冬令营的分享:http://pan.baidu.com/s/1uDbPk

练习题

BZOJ 1992 集合堆栈机
http://www.lydsy.com/JudgeOnline/problem.php?id=1932

BZOJ 1150: [CTSC2007]数据备份Backup
http://www.lydsy.com/JudgeOnline/problem.php?id=1150

BZOJ 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居
了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1<=N<=100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l<=Xi,Yi<=$10^9$;Xi,Yi 为整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过C(1<=C<=$10^9$),即|Xi - Xj|+|Yi - Yj|<=C.
2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.

给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

任何形式的使用、转载请注明出处!

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框