目录前言一、定义及初始化二、添加或删除元素1.添加元素2.删除元素三、常用迭代器四、常用运算符五、常用成员函数1.clear 成员函数2.count 成员函数3.emplace 成员函数4.empty 成员函数5.erase 成员函数6.find 成员函数7.equal_range 成员函数8.insert 成员函数9.size 成员函数10.swap 成员函数六、哈希表相关成员函数1.bucket_count 成员函数2.load_factor 成员函数3.max_load_factor 成员函数4.rehash 成员函数5.reserve 成员函数七、应用场景1. 键值对存储2. 统计词频3. 缓存实现4. 存储多个值对应同一个键八、总结前言本文全面介绍了C标准库中的两种无序关联容器。unordered_map存储唯一键值对而unordered_multimap允许键重复。文章详细讲解了容器的初始化方法、元素操作插入/删除、迭代器使用、运算符重载以及常用成员函数如find、count、equal_range等。特别强调了哈希表相关特性包括桶管理、负载因子控制等。通过词频统计、缓存实现等应用场景展示了容器的实际用途。unordered_map/unordered_multimap基于哈希表实现提供O(1)平均时间复杂度的查找操作但元素无序存储。选择时应根据是否需要元素有序或更高性能来决定使用有序还是无序容器。一、定义及初始化unordered_map 和 unordered_multimap 是 C 标准库中的无序关联容器它们存储键值对key-value pairs并使用哈希表实现因此元素不会按特定顺序排序。unordered_map 中的键是唯一的而 unordered_multimap 允许键重复。#include unordered_map // unordered_map 的定义和初始化 std::unordered_mapint, std::string um1; // 默认初始化空映射 std::unordered_mapint, std::string um2({{1, one}, {2, two}, {3, three}}); // 列表初始化 std::unordered_mapint, std::string um3(um2); // 拷贝初始化 std::unordered_mapint, std::string um4(um2.begin(), um2.end()); // 范围初始化 // 指定桶数和哈希函数 std::unordered_mapint, std::string um5(10); // 桶数为10 // unordered_multimap 的定义和初始化 std::unordered_multimapint, std::string umm1; // 默认初始化空映射 std::unordered_multimapint, std::string umm2({{1, one}, {2, two}, {2, second}, {3, three}}); // 列表初始化允许重复键 std::unordered_multimapint, std::string umm3(umm2); // 拷贝初始化 std::unordered_multimapint, std::string umm4(umm2.begin(), umm2.end()); // 范围初始化 // 指定桶数和哈希函数 std::unordered_multimapint, std::string umm5(10); // 桶数为10二、添加或删除元素1.添加元素使用insert成员函数或下标操作符向 unordered_map 中添加元素使用insert成员函数向 unordered_multimap 中添加元素。// 向 unordered_map 添加元素 std::unordered_mapint, std::string um; um.insert({1, one}); // 插入单个键值对 um.insert({{2, two}, {3, three}}); // 插入多个键值对 // 使用下标操作符仅 unordered_map 支持 um[4] four; // 如果键 4 不存在则插入如果存在则更新值 // 使用 emplace 方法构造并插入元素更高效 um.emplace(5, five); // 向 unordered_multimap 添加元素 std::unordered_multimapint, std::string umm; um.insert({1, one}); // 插入单个键值对 umm.insert({{2, two}, {2, second}, {3, three}}); // 插入多个键值对允许重复键 // 使用 emplace 方法构造并插入元素 umm.emplace(2, third);2.删除元素使用erase成员函数从 unordered_map 或 unordered_multimap 中删除元素。// 从 unordered_map 删除元素 std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}, {4, four}}); um.erase(2); // 删除键为 2 的元素 um.erase(um.begin()); // 删除第一个元素 um.erase(um.find(3), um.end()); // 删除从键为 3 开始到末尾的所有元素 // 从 unordered_multimap 删除元素 std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); um.erase(2); // 删除所有键为 2 的元素 umm.erase(umm.begin()); // 删除第一个元素 umm.erase(umm.find(3), umm.end()); // 删除从键为 3 开始到末尾的所有元素三、常用迭代器unordered_map 和 unordered_multimap 提供前向迭代器可以用来遍历容器中的键值对。注意由于是无序容器遍历顺序可能与插入顺序不同且在容器修改后可能会改变。// 遍历 unordered_map std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); for (auto it um.begin(); it ! um.end(); it) { std::cout Key: it-first , Value: it-second std::endl; // 输出顺序可能是任意的例如 // Key: 3, Value: three // Key: 1, Value: one // Key: 2, Value: two } // 遍历 unordered_multimap std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); for (auto it umm.begin(); it ! umm.end(); it) { std::cout Key: it-first , Value: it-second std::endl; // 输出顺序可能是任意的例如 // Key: 3, Value: three // Key: 1, Value: one // Key: 2, Value: two // Key: 2, Value: second } // 使用范围for循环遍历 std::cout Using range-based for loop: std::endl; for (auto pair : um) { std::cout pair.first : pair.second ; } std::cout std::endl;四、常用运算符unordered_map 和 unordered_multimap 支持以下运算符检查两个容器是否相等!检查两个容器是否不相等此外unordered_map 还支持下标运算符[]用于访问和修改元素。std::unordered_mapint, std::string um1({{1, one}, {2, two}, {3, three}}); std::unordered_mapint, std::string um2({{1, one}, {2, two}, {3, three}}); std::unordered_mapint, std::string um3({{1, one}, {2, two}, {4, four}}); bool eq (um1 um2); // true元素相同顺序无关 bool neq (um1 ! um3); // true // unordered_map 的下标运算符 std::unordered_mapint, std::string um; um[1] one; // 插入键值对 {1, one} um[2] two; // 插入键值对 {2, two} um[1] first; // 更新键 1 的值为 first std::cout um[1] std::endl; // 输出first std::unordered_multimapint, std::string umm1({{1, one}, {2, two}, {2, second}}); std::unordered_multimapint, std::string umm2({{2, two}, {1, one}, {2, second}}); std::unordered_multimapint, std::string umm3({{1, one}, {2, two}, {3, three}}); bool eq_m (umm1 umm2); // true元素相同包括重复次数顺序无关 bool neq_m (umm1 ! umm3); // true五、常用成员函数unordered_map/unordered_multimap 的成员函数含义m.clear()清空数据m.count(key)统计和关键字key相同的元素个数。m.empty()判断映射是否为空m.erase()删除元素或一个区间m.find(val)查找和val相同的第一个值m.equal_range(val)查找和val相同的关键字,返回一对迭代器,一个是相同值的起始位置,另一个是相同值的结束位置.m.insert()插入数据m.size()映射元素个数m.swap()两个映射交换数据1.clear 成员函数清除容器中的所有元素。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); um.clear(); bool is_empty um.empty(); // true std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); um.clear(); bool is_empty_m umm.empty(); // true2.count 成员函数返回容器中键为指定值的元素个数。对于 unordered_map返回 0 或 1对于 unordered_multimap返回实际个数。// unordered_map 中的 count std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); size_t count_2 um.count(2); // 1 size_t count_4 um.count(4); // 0 // unordered_multimap 中的 count std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); size_t count_2_mm umm.count(2); // 2 size_t count_4_mm umm.count(4); // 03.emplace 成员函数构造并插入元素比 insert 更高效因为它避免了额外的拷贝或移动操作。// unordered_map 的 emplace std::unordered_mapint, std::string um; um.emplace(1, one); um.emplace(2, two); // 对于自定义类型 struct Person { std::string name; int age; Person(std::string n, int a) : name(n), age(a) {} }; std::unordered_mapint, Person person_map; person_map.emplace(1, Person(Alice, 30)); // 直接在容器中构造对象 person_map.emplace(2, Bob, 25); // 更简洁的语法直接传递构造参数 // unordered_multimap 的 emplace std::unordered_multimapint, std::string umm; um.emplace(1, one); um.emplace(2, two); um.emplace(2, second); // 允许重复键4.empty 成员函数检查容器是否为空返回布尔值。std::unordered_mapint, std::string um; bool is_empty um.empty(); // true um.insert({1, one}); is_empty um.empty(); // false std::unordered_multimapint, std::string umm; bool is_empty_m umm.empty(); // true umm.insert({1, one}); is_empty_m umm.empty(); // false5.erase 成员函数删除容器中的元素有三种重载形式删除指定键的元素删除指定位置的元素删除指定范围的元素std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}, {4, four}}); // 删除指定键的元素 um.erase(2); // 现在 um 包含 {{1, one}, {3, three}, {4, four}} // 删除指定位置的元素 um.erase(um.begin()); // 现在 um 包含 {{3, three}, {4, four}} // 删除指定范围的元素 auto it um.find(3); if (it ! um.end()) { um.erase(it, um.end()); // 现在 um 为空 } // unordered_multimap 的 erase 操作类似 std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); um.erase(2); // 删除所有键为 2 的元素6.find 成员函数查找指定键的元素返回指向该元素的迭代器如果未找到返回 end() 迭代器。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); auto it um.find(2); if (it ! um.end()) { std::cout Found: Key it-first , Value it-second std::endl; // 输出Found: Key 2, Value two } it um.find(4); if (it um.end()) { std::cout Key 4 not found std::endl; // 输出Key 4 not found } // unordered_multimap 的 find 操作类似 std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); auto it_m umm.find(2); if (it_m ! umm.end()) { std::cout Found: Key it_m-first , Value it_m-second std::endl; // 输出Found: Key 2, Value two找到的是第一个匹配的元素 }7.equal_range 成员函数返回一个 pair其中第一个迭代器指向键等于指定值的第一个元素第二个迭代器指向键等于指定值的最后一个元素的下一个位置。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); auto range um.equal_range(2); if (range.first ! range.second) { std::cout Found: Key range.first-first , Value range.first-second std::endl; // 输出Found: Key 2, Value two } // 在 unordered_multimap 中 std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); auto range_mm umm.equal_range(2); std::cout Elements with key 2: std::endl; for (auto it range_mm.first; it ! range_mm.second; it) { std::cout Key: it-first , Value: it-second std::endl; // 输出 // Key: 2, Value: two // Key: 2, Value: second }8.insert 成员函数向容器中插入元素有多种重载形式插入单个键值对插入多个键值对插入范围std::unordered_mapint, std::string um; // 插入单个键值对 um.insert({1, one}); // 插入多个键值对 um.insert({{2, two}, {3, three}}); // 插入范围 std::unordered_mapint, std::string um2({{4, four}, {5, five}}); um.insert(um2.begin(), um2.end()); // unordered_multimap 的 insert 操作类似 std::unordered_multimapint, std::string umm; um.insert({{1, one}, {2, two}, {2, second}, {3, three}});9.size 成员函数返回容器中元素的数量。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); size_t size um.size(); // 3 std::unordered_multimapint, std::string umm({{1, one}, {2, two}, {2, second}, {3, three}}); size_t size_m umm.size(); // 410.swap 成员函数交换两个容器的内容。std::unordered_mapint, std::string um1({{1, one}, {2, two}}); std::unordered_mapint, std::string um2({{3, three}, {4, four}}); std::cout Before swap: std::endl; for (auto pair : um1) std::cout pair.first : pair.second ; std::cout std::endl; for (auto pair : um2) std::cout pair.first : pair.second ; std::cout std::endl; um1.swap(um2); std::cout After swap: std::endl; for (auto pair : um1) std::cout pair.first : pair.second ; std::cout std::endl; for (auto pair : um2) std::cout pair.first : pair.second ; std::cout std::endl; // unordered_multimap 的 swap 操作类似 std::unordered_multimapint, std::string umm1({{1, one}, {2, two}}); std::unordered_multimapint, std::string umm2({{2, second}, {3, three}}); um1.swap(umm2);六、哈希表相关成员函数unordered_map 和 unordered_multimap 还提供了一些与哈希表相关的成员函数1.bucket_count 成员函数返回容器中的桶数。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); size_t buckets um.bucket_count(); std::cout Number of buckets: buckets std::endl;2.load_factor 成员函数返回容器的负载因子元素数量除以桶数。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); double load um.load_factor(); std::cout Load factor: load std::endl;3.max_load_factor 成员函数获取或设置容器的最大负载因子。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); double max_load um.max_load_factor(); std::cout Max load factor: max_load std::endl; // 设置最大负载因子 um.max_load_factor(0.5); std::cout New max load factor: um.max_load_factor() std::endl;4.rehash 成员函数设置桶数为至少指定值并重新哈希所有元素。std::unordered_mapint, std::string um({{1, one}, {2, two}, {3, three}}); std::cout Before rehash - bucket count: um.bucket_count() std::endl; um.rehash(20); std::cout After rehash - bucket count: um.bucket_count() std::endl;5.reserve 成员函数设置容器的桶数以适应至少指定数量的元素而不重新哈希。std::unordered_mapint, std::string um; um.reserve(100); // 预留空间以存储至少100个元素 std::cout Bucket count after reserve: um.bucket_count() std::endl;七、应用场景1. 键值对存储unordered_map 最基本的应用是存储键值对方便通过键快速查找对应的值。// 存储学生ID和姓名 std::unordered_mapint, std::string student_map; student_map[1001] Alice; student_map[1002] Bob; student_map[1003] Charlie; // 通过ID查找姓名 int id 1002; auto it student_map.find(id); if (it ! student_map.end()) { std::cout Student id is it-second std::endl; // 输出Student 1002 is Bob }2. 统计词频使用 unordered_map 统计文本中单词出现的频率。#include sstream #include string std::string text hello world hello cpp world hello; std::unordered_mapstd::string, int word_count; std::istringstream iss(text); std::string word; while (iss word) { word_count[word]; // 如果单词不存在插入并设置计数为1如果存在计数加1 } // 输出词频 for (auto pair : word_count) { std::cout pair.first : pair.second std::endl; // 输出 // cpp: 1 // hello: 3 // world: 2 }3. 缓存实现使用 unordered_map 实现简单的缓存系统。// 简单的缓存实现 template typename Key, typename Value class Cache { private: std::unordered_mapKey, Value cache_map; size_t max_size; public: Cache(size_t size) : max_size(size) {} void put(const Key key, const Value value) { // 如果缓存已满删除最早插入的元素这里简化处理实际应使用LRU等策略 if (cache_map.size() max_size) { cache_map.erase(cache_map.begin()); } cache_map[key] value; } bool get(const Key key, Value value) { auto it cache_map.find(key); if (it ! cache_map.end()) { value it-second; return true; } return false; } }; // 使用示例 Cachestd::string, int cache(3); cache.put(a, 1); cache.put(b, 2); cache.put(c, 3); int value; if (cache.get(a, value)) { std::cout a: value std::endl; // 输出a: 1 } cache.put(d, 4); // 缓存已满删除最早的 a if (!cache.get(a, value)) { std::cout a not found std::endl; // 输出a not found } if (cache.get(d, value)) { std::cout d: value std::endl; // 输出d: 4 }4. 存储多个值对应同一个键使用 unordered_multimap 存储多个值对应同一个键的情况。// 存储学生姓名和对应的课程 std::unordered_multimapstd::string, std::string student_courses; student_courses.insert({Alice, Math}); student_courses.insert({Alice, Physics}); student_courses.insert({Bob, Math}); student_courses.insert({Bob, Chemistry}); student_courses.insert({Bob, Biology}); // 查找某个学生的所有课程 std::string student_name Bob; auto range student_courses.equal_range(student_name); std::cout student_name s courses: std::endl; for (auto it range.first; it ! range.second; it) { std::cout - it-second std::endl; // 输出 // - Math // - Chemistry // - Biology }八、总结unordered_map 和 unordered_multimap 是 C 标准库中基于哈希表实现的无序关联容器它们具有以下特点无序性元素存储在哈希表中没有特定的顺序键值对存储存储键值对通过键快速查找值唯一性unordered_map 中的键是唯一的unordered_multimap 中的键可以重复高效操作插入、删除、查找操作的平均时间复杂度为 O(1)前向迭代器支持前向遍历但遍历顺序可能与插入顺序不同哈希表相关操作提供了桶管理、负载因子控制等哈希表相关的成员函数在选择使用 unordered_map/unordered_multimap 还是 map/multimap 时主要考虑以下因素如果需要元素有序使用 map/multimap如果需要更快的查找、插入和删除操作使用 unordered_map/unordered_multimap如果内存使用是关键因素map/multimap 通常比 unordered_map/unordered_multimap 更节省内存