110 std::unordered_multiset (哈希表)
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 概述
- 定义：
std::unordered_multiset是 C++ STL 中的关联容器，允许存储重复的元素，基于哈希表实现。 - 特点：
- 无序性：元素不按特定顺序存储（与
std::multiset的有序性对比）。 - 允许重复键：不同于
std::unordered_set，可以插入多个相同值的元素。 - 平均时间复杂度：插入、删除、查找操作的平均复杂度为 O(1)，最坏情况 O(n)（哈希冲突时）。
2. 头文件与声明
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <unordered_set>
2
using namespace std;
3
4
unordered_multiset<int> ums; // 声明一个存储int的无序多重集合
3. 模板参数
1.双击鼠标左键复制此行；2.单击复制所有代码。
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_multiset;
- Key：元素类型。
- Hash：哈希函数对象（默认
std::hash<Key>）。 - KeyEqual：键比较函数（默认
std::equal_to<Key>）。 - Allocator：内存分配器（通常无需修改）。
4. 核心操作
| 操作 | 语法 | 说明 |
|---|---|---|
| 插入元素 | ums.insert(value) | 插入一个元素（允许重复）。 |
| 删除元素 | ums.erase(value) | 删除所有匹配的 value。 |
| 查找元素 | ums.find(value) | 返回首个匹配的迭代器，无则返回 end()。 |
| 计数元素 | ums.count(value) | 返回 value 的出现次数。 |
| 判断空容器 | ums.empty() | 返回是否为空。 |
| 获取元素数量 | ums.size() | 返回元素总数（包括重复）。 |
| 清空容器 | ums.clear() | 移除所有元素。 |
5. 迭代器与遍历
- 迭代器类型：前向迭代器（
begin(),end(),cbegin(),cend()）。 - 遍历示例：
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
for (auto it = ums.begin(); it != ums.end(); ++it) {
2
cout << *it << " ";
3
}
4
// 或使用范围for循环
5
for (const auto& val : ums) {
6
cout << val << " ";
7
}
6. 桶管理（Bucket Interface）
- 哈希表特性：元素被分配到不同的桶中。
- 关键操作：
bucket_count()：返回桶的总数。bucket_size(n)：返回第n个桶的元素数量。bucket(key)：返回key所在的桶索引。
7. 哈希策略
- 负载因子（Load Factor）：
size() / bucket_count()。 load_factor()：返回当前负载因子。max_load_factor()：获取/设置最大负载因子（触发重哈希的阈值）。- 重哈希：
rehash(n)：将桶数量调整为至少n。reserve(n)：预留空间以避免重复重哈希。
8. 示例代码
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <unordered_set>
3
4
int main() {
5
std::unordered_multiset<int> ums = {1, 2, 3, 2, 4};
6
7
ums.insert(2); // 插入重复元素
8
ums.erase(3); // 删除所有值为3的元素
9
10
std::cout << "Count of 2: " << ums.count(2) << std::endl; // 输出3
11
12
for (int val : ums) {
13
std::cout << val << " "; // 输出顺序不确定，如：1 4 2 2 2
14
}
15
}
9. 与 std::multiset 对比
| 特性 | std::unordered_multiset | std::multiset |
|---|---|---|
| 底层结构 | 哈希表 | 红黑树（平衡二叉搜索树） |
| 顺序性 | 无序 | 有序（默认升序） |
| 时间复杂度 | 平均 O(1)，最坏 O(n) | 插入/查找/删除均为 O(log n) |
| 自定义排序 | 不支持（依赖哈希） | 支持（通过 Compare 模板参数） |
10. 注意事项
- 哈希冲突：性能可能因哈希函数质量下降。
- 迭代器失效：
- 插入操作可能导致重哈希，使所有迭代器失效。
- 删除操作仅使被删除元素的迭代器失效。
- 自定义类型：需提供自定义
Hash和KeyEqual函数对象。
11. 进阶用法
自定义哈希函数：
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
struct MyHash {
2
size_t operator()(const MyClass& obj) const {
3
return std::hash<int>()(obj.key);
4
}
5
};
6
std::unordered_multiset<MyClass, MyHash> customSet;
性能优化：通过 reserve() 预分配空间减少重哈希次数。
std::unordered_multiset
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| 构造函数 | 创建无序多重集合 | unordered_multiset<Key, Hash, KeyEqual, Allocator>::unordered_multiset(...) | std::unordered_multiset<int> nums = {1, 2, 2, 3}; | 支持默认构造、范围构造、拷贝构造等。 |
| insert | 插入元素（允许重复） | iterator insert(const value_type& value); | nums.insert(4); | 返回指向插入元素的迭代器。 |
| emplace | 直接构造元素（避免拷贝） | template <class... Args> iterator emplace(Args&&... args); | nums.emplace(5); | 效率可能高于 insert。 |
| erase | 删除元素 | iterator erase(iterator pos);size_type erase(const key_type& key); | nums.erase(2);nums.erase(nums.begin()); | 按值删除会移除所有匹配项，返回删除数量；按迭代器删除返回下一个迭代器。 |
| clear | 清空容器 | void clear() noexcept; | nums.clear(); | 容器大小变为 0。 |
| find | 查找元素 | iterator find(const key_type& key); | auto it = nums.find(3); | 返回首个匹配的迭代器，未找到时返回 end()。 |
| count | 统计元素出现次数 | size_type count(const key_type& key) const; | size_t n = nums.count(2); | 返回键值 key 的出现次数（可能 > 1）。 |
| equal_range | 返回匹配元素的范围 | std::pair<iterator, iterator> equal_range(const key_type& key); | auto [first, last] = nums.equal_range(2); | 返回包含所有匹配元素的迭代器范围。 |
| size | 返回元素数量 | size_type size() const noexcept; | size_t s = nums.size(); | 包括所有重复元素。 |
| empty | 检查容器是否为空 | bool empty() const noexcept; | if (nums.empty()) { ... } | 等价于 size() == 0。 |
| bucket_count | 返回桶的数量 | size_type bucket_count() const noexcept; | size_t bc = nums.bucket_count(); | 哈希表内部的桶数。 |
| load_factor | 返回当前负载因子（元素数/桶数） | float load_factor() const noexcept; | float lf = nums.load_factor(); | 负载因子过高时可能触发 rehash。 |
| rehash | 设置桶的数量 | void rehash(size_type n); | nums.rehash(20); | 调整桶数以适应至少 n 个元素。 |
| begin/end | 返回迭代器 | iterator begin() noexcept;iterator end() noexcept; | for (auto it = nums.begin(); it != nums.end(); ++it) | 支持常量迭代器 cbegin()/cend()。 |
示例代码（综合使用）
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <unordered_set>
3
4
int main() {
5
std::unordered_multiset<int> nums = {1, 2, 2, 3};
6
7
// 插入元素
8
nums.insert(4);
9
nums.emplace(5);
10
11
// 查找与统计
12
if (nums.find(3) != nums.end()) {
13
std::cout << "Found 3, count: " << nums.count(3) << std::endl;
14
}
15
16
// 删除元素
17
nums.erase(2); // 删除所有值为2的元素
18
19
// 遍历
20
for (int num : nums) {
21
std::cout << num << " ";
22
}
23
24
return 0;
25
}
注释说明
- 允许重复：与
unordered_set不同，unordered_multiset允许存储相同键值的元素。 - 哈希冲突：元素通过哈希函数分配到桶中，冲突时通过链表存储。
- 迭代器失效：插入或删除操作可能导致迭代器失效（除非是当前元素的
erase返回的迭代器）。
文章目录