C++ 学习杂记06：std::unordered_map

概述std::unordered_map是C标准模板库STL中的一个关联容器实现基于哈希表的键值对映射。自C11起成为标准库的一部分位于unordered_map头文件中。核心特性数据结构基于哈希表使用散列函数将键映射到存储桶bucket无序存储元素不以特定顺序存储遍历顺序不确定唯一键每个键在容器中只能出现一次平均常数时间复杂度插入、删除、查找操作平均O(1)最坏情况O(n)模板声明template class Key, class T, class Hash std::hashKey, class KeyEqual std::equal_toKey, class Allocator std::allocatorstd::pairconst Key, T class unordered_map;基本操作1. 构造与初始化// 默认构造 std::unordered_mapstd::string, int map1; // 初始化列表构造 std::unordered_mapstd::string, int map2 { {apple, 1}, {banana, 2}, {orange, 3} }; // 范围构造 std::vectorstd::pairstd::string, int vec {{a, 1}, {b, 2}}; std::unordered_mapstd::string, int map3(vec.begin(), vec.end()); // 拷贝构造 std::unordered_mapstd::string, int map4(map2);2. 元素访问// operator[] - 访问或插入键不存在时插入默认值 int value map[apple]; // 如果不存在会插入{apple, 0} map[apple] 10; // 修改或插入 // at() - 边界检查访问 try { int val map.at(apple); // 存在则返回 } catch (const std::out_of_range e) { // 键不存在时抛出异常 } // find() - 安全查找 auto it map.find(apple); if (it ! map.end()) { // 找到元素it-first是键it-second是值 }3. 修改操作// 插入元素 auto result map.insert({apple, 1}); // 返回pairiterator, bool map.emplace(banana, 2); // 原地构造更高效 // 插入或赋值 (C17) map.insert_or_assign(apple, 3); // 存在则赋值不存在则插入 // 删除元素 map.erase(apple); // 按键删除 auto it map.find(banana); if (it ! map.end()) { map.erase(it); // 按迭代器删除 } map.erase(map.begin(), map.end()); // 范围删除 // 清空 map.clear();4. 容量查询bool empty map.empty(); // 是否为空 size_t size map.size(); // 元素数量 size_t max map.max_size(); // 理论最大容量哈希表特定操作1. 桶接口// 桶数量相关 size_t bucket_count map.bucket_count(); // 桶总数 size_t bucket_idx map.bucket(apple); // 键所在的桶索引 // 桶信息 size_t bucket_size map.bucket_size(0); // 指定桶中的元素数 // 负载因子 float load_factor map.load_factor(); // 平均每个桶的元素数 float max_lf map.max_load_factor(); // 最大负载因子 map.max_load_factor(0.75f); // 设置最大负载因子2. 哈希策略// 调整桶数量 map.rehash(100); // 确保至少有100个桶 map.reserve(1000); // 确保能容纳1000个元素而不超过最大负载因子迭代器类型// 迭代器类型 std::unordered_mapstd::string, int::iterator it; std::unordered_mapstd::string, int::const_iterator cit; std::unordered_mapstd::string, int::local_iterator lit; // 桶内迭代器遍历方式// 1. 基于范围的for循环 (C11) for (const auto [key, value] : map) { // C17结构化绑定 // 使用key和value } // 2. 迭代器遍历 for (auto it map.begin(); it ! map.end(); it) { const auto key it-first; const auto value it-second; } // 3. 遍历所有桶 for (size_t i 0; i map.bucket_count(); i) { for (auto lit map.begin(i); lit ! map.end(i); lit) { // 遍历第i个桶 } }自定义类型作为键1. 定义哈希函数struct Person { std::string name; int age; bool operator(const Person other) const { return name other.name age other.age; } }; // 自定义哈希函数 struct PersonHash { size_t operator()(const Person p) const { return std::hashstd::string()(p.name) ^ (std::hashint()(p.age) 1); } }; // 使用自定义哈希 std::unordered_mapPerson, std::string, PersonHash person_map;2. 使用标准库组合哈希 (C14)#include functional struct PersonHash { size_t operator()(const Person p) const { return std::hashstd::string{}(p.name) ^ (std::hashint{}(p.age) 1); } };性能特性时间复杂度操作平均情况最坏情况插入O(1)O(n)删除O(1)O(n)查找O(1)O(n)遍历O(n)O(n)空间复杂度需要额外的空间存储桶数组和链表指针通常比std::map占用更多内存与std::map对比特性std::unordered_mapstd::map底层结构哈希表红黑树顺序无序按键排序操作复杂度平均O(1)O(log n)内存使用通常更高通常更低迭代器稳定性插入可能使所有迭代器失效除删除元素外迭代器稳定自定义键要求需要哈希函数需要比较函数最佳实践1. 预分配空间std::unordered_mapint, std::string map; map.reserve(1000); // 预分配避免多次rehash2. 选择合适的哈希函数对于整数类型标准哈希通常足够对于字符串考虑使用更好的分布避免哈希冲突过多3. 查找优化// 避免重复查找 auto it map.find(key); if (it ! map.end()) { // 使用it-second } else { // 键不存在 } // 而不是 if (map.count(key) 0) { // 额外查找 int value map[key]; // 再次查找 }4. 遍历时修改// 安全删除遍历中的元素 for (auto it map.begin(); it ! map.end(); ) { if (condition) { it map.erase(it); // erase返回下一个有效迭代器 } else { it; } }线程安全性多个线程可以同时读取容器如果有任何线程修改容器所有线程访问都需要同步使用std::shared_mutexC17或互斥锁保护并发访问特殊成员函数 (C17)1.extract()- 节点句柄// 提取节点而不重新分配内存 auto nh map.extract(apple); if (!nh.empty()) { nh.key() new_apple; // 修改键 map.insert(std::move(nh)); // 重新插入 }2.merge()- 合并容器std::unordered_mapstd::string, int map1, map2; // ... 填充数据 map1.merge(map2); // 尝试合并所有元素常见问题与解决方案1. 哈希冲突过多调整负载因子使用更好的哈希函数增加桶数量2. 自定义键的哈希质量差确保哈希函数分布均匀考虑使用现成的哈希组合库3. 迭代器失效插入操作可能使所有迭代器失效删除操作只使指向被删元素的迭代器失效总结std::unordered_map提供了高效的键值对存储适合需要快速查找而不关心顺序的场景。正确使用时其性能通常优于基于树的std::map。使用时需注意内存使用、哈希函数质量和线程安全性。