C++ std::unordered_set

std::unordered_set 是 C++ STL 中的无序关联容器，其核心特性是存储唯一元素且不保证元素顺序，底层基于哈希表实现，因此插入、查找、删除操作的平均时间复杂度为 O(1)。与 std::set（红黑树实现）相比，它更适合对查找速度有高要求且无需元素有序的场景。

1、底层数据结构与核心特性

1.1 底层数据结构

• 底层结构：哈希表（Hash Table）。
• 核心特性：
  1. 关联性：元素是键（Key）本身。
  2. 无序性：容器中的元素是无序的。元素的存储顺序取决于其哈希值以及它们如何被映射到桶中。遍历集合时，元素的顺序是不确定的，并且可能在插入新元素后发生改变。
  3. 唯一性：集合中每个元素的键都是唯一的。
• 实现原理：
  • 容器维护一个桶数组（Array of Buckets）。
  • 通过一个哈希函数（Hash Function）将元素的键转换成一个哈希值（通常是一个 size_t 类型的数）。
  • 根据哈希值通过某种映射（通常是 hash_value % bucket_count）计算出该元素应该属于哪个桶（Bucket）。
  • 不同的键可能被映射到同一个桶中，这称为哈希冲突。std::unordered_set 采用链地址法（Separate Chaining）解决冲突，即每个桶实际上是一个链表（或一个小型容器），所有映射到同一桶的元素都放在这个链表中。

1.2 核心特性与原理

1. 平均常数时间复杂度 (O(1))

   • 在理想情况下（哈希函数均匀，冲突极少），插入、删除和查找操作的平均时间复杂度是常数级的，即 O(1)。
   • 这是 unordered_set 相对于 set 最大的优势。

2. 最坏情况时间复杂度 (O(n))

   • 在最坏情况下（例如，哈希函数极差，所有元素都冲突到同一个桶中），整个哈希表退化为一个链表，所有操作的时间复杂度都变为线性级 O(n)。
   • 因此，选择一个好的哈希函数至关重要。

3. 负载因子与重哈希（Rehashing）

   • 负载因子（Load Factor）：load_factor = size() / bucket_count()。它衡量一个桶的平均元素数量，是哈希表“满”程度的指标。
   • 最大负载因子（Max Load Factor）：一个阈值。当 load_factor > max_load_factor 时，容器会自动执行重哈希。
   • 重哈希过程：
     1. 分配一个更大的新桶数组（通常是大约两倍于原来的质数大小）。
     2. 遍历所有现有元素，根据新的桶数量重新计算每个元素的哈希值和桶索引。
     3. 将所有元素插入到新的桶数组中。
     4. 释放旧的桶数组。
   • 重哈希是一个开销很大的操作，会导致所有迭代器失效。

4. 迭代器不稳定性

   • 插入操作可能会导致重哈希，从而使所有迭代器失效。
   • 删除操作只会使指向被删除元素的迭代器失效。

2. 操作指导与代码示例

2.1 初始化与构造函数

#include <unordered_set>
#include <iostream>// 1. 空unordered_set
std::unordered_set<int> uset1;// 2. 使用初始化列表 (C++11)
std::unordered_set<int> uset2 = {5, 2, 8, 1, 2, 4}; // 重复的2会被忽略 -> {1, 2, 4, 5, 8} (顺序不确定!)// 3. 通过迭代器范围（另一个容器的）
std::vector<int> vec = {6, 7, 7, 8, 1};
std::unordered_set<int> uset3(vec.begin(), vec.end()); // {1, 6, 7, 8} (顺序不确定)// 4. 指定初始桶数量（用于性能调优）
std::unordered_set<std::string> uset4(100); // 创建时约有100个桶// 5. 拷贝构造函数
std::unordered_set<int> uset5(uset2);

2.2 元素访问与查找

std::unordered_set<std::string> fruits = {"apple", "banana", "orange"};// 1. find: 查找元素，返回迭代器
auto it = fruits.find("banana");
if (it != fruits.end()) {std::cout << "Found: " << *it << "\n";
} else {std::cout << "Not found\n";
}// 2. count: 检查存在性，对于set只能是0或1
if (fruits.count("apple") > 0) {std::cout << "Apple is in the set\n";
}// 3. 访问桶接口（高级用法，通常用于调试）
size_t bucket_index = fruits.bucket("apple"); // "apple" 所在的桶的索引
size_t bucket_size = fruits.bucket_size(bucket_index); // 该桶中有多少个元素
std::cout << "'apple' is in bucket #" << bucket_index << " which has " << bucket_size << " elements.\n";

2.3 增加元素

std::unordered_set<int> uset;// 1. insert: 插入一个值
std::pair<std::unordered_set<int>::iterator, bool> ret1 = uset.insert(100);
if (ret1.second) {std::cout << "Insertion of 100 succeeded.\n";
}// 2. emplace: 原地构造，避免临时对象，更高效
// 直接传递构造参数给emplace
auto ret2 = uset.emplace(200);
if (ret2.second) {std::cout << "Emplace of 200 succeeded.\n";
}// 3. 插入提示版本（效率提升有限，因为unordered_set的插入位置由哈希决定）
uset.insert(uset.begin(), 300); // 提示通常被忽略

2.4 删除元素

std::unordered_set<int> uset = {10, 20, 30, 40, 50};// 1. erase by key: 删除键为30的元素，返回删除的元素个数（0或1）
size_t numErased = uset.erase(30); // numErased = 1// 2. erase by iterator: 删除指定位置的元素，更高效
auto it = uset.find(20);
if (it != uset.end()) {uset.erase(it);
}// 3. erase by range: 删除一个区间的元素 [first, last)
// (不常用，因为元素无序)
auto first = uset.find(40);
auto last = uset.end();
uset.erase(first, last); // 删除40和50

2.5 遍历元素

std::unordered_set<std::string> uset = {"apple", "banana", "cherry", "date"};// 1. 范围for循环 (最常用)
std::cout << "Elements: ";
for (const auto& elem : uset) {std::cout << elem << " ";
}
// 输出顺序不确定，可能是: date apple cherry banana
std::cout << "\n";// 2. 使用迭代器
for (auto it = uset.begin(); it != uset.end(); ++it) {std::cout << *it << " ";
}
std::cout << "\n";// 注意：遍历顺序是无意义的，并且可能随时间（插入/删除）而改变。

2.6 容量与性能管理

std::unordered_set<int> uset;// 1. 预留空间：避免多次重哈希，提升性能
uset.reserve(1000); // 预留至少能容纳1000个元素的空间，容器会自动选择足够的桶数// 2. 重哈希：手动控制，强制将桶数调整为至少 n
uset.rehash(500); // 强制桶数 >= 500// 3. 查看当前状态
std::cout << "Size: " << uset.size() << "\n";
std::cout << "Bucket count: " << uset.bucket_count() << "\n"; // 桶的数量（通常是质数）
std::cout << "Load factor: " << uset.load_factor() << "\n"; // 当前负载因子
std::cout << "Max load factor: " << uset.max_load_factor() << "\n"; // 最大负载因子（默认~1.0）// 4. 修改最大负载因子
uset.max_load_factor(0.75f); // 设置更小的最大负载因子，减少冲突概率，但可能增加内存使用

2.7 自定义类型作为键

要让自定义类型（如MyClass）作为 unordered_set 的键，你需要为其定义两个东西：

1. 哈希函数：告诉容器如何计算对象的哈希值。
2. 相等比较函数：告诉容器如何判断两个对象是否相等。

2.7.1 特化 std::hash 模板并重载 operator==（推荐，最简洁）

struct Person {std::string name;int age;// 1. 必须重载 operator==bool operator==(const Person& other) const {return name == other.name && age == other.age;}
};// 2. 打开std命名空间，特化std::hash模板
namespace std {template<>struct hash<Person> {size_t operator()(const Person& p) const {// 组合各个成员的哈希值（这是一个简单示例，更好的方法见下文）return hash<std::string>()(p.name) ^ (hash<int>()(p.age) << 1);}};
}// 现在可以直接使用
std::unordered_set<Person> personSet;
personSet.insert({"Alice", 25});
personSet.insert({"Bob", 30});

2.7.2 提供自定义的哈希器和相等比较器作为模板参数

struct Person {std::string name;int age;
};// 自定义哈希器
struct PersonHash {size_t operator()(const Person& p) const {// 更好的哈希组合方式：使用现成的hash_combine技术size_t h1 = std::hash<std::string>{}(p.name);size_t h2 = std::hash<int>{}(p.age);return h1 ^ (h2 << 1);}
};// 自定义相等比较器
struct PersonEqual {bool operator()(const Person& a, const Person& b) const {return a.name == b.name && a.age == b.age;}
};// 使用时必须将两个比较器作为模板参数传入
std::unordered_set<Person, PersonHash, PersonEqual> personSet;

2.7.3 更好的哈希组合方法（Boost风格）

// 一个通用的哈希组合函数
template <class T>
inline void hash_combine(std::size_t& seed, const T& v) {std::hash<T> hasher;seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}// 在自定义哈希器中使用
struct PersonHash {size_t operator()(const Person& p) const {std::size_t seed = 0;hash_combine(seed, p.name);hash_combine(seed, p.age);return seed;}
};

3、常见问题

1. std::unordered_set 的底层实现是什么？**
   底层是哈希表。它维护一个桶数组，通过哈希函数将键映射到桶的索引，并使用链地址法解决哈希冲突。

2. 什么是哈希冲突？unordered_set 是如何解决它的？**
   哈希冲突是指不同的键被哈希函数映射到了同一个桶中。std::unordered_set 采用链地址法解决冲突，即每个桶是一个链表，所有映射到同一桶的元素都放在这个链表中。

3. 什么是重哈希（Rehashing）？什么时候会发生？**
   重哈希是哈希表扩容的过程。当当前负载因子（size() / bucket_count()）超过最大负载因子（max_load_factor()）时，容器会自动执行重哈希：分配一个更大的新桶数组，并重新映射所有元素。重哈希会导致所有迭代器失效。

4. 如何让一个自定义类型可以作为 unordered_set 的键？**
   需要提供两个东西：
   1. 哈希函数：通过特化 std::hash 模板或提供自定义的哈希函数对象。
   2. 相等比较函数：通过重载 operator== 或提供自定义的相等比较函数对象。

• Q: unordered_set 的迭代器在插入操作后会失效吗？
  • A: 可能会。如果插入操作导致重哈希发生，那么所有迭代器都会失效。如果没有导致重哈希，则插入操作不会使迭代器失效。

5. 什么时候应该选择 unordered_set 而不是 set？**
   当你需要极快的查找速度（平均O(1)），并且不关心元素的顺序时，应该选择 unordered_set。当你需要元素有序，或者需要进行范围查询，或者担心最坏情况的性能时，应该选择 set。

6. 如何提高 unordered_set 的性能？**
   主要有几种方法：

   1. 在插入大量元素之前，使用 reserve(n) 预分配足够空间，避免多次重哈希。
   2. 提供一个高质量、低冲突的哈希函数。
   3. 适当调整 max_load_factor()（通常降低它可以减少冲突，但会增加内存使用）。

7. 什么是负载因子（Load Factor）？它对 std::unordered_set 性能有何影响？
   负载因子 = 元素数量 / 桶数量。它是衡量哈希表拥挤程度的指标：

   • 负载因子过小：桶数量过多，浪费内存。
   • 负载因子过大：哈希冲突率高，桶内链表/红黑树变长，操作效率退化。
     std::unordered_set 默认最大负载因子为 1.0，超过时会触发 rehash（扩容桶）。

8. std::unordered_set 的迭代器为什么是前向迭代器而不是双向迭代器？
   因为哈希表的桶内元素通过单链表（或红黑树）存储，单链表仅支持前向遍历（++），不支持反向遍历（--）。即使桶内用红黑树，整体哈希表的无序性也使得双向迭代意义不大，因此标准定为前向迭代器。

9. 如何避免 std::unordered_set 的 rehash 操作？
   提前通过 reserve(n) 预留足够的桶数量（确保 n 大于预期最大元素数），使元素数不会超过 max_load_factor() * bucket_count()，从而避免自动 rehash。例如：

   unordered_set<int> us;
   us.reserve(1000);  // 预计存储 1000 个元素，提前预留桶