109 std::unordered_set (无序集合)

作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58

1. 基本概念

1.1 定义与特性

定义：std::unordered_set 是 C++ STL 中的关联容器，存储唯一元素的无序集合
关键特性：
无序存储（不按特定顺序排列）
唯一元素（不允许重复）
基于哈希表实现
平均时间复杂度 O(1) 的查找、插入和删除操作
最坏情况下时间复杂度 O(n)

1.2 头文件

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            #include <unordered_set>

1.3 模板参数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            template<
                        
                                class Key,
                        
                                class Hash = std::hash<Key>,
                        
                                class KeyEqual = std::equal_to<Key>,
                        
                                class Allocator = std::allocator<Key>
                        
                            > class unordered_set;

Key：存储的元素类型
Hash：哈希函数对象类型（默认为 std::hash<Key>）
KeyEqual：键比较函数对象类型（默认为 std::equal_to<Key>）
Allocator：分配器类型（默认为 std::allocator<Key>）

2. 构造函数与初始化

2.1 常用构造方式

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 1. 默认构造函数
                        
                            std::unordered_set<int> set1;
                        
                            // 2. 范围构造函数
                        
                            std::vector<int> vec = {1, 2, 3, 4, 5};
                        
                            std::unordered_set<int> set2(vec.begin(), vec.end());
                        
                            // 3. 初始化列表构造函数
                        
                            std::unordered_set<int> set3 = {1, 2, 3, 4, 5};
                        
                            // 4. 复制构造函数
                        
                            std::unordered_set<int> set4(set3);
                        
                            // 5. 移动构造函数
                        
                            std::unordered_set<int> set5(std::move(set4));
                        
                            // 6. 指定桶数量的构造函数
                        
                            std::unordered_set<int> set6(10); // 初始桶数为10

2.2 自定义哈希和比较函数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            struct MyHash {
                        
                                size_t operator()(const std::string& s) const {
                        
                                    return s.length(); // 简单示例：按字符串长度哈希
                        
                                }
                        
                            };
                        
                            struct MyEqual {
                        
                                bool operator()(const std::string& lhs, const std::string& rhs) const {
                        
                                    return lhs.length() == rhs.length(); // 按长度比较
                        
                                }
                        
                            };
                        
                            std::unordered_set<std::string, MyHash, MyEqual> custom_set;

3. 常用操作

3.1 元素访问

查找元素：

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            auto it = set.find(key); // 返回迭代器，未找到则返回 end()
                        
                            if (set.find(key) != set.end()) { /* 存在 */ }
                        
                            // C++20 引入
                        
                            bool contains = set.contains(key); // 直接返回bool

3.2 修改操作

插入元素：

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            set.insert(value); // 插入单个值
                        
                            set.insert({value1, value2, value3}); // 插入多个值
                        
                            set.emplace(args...); // 原地构造元素
                        
                            auto [iter, success] = set.insert(value); // 返回pair<iterator, bool>

删除元素：

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            set.erase(key); // 删除键为key的元素，返回删除的数量(0或1)
                        
                            set.erase(iterator); // 删除指定位置的元素
                        
                            set.erase(first, last); // 删除范围[first, last)内的元素
                        
                            set.clear(); // 清空所有元素

3.3 容量查询

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            bool empty = set.empty(); // 是否为空
                        
                            size_t size = set.size(); // 元素数量
                        
                            size_t max_size = set.max_size(); // 最大可能容量

4. 哈希特性相关操作

4.1 桶接口

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            size_t bucket_count = set.bucket_count(); // 桶的数量
                        
                            size_t bucket = set.bucket(key); // 键key所在的桶索引
                        
                            size_t bucket_size = set.bucket_size(bucket_index); // 指定桶中的元素数量

4.2 哈希策略

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            float load_factor = set.load_factor(); // 当前负载因子(元素数/桶数)
                        
                            float max_lf = set.max_load_factor(); // 获取最大负载因子
                        
                            set.max_load_factor(new_max_lf); // 设置最大负载因子
                        
                            // 重新哈希
                        
                            set.rehash(new_bucket_count); // 设置至少能容纳new_bucket_count个桶
                        
                            set.reserve(new_size); // 设置至少能容纳new_size个元素而不需要rehash

5. 迭代器

5.1 迭代器类型

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 常规迭代器
                        
                            std::unordered_set<int>::iterator it;
                        
                            std::unordered_set<int>::const_iterator cit;
                        
                            // 局部迭代器（遍历单个桶）
                        
                            std::unordered_set<int>::local_iterator lit;
                        
                            std::unordered_set<int>::const_local_iterator clit;

5.2 迭代器使用

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 遍历所有元素
                        
                            for (auto it = set.begin(); it != set.end(); ++it) {
                        
                                // *it 访问元素
                        
                            }
                        
                            // C++11 范围for循环
                        
                            for (const auto& value : set) {
                        
                                // 访问value
                        
                            }
                        
                            // 遍历特定桶的元素
                        
                            size_t bucket_idx = /*...*/;
                        
                            for (auto lit = set.begin(bucket_idx); lit != set.end(bucket_idx); ++lit) {
                        
                                // *lit 访问该桶中的元素
                        
                            }

6. 性能与优化

6.1 时间复杂度

操作	平均情况	最坏情况
insert()	O(1)	O(n)
erase()	O(1)	O(n)
find()	O(1)	O(n)
count()	O(1)	O(n)
equal_range()	O(1)	O(n)

6.2 优化建议

选择合适的哈希函数：减少冲突
预分配空间：使用 reserve() 或 rehash() 避免多次重新哈希
调整负载因子：根据场景设置合适的 max_load_factor
自定义相等比较：对于复杂类型可优化比较操作

7. 与其他容器比较

特性	unordered_set	set	multiset
排序	无序	有序	有序
实现	哈希表	红黑树	红黑树
查找复杂度	O(1)平均	O(log n)	O(log n)
插入复杂度	O(1)平均	O(log n)	O(log n)
允许重复元素	否	否	是
内存使用	通常较高	通常较低	通常较低
迭代器稳定性	插入可能失效	总是稳定	总是稳定

8. 实际应用示例

8.1 去重

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 5};
                        
                            std::unordered_set<int> unique_numbers(numbers.begin(), numbers.end());
                        
                            // unique_numbers 包含 {1, 2, 3, 4, 5}（顺序可能不同）

8.2 快速查找

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            std::unordered_set<std::string> dictionary = {"apple", "banana", "cherry"};
                        
                            if (dictionary.find("apple") != dictionary.end()) {
                        
                                std::cout << "Found apple!" << std::endl;
                        
                            }

8.3 自定义类型使用

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            struct Point {
                        
                                int x, y;
                        
                                bool operator==(const Point& other) const {
                        
                                    return x == other.x && y == other.y;
                        
                                }
                        
                            };
                        
                            namespace std {
                        
                                template<> struct hash<Point> {
                        
                                    size_t operator()(const Point& p) const {
                        
                                        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
                        
                                    }
                        
                                };
                        
                            }
                        
                            std::unordered_set<Point> points = {{1, 2}, {3, 4}, {5, 6}};

9. 注意事项

迭代器失效：
- 插入操作可能导致所有迭代器失效（如果触发rehash）
- 删除操作仅使被删除元素的迭代器失效
自定义类型要求：
- 必须定义 operator==
- 最好提供特化的 std::hash 或自定义哈希函数
性能考虑：
- 哈希冲突会影响性能
- 频繁的rehash操作会降低性能
线程安全：
- 不同元素可以安全地从多个线程访问
- 同一元素的并发访问需要同步
C++17 结构化绑定：

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            auto [iter, inserted] = set.insert(value);
                        
                            if (inserted) {
                        
                               // 插入成功
                        
                            }

std::unordered_set 常用 API 的整理表格

名称	用途	原型	代码示例	注释
构造函数	创建无序集合	`unordered_set()` `unordered_set(initializer_list)`	`std::unordered_set<int> s1;` `std::unordered_set<int> s2 = {1, 2, 3};`	默认构造或通过初始化列表构造
insert	插入元素	`pair<iterator, bool> insert(const T& value)`	`s1.insert(10);` `auto [it, success] = s1.insert(20);`	返回插入结果的迭代器和是否成功的布尔值
emplace	原地构造元素	`pair<iterator, bool> emplace(Args&&... args)`	`s1.emplace(30);`	避免拷贝，直接构造元素
erase	删除元素	`size_type erase(const T& value)` `iterator erase(iterator pos)`	`s1.erase(10);` `s1.erase(s1.begin());`	按值或迭代器删除，返回删除的元素数量或下一个迭代器
find	查找元素	`iterator find(const T& value)`	`auto it = s1.find(20);` `if (it != s1.end()) { /* 找到 */ }`	返回指向元素的迭代器，未找到时返回 `end()`
count	统计元素出现次数	`size_type count(const T& value)`	`if (s1.count(20) > 0) { /* 存在 */ }`	由于集合唯一性，返回 0 或 1
size	返回元素数量	`size_type size() const`	`std::cout << "Size: " << s1.size();`	当前集合中的元素个数
empty	检查是否为空	`bool empty() const`	`if (s1.empty()) { /* 集合为空 */ }`	等价于 `size() == 0`
clear	清空集合	`void clear()`	`s1.clear();`	移除所有元素
bucket_count	返回桶的数量	`size_type bucket_count() const`	`std::cout << "Buckets: " << s1.bucket_count();`	哈希表中桶的总数
load_factor	返回当前负载因子	`float load_factor() const`	`std::cout << "Load factor: " << s1.load_factor();`	元素数量 / 桶数量，反映哈希表密度
reserve	预分配存储空间	`void reserve(size_type count)`	`s1.reserve(100);`	提前分配至少能容纳 `count` 个元素的空间，避免重复扩容
迭代器	遍历集合	`begin()`, `end()`, `cbegin()`, `cend()`	`for (auto it = s1.begin(); it != s1.end(); ++it)` `for (int x : s1)`	支持正向迭代和范围循环

补充说明

哈希特性：std::unordered_set 基于哈希表实现，元素无序存储，平均 O(1) 时间复杂度。
自定义哈希/比较：可通过模板参数自定义哈希函数和键比较方式（需满足 Hash 和 KeyEqual 要求）。
线程安全：多线程环境下需外部同步（如互斥锁）。

文章目录

1	template<
2	class Key,
3	class Hash = std::hash<Key>,
4	class KeyEqual = std::equal_to<Key>,
5	class Allocator = std::allocator<Key>
6	> class unordered_set;

1	// 1. 默认构造函数
2	std::unordered_set<int> set1;
3
4	// 2. 范围构造函数
5	std::vector<int> vec = {1, 2, 3, 4, 5};
6	std::unordered_set<int> set2(vec.begin(), vec.end());
7
8	// 3. 初始化列表构造函数
9	std::unordered_set<int> set3 = {1, 2, 3, 4, 5};
10
11	// 4. 复制构造函数
12	std::unordered_set<int> set4(set3);
13
14	// 5. 移动构造函数
15	std::unordered_set<int> set5(std::move(set4));
16
17	// 6. 指定桶数量的构造函数
18	std::unordered_set<int> set6(10); // 初始桶数为10

1	struct MyHash {
2	size_t operator()(const std::string& s) const {
3	return s.length(); // 简单示例：按字符串长度哈希
4	}
5	};
6
7	struct MyEqual {
8	bool operator()(const std::string& lhs, const std::string& rhs) const {
9	return lhs.length() == rhs.length(); // 按长度比较
10	}
11	};
12
13	std::unordered_set<std::string, MyHash, MyEqual> custom_set;

1	auto it = set.find(key); // 返回迭代器，未找到则返回 end()
2	if (set.find(key) != set.end()) { /* 存在 */ }
3
4	// C++20 引入
5	bool contains = set.contains(key); // 直接返回bool

1	set.insert(value); // 插入单个值
2	set.insert({value1, value2, value3}); // 插入多个值
3	set.emplace(args...); // 原地构造元素
4
5	auto [iter, success] = set.insert(value); // 返回pair<iterator, bool>

1	set.erase(key); // 删除键为key的元素，返回删除的数量(0或1)
2	set.erase(iterator); // 删除指定位置的元素
3	set.erase(first, last); // 删除范围[first, last)内的元素
4	set.clear(); // 清空所有元素

1	bool empty = set.empty(); // 是否为空
2	size_t size = set.size(); // 元素数量
3	size_t max_size = set.max_size(); // 最大可能容量

1	size_t bucket_count = set.bucket_count(); // 桶的数量
2	size_t bucket = set.bucket(key); // 键key所在的桶索引
3	size_t bucket_size = set.bucket_size(bucket_index); // 指定桶中的元素数量

1	float load_factor = set.load_factor(); // 当前负载因子(元素数/桶数)
2	float max_lf = set.max_load_factor(); // 获取最大负载因子
3	set.max_load_factor(new_max_lf); // 设置最大负载因子
4
5	// 重新哈希
6	set.rehash(new_bucket_count); // 设置至少能容纳new_bucket_count个桶
7	set.reserve(new_size); // 设置至少能容纳new_size个元素而不需要rehash

1	// 常规迭代器
2	std::unordered_set<int>::iterator it;
3	std::unordered_set<int>::const_iterator cit;
4
5	// 局部迭代器（遍历单个桶）
6	std::unordered_set<int>::local_iterator lit;
7	std::unordered_set<int>::const_local_iterator clit;

1	// 遍历所有元素
2	for (auto it = set.begin(); it != set.end(); ++it) {
3	// *it 访问元素
4	}
5
6	// C++11 范围for循环
7	for (const auto& value : set) {
8	// 访问value
9	}
10
11	// 遍历特定桶的元素
12	size_t bucket_idx = /.../;
13	for (auto lit = set.begin(bucket_idx); lit != set.end(bucket_idx); ++lit) {
14	// *lit 访问该桶中的元素
15	}

1	std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 5};
2	std::unordered_set<int> unique_numbers(numbers.begin(), numbers.end());
3	// unique_numbers 包含 {1, 2, 3, 4, 5}（顺序可能不同）

1	std::unordered_set<std::string> dictionary = {"apple", "banana", "cherry"};
2
3	if (dictionary.find("apple") != dictionary.end()) {
4	std::cout << "Found apple!" << std::endl;
5	}

1	struct Point {
2	int x, y;
3	bool operator==(const Point& other) const {
4	return x == other.x && y == other.y;
5	}
6	};
7
8	namespace std {
9	template<> struct hash<Point> {
10	size_t operator()(const Point& p) const {
11	return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
12	}
13	};
14	}
15
16	std::unordered_set<Point> points = {{1, 2}, {3, 4}, {5, 6}};

1	auto [iter, inserted] = set.insert(value);
2	if (inserted) {
3	// 插入成功
4	}