C++标准模板库（STL）

参考来源：知乎：【C++】标准模板库（STL）：超快入门！算法竞赛必看！

参考来源：C++ STL 总结-基于算法竞赛（悠享版）

2023.10.22@isSeymour

零、废话说在前头

0.1 什么是C++标准模板库（STL）？

  • 标准模板库 STL（Standard Template Library），是 C++ 标准库的一部分，不需要单独安装，只需要#include 头文件。

  • C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。

  • C++ 语言的核心优势之一就是便于软件的复用。

    C++ 语言有两个方面体现了复用：

    • 面向对象的继承和多态机制
    • 通过模板的概念实现了对泛型程序设计的支持

  • C++中的模板，就好比英语作文的模板，只换主题，不换句式和结构。对应到C++模板，就是只换类型，不换方法。

0.2 STL有什么优势？

  • STL封装了很多实用的容器，省时省力，能够让你将更多心思放到解决问题的步骤上，而非费力去实现数据结构诸多细节上，像极了用python时候的酣畅淋漓。

    P.S. 如果你对STL源码颇有兴趣，那你不妨拜读C++大师侯捷的杰作《STL源码剖析》。

0.3 STL六大部件

  • 容器（Containers）
  • 分配器（Allocators）
  • 算法（Algorithm）
  • 迭代器（Iterators）
  • 适配器（Adapters）
  • 仿函数（Functors）

要真正提高C++编程效率，需要将STL六大部件结合使用，才能大放异彩。所谓部件，也即是零件，需要将这六大零件组装在一起，配合使用，整整齐齐。

STL的基本使用：

  • vector
  • set
  • string
  • map
  • queue
  • priority_queue
  • stack
  • pair
  • algorithm

第一部分 数据结构

一、vector

vector（矢量），是一种「变长数组」，即“自动改变数组长度的数组”。

注意：在局部区域中（比如局部函数里面）开vector数组，是在堆空间里面开的。

在局部区域开数组是在栈空间开的，而栈空间比较小，如果开了非常长的数组就会发生爆栈。

故局部区域不可以开大长度数组，但是可以开大长度vector。

1.1 初始化

要使用vector，需要添加头文件：

1
2
#include <vector>
using namespace std;

（1）一维初始化

像定义变量一样定义vector变量。类型名可以是int、double、char、struct，也可以是STL容器：vector、set、queue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<类型名> 变量名;

// 用例
vector<int> a;		//定义了一个名为a的一维数组,数组存储int类型数据
vector<double> b;	//定义了一个名为b的一维数组，数组存储double类型数据
vector<node> c;		//定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型
vector<vector<int> > name;	//注意：> >之间要加空格

// 指定长度和初始值的初始化
vector<int> v(n);	//定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1]
vector<int> v(n, 1);//v[0]到v[n-1]所有的元素初始值均为1
//注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）

// 初始化中有多个元素
vector<int> a{1, 2, 3, 4, 5};//数组a中有五个元素，数组长度就为5

// 拷贝初始化
vector<int> a(n + 1, 0);
vector<int> b(a);		//两个数组中的类型必须相同,a和b都是长度为n+1，初始值都为0的数组

（2）二维初始化

1
2
3
4
5
6
7
8
9
10
// 定义第一维固定长度为5，第二维可变化的二维数组。
vector<int> v[5];
//注意：行不可变（只有5行）, 而列可变,可以在指定行添加元素
//第一维固定长度为5，第二维长度可以改变

// 理解：
// 长度为5的v数组，数组中存储的是vector<int>数据类型，而该类型就是数组形式，故v为二维数组。
// 其中每个数组元素均为空，因为没有指定长度，所以第二维可变长。可以进行下述操作：
v[1].push_back(2);
v[2].push_back(3);
1
2
3
4
5
6
7
8
9
10
// 行列均可变
// 初始化二维均可变长数组
vector<vector<int>> v;//定义一个行和列均可变的二维数组

// 可以在v数组里面装多个数组
vector<int> t1{1, 2, 3, 4};
vector<int> t2{2, 3, 4, 5};
v.push_back(t1);
v.push_back(t2);
v.push_back({3, 4, 5, 6}) // {3, 4, 5, 6}可以作为vector的初始化,相当于一个无名vector
1
2
// 行列长度均固定 n + 1行 m + 1列初始值为0
vector<vector<int> > a(n + 1, vector<int>(m + 1, 0));

1.2 方法函数

（1）函数清单

c指定为数组名称，含义中会注明算法复杂度。

方法函数 含义 时间复杂度
c.front() 返回第一个数据 O(1)
c.back() 返回数组中的最后一个数据 O(1)
c.pop_back() 删除最后一个数据 O(1)
c.push_back(element) 在尾部加一个数据 O(1)
c.size() 返回实际数据个数（unsigned类型） O(1)
c.clear() 清空 O(N)，N为元素个数
c.resize(n, v) 改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0
c.insert(it, x) 向任意迭代器it插入一个元素x O(N)
c.erase(__position) 删除一个元素
c.erase(first,last) 删除[first,last)的所有元素 O(N)
c.begin() 返回首元素的迭代器（通俗来说就是地址） O(1)
c.end() 返回最后一个元素后一个位置的迭代器（地址） O(1)
c.empty() 判断是否为空，为空返回真，反之返回假 O(1)

注意：

  • end()返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址，所有STL容器均是如此

  • 删除一个的使用示例

    • v.erase(v.begin()+3);删除v[3]

（2）排序

1
2
3
4
5
sort(c.begin(), c.end());
// 对所有元素进行排序，如果要对指定区间进行排序，可以对sort()里面的参数进行加减改动。

vector<int> a(n + 1);
sort(a.begin() + 1, a.end()); // 对[1, n]区间进行从小到大排序

1.3 访问

（1）下标

一维数组的下标是从0到v.size()−1，访问之外的数会出现越界错误

1
2
3
4
5
6
7
//添加元素
for(int i = 0; i < 5; i++)
    vi.push_back(i);

//下标访问 
for(int i = 0; i < 5; i++)
    cout << vi[i] << " ";

（2）迭代器

类似指针一样的访问 ，首先需要声明迭代器变量，和声明指针变量一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//迭代器访问
vector<int>::iterator it;   
//相当于声明了一个迭代器类型的变量it
//通俗来说就是声明了一个指针变量

//方式一：
vector<int>::iterator it = vi.begin(); 
for(int i = 0; i < 5; i++)
    cout << *(it + i) << " ";
cout << "\n";

//方式二：
vector<int>::iterator it;
for(it = vi.begin(); it != vi.end();it ++)
    cout << *it << " ";
//vi.end()指向尾元素地址的下一个地址

注意：

  • vi[i] 和 *(vi.begin() + i) 等价
  • vector和string的STL容器支持*(it + i)的元素访问，其它容器可能也可以支持这种方式访问，但用的不多，可自行尝试

1.4 常见用途

（1）储存数据

vector本身可以作为数组使用，而且在一些元素个数不确定的场合可以很好地节省空间。

（2）用邻接表存储图

使用vector实现邻接表，更为简单。

二、stack

栈为数据结构的一种，是STL中实现的一个先进后出，后进先出的容器。

2.1 初始化

1
2
3
4
5
6
7
//头文件需要添加
#include<stack>

//声明
stack<int> s;
stack<string> s;
stack<node> s;//node是结构体类型

2.2 方法函数

（1）函数清单

方法函数 含义 时间复杂度
s.push(ele) 元素ele入栈 O(1)
s.pop() 移除栈顶元素 O(1)
s.top() 取得栈顶元素（但不删除） O(1)
s.empty() 检测栈内是否为空，空为真 O(1)
s.size() 返回栈内元素的个数 O(1)

2.3 栈遍历

栈遍历

  • 栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中

数组模拟栈进行遍历

  • 通过一个数组对栈进行模拟，一个存放下标的变量top模拟指向栈顶的指针。
  • 特点： 比STL的stack速度更快，遍历元素方便
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针,初始栈内无元素，tt为-1

for(int i = 0; i <= 5; i++) {
    //入栈 
    s[++tt] = i;
}
// 出栈
int top_element = s[tt--]; 

//入栈操作示意
//  0  1  2  3  4  5  
//                tt
//出栈后示意
//  0  1  2  3  4 
//              tt

三、queue

队列是一种先进先出的数据结构。

3.1 初始化

1
2
3
4
//头文件
#include<queue>
//定义初始化
queue<int> q;

3.2 方法函数

方法函数 含义 时间复杂度
q.front() 返回队首元素 O(1)
q.back() 返回队尾元素 O(1)
q.push(element) 尾部添加一个元素element 进队 O(1)
q.pop() 删除第一个元素 出队 O(1)
q.size() 返回队列中元素个数，返回值类型unsigned int O(1)
q.empty() 判断是否为空，队列为空，返回true O(1)

3.3 队列模拟

使用q[]数组模拟队列
hh表示队首元素的下标，初始值为0
tt表示队尾元素的下标，初始值为-1，表示刚开始队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int q[N];

int main() {
    int hh = 0,tt = -1;
	// 入队 
    q[++tt] = 1;
    q[++tt] = 2; 
    // 将所有元素出队 
    while(hh <= tt) {
        int t = q[hh++];
        printf("%d ",t);
    }
    return 0;
 }

四、deque

首尾都可插入和删除的队列为双端队列。

4.1 初始化

1
2
3
4
//添加头文件
#include<deque>
//初始化定义
deque<int> dq;

4.2 方法函数

方法函数 含义 时间复杂度
push_back(x)/push_front(x) 把x插入队尾后 / 队首 O(1)
back()/front() 返回队尾 / 队首元素 O(1)
pop_back() / pop_front() 删除队尾 / 队首元素 O(1)
erase(iterator it) 删除双端队列中的某一个元素
erase(iterator first,iterator last) 删除双端队列中[first,last)中的元素
empty() 判断deque是否空 O(1)
size() 返回deque的元素数量 O(1)
clear() 清空deque O(1)

4.3 排序

deque可以进行排序

1
2
3
4
5
//从小到大
sort(q.begin(), q.end())
//从大到小排序
sort(q.begin(), q.end(), greater<int>());//deque里面的类型需要是int型
sort(q.begin(), q.end(), greater());//高版本C++才可以用

五、priority_queue

优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最大的。

可以实现每次从优先队列中取出的元素都是队列中优先级最大的一个。

它的底层是通过堆来实现的。

5.1 初始化

1
2
3
4
//头文件
#include<queue>
//初始化定义
priority_queue<int> q;

5.2 函数方法

方法函数 含义 时间复杂度
q.top() 访问队首元素
q.push() 入队
q.pop() 堆顶（队首）元素出队
q.size() 队列元素个数
q.empty() 是否为空
empty() 判断deque是否空
  • 注意没有clear()！
  • 优先队列只能通过top()访问队首元素（优先级最高的元素）

5.3 设置优先级

5.3.1 基本数据类型的优先级

1
2
priority_queue<int> pq; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int> > q; // 小根堆, 每次取出的元素是队列中的最小值

参数解释：

  • 第二个参数：
    vector< int > 是用来承载底层数据结构堆的容器，若优先队列中存放的是double型数据，就要填vector< double >
    总之存的是什么类型的数据，就相应的填写对应类型。同时也要改动第三个参数里面的对应类型。
  • 第三个参数：
    less< int > 表示数字大的优先级大，堆顶为最大的数字
    greater< int >表示数字小的优先级大，堆顶为最小的数字
    int代表的是数据类型，也要填优先队列中存储的数据类型
1. 基础写法（非常常用）
1
2
3
priority_queue<int> q1; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, less<int> > q2; // 大根堆, 每次取出的元素是队列中的最大值，同第一行
priority_queue<int, vector<int>, greater<int> > q3; // 小根堆, 每次取出的元素是队列中的最小值
2. 自定义排序（不常见，主要是写着麻烦）
1
2
3
4
5
6
7
8
9
10
11
12
struct cmp1 {
    bool operator()(int x,int y) {
        return x > y;
    }
};
struct cmp2 {
    bool operator()(const int x,const int y) {
        return x < y;
    }
};
priority_queue<int, vector<int>, cmp1> q1; // 小根堆
priority_queue<int, vector<int>, cmp2> q2; // 大根堆

5.3.2 结构体优先级设置

优先队列中存储结构体类型，必须要设置优先级，即结构体的比较运算（因为优先队列的堆中要比较大小，才能将对应最大或者最小元素移到堆顶）。

  • 优先级设置可以定义在结构体内进行小于号重载，也可以定义在结构体外。
1
2
3
4
5
6
7
8
//要排序的结构体（存储在优先队列里面的）
struct Point
{
    int x,y;
};

// 优先队列的定义
priority_queue<Point> q;
  • 版本一：自定义全局比较规则
1
2
3
4
5
6
7
8
9
//定义的比较结构体
//注意：cmp是个结构体 
struct cmp {//自定义堆的排序规则 
    bool operator()(const Point& a,const Point& b) {
        return a.x < b.x;
    }
};
//初始化定义， 
priority_queue<Point, vector<Point>, cmp> q; // x大的在堆顶

  • 版本二：直接在结构体里面写

    因为是在结构体内部自定义的规则，一旦需要比较结构体，自动调用结构体内部重载运算符规则。

1
2
3
4
5
6
7
// 方式一
struct node {
    int x, y;
    friend bool operator < (Point a, Point b) {	//为两个结构体参数，结构体调用一定要写上friend
        return a.x < b.x;//按x从小到大排，x大的在堆顶
    }
};
1
2
3
4
5
6
7
// 方式二
struct node {
    int x, y;
    bool operator < (const Point &a) const {//直接传入一个参数，不必要写friend
        return x < a.x;//按x升序排列，x大的在堆顶
    }
};

注意： 优先队列自定义排序规则和sort()函数定义cmp函数很相似，但是最后返回的情况是相反的。即相同的符号，最后定义的排列顺序是完全相反的。
所以只需要记住sort的排序规则和优先队列的排序规则是相反的就可以了。

5.4 存储特殊类型的优先级

存储pair类型

  • 排序规则：
    默认先对pair的first进行降序排序，然后再对second降序排序
    对first先排序，大的排在前面，如果first元素相同，再对second元素排序，保持大的在前面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main() {
    priority_queue<pair<int, int> >q;
    q.push({7, 8});
    q.push({7, 9});
    q.push(make_pair(8, 7));
    while(!q.empty()) {
        cout << q.top().first << " " << q.top().second << "\n";
        q.pop();
    }
    return 0;
}

结果：
8 7
7 9
7 8

六、map

未完待续…

第二部分 算法

1.排序sort

未完待续…