STL 容器

stack

queue

pair

pair 是一个容器，可以存储两个不同类型的值。例如，pair<int, string> a 可以存储一个整数和一个字符串。可以简单理解为系统自带的两个元素的结构体。
获取元素一：a.first，获取元素二：a.second。
pair 已经实现了默认的比较方式，即两个 pair 比较先按照 first 优先，first 相同比 second。
因此 pair 类型可以直接使用 sort 函数。（当需要按照 first 优先比较的时候）

pair<int, int> a[N];

for (int i = 1; i <= n; i++)
{
    cin >> a[i].first >> a[i].second;
}

sort(a + 1, a + n + 1); // 直接按 first 优先从小到大排序

sort(a + 1, a + n + 1, greater<>()); // 按照 first 优先从大到小排序

array

array 是一个数组容器。例如，array<int, 3> a 相当于一个大小为 $3$ 的 int 数组，其元素分别为 $a[0],\ a[1],\ a[2]$ 。
array 已经实现了默认的比较方式，即两个 array 比较先按照下标为 $0$ 的优先，下标为 $0$ 的相同的继续向后比，以此类推。
array 比 pair 更适用于多个元素的情况，但 array 要求所有元素类型必须一致。

array<int, 3> a[N];
for (int i = 1; i <= n; i++)
{
    cin >> a[i][0] >> a[i][1] >> a[i][2];
}

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

sort(a + 1, a + n + 1, greater<>());

总结

是否有自带的支持超过 $2$ 个以上元素且元素类型可以不同的容器？

答：tuple（元组），感兴趣可以自学。或者选择 pair 套 pair。例 pair<int, pair<char, bool>>

map

概述

map 是有序键值对容器，它的元素的键是唯一的。查找、删除和插入操作拥有对数复杂度（ $\log{n}$ ）。map 通常实现为 $\textbf{红黑树}$ 。

定义：map<键, 值> 变量名。其中键和值写对应的元素类型即可。例如：

map<int, int> mp。定义一个键和值都是 int 类型的 map。
map<string, int> mp。定义一个键是 string，值是 int 类型的 map。
map<vector<int>, int> mp。定义一个键是 vector<int>，值是 int 类型的 map。
map<int, vector<int>> mp。定义一个键是 int，值是 vector<int> 类型的 map。
map<int, map<int, int>> mp。定义一个键是 int，值是 map<int, int> 类型的 map。

注意键必须是支持比较的类型。若使用自定义的结构体类型时，还需要自定义比较规则传入 map。

基础使用

以 map<int, int> mp 为例，设 $n$ 为 map 里存储的元素个数。

修改（创建）：和数组用法类似，执行 mp[x] = y。只要 $x$ 和 $y$ 均在 int 范围内即可。复杂度 $O(\log{n})$
查找（查找键）：使用 count 函数，mp.count(x)。返回值为 true 说明存在键 $x$ ，否则不存在。复杂度 $O(\log{n})$
删除（删除键）：使用 erase 函数，mp.erase(x)。 $\textcolor{red}{前提键 x 存在}$ ，复杂度 $O(\log{n})$
键的个数：使用 size 函数。mp.size() 可以求出存了几个键（几个键值对）。
清空 map：使用函数 clear 完成 mp.clear()，可以清除 map 的所有键值对。

map 的遍历

以 map<int, int> mp 为例。

法一

使用迭代器遍历。首先 map<int, int> iterator:: it。创建一个名为 it 的 map<int, int> 的迭代器。

map<int, int> iterator:: it;
for (it = mp.begin(); it != mp.end(); ++it)
{
    // 键是 it->first，值是 it->second
    cout << it->first << " " << it->second << "\n";
}

-> 运算符： -> 是一个成员访问运算符。对于迭代器，它用于访问迭代器所指向的元素的成员。

map 的键值对是一个 pair 对象，当我们使用迭代器遍历时，需要使用 it->first 和 it->second 分别获取键和值。

法二

使用 auto 遍历。语法简单且推荐。

for (auto it : mp)
{
    // 键是 it.first，值是 it.second
    cout << it.first << " " << it.second << "\n";
}

应用场景

通俗理解 map 就是一个下标是任意类型的 $\textbf{数组}$ ，通过以下例子体会 map 的使用场景。

输入 $n$ 个数字 $a_i$ ，请统计每个数字的出现次数。（ $1\leq n,a_i\leq 10^5$ ）

答：简单，开一个大小为 $10^5$ 的数组 cnt，执行 cnt[x]++ 即可。

输入 $n$ 个数字 $a_i$ ，请统计每个数字的出现次数。（ $1\leq n\leq 10^5$ ， $1\leq a_i\leq 10^9$ ）

答：开大小为 $10^9$ 的数组通常会 MLE。主要是由于只存储 $10^5$ 个数字，但数值范围过大，有很多位置根本不需要。如何解决？

定义 map<int, int> cnt 即可，如果存储 long long 范围内的数字就改为 map<long long, int> cnt。

输入 $n$ 个字符串 $s$ ，请统计每个字符串的出现次数。

答：定义 map<string, int> cnt 即可。

算法函数

由于 map 自动按照键排序，因此支持一些算法函数。

以 map<int, int> mp 为例。

lower_bound(x): 返回指向刚好大于或等于 $x$ 的 $\textcolor{red}{键的迭代器}$ 。

mp.lower_bound(x)。注意和 vector 和数组的使用方式区分。

返回值是迭代器，不存在返回 mp.end()。

auto it = mp.lower_bound(x);
if (it != mp.end())
{
    cout << it->first << " " << it->second;
}

upper_bound(x): 返回指向刚好大于 $x$ 的 $\textcolor{red}{键的迭代器}$ 。用法同上

二维 map

方式一：map<int, int> mp[100005]。每一个 mp[i] 都是一个 map。例如：mp[i][j] = k。

$\textcolor{red}{mp[i] 指的是第 i 个 map，第 i 个 map 创建了一个键为j 其值是 k。}$

方式二：定义 map<int, map<int, int>> mp 即可。 $\textcolor{red}{键是 int，其对应的值又是一个 map，相当于是一个二维的 map}$

$\textcolor{red}{mp[i] 指的是键为 i，其对应的值又是一个 map，在值这个 map 里，键是 j，值是 k。}$

unordered_map

unordered_map 是 C++ 标准库（STL）中的一个关联容器，用于存储键值对。它基于哈希实现， $\textcolor{red}{内部元素不以任何特定顺序进行排序}$ 。它的大部分操作最好情况下的时间复杂度是常数级别的，但最坏情况下都是 $O(n)$ 。（产生哈希冲突）

其大部分操作和 map 相同，但由于键不排序所以无法使用二分函数。

以下操作 $\textcolor{red}{在平均情况下}$ 复杂度为常数级别， $\textcolor{red}{最坏情况下}$ 为 $O(n)$ 。

以 unordered_map<int, int> mp 为例。

创建或赋值：mp[x] = y，平均复杂度为 $O(1)$ ，最坏复杂度为 $O(n)$ 。
删除 erase：mp.erase(x)，删除键 $x$ ，复杂度同上。
查找键 count: mp.count(x)，判断键是否存在，复杂度同上。
其他函数：size（键的个数），clear（清空）等。

multimap

它和 map 的区别在于：map 的键是唯一的，而 multimap 键是可以重复的。即可以储存更多的信息。因此操作函数会有一些差别。

由于键依然排序，所以复杂度还是 $O(\log{n})$ 级别的。

insert：插入键值对函数，例如 mp.insert({1, 3})，插入键是 $1$ 值是 $3$ 。不支持像 map 一样的赋值操作。
find：查找键 $\textcolor{red}{第一次出现}$ 的位置，返回值为迭代器。
erase：删除键或删除迭代器。由于键可以重复，若传入键会删除所有的键，用时需谨慎。
count：统计键的个数。
支持二分函数，lower_bound 和 upper_bound。

总结

map 就像是一个下标可以是任意类型的数组。掌握好 map 的使用很多题做起来都游刃有余。

set

概述

set 是一个关联式容器。其内部元素自动排序且去重（默认升序）。搜索、移除和插入拥有 $\log$ 级别的复杂度。

set<类型名> 变量名。

set<int> s, set<long long> s
set<string> s, set<pair<int, int>> s

操作函数

以 set<int> s 为例。

s.insert(x) 当容器中没有等价元素的时候，将元素 $x$ 插入到 set 中。时间复杂度 $O(\log{n})$
s.erase(x) 删除值为 $x$ 的元素。时间复杂度 $O(\log{n})$
s.erase(pos) 删除迭代器为 $pos$ 的元素，要求迭代器必须存在，否则 RE。时间复杂度 $O(\log{n})$
s.erase(first,last) 删除迭代器在 $[first,last)$ 范围内的所有元素。（不包括迭代器 last）
s.clear() 清空 set。

注意一些和迭代器有关的操作先判断是否存在该迭代器在操作，例如 s.erase(s.begin()) 相当于删除集合的最小值。若集合为空这是一个会造成 RE 的操作。

其余函数和技巧

find 函数，s.find(x) 判断集合里是否存在 $x$ ，返回值为迭代器，不存在返回 s.end()。时间复杂度 $O(\log{n})$
lower_bound 函数，s.lower_bound(x) 找到集合里首个大于或等于元素 $x$ 的迭代器，不存在返回 s.end()。
upper_bound 同上，找到首个大于 $x$ 的迭代器。
获取最小值：auto it = s.begin()。

注意 it 是一个迭代器。通过 *it 解引用获取迭代器对应的数值。

获取最大值：auto it = s.rbegin()，利用 rbegin 逆迭代器即可。

multiset

multiset 是一个关联式容器。其内部元素自动排序（默认升序） $\textcolor{red}{不去重}$ 。搜索、移除和插入拥有 $\log$ 级别的复杂度。

multiset<类型名> 变量名。下面以 multiset<int> s 为例。

插入和二分等函数都没有区别。
注意删除函数的差异。

按值删除：s.erase(x)，会删除所有的 $x$ 。

按迭代器删除：只会删除迭代器这个位置的元素。

auto it = s.find(x); // 找到第一个 x 的迭代器
if (it != s.end()) s.erase(it); // 不存在别删除

其它类型的 set

unordered_set：无序集合，元素去重但不排序。竞赛中不常用。
unordered_multiset：无序可重集合，元素不去重也不排序。竞赛中不常用。

STL课件

认领作业后才可以查看作业内容。

状态: 正在进行…
题目: 11
开始时间: 2025-8-17 0:00
截止时间: 2026-8-5 22:00
可延期: 24 小时

作业介绍