112 std::unordered_multimap (哈希表实现的关联容器)
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 基本概念
std::unordered_multimap 是 C++ STL 中的一个关联容器，具有以下特性：
- 无序：元素不以任何特定顺序存储
- 关联：通过键值对存储元素
- 允许多个相同键：与
unordered_map不同，允许多个元素拥有相同的键 - 哈希表实现：底层通常使用哈希表实现
2. 头文件和声明
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <unordered_map>
2
3
// 基本声明
4
std::unordered_multimap<Key, T> myMap;
5
6
// 带分配器和哈希函数的声明
7
std::unordered_multimap<Key, T, Hash, KeyEqual, Allocator> myMap;
3. 模板参数
| 参数 | 描述 | 默认值 |
|---|---|---|
Key | 键的类型 | - |
T | 映射值的类型 | - |
Hash | 哈希函数对象类型 | std::hash<Key> |
KeyEqual | 键比较函数对象类型 | std::equal_to<Key> |
Allocator | 分配器类型 | std::allocator<std::pair<const Key, T>> |
4. 成员类型
| 类型 | 描述 |
|---|---|
key_type | Key |
mapped_type | T |
value_type | std::pair<const Key, T> |
size_type | 无符号整数类型 |
difference_type | 有符号整数类型 |
hasher | Hash |
key_equal | KeyEqual |
allocator_type | Allocator |
reference | value_type& |
const_reference | const value_type& |
pointer | std::allocator_traits<Allocator>::pointer |
const_pointer | std::allocator_traits<Allocator>::const_pointer |
iterator | 前向迭代器 |
const_iterator | 常前向迭代器 |
local_iterator | 桶迭代器 |
const_local_iterator | 常桶迭代器 |
5. 构造函数
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
// 1. 默认构造函数
2
unordered_multimap();
3
4
// 2. 带分配器的构造函数
5
explicit unordered_multimap(const Allocator& alloc);
6
7
// 3. 范围构造函数
8
template<class InputIt>
9
unordered_multimap(InputIt first, InputIt last,
10
size_type bucket_count = /*实现定义*/,
11
const Hash& hash = Hash(),
12
const KeyEqual& equal = KeyEqual(),
13
const Allocator& alloc = Allocator());
14
15
// 4. 拷贝构造函数
16
unordered_multimap(const unordered_multimap& other);
17
unordered_multimap(const unordered_multimap& other, const Allocator& alloc);
18
19
// 5. 移动构造函数
20
unordered_multimap(unordered_multimap&& other);
21
unordered_multimap(unordered_multimap&& other, const Allocator& alloc);
22
23
// 6. 初始化列表构造函数
24
unordered_multimap(std::initializer_list<value_type> init,
25
size_type bucket_count = /*实现定义*/,
26
const Hash& hash = Hash(),
27
const KeyEqual& equal = KeyEqual(),
28
const Allocator& alloc = Allocator());
6. 容量操作
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
empty() | 检查容器是否为空 | O(1) |
size() | 返回元素数量 | O(1) |
max_size() | 返回可容纳的最大元素数 | O(1) |
7. 修改操作
插入元素
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
// 1. 插入单个元素
2
iterator insert(const value_type& value);
3
4
// 2. 使用提示插入
5
iterator insert(const_iterator hint, const value_type& value);
6
7
// 3. 范围插入
8
template<class InputIt>
9
void insert(InputIt first, InputIt last);
10
11
// 4. 初始化列表插入
12
void insert(std::initializer_list<value_type> ilist);
13
14
// 5. 原位构造插入
15
template<class... Args>
16
iterator emplace(Args&&... args);
17
18
// 6. 使用提示原位构造插入
19
template<class... Args>
20
iterator emplace_hint(const_iterator hint, Args&&... args);
删除元素
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
// 1. 通过迭代器删除
2
iterator erase(const_iterator pos);
3
4
// 2. 通过键范围删除
5
size_type erase(const key_type& key);
6
7
// 3. 通过迭代器范围删除
8
iterator erase(const_iterator first, const_iterator last);
9
10
// 4. 清空容器
11
void clear() noexcept;
8. 查找操作
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
count(const Key& key) | 返回匹配键的元素数量 | 平均O(count(key))，最坏O(size()) |
find(const Key& key) | 查找键的第一个匹配元素 | 平均O(1)，最坏O(size()) |
equal_range(const Key& key) | 返回匹配键的元素范围 | 平均O(count(key))，最坏O(size()) |
contains(const Key& key) (C++20) | 检查是否存在匹配键的元素 | 平均O(1)，最坏O(size()) |
9. 桶接口
| 方法 | 描述 |
|---|---|
bucket_count() | 返回桶的数量 |
max_bucket_count() | 返回桶的最大可能数量 |
bucket_size(size_type n) | 返回第n个桶中的元素数量 |
bucket(const Key& key) | 返回键key所在的桶编号 |
begin(size_type n) | 返回第n个桶的起始迭代器 |
end(size_type n) | 返回第n个桶的结束迭代器 |
cbegin(size_type n) | 返回第n个桶的起始常迭代器 |
cend(size_type n) | 返回第n个桶的结束常迭代器 |
10. 哈希策略
| 方法 | 描述 |
|---|---|
load_factor() | 返回负载因子(元素数/桶数) |
max_load_factor() | 返回最大负载因子 |
max_load_factor(float ml) | 设置最大负载因子 |
rehash(size_type count) | 设置桶数为至少count并重新哈希 |
reserve(size_type count) | 预留空间至少容纳count个元素 |
11. 观察器
| 方法 | 描述 |
|---|---|
hash_function() | 返回哈希函数 |
key_eq() | 返回键比较函数 |
get_allocator() | 返回分配器 |
12. 非成员函数
| 函数 | 描述 |
|---|---|
operator==, operator!= | 比较两个unordered_multimap的内容 |
std::swap() | 特化的swap算法 |
13. 示例代码
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <string>
3
#include <unordered_map>
4
5
int main() {
6
// 创建unordered_multimap
7
std::unordered_multimap<std::string, int> wordMap;
8
9
// 插入元素
10
wordMap.insert({"apple", 1});
11
wordMap.insert({"banana", 2});
12
wordMap.insert({"apple", 3}); // 允许重复键
13
14
// 查找元素
15
auto range = wordMap.equal_range("apple");
16
for (auto it = range.first; it != range.second; ++it) {
17
std::cout << it->first << ": " << it->second << std::endl;
18
}
19
20
// 遍历所有元素
21
for (const auto& pair : wordMap) {
22
std::cout << pair.first << " => " << pair.second << std::endl;
23
}
24
25
// 桶接口使用
26
std::cout << "bucket_count: " << wordMap.bucket_count() << std::endl;
27
std::cout << "load_factor: " << wordMap.load_factor() << std::endl;
28
29
return 0;
30
}
14. 性能特点
- 平均时间复杂度：
- 插入、删除、查找：O(1)
- 最坏时间复杂度：
- 插入、删除、查找：O(n) (当哈希冲突严重时)
- 空间复杂度：O(n)
15. 使用场景
- 需要快速查找但不需要排序
- 允许多个相同键值对存在
- 不需要按特定顺序遍历元素
- 对内存使用不敏感但对查找性能要求高
16. 注意事项
迭代器失效：
- 插入操作可能使所有迭代器失效（如果导致重哈希）
- 删除操作只使被删除元素的迭代器失效
自定义哈希函数：
- 需要保证相同的键总是产生相同的哈希值
- 理想情况下，不同的键应尽量产生不同的哈希值
自定义键比较函数：
- 必须实现严格的弱序关系
- 必须与哈希函数兼容：如果两个键相等，它们的哈希值必须相等
性能调优：
- 可以通过
reserve()预分配空间减少重哈希 - 调整
max_load_factor可以平衡内存使用和性能
- 可以通过
std::unordered_multimap 的常用 API 整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| 构造函数 | 创建无序多重映射容器 | unordered_multimap()unordered_multimap(size_type bucket_count) | std::unordered_multimap<int, std::string> umm;std::unordered_multimap<int, int> umm(10); | 默认构造函数或指定初始桶数量。 |
| insert | 插入键值对 | iterator insert(const value_type& val) | umm.insert({1, "one"});umm.insert(std::make_pair(2, "two")); | 插入单个键值对，允许重复键。返回插入位置的迭代器。 |
| emplace | 原地构造键值对 | template <class... Args> iterator emplace(Args&&... args) | umm.emplace(3, "three"); | 直接构造元素，避免临时对象拷贝。 |
| erase | 删除元素 | iterator erase(iterator pos)size_type erase(const key_type& key) | umm.erase(1);auto it = umm.find(2);if (it != umm.end()) umm.erase(it); | 删除指定键或迭代器位置的元素。返回删除后的下一个迭代器或删除的元素数量。 |
| find | 查找键 | iterator find(const key_type& key) | auto it = umm.find(3);if (it != umm.end()) { /* 存在 */ } | 返回第一个匹配键的迭代器，未找到时返回 end()。 |
| count | 统计键出现的次数 | size_type count(const key_type& key) const | size_t cnt = umm.count(2); | 返回键在容器中的出现次数（可能 > 1）。 |
| equal_range | 获取键的所有元素范围 | std::pair<iterator, iterator> equal_range(const key_type& key) | auto range = umm.equal_range(2);for (auto it = range.first; it != range.second; ++it) | 返回匹配键的迭代器范围（[first, last)），用于遍历重复键的所有值。 |
| size | 返回元素数量 | size_type size() const | size_t num = umm.size(); | 容器中键值对的总数（包括重复键）。 |
| empty | 检查容器是否为空 | bool empty() const | if (umm.empty()) { /* 空 */ } | 等价于 size() == 0。 |
| clear | 清空容器 | void clear() | umm.clear(); | 移除所有元素，保留桶结构。 |
| bucket_count | 返回桶的数量 | size_type bucket_count() const | size_t buckets = umm.bucket_count(); | 哈希表中桶的总数（非元素数量）。 |
| begin/end | 获取迭代器 | iterator begin()iterator end() | for (auto it = umm.begin(); it != umm.end(); ++it) | 遍历所有元素（顺序不确定）。 |
示例代码（完整）
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <unordered_map>
3
#include <string>
4
5
int main() {
6
std::unordered_multimap<int, std::string> umm;
7
8
// 插入元素（允许重复键）
9
umm.insert({1, "apple"});
10
umm.emplace(2, "banana");
11
umm.emplace(2, "blueberry"); // 重复键
12
13
// 查找并遍历
14
auto range = umm.equal_range(2);
15
for (auto it = range.first; it != range.second; ++it) {
16
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
17
}
18
19
// 删除元素
20
umm.erase(1); // 删除键为1的所有元素
21
22
// 输出统计
23
std::cout << "Size: " << umm.size() << ", Buckets: " << umm.bucket_count() << std::endl;
24
return 0;
25
}
关键特性说明
- 允许重复键：与
unordered_map不同，unordered_multimap允许多个元素拥有相同键。 - 无序存储：元素按哈希值分布，无固定顺序。
- 哈希策略：可通过
bucket_count()和load_factor()调整性能。