C++ STL精通之旅：向量、集合与映射等容器详解
C++ STL精通之旅：向量、集合与映射等容器详解
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>
提供对数时间的有序键值对结构。底层原理是红黑树。
映射：
性质 | 解释 | 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++
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() |
尾接字符串一定要用 +=
代码演示
运行结果
对与元组
- 二元组pair
头文件#include <utility>
顾名思义，就是储存二元组的。
常用方法
构造
pair<第一个值类型, 第二个值类型> pr
- 第一个值类型：要储存的第一个值的数据类型
- 第二个值类型：要储存的第二个值的数据类型
赋值
老式
列表构造 C++11
取值
直接取值
- 取第一个值：
.first - 取第二个值：
.second
结构化绑定 C++17
判同
直接用 == 运算符
适用场景
所有需要二元组的场景均可使用，效率和自己定义结构体差不多。
代码演示
运行结果
希望对你有帮助！加油！
若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！