Introduction to Sets & Maps
集合与映射入门
通过集合（set）和映射（map）维护独特元素/键的集合。
引言
参考资料 | ||||
|---|---|---|---|---|
IUSACO | 4.4 - 集合与映射 | 本模块基于此内容编写 | ||
《算法竞赛入门》（CPH） | 4.2、4.3 - 集合、映射 | 涵盖相似内容 |
集合是独特元素的集合，主要有三种操作：
1. 添加元素
2. 删除元素
3. 检查元素是否存在
映射是键值对（entry）的集合，每个键值对包含一个键（key）和一个值（value）。在映射中，所有键必须是唯一的（即键会构成一个集合），但值可以重复。映射主要有三种操作：
1. 添加指定的键值对
2. 删除键值对
3. 根据给定的键获取对应的值
C++和Java中，集合和映射各有两种实现方式：一种基于排序，另一种基于哈希；Python中的集合和映射则基于哈希实现。
集合
不同的数（Distinct Numbers）
CSES - 简单
重点题目——在继续学习之前，请尽力解决这道题！
有序集合
有序集合会将元素按排序后的顺序存储。所有主要操作（添加、删除、检查）的最坏时间复杂度为$\mathcal{O}(\log N)$，其中$N$是集合中的元素个数。
在C++中，有序集合通过<set>头文件中的std::set实现。对于名为s的std::set，其基本操作包括：
s.insert(x)：若x尚未在s中，则将x添加到s中。s.erase(x)：若x在s中，则将x从s中删除。s.count(x)：若s包含x，则返回1；否则返回0。
也可以使用范围for循环按排序顺序遍历集合。
#include <iostream>
#include <set>
using namespace std;
void demo() {
set<int> s;
s.insert(1); // [1]
s.insert(4); // [1, 4]
s.insert(2); // [1, 2, 4]
s.insert(1); // does nothing because 1's already in the set
cout << s.count(1) << endl; // 1
s.erase(1); // [2, 4]
cout << s.count(5) << endl; // 0
s.erase(0); // does nothing because 0 wasn't in the set
s.insert(6); // [2, 4, 6]
// Outputs 2, 4, and 6 separated by spaces
for (int element : s) { cout << element << " "; }
}哈希集合
哈希集合通过哈希方式存储元素。大致来说，哈希集合包含若干个桶（bucket），数量记为$B$，每个元素通过哈希函数映射到某个桶中。若$B\approx N$，且哈希函数能将每个不同元素独立地映射到随机的桶中，那么每个桶中的元素数量通常很少，所有主要操作的期望时间复杂度为$\mathcal{O}(1)$。
警告！
在最坏情况下，C++中哈希集合的每个操作可能需要$\Theta(N)$的时间，本模块后续会对此进行演示。
在C++中，哈希集合通过<unordered_set>头文件中的std::unordered_set实现。
#include <iostream>
#include <unordered_set>
using namespace std;
void demo() {
unordered_set<int> s;
s.insert(1); // {1}
s.insert(4); // {1, 4}
s.insert(2); // {1, 2, 4}
s.insert(1); // does nothing because 1's already in the set
cout << s.count(1) << endl; // 1
s.erase(1); // {2, 4}
cout << s.count(5) << endl; // 0
s.erase(0); // does nothing because 0 wasn't in the set
s.insert(6); // {2, 4, 6}
// Outputs 6, 2, and 4 separated by spaces (not in sorted order)
for (int element : s) { cout << element << " "; }
}哈希集合可直接用于基本数据类型，但对于vector（向量）、pair（对）等结构体/类，需要自定义哈希函数才能使用。
解决方案 - 不同的数
该问题要求计算给定列表中不同值的个数。
方法1 - 有序集合
由于集合仅存储每个值的一个副本，因此可将所有数字插入集合，然后输出集合的大小。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
set<int> distinctNumbers;
for (int i = 0; i < n; i++) {
int number;
cin >> number;
distinctNumbers.insert(number);
}
cout << distinctNumbers.size() << endl;
}方法2 - 哈希集合
与方法1逻辑相同，只是将有序集合替换为哈希集合。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<int> distinctNumbers;
for (int i = 0; i < n; i++) {
int number;
cin >> number;
distinctNumbers.insert(number);
}
cout << distinctNumbers.size() << endl;
}但该方法在某个测试用例中会失效，该测试用例专门设计为使unordered_set的运行时间达到$\Theta(N^2)$。要解决此问题，可切换为使用set，或使用自定义哈希函数。
在USACO中需要担心抗哈希测试用例吗？
不需要——从历史数据来看，USACO的题目中从未出现过抗哈希测试用例。但这类测试用例在Codeforces中很常见，尤其是在允许公开“hack”（攻击他人代码）的教育场比赛中。
方法3 - 排序
可参考基于排序的解决方案。
映射
关联数组（Associative Array）
YS - 简单
重点题目——在继续学习之前，请尽力解决这道题！
在有序映射中，键值对按键的顺序排序。与有序集合类似，所有主要操作的最坏时间复杂度为$\mathcal{O}(\log N)$，其中$N$是映射中的键值对个数。
在哈希映射中，键值对通过键的哈希值映射到桶中。与哈希集合类似，在对哈希函数有一定假设的前提下，所有主要操作的期望时间复杂度为$\mathcal{O}(1)$。
在C++中，有序映射通过std::map实现，哈希映射通过std::unordered_map实现。
对于名为m的std::map或std::unordered_map，其部分操作包括：
m[key]：返回与键key关联的值的引用。
若key不在映射中，则会使用值类型的默认构造函数创建该键对应的值。例如，若值类型为int，调用m[key]（key不在映射中）会将该键对应的值设为0；若值类型为std::string，则会将该键对应的值设为空字符串。关于此场景下的更多说明，可参考此处。
此外，m.at(key)的行为与m[key]类似（当key在映射中时），但若key不在映射中，m.at(key)会抛出异常。
m[key] = value：将键key对应的值设为value。m.count(key)：返回键key在映射中出现的次数（1或0），可用于检查键是否存在于映射中。m.erase(key)：若键key在映射中，则删除该键对应的键值对。
#include <iostream>
#include <map>
using namespace std;
void demo() {
map<int, int> m;
m[1] = 5; // [(1, 5)]
m[3] = 14; // [(1, 5); (3, 14)]
m[2] = 7; // [(1, 5); (2, 7); (3, 14)]
m[0] = -1; // [(0, -1); (1, 5); (2, 7); (3, 14)]
m.erase(2); // [(0, -1); (1, 5); (3, 14)]
cout << m[1] << endl; // 5
cout << m.count(7) << endl; // 0
cout << m.count(1) << endl; // 1
cout << m[2] << endl; // 0
}遍历映射
std::map以{key, value}形式的键值对存储条目。可使用for循环遍历映射，auto关键字可自动匹配键值对的类型（此处auto等价于pair<int, int>）。
// 两种方式输出结果相同
for (const auto &x : m) { cout << x.first << " " << x.second << endl; }
for (auto x : m) { cout << x.first << " " << x.second << endl; }第一种方式（通过const引用遍历）通常比第二种方式更优，因为第二种方式会对遍历的每个元素进行拷贝。此外，遍历映射时也可通过引用修改值（但不能修改键）：
for (auto &x : m) {
x.second = 1234; // 将所有值修改为1234
}尽管可像上述示例那样在遍历映射时修改值，但通常不建议在遍历过程中插入或删除映射中的元素。
例如，以下代码尝试删除映射中的所有条目，最终会导致段错误（segmentation fault）：
map<int, int> m;
for (int i = 0; i < 10; ++i) m[i] = i;
for (auto &it : m) {
cout << "Current Key: " << it.first << endl;
m.erase(it.first);
}原因是“被函数（指erase）删除的元素对应的迭代器、指针和引用会失效”（如erase的文档所述），不过迭代器相关内容超出了本模块的范围。
解决此问题的一种方法是创建一个新映射，而非在原映射中删除元素：
map<int, int> m, M;
for (int i = 0; i < 10; ++i) m[i] = i;
int current_iteration = 0;
for (const auto &it : m) {
// only includes every third element
if (current_iteration % 3 == 0) { M[it.first] = it.second; }
current_iteration++;
}
swap(m, M);
cout << "Entries:" << endl;
for (const auto &it : m) { cout << it.first << " " << it.second << endl; }
/*
* Entries:
* 0 0
* 3 3
* 6 6
* 9 9
*/另一种方法是先记录所有需要删除的键，待遍历结束后再执行删除操作：
map<int, int> m;
for (int i = 0; i < 10; ++i) { m[i] = i; }
vector<int> to_erase;
int current_iteration = 0;
for (const auto &it : m) {
// removes every third element
if (current_iteration % 3 == 0) { to_erase.push_back(it.first); }
current_iteration++;
}
for (int key : to_erase) { m.erase(key); }
cout << "Remaining entries:" << endl;
for (const auto &it : m) { cout << it.first << " " << it.second << endl; }
/*
* Remaining entries:
* 1 1
* 2 2
* 4 4
* 5 5
* 7 7
* 8 8
*/解决方案 - 关联数组
要高效解决此问题，需要一种具备以下功能的数据结构：
1. 为任意索引k（k最大可达到$10^{18}$）赋值。
2. 快速获取任意索引k的值。
普通数组无法满足需求，因为索引可能极大，导致无法分配足够的内存。但由于所有值初始均为0，且仅有少量索引会被赋值或查询，因此可使用映射（也称为关联数组或字典）仅存储已被赋值的索引。
当接收到0 k v查询时，在映射中执行a[k] = v操作；
当接收到1 k查询时，若k在映射中存在，则输出a[k]；否则输出0。
该方法效率较高，因为映射中的两种操作速度都很快，且仅存储实际使用的键。
需注意，由于k和v可能较大，应使用64位整数。
#include <iostream>
#include <map>
using namespace std;
int main() {
int query_num;
cin >> query_num;
map<long long, long long> a; // Map to store only assigned indices
for (int q = 0; q < query_num; q++) {
int t;
cin >> t;
if (t == 0) {
long long k, v;
cin >> k >> v;
a[k] = v;
} else if (t == 1) {
long long k;
cin >> k;
// If k is not in the map, operator[] returns 0 by default
cout << a[k] << '\n';
}
}
}题目
部分题目仅通过排序即可解决，但使用集合或映射可简化实现过程。
状态 | 来源 | 题目名称 | 难度 | 标签 | ||
|---|---|---|---|---|---|---|
CSES | 两数之和（Sum of Two Values） | 简单 | 显示标签：映射 | |||
青铜级 | 我在哪里？（Where Am I?） | 简单 | 显示标签：集合 | |||
青铜级 | 团队井字棋（Team Tic Tac Toe） | 中等 | 显示标签：集合、模拟 | |||
青铜级 | 牛年（Year of the Cow） | 中等 | 显示标签：映射 | |||
青铜级 | 不要当最后一名！（Don't Be Last!） | 中等 | 显示标签：映射、排序 | |||
白银级 | 城市与州（Cities & States） | 中等 | 显示标签：映射 | |||
CF | 评委分数（Jury Marks） | 中等 | 显示标签：前缀和、集合 | |||
青铜级 | 哞哞时间到（It's Mooin' Time） | 困难 | 显示标签：映射、集合 | |||
AC | 虚构（Made Up） | 困难 | 显示标签：映射 | |||
CF | 分块（Into Blocks） | 困难 | 显示标签：映射、集合 |
测验
