麦地

Back

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(); // 3
cpp

1.2 三个关键词#

  1. 哈希:根据 key 的哈希值快速定位。
  2. 无序:遍历顺序不是升序,也不保证插入顺序。
  3. 唯一:相等 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 已经出现过
}
cpp

3.2 批量插入#

s.insert(v.begin(), v.end());
s.insert({1, 2, 3});
cpp

3.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 存在
}
cpp

find 返回指向元素的迭代器;不存在返回 s.end()。

4.2 count#

if (s.count(x)) {}
cpp

unordered_set 中 count 只会是 0 或 1。写 if (s.count(x)) 简洁,但 find 可以同时拿到迭代器。

4.3 contains:C++20#

if (s.contains(x)) {}
cpp

4.4 不存在时不会有副作用#

与 unordered_map 的 operator[] 不同,unordered_set 没有 operator[],查询不会自动插入元素:

// s[x]; // 错误:set 没有 operator[]
cpp

5. 删除:erase 与 clear#

5.1 按值删除#

size_t removed = s.erase(x); // 返回 0 或 1
cpp

删除不存在的 key 不会产生错误,只是返回 0。

5.2 按迭代器删除#

auto it = s.find(x);
if (it != s.end()) {
    it = s.erase(it); // 返回后继迭代器
}
cpp

5.3 遍历时删除#

for (auto it = s.begin(); it != s.end();) {
    if (*it < 0) it = s.erase(it);
    else ++it;
}
cpp

5.4 清空#

s.clear();
cpp

删除全部元素。清空后的桶数不一定立即缩小到初始状态,不要依赖容量细节。


6. 遍历与迭代器#

6.1 遍历#

for (int x : s) {
    cout << x << ' ';
}
cpp

6.2 顺序未指定#

不要假设:

  • 升序。
  • 降序。
  • 插入顺序。
  • 跨平台一致。
  • rehash 前后一致。

需要有序输出时,把元素复制到 vector 后排序:

vector<int> a(s.begin(), s.end());
sort(a.begin(), a.end());
cpp

6.3 迭代器能力#

unordered_set 提供至少前向迭代器,不支持随机访问,也没有 rbegin():

// s.begin() + 3; // 错误
// --s.end();     // 不能当作有序容器的最大元素操作
cpp

6.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);  // 桶数至少为 n
cpp

区别:

  • 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();
cpp

8.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);
cpp

string 哈希成本与长度相关,状态很长时应考虑滚动哈希、压缩状态或专门编码。


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());
cpp

10.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

关键点:

  1. 全部元素先放入哈希集合,自动去重。
  2. 只有 x-1 不存在时,x 才是连续段起点。
  3. 从起点向后扩展,避免每个元素都从头扫描造成 O(n^2)。
  4. 使用 long long 防止 INT_MIN-1 或 INT_MAX+1 溢出。
  5. 平均时间 O(n),空间 O(n);哈希最坏情况可能退化。

12. 自定义 key 与防哈希攻击#

12.1 pair 默认不能直接作为 key#

// unordered_set<pair<int,int>> points; // 默认没有 std::hash<pair<int,int>>
cpp

12.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;
cpp

12.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});
cpp

12.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. 一页速记#

最终必须牢牢记住:

  1. unordered_set 只保存唯一 key,用于存在性判断,不保存 value。
  2. 遍历顺序未指定,begin() 不是最小元素。
  3. 插入、查找、删除平均 O(1),最坏可能 O(n)。
  4. 没有 operator[],查询使用 find/count,不会隐式插入。
  5. insert(x).second == false 表示 x 已存在。
  6. pair、tuple、自定义结构体需要自定义 Hash 与相等比较。
  7. 大规模插入前使用 reserve,连续小整数下标优先 vector 标记。
  8. 需要有序、前驱、后继或最值时使用 set。
Comment seems to stuck. Try to refresh?✨