前言

把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>。

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

排序

排序(即sort与stable_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);

最大值 & 最小值

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

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

使用方法如下

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

如果要取出一组元素的最大或最小值，可以使用max_element或min_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_bound与binary_search，最为常用的是lower_bound。

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

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

binary_search用于确定某个元素有没有在一个升序序列中出现过，返回true或false。

三个函数的时间复杂度均为$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