当前位置：首页 > news >正文

C++ STL精通之旅：向量、集合与映射等容器详解

news 来源：原创 2024/5/12 4:25:20

常用容器

顺序容器

向量vector

构造

尾接 & 尾删

中括号运算符

获取长度

清空

判空

改变长度

提前分配好空间

代码演示

运行结果

关联容器

集合set

构造

遍历

其他

代码演示

运行结果编辑

映射map

常用方法

构造

遍历

其他

代码演示1编辑

运行结果1

代码演示2

运行结果2

string map

代码演示3

运行结果3

mp没赋初值，默认为0

代码演示4

运行结果4

容器适配器

栈stack

常用方法

代码演示1

运行结果1

vector也可以当栈来用

代码演示2

运行结果2

队列queue

常用方法

代码演示

运行结果

优先队列priority_queue

常用方法

构造

其他

大顶堆

代码演示1

运行结果1

小顶堆

代码演示2

运行结果2

修改堆顶元素

代码演示3

运行结果3

字符串

string (basic_string)

常用方法

构造

输入输出

其他

数值与字符串互转（C++11）

尾接字符串一定要用 +=

代码演示

运行结果

对与元组

二元组pair

常用方法

构造

赋值

取值

判同

适用场景

代码演示

运行结果

STL

STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间，这一点不仅是由于可以直接调用，还是因为它封装良好，可以让代码的可读性变高，解题思路更清晰，调试过程往往更顺利。

不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能，它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此，STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此，在实际比赛中要权衡 STL 的利弊，不过这一点就得靠经验了。

接下来，博主会分享在算法竞赛中常用的 STL 容器，对于算法，函数和迭代器，就不着重展开讲了。

C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

示例：

算法（Algorithms）：STL中的算法是一组对容器进行操作的函数，它们独立于任何特定的数据结构，可以用于执行各种任务，如搜索、排序、复制和修改容器中的元素。这些算法是泛型的，意味着它们可以用于不同类型和容器的数据，体现了泛型编程的思想。

容器（Containers）：容器是用来存储数据的对象，例如数组、队列、链表、集合等。STL提供了多种容器类型，每种都设计用于特定类型的数据访问和存储。容器管理对象的集合，并提供插入、删除和遍历元素等操作。

仿函数（Functors）：仿函数是重载了操作符()的类或类对象，它可以像函数一样被调用。在STL中，仿函数通常用作算法的参数，允许用户自定义算法的行为，使得算法更加灵活和可配置。

迭代器（Iterators）：迭代器是一种类似于指针的对象，用于在容器中遍历元素。每个容器都定义了相应的迭代器类型，迭代器提供了读取和修改容器元素的方法。迭代器分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器，不同类型的迭代器支持不同的操作。

常用容器

顺序容器

向量vector

头文件：#include <vector>

连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

构造

vector<类型> arr(长度, [初值])

时间复杂度：O(n)

尾接 & 尾删

push_back(元素)：在 vector 尾接一个元素，数组长度 +1.
pop_back()：删除 vector 尾部的一个元素，数组长度 -1.

时间复杂度：均摊 O(1)

中括号运算符

和一般数组一样的作用

时间复杂度：O(1)

获取长度

.size()

获取当前 vector 的长度

时间复杂度：O(1)

清空

.clear()

清空 vector

时间复杂度：O(n)

判空

.empty()

如果是空返回 true 反之返回 false.

时间复杂度：O(1)

改变长度

.resize(新长度, [默认值])

修改 vector 的长度

如果是缩短，则删除多余的值
如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）

时间复杂度：O(n)

提前分配好空间

代码演示

运行结果

关联容器

集合set

头文件#include <set>

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

集合三要素	解释	set	multiset	unordered_set
确定性	一个元素要么在集合中，要么不在	✔	✔	✔
互异性	一个元素仅可以在集合中出现一次	✔	❌（任意次）	✔
无序性	集合中的元素是没有顺序的	❌（从小到大）	❌（从小到大）	✔

构造

set<类型, 比较器> st

类型：要储存的数据类型
比较器：比较大小使用的比较器，默认为 less<类型>，可自定义

对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。

遍历

其他

作用	用法	示例
插入元素	`.insert(元素)`	`st.insert(1);`
删除元素	`.erase(元素)`	`st.erase(2);`
查找元素	`.find(元素)`	`auto it = st.find(1);`
判断元素是否存在	`.count(元素)`	`st.count(3);`
查看大小 / 清空 / 判空	略	略

增删查时间复杂度均为 O(\log n)

代码演示

运行结果

映射map

头文件#include <map>

提供对数时间的有序键值对结构。底层原理是红黑树。

映射：

$\begin{matrix} 1&\to&2\\ 2&\to&2\\ 3&\to&1\\ 4&\to&5\\ &\vdots \end{matrix}$

性质	解释	map	multimap	unordered_map
互异性	一个键仅可以在映射中出现一次	✔	❌（任意次）	✔
无序性	键是没有顺序的	❌（从小到大）	❌（从小到大）	✔

常用方法

构造

map<键类型, 值类型, 比较器> mp

键类型：要储存键的数据类型
值类型：要储存值的数据类型
比较器：键比较大小使用的比较器，默认为 less<类型>，可自定义

遍历

其他

作用	用法	示例
增 / 改 / 查元素	中括号	`mp[1] = 2;`
查元素（返回迭代器）	`.find(元素)`	`auto it = mp.find(1);`
删除元素	`.erase(元素)`	`mp.erase(2);`
判断元素是否存在	`.count(元素)`	`mp.count(3);`
查看大小 / 清空 / 判空	略	略

增删改查时间复杂度均为 O(\log n)

代码演示1

运行结果1

代码演示2

运行结果2

string map

代码演示3

运行结果3

mp没赋初值，默认为0

代码演示4

运行结果4

容器适配器

栈stack

头文件#include <stack>

通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。

常用方法

作用	用法	示例
构造	`stack<类型> stk`	`stack<int> stk;`
进栈	`.push(元素)`	`stk.push(1);`
出栈	`.pop()`	`stk.pop();`
取栈顶	`.top()`	`int a = stk.top();`
查看大小 / 清空 / 判空	略	略

代码演示1

运行结果1

vector也可以当栈来用

代码演示2

运行结果2

队列queue

头文件#include <queue>

通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。

常用方法

作用	用法	示例
构造	`queue<类型> que`	`queue<int> que;`
进队	`.push(元素)`	`que.push(1);`
出队	`.pop()`	`que.pop();`
取队首	`.front()`	`int a = que.front();`
取队尾	`.back()`	`int a = que.back();`
查看大小 / 清空 / 判空	略	略

代码演示

运行结果

优先队列priority_queue

头文件#include <queue>

提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

常用方法

构造

priority_queue<类型, 容器, 比较器> pque

类型：要储存的数据类型
容器：储存数据的底层容器，默认为 vector<类型>，竞赛中保持默认即可
比较器：比较大小使用的比较器，默认为 less<类型>，可自定义

priority_queue<int> pque1;                            // 储存int的大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆

其他

作用	用法	示例
进堆	`.push(元素)`	`que.push(1);`
出堆	`.pop()`	`que.pop();`
取堆顶	`.top()`	`int a = que.top();`
查看大小 / 判空	略	略

进出队复杂度 O(\log n)，取堆顶 $O(1).

大顶堆

代码演示1

运行结果1

小顶堆

代码演示2

运行结果2

修改堆顶元素

代码演示3

运行结果3

字符串

string (basic_string<char>)

头文件#include <string>

顾名思义，就是储存字符串的。

常用方法

构造

输入输出

C++

其他

作用	用法	示例
修改、查询指定下标字符	`[]`	`s[1] = 'a';`
是否相同	`==`	`if (s1 == s2) ...`
字符串连接	`+`	`string s = s1 + s2;`
尾接字符串	`+=`	`s += "awa";`
取子串	`.substr(起始下标, 子串长度)`	`string sub = s.substr(2, 10);`
查找字符串	`.find(字符串, 起始下标)`	`int pos = s.find("awa");`

数值与字符串互转（C++11）

源	目的	函数
int / long long / float / double / long double	string	to_string()
string	int	stoi()
string	long long	stoll()
string	float	stof()
string	double	stod()
string	long double	stold()