前言

把STL放在心底,永远都有惊喜
——《Tonight Forever》

众所周知,C++语言有一个巨大的标准模板库,即STL。其内部包含了大量模板与容器。

正确的使用STL,可以极大提高代码编写的效率。

NOI系列赛事在$2011$年起允许选手使用STL,这无疑为C++党带来了福音。

因此,学好STL是一件很重要的事情。


STL的分类

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

由于文章篇幅限制,本文只会讲解容器,迭代器,算法三个部分,其他三部分一般很少在$OI$中用到。


前置芝士

命名空间

命名空间(即namespace)是C++的一大特性,可以用来解决变量或函数重名问题。

举个栗子,比如Payphone-X在一次考试中采用了数据分治,需要写两个叫做work的函数。

如果直接写的话必定会导致编译失败。而分开写又很难分清到底是那一档部分分。

这时候就可以通过写两个namespace来解决问题。

namespace Subtask1{
void work(int x , int y){
…………
}
}

namespace Subtask2{
void work(int a , int b){
…………
}
}

int main(){
cin >> n;
cin >> a >> b;
if(n < 1000){
Subtast1 :: work(a , b);
}
else{
Sbutask2 :: work(a , b);
}
return 0;
}

其中每一个namespace之间都是相互独立的,调用之前需要添加NAME :: name(),表示调用NAME命名空间内的name函数。

当然,也可以选择写using namespace NAME,将NAME这个命名空间引入全局。这样就可以访问这个命名空间的全部内容,但更容易引起变量冲突。

而STL的所有内容都在std这个命名空间内,使用时需要加std ::或者using namespace std


运算符重载

运算符重载可以在有歧义的情况下赋予运算符一个具体的比较参数。

举个栗子,在我们平时写邻接表时,我们很多时候需要根据边权大小进行排序。

直接排序肯定是不行的。这时,我们就可以选择重载运算符。

//对m条边根据边权大小进行升序排序

struct Edge{
int to;
int last;
int dis;

bool operator < (const Edge &other) const{
return dis < other.dis;
}
}edge[10001];


std :: sort(edge + 1 , edge + 1 + m);

上面的写法等价于

struct Edge{
int to;
int last;
int dis;
}edge[10001];

bool cmp(Edge a , Edge b){
return a.dis < b.dis;
}

std :: sort(edge + 1 , edge + 1 + m , cmp);

预编译指令

预处理命令就是我们程序开头以#字符开头的命令。叫他们预编译指令是因为这些命令是在编译时的第一步就执行,不会随编译转为汇编码。

最常用的预编译指令有三种,分别是include,define,pragma

其中,include用来调用头文件,define用来进行文本替换,而pragma可以指定编译选项,或者让编译器完成一些命令。

但要注意,NOI系列赛事是禁止使用pragma系列的编译指令的,在这里就不多介绍了。

感兴趣的同学可以参考这篇文章自行了解一下。


算法系列

STL的算法都包含在algorithm库中,使用之前需要#include<algorithm>

提醒一句,这个文件名很重要,一定要背下来,每天一遍!


排序

排序(即sortstable_sort),是最常用的STL函数之一。可以对一段区间进行排序。

其中,sort为不稳定排序,采用的是类似于快速排序的算法实现,十分高效,期望时间复杂度为$O(n \log n)$,一般比较常用。

stable_sort为稳定排序,采用的是类似于归并排序的算法实现,可以在稳定的情况下获得较高的效率,时间复杂度为$O(n \log n)$。

使用方法如下

//对数组a的n个元素升序排序(即从小到大排序)
int a[101];

std :: sort(a + 1 , a + 1 + n);

如果要降序排序(即从大到小排序)的话需要手写cmp函数,即

//对数组a的n个元素降序排序(即从大到小排序)
bool cmp(int a , int b){
return a > b;
}

std :: sort(a + 1 , a + 1 + n , cmp);

而如果对结构体进行排序的话需要重载运算符或手写cmp函数,具体使用方法如下

//将结构体Node按照y为关键字进行升序排序
struct Node{
int x , y;

bool operator < (const Node &other) const{
return y < other.y;
}
}node[10001];

std :: sort(node + 1 , node + 1 + n);

或者

struct Node{
int x , y;
}node[10001];

bool cmp(Node a , Node b){
return a.y < b.y;
}

std :: sort(node + 1 , node + 1 + n , cmp);

下面的代码演示了对$n(n < 10^5)$个整数进行降序排序后并输出。可以借助其理解sort函数

#include<iostream>
#include<algorithm>

#define N 100001

using namespace std;

int n , a[N];

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

int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a + 1 , a + 1 + n , cmp);
for(int i = 1; i <= n; i ++){
cout << a[i] << " ";
}
return 0;
}

去重

去重函数(即unique)函数可以对一段序列实现去重,并不会删除重复的元素,而是将重复元素放到序列末尾。

使用unique函数之前必须保证序列是有序的(升序降序均可)。

unique会返回去重后的数组的最后一个元素,一般通过用返回值减去首地址的方法获得不重复的元素数。即

int number = std :: unique(a + 1 , a + 1 + n) - a - 1;

时间复杂度为$O(n)$,一般用于离散化。

下面的代码演示了对$n(n < 10^5)$个整数进行降序排序后去重并输出。可以借助其理解unique函数。

#include<iostream>
#include<algorithm>

#define N 100001

using namespace std;

int n , a[N];

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

int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a + 1 , a + 1 + n , cmp);
int number = unique(a + 1 , a + 1 + n) - 1 - a;
for(int i = 1; i <= number; i ++){
cout << a[i] << " ";
}
return 0;
}

交换

交换函数(即swap),可以交换任意两个同类型元素的值。

时间复杂度$O(1)$。

使用方法如下

std :: swap(a , b);

最大值 & 最小值

maxmin函数。可以返回两个同类型元素的最大值或最小值。

时间复杂度$O(1)$。

使用方法如下

int a , b;
std :: max(a , b);
std :: min(a , b);

如果要取出一组元素的最大或最小值,可以使用max_elementmin_element,时间复杂度均为$O(n)$

使用方法如下

int a[1001];

int maxn = max_element(a + 1 , a + 1 + n);
int minn = min_element(a + 1 , a + 1 + n);

查找

STL用于查找的函数有三个,分别是lower_bound,upper_boundbinary_search,最为常用的是lower_bound

lower_bound用于在一个升序序列中查找某个元素,并返回第一个不小于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器。

upper_bound用于在一个升序序列中查找某个元素,并返回第一个大于该元素的元素的迭代器,如果找不到,则返回指向序列中最后一个元素之后的迭代器。

binary_search用于确定某个元素有没有在一个升序序列中出现过,返回truefalse

三个函数的时间复杂度均为$O(\log n)$。

使用方法如下

int a[N] = {0 , 1 , 2 , 3 , 4 , 5 , 6 , 7};

int num1 = lower_bound(a + 1 , a + 8 , 3) - a - 1; //答案是2
int num2 = upper_bound(a + 1 , a + 8 , 3) - a - 1; //答案是3
bool num3 = binary_search(a + 1 , a + 8 , 3) //答案为1,即true

全排列

next_permutation函数,可以枚举一段序列的全排列。

由于全排列数量为$O(n!)$,因此它的时间复杂度也是$O(n!)$的。

使用方法如下

int a[4] = {1 , 2 , 3 , 4};
do{
for(int i = 0; i < 4; i++){
cout << a[i] << endl;;
}
}while(next_permutation(a, a + 4));

迭代器

迭代器是用于访问 STL 容器中元素的一种数据类型,一般迭代器的声明如下:

std :: NAME<TYPE > :: iterator p;

其中,NAME为该迭代器的名字,而TYPE为该迭代器存储的元素类型。

一般来说,一个容器的begin()返回的是该容器首个元素的迭代器,而end()返回的是该容器最后一个元素之后的迭代器。

也就是说,容器的begin()end()表示的是一个左闭右开区间,其中,begin()在这个区间内,而end()不在

因此,不要试图去访问end()对应的元素。这是非法的。

在使用 STL 的容器或算法时,也可以使用begin()end()来表示一段区间。如

std :: sort(V.begin() , V.end());

有一部分容器的迭代器支持随机访问,比如vector,访问vector[i]相当于访问vector.begin() + i。但有些set这样的迭代器是不支持随机访问的。

一般的,使用迭代器遍历容器类似于以下代码,可以借其理解迭代器的具体实现。

for (std :: NAME<T > :: iterator p = C.begin(); p != C.end(); p ++) {
std :: cout << *p << std :: endl;
}

容器

Stack

stack即栈,是一种后入先出的数据结构,包含于#include<stack>中。

可以通过stack<int > S来定义一个内部元素为int的栈。

具体操作如下:

操作名称 实现方式 时间复杂度
插入一个元素 S.push() $O(1)$
获得栈顶元素(不删除) S.top() $O(1)$
判断是否为空 S.empty() $O(1)$
删除栈顶元素 S.pop() $O(1)$

下面的代码对于这些操作进行了演示,可以借此理解栈的基本操作。

#include<iostream>
#include<stack>

using namespace std;

stack<int > S;

int main(){
bool flag = S.empty(); //flag = true;

for(int i = 1; i <= 3; i ++){
S.push(20040921 + i);
}
while(!S.empty()){
cout << S.top() << "\n";
S.pop();
}
//依次输出20040924 , 20040923 ,20040922
return 0;
}

Queue

queue即队列,是一种后入后出的数据结构,包含于#include<queue>

可以通过queue<int > Q来定义一个内部元素为int型的队列。

具体操作如下:

操作名称 实现方式 时间复杂度
在队尾插入一个元素 Q.push() $O(1)$
获得队首元素(不删除) Q.front() $O(1)$
获得队尾元素(不删除) Q.back() $O(1)$
判断是否为空 Q.empty() $O(1)$
删除队首元素 Q.pop() $O(1)$
获得队列中元素个数 Q.size() $O(1)$

下面的代码对于这些操作进行了演示,可以借此理解队列的基本操作。

#include<iostream>
#include<queue>

using namespace std;

queue<int > Q;

int main(){
bool flag = Q.empty(); //flag = true
for(int i = 1; i <= 3; i ++){
Q.push(20040921 + i);
}
int a = Q.front(); //a = 20040922
int b = Q.back(); //b = 20040924
int size = Q.size(); //size = 3
while(!Q.empty()){
cout << Q.front() << "\n";
Q.pop(); //输出依次为20040924,20040923 ,20040922
}
return 0;
}

Priority_queue

priority_queue即优先队列,又称二叉堆。可以随时获取区间最值

使用之前需要添加#include<queue>

由于优先队列为树形结构,因此它的时间复杂度会带一个$\log$,具体复杂度详见下表。

操作名称 实现方式 时间复杂度
插入一个元素 Q.push() $O(\log n)$
获得堆顶元素(不删除) Q.top() $O(1)$
判断是否为空 Q.empty() $O(1)$
删除堆顶元素 Q.pop() $O(\log n)$

但要注意,priority_queue默认提供的优先队列是最大优先队列,即大根堆,若需要使用最小优先队列,需要按照以下方法声明

priority_queue<int , vector<int > , greater<int > > Q;

其中,greater<int >的后面需要多打一个空格,否则会被编译器识别为右移>>运算符而报错。


Vector

vector即动态数组,是一种可以根据放入元素的多少来自动扩充的数组。包含于#include<vector>中。

可以使用vector<int > V来定义一个内部元素为int型的动态数组。

具体操作如下:

操作名称 实现方式 时间复杂度
在尾部插入一个元素 V.push_back() $O(1)$
删除尾部元素 V.pop_back() $O(1)$
在特定位置插入元素 V.insert() $O(n)$
删除特定位置的元素 V.erase() $O(n)$
获得元素数量 V.size() $O(1)$
对数组进行排序 sort(V.begin() , V.end()) $O(n \log n)$

需要注意的是,在加入元素时,如果 vector 拥有的内存空间不足以存放欲加入的元素,则 vector 会申请一块新的内存,并将旧数据拷贝过去。这个过程的时间复杂度是$O(n)$的。


Set

set即集合,是STL提供的最良心容器之一,其内部利用红黑树实现。

说其良心是因为set中的元素会自动升序排列,且具有唯一性,很方便我们进行各项操作。

但可惜的是,set并不支持随机访问,即无法使用下标来访问集合中的元素,只能通过迭代器遍历。

在使用set之前,我们需要包含#include<set>这个头文件,并对其定义,格式如下:

set<int > S;    //定义一个类型为int的set

其具体操作如下:

操作名称 实现方式 时间复杂度
插入一个元素 S.insert() $O(\log n)$
删除一个元素 S.erase() $O(\log n)$

若需要遍历set则必须使用迭代器,其迭代器为set<T > :: iterator,其中T为其元素类型。


Map

map是STL中的一个关联容器,可以提供一对一的数据对应。和set一样,其内部也是用红黑树实现的。

可以形象化的将map理解为一个可以使用任何元素作为下标的数组。

使用map之前,我们需要包含#include<map>这个头文件,并对其定义,格式如下:

map<string , int > M;   //定义一个以string为下标,映射为int的map

在上面的代码中,我们定义了一个以字符串做下标,整数作为其映射的map

使用时,我们可以

M["qwq"] = 123456789;

值得注意的是,由于map本身为红黑树实现,是一种树形结构,它的复杂度为$O(\log n)$的,而不是$O(1)$。

因此,map只能对于一些特殊映射进行存储,而不能直接当做数组使用。


参考资料

  1. Menci’s Blog
  2. C++ Reference - map
  3. C++ Reference - set

感谢Menci在STL学习中给我的帮助。


THE END