1. 核心概念:无序且唯一#
1.1 基本定义#
#include <unordered_set>
std::unordered_set<int> s;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
unordered_set<int> s;cpp插入元素:
s.insert(30);
s.insert(10);
s.insert(20);
s.insert(10); // 重复插入不会改变集合
cout << s.size(); // 3cpp1.2 三个关键词#
- 哈希:根据 key 的哈希值快速定位。
- 无序:遍历顺序不是升序,也不保证插入顺序。
- 唯一:相等 key 只保留一个。
1.3 与 set 的本质区别#
set:有序树形集合,操作通常稳定O(log n),支持前驱、后继和最值。unordered_set:哈希集合,平均O(1),最坏可退化为O(n),没有顺序语义。
1.4 与 unordered_map 的本质区别#
- unordered_set:只保存 key,用于存在性判断。
- unordered_map:保存 key 到 value 的映射。
如果需要记录次数、下标、距离、分组等额外信息,应使用 unordered_map;如果只关心是否出现过,使用 unordered_set 更省、更直接。
2. 创建与初始化#
unordered_set<int> a;
unordered_set<string> b;
unordered_set<int> c = {1, 2, 3, 3}; // 实际保存 1 2 3
vector<int> v = {5, 1, 5, 3};
unordered_set<int> d(v.begin(), v.end()); // 区间构造并去重cpp已知大致元素数量时提前预留:
s.reserve(n * 2);cpp可以减少扩容与 rehash。是否乘以 2 取决于负载因子和内存需求,不必机械照搬。
3. 插入:insert 与 emplace#
3.1 insert#
auto [it, inserted] = s.insert(x);cpp- key 不存在:插入,
inserted == true。 - key 已存在:不插入,
inserted == false,it指向已有元素。
高频判断:
if (!s.insert(x).second) {
// x 已经出现过
}cpp3.2 批量插入#
s.insert(v.begin(), v.end());
s.insert({1, 2, 3});cpp3.3 emplace#
setState.emplace(args...);cpp对 int 等基本类型,与 insert 通常没有性能差别;对可构造的复合 key,可直接传递构造参数。
3.4 没有覆盖概念#
set 元素本身只有 key,没有 mapped value,因此重复插入不是“更新”,只是不生效。需要更新信息应改用 unordered_map。
4. 查询:find、count、contains#
4.1 find#
auto it = s.find(x);
if (it != s.end()) {
// x 存在
}cppfind 返回指向元素的迭代器;不存在返回 s.end()。
4.2 count#
if (s.count(x)) {}cppunordered_set 中 count 只会是 0 或 1。写 if (s.count(x)) 简洁,但 find 可以同时拿到迭代器。
4.3 contains:C++20#
if (s.contains(x)) {}cpp4.4 不存在时不会有副作用#
与 unordered_map 的 operator[] 不同,unordered_set 没有 operator[],查询不会自动插入元素:
// s[x]; // 错误:set 没有 operator[]cpp5. 删除:erase 与 clear#
5.1 按值删除#
size_t removed = s.erase(x); // 返回 0 或 1cpp删除不存在的 key 不会产生错误,只是返回 0。
5.2 按迭代器删除#
auto it = s.find(x);
if (it != s.end()) {
it = s.erase(it); // 返回后继迭代器
}cpp5.3 遍历时删除#
for (auto it = s.begin(); it != s.end();) {
if (*it < 0) it = s.erase(it);
else ++it;
}cpp5.4 清空#
s.clear();cpp删除全部元素。清空后的桶数不一定立即缩小到初始状态,不要依赖容量细节。
6. 遍历与迭代器#
6.1 遍历#
for (int x : s) {
cout << x << ' ';
}cpp6.2 顺序未指定#
不要假设:
- 升序。
- 降序。
- 插入顺序。
- 跨平台一致。
- rehash 前后一致。
需要有序输出时,把元素复制到 vector 后排序:
vector<int> a(s.begin(), s.end());
sort(a.begin(), a.end());cpp6.3 迭代器能力#
unordered_set 提供至少前向迭代器,不支持随机访问,也没有 rbegin():
// s.begin() + 3; // 错误
// --s.end(); // 不能当作有序容器的最大元素操作cpp6.4 元素不可修改#
set 的 key 是哈希定位依据,不能通过迭代器原地修改:
// *s.begin() = 100; // 错误cpp需要修改时,删除旧值再插入新值。
6.5 结构性修改与失效#
- rehash 会使迭代器失效,并可能改变遍历顺序。
- 插入可能触发 rehash。
- 删除只会使指向被删元素的迭代器、指针和引用失效。
- 修改容器后不要继续使用可能失效的旧迭代器。
不要在范围 for 中随意插入元素;应先收集新增元素,循环结束后统一插入。
7. 复杂度、桶与扩容#
7.1 常用复杂度#
设元素数为 n:
| 操作 | 平均复杂度 | 最坏复杂度 |
|---|---|---|
insert / emplace |
O(1) |
O(n) |
find / count |
O(1) |
O(n) |
按值 erase |
O(1) |
O(n) |
按迭代器 erase |
O(1) |
通常 O(1) |
| 遍历 | O(n) |
O(n) |
clear |
O(n) |
O(n) |
| rehash | O(n) |
O(n) |
字符串 key 还要考虑哈希计算与字符串比较的线性长度成本。
7.2 桶与负载因子#
s.bucket_count(); // 桶数
s.load_factor(); // size / bucket_count
s.max_load_factor(); // 最大负载因子cpp调整最大负载因子:
s.max_load_factor(0.7f);cpp较小负载因子通常减少冲突但增加内存;竞赛一般保持默认,除非性能需求明确。
7.3 reserve 与 rehash#
s.reserve(n); // 为至少 n 个元素预留
s.rehash(n); // 桶数至少为 ncpp区别:
reserve(n)以元素数量为目标,减少插入 n 个元素期间的 rehash。rehash(n)以桶数量为目标。
大规模插入前优先使用 reserve。
8. 应用一:去重与重复检测#
8.1 统计不同元素个数#
unordered_set<int> s;
s.reserve(n * 2);
for (int x : a) s.insert(x);
int distinct = s.size();cpp8.2 判断是否存在重复元素#
unordered_set<int> seen;
seen.reserve(a.size() * 2);
for (int x : a) {
if (!seen.insert(x).second) {
// x 是重复元素
}
}cpp平均时间 O(n),空间 O(n)。
8.3 得到去重后的数组#
unordered_set<int> s(a.begin(), a.end());
vector<int> b(s.begin(), s.end());cpp此时 b 的顺序未指定。若需要升序,继续排序:
sort(b.begin(), b.end());cpp若只需要静态数组有序去重,sort + unique 通常比哈希表更直接。
9. 应用二:访问标记与状态集合#
9.1 BFS/DFS 已访问集合#
unordered_set<int> vis;
vis.insert(start);
if (!vis.count(v)) {
vis.insert(v);
// 加入搜索结构
}cpp当节点编号是连续整数且范围可接受时,vector<char> vis(n+1) 通常更快;当状态稀疏、很大或不是整数时,哈希集合更合适。
9.2 坐标状态#
二维坐标可以编码为一个整数,或使用 pair key 加自定义哈希。编码必须考虑范围和负数,不能盲目乘法:
long long key = 1LL * x * width + y; // 仅当范围设计安全时cpp更通用的做法是使用 unordered_set<pair<int,int>, PairHash>。
9.3 字符串状态#
unordered_set<string> seen;
seen.insert(state);cppstring 哈希成本与长度相关,状态很长时应考虑滚动哈希、压缩状态或专门编码。
10. 应用三:集合运算#
10.1 交集#
vector<int> intersection;
const auto &small = a.size() <= b.size() ? a : b;
const auto &large = a.size() <= b.size() ? b : a;
for (int x : small) {
if (large.count(x)) intersection.push_back(x);
}cpp要求结果去重时,可再对交集去重,或遍历时维护一个输出集合。若两个输入本身都是 set,遍历时不会重复。
10.2 并集#
unordered_set<int> uni = a;
uni.insert(b.begin(), b.end());cpp10.3 差集:a 有而 b 没有#
vector<int> diff;
for (int x : a) {
if (!b.count(x)) diff.push_back(x);
}cpp这些操作直接实现通常需要与较小集合规模相关的时间和结果空间;若需要严格集合论去重语义,要注意输入是否本身已去重。
11. 应用四:最长连续序列#
要求在未排序数组中找最长连续整数序列长度:
int longestConsecutive(const vector<int> &a) {
unordered_set<long long> s(a.begin(), a.end());
int ans = 0;
for (long long x : s) {
if (s.count(x - 1)) continue; // 只从连续段起点开始
long long y = x;
while (s.count(y + 1)) ++y;
long long len = y - x + 1;
ans = max<long long>(ans, len);
}
return ans;
}cpp关键点:
- 全部元素先放入哈希集合,自动去重。
- 只有
x-1不存在时,x才是连续段起点。 - 从起点向后扩展,避免每个元素都从头扫描造成
O(n^2)。 - 使用 long long 防止
INT_MIN-1或INT_MAX+1溢出。 - 平均时间
O(n),空间O(n);哈希最坏情况可能退化。
12. 自定义 key 与防哈希攻击#
12.1 pair 默认不能直接作为 key#
// unordered_set<pair<int,int>> points; // 默认没有 std::hash<pair<int,int>>cpp12.2 splitmix64 基础哈希#
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};cpp使用:
unordered_set<long long, custom_hash> safeSet;cpp12.3 pair 哈希#
struct PairHash {
size_t operator()(pair<int,int> p) const noexcept {
uint64_t a = static_cast<uint32_t>(p.first);
uint64_t b = static_cast<uint32_t>(p.second);
uint64_t mixed = a ^ (b + 0x9e3779b97f4a7c15ULL + (a << 6) + (a >> 2));
return custom_hash{}(mixed);
}
};
unordered_set<pair<int,int>, PairHash> points;
points.insert({1, 2});cpp12.4 自定义结构体#
struct Point {
int x, y;
bool operator==(const Point &other) const {
return x == other.x && y == other.y;
}
};
struct PointHash {
size_t operator()(const Point &p) const noexcept {
return PairHash{}({p.x, p.y});
}
};
unordered_set<Point, PointHash> seen;cpp哈希与相等比较必须一致:若 a == b,必须有 hash(a) == hash(b)。
12.5 为什么需要随机化哈希#
固定、容易预测的整数哈希可能被针对性构造大量冲突,使平均 O(1) 退化为最坏 O(n)。splitmix64 加随机启动种子是竞赛中常见的防护手段,但不是密码学安全保证。
13. 与其他容器的选择#
| 需求 | 推荐容器 |
|---|---|
| 只判断 key 是否存在,不要求顺序 | unordered_set |
| 要求有序、前驱、后继、最值 | set |
| 允许重复元素且不要求顺序 | unordered_multiset |
| 允许重复且要求有序 | multiset |
| 需要记录 key 对应的次数、下标等 | unordered_map 或 map |
| key 是连续小整数 | vector<char> 或 vector<int> 更快 |
| 静态数组有序去重 | sort + unique |
| 需要严格最坏复杂度 | 有序树结构通常更稳定 |
13.1 与 set 对比#
- unordered_set:平均快,但无序且最坏可退化。
- set:每次通常稳定
O(log n),能直接做有序边界查询。
13.2 与 unordered_map 对比#
- 只存存在性:unordered_set。
- key 附带任何数据:unordered_map。
13.3 与 vector 布尔数组对比#
若 key 范围小且连续:
vector<char> seen(maxValue + 1, false);cpp通常比 unordered_set 更快、更省、遍历稳定。key 稀疏、范围巨大或类型不是整数时再考虑哈希集合。
14. 高频错误与避坑清单#
14.1 误以为遍历有序#
unordered_set 的 begin() 不是最小值,遍历顺序未指定。需要有序输出必须排序或使用 set。
14.2 期待 operator[]#
unordered_set 没有 operator[]。查询用 find/count,插入用 insert。
14.3 忘记重复插入不生效#
insert 返回的 bool 表示是否插入;不要用 size 变化之外的方式假设旧值被覆盖,因为根本没有 value 可覆盖。
14.4 直接拿 pair/tuple 作 key#
默认没有相应 std::hash,需要自定义哈希或安全编码。
14.5 遍历时插入触发 rehash#
插入可能使迭代器失效。应收集待插入元素,循环后统一处理。
14.6 忽略最坏复杂度#
平均 O(1) 不等于严格 O(1)。大量冲突会退化,竞赛环境可考虑随机化自定义哈希。
14.7 状态编码溢出或负数冲突#
把二维坐标编码成一个整数前,必须确认范围和符号;不确定时使用 pair + hash 更安全。
14.8 对连续小整数滥用哈希#
vector<char> 通常比 unordered_set 更快,尤其在大规模 BFS 标记中。
15. 一页速记#
#include <unordered_set>
unordered_set<int> s;
unordered_set<string> words;
s.reserve(n); // 预计元素数,减少 rehash
s.insert(x); // 重复插入无效
auto [it, inserted] = s.insert(x);
if (!s.insert(x).second) {} // x 已存在
auto it2 = s.find(x); // 不存在返回 end()
if (it2 != s.end()) {}
if (s.count(x)) {} // count 只会是 0 或 1
s.erase(x); // 返回 0 或 1
auto it3 = s.find(x);
if (it3 != s.end()) it3 = s.erase(it3);
for (int x : s) {} // 顺序未指定
for (auto it = s.begin(); it != s.end();) {
if (condition(*it)) it = s.erase(it);
else ++it;
}
s.size(); s.empty(); s.clear();
s.bucket_count(); s.load_factor();
// 不同元素个数
unordered_set<int> distinct(a.begin(), a.end());
int cnt = distinct.size();
// 有序输出去重结果
vector<int> b(distinct.begin(), distinct.end());
sort(b.begin(), b.end());
// BFS 访问标记
unordered_set<int> vis;
vis.insert(start);
if (!vis.count(v)) {
vis.insert(v);
// 加入队列或栈
}cpp最终必须牢牢记住:
- unordered_set 只保存唯一 key,用于存在性判断,不保存 value。
- 遍历顺序未指定,
begin()不是最小元素。 - 插入、查找、删除平均
O(1),最坏可能O(n)。 - 没有
operator[],查询使用find/count,不会隐式插入。 insert(x).second == false表示 x 已存在。- pair、tuple、自定义结构体需要自定义 Hash 与相等比较。
- 大规模插入前使用
reserve,连续小整数下标优先 vector 标记。 - 需要有序、前驱、后继或最值时使用 set。