1. 无序关联容器概述
在C++标准库中,unordered_map和unordered_multimap是基于哈希表实现的无序关联容器,它们提供了高效的键值对存储和访问能力。与有序关联容器map和multimap不同,这些无序容器不保证元素的特定顺序,但提供了平均O(1)时间复杂度的查找、插入和删除操作。
unordered_map要求键是唯一的,而unordered_multimap允许键重复。这两种容器都使用哈希函数将键映射到哈希表中的特定位置(桶),这使得它们特别适合需要快速查找的场景。
提示:选择无序容器而非有序容器时,需要考虑是否真的不需要元素排序。虽然无序容器通常更快,但它们的内存使用可能更高,且迭代顺序不可预测。
2. 容器定义与初始化
2.1 基本定义
要使用unordered_map和unordered_multimap,首先需要包含头文件:
cpp复制#include <unordered_map>
定义unordered_map的基本语法是:
cpp复制std::unordered_map<KeyType, ValueType> map_name;
对于unordered_multimap:
cpp复制std::unordered_multimap<KeyType, ValueType> multimap_name;
2.2 初始化方式
无序关联容器支持多种初始化方式:
- 默认初始化:创建空容器
cpp复制std::unordered_map<int, std::string> um1;
- 列表初始化:使用花括号直接初始化
cpp复制std::unordered_map<int, std::string> um2 = {{1, "one"}, {2, "two"}, {3, "three"}};
- 拷贝初始化:从另一个同类型容器复制
cpp复制std::unordered_map<int, std::string> um3(um2);
- 范围初始化:使用迭代器范围初始化
cpp复制std::unordered_map<int, std::string> um4(um2.begin(), um2.end());
- 指定桶数:预先分配一定数量的桶
cpp复制std::unordered_map<int, std::::string> um5(10); // 初始桶数为10
对于unordered_multimap,初始化方式类似,但允许键重复:
cpp复制std::unordered_multimap<int, std::string> umm = {{1, "one"}, {2, "two"}, {2, "second"}};
2.3 自定义哈希函数和比较器
对于自定义类型作为键的情况,需要提供哈希函数和相等比较器:
cpp复制struct MyKey {
int id;
std::string name;
};
struct MyKeyHash {
size_t operator()(const MyKey& k) const {
return std::hash<int>()(k.id) ^ std::hash<std::string>()(k.name);
}
};
struct MyKeyEqual {
bool operator()(const MyKey& lhs, const MyKey& rhs) const {
return lhs.id == rhs.id && lhs.name == rhs.name;
}
};
std::unordered_map<MyKey, std::string, MyKeyHash, MyKeyEqual> custom_map;
3. 元素操作
3.1 添加元素
unordered_map支持多种添加元素的方式:
- insert方法:
cpp复制std::unordered_map<int, std::string> um;
um.insert({1, "one"});
um.insert(std::make_pair(2, "two"));
- 下标操作符(仅unordered_map):
cpp复制um[3] = "three"; // 插入或更新
- emplace方法(更高效,直接构造元素):
cpp复制um.emplace(4, "four");
unordered_multimap的添加方式类似,但不支持下标操作符:
cpp复制std::unordered_multimap<int, std::string> umm;
umm.insert({1, "one"});
umm.emplace(2, "two");
注意:emplace比insert更高效,因为它直接在容器内部构造元素,避免了临时对象的创建和拷贝。
3.2 删除元素
删除元素主要通过erase方法实现:
- 通过键删除:
cpp复制um.erase(1); // 删除键为1的元素
- 通过迭代器删除:
cpp复制auto it = um.find(2);
if (it != um.end()) {
um.erase(it);
}
- 删除范围:
cpp复制um.erase(um.begin(), um.end()); // 清空容器
对于unordered_multimap,erase(key)会删除所有匹配键的元素:
cpp复制umm.erase(2); // 删除所有键为2的元素
3.3 访问元素
访问元素的主要方式:
- find方法:
cpp复制auto it = um.find(3);
if (it != um.end()) {
std::cout << "Found: " << it->second << std::endl;
}
- 下标操作符(仅unordered_map):
cpp复制std::string value = um[3]; // 如果键不存在,会插入默认值
- at方法(安全访问,键不存在时抛出异常):
cpp复制try {
std::string value = um.at(3);
} catch (const std::out_of_range& e) {
std::cerr << "Key not found: " << e.what() << std::endl;
}
对于unordered_multimap,可以使用equal_range获取所有匹配键的元素:
cpp复制auto range = umm.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->second << std::endl;
}
4. 迭代器与遍历
4.1 基本迭代器
无序关联容器提供前向迭代器,可以用于遍历所有元素:
cpp复制for (auto it = um.begin(); it != um.end(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
或者使用范围for循环:
cpp复制for (const auto& pair : um) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
注意:由于是无序容器,遍历顺序与插入顺序无关,且可能在容器修改后发生变化。
4.2 常量迭代器
对于const容器或不需要修改元素的情况,应使用const_iterator:
cpp复制const std::unordered_map<int, std::string> cum = um;
for (auto it = cum.cbegin(); it != cum.cend(); ++it) {
// it->second = "new"; // 错误,不能修改const元素
}
4.3 局部迭代
可以获取特定桶的迭代器:
cpp复制size_t bucket = um.bucket(3); // 获取键3所在的桶
for (auto it = um.begin(bucket); it != um.end(bucket); ++it) {
std::cout << "Bucket " << bucket << ": " << it->second << std::endl;
}
5. 容器容量与状态查询
5.1 基本容量查询
- empty:检查容器是否为空
cpp复制bool is_empty = um.empty();
- size:获取元素数量
cpp复制size_t count = um.size();
- max_size:获取容器可容纳的最大元素数量
cpp复制size_t max = um.max_size();
5.2 哈希表特性查询
- bucket_count:获取当前桶的数量
cpp复制size_t buckets = um.bucket_count();
- max_bucket_count:获取容器支持的最大桶数
cpp复制size_t max_buckets = um.max_bucket_count();
- bucket:获取指定键所在的桶索引
cpp复制size_t bucket_index = um.bucket(3);
- bucket_size:获取指定桶中的元素数量
cpp复制size_t elems_in_bucket = um.bucket_size(0);
5.3 负载因子
- load_factor:当前负载因子(元素数/桶数)
cpp复制float lf = um.load_factor();
- max_load_factor:获取或设置最大负载因子
cpp复制float max_lf = um.max_load_factor();
um.max_load_factor(0.75f); // 设置新的最大负载因子
当负载因子超过max_load_factor时,容器会自动增加桶数并重新哈希。
6. 哈希表调整
6.1 rehash
rehash设置桶数为至少指定值,并重新哈希所有元素:
cpp复制um.rehash(20); // 确保至少有20个桶
6.2 reserve
reserve设置容器的桶数,以适应至少指定数量的元素:
cpp复制um.reserve(100); // 预留空间以存储至少100个元素
提示:reserve比rehash更高效,因为它只考虑元素数量,不强制立即重新哈希。
6.3 哈希策略选择
选择合适的哈希策略对性能至关重要:
-
好的哈希函数应该:
- 均匀分布键到各个桶
- 计算速度快
- 对相似的键产生不同的哈希值
-
负载因子通常保持在0.5-1.0之间:
- 太低浪费内存
- 太高增加冲突
-
桶数最好是质数,可以减少哈希冲突
7. 成员函数详解
7.1 clear
清空容器中的所有元素:
cpp复制um.clear(); // 清空后size()为0
7.2 count
统计与指定键匹配的元素数量:
cpp复制size_t c = um.count(3); // unordered_map返回0或1
size_t cm = umm.count(2); // unordered_multimap返回实际数量
7.3 emplace
直接构造并插入元素,避免拷贝:
cpp复制um.emplace(5, "five"); // 相当于insert({5, "five"})
对于复杂类型更高效:
cpp复制um.emplace(std::piecewise_construct,
std::forward_as_tuple(6),
std::forward_as_tuple("six", 3)); // 直接构造键和值
7.4 equal_range
获取与指定键匹配的元素范围(pair<iterator, iterator>):
cpp复制auto range = umm.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
// 处理所有键为2的元素
}
7.5 swap
交换两个容器的内容:
cpp复制std::unordered_map<int, std::string> um1, um2;
um1.swap(um2); // 交换内容
也可以使用std::swap:
cpp复制std::swap(um1, um2);
8. 应用场景与实例
8.1 键值对存储
unordered_map最基本的用途是存储键值对:
cpp复制std::unordered_map<std::string, std::string> config = {
{"host", "example.com"},
{"port", "8080"},
{"timeout", "30"}
};
std::string host = config["host"];
8.2 词频统计
统计文本中单词出现的频率:
cpp复制std::unordered_map<std::string, int> word_counts;
std::string text = "the quick brown fox jumps over the lazy dog";
std::istringstream iss(text);
std::string word;
while (iss >> word) {
++word_counts[word];
}
for (const auto& [word, count] : word_counts) {
std::cout << word << ": " << count << std::endl;
}
8.3 缓存实现
简单的LRU缓存实现:
cpp复制template <typename Key, typename Value>
class SimpleCache {
std::unordered_map<Key, Value> cache;
size_t capacity;
public:
SimpleCache(size_t cap) : capacity(cap) {}
bool get(const Key& key, Value& value) {
auto it = cache.find(key);
if (it == cache.end()) return false;
value = it->second;
return true;
}
void put(const Key& key, const Value& value) {
if (cache.size() >= capacity) {
cache.erase(cache.begin());
}
cache[key] = value;
}
};
8.4 多值映射
使用unordered_multimap存储一个键对应多个值:
cpp复制std::unordered_multimap<std::string, std::string> department_employees = {
{"IT", "Alice"},
{"IT", "Bob"},
{"HR", "Charlie"},
{"HR", "David"}
};
auto range = department_employees.equal_range("IT");
for (auto it = range.first; it != range.second; ++it) {
std::cout << "IT employee: " << it->second << std::endl;
}
9. 性能优化与注意事项
9.1 哈希函数选择
- 对于内置类型,标准库提供了默认哈希函数
- 对于自定义类型,需要实现良好的哈希函数
- 哈希函数应该快速计算且分布均匀
示例自定义哈希:
cpp复制struct Point {
int x, y;
};
struct PointHash {
size_t operator()(const Point& p) const {
size_t h1 = std::hash<int>()(p.x);
size_t h2 = std::hash<int>()(p.y);
return h1 ^ (h2 << 1);
}
};
std::unordered_map<Point, std::string, PointHash> point_map;
9.2 内存管理
- 无序容器通常比有序容器占用更多内存
- 可以通过reserve预分配空间减少重新哈希
- 调整max_load_factor可以平衡内存和性能
9.3 线程安全
标准无序容器不是线程安全的。多线程环境下需要外部同步:
cpp复制std::mutex mtx;
std::unordered_map<int, std::string> shared_map;
// 线程安全访问
{
std::lock_guard<std::mutex> lock(mtx);
shared_map[1] = "one";
}
9.4 常见陷阱
-
迭代器失效:
- 插入操作可能导致重新哈希,使所有迭代器失效
- 删除操作只使被删除元素的迭代器失效
-
默认构造值:
cpp复制std::unordered_map<int, int> m; int val = m[42]; // 插入{42, 0}并返回0 -
性能波动:
- 最坏情况下(大量冲突)操作复杂度退化为O(n)
- 需要监控负载因子和冲突情况
10. 与有序容器的比较
10.1 性能对比
| 操作 | unordered_map | map |
|---|---|---|
| 插入 | O(1)平均 | O(log n) |
| 查找 | O(1)平均 | O(log n) |
| 删除 | O(1)平均 | O(log n) |
| 遍历 | O(n) | O(n) |
| 内存使用 | 通常更高 | 通常更低 |
10.2 使用场景选择
选择unordered_map当:
- 需要快速查找
- 不需要元素有序
- 可以接受更高内存使用
选择map当:
- 需要元素有序
- 内存受限
- 需要稳定的遍历顺序
- 键的比较操作比哈希计算更快
10.3 混合使用策略
在某些场景下,可以结合使用两种容器:
cpp复制std::map<std::string, int> ordered_map; // 需要有序访问时使用
std::unordered_map<std::string, int> unordered_map; // 需要快速查找时使用
// 保持两个容器同步
auto insert_pair = [&](const std::string& key, int value) {
ordered_map.insert({key, value});
unordered_map.insert({key, value});
};
在实际项目中,我经常发现开发者过度使用unordered_map,仅仅因为听说它"更快"。但经过性能测试,当元素数量较少(通常少于100)时,map可能表现更好,因为哈希计算的开销超过了二叉树查找的开销。因此,选择容器类型时应该基于实际性能测试,而不仅仅是理论复杂度。
