简介底层实现基于哈希表实现。元素的存储顺序是无序的取决于哈希函数和哈希表的结构。插入、删除和查找操作的平均时间复杂度为O(1)但在最坏情况下如大量哈希冲突可能退化到O(n)。查找性能平均查找效率为O(1)适合频繁查找的场景尤其是当数据量较大时性能优势更明显。插入和删除性能平均情况下插入和删除操作的时间复杂度为O(1)但在大量哈希冲突时可能退化。键的有序性键是无序的元素的存储和遍历顺序取决于哈希函数和哈希表的结构。如果需要按键值顺序遍历需要额外排序。内粗使用内存使用可能比std::map稍高因为哈希表需要额外的空间来处理哈希冲突如开放寻址法或链表法。但可以通过调整负载因子load factor来优化内存使用。使用场景适用于需要频繁查找、插入和删除的场景尤其是当数据量较大时。哈希冲突和负载因子哈希表的性能高度依赖于哈希函数的质量和负载因子。负载因子load factor定义为元素数量 / 哈希表大小。当负载因子过高时哈希冲突会增加性能会下降。可以通过rehash方法调整哈希表的大小或者通过max_load_factor方法设置最大负载因子。与map容器的比较特性std::mapstd::unordered_map底层实现红黑树哈希表查找效率O(log n)平均O(1)最坏O(n)插入/删除效率O(log n)平均O(1)最坏O(n)键的有序性有序无序内存使用相对紧凑可能稍高使用场景需要按键值有序存储需要频繁查找、插入和删除如果需要按键值有序存储或频繁进行范围查找使用std::map。如果需要高效的查找、插入和删除操作且对键值的顺序没有要求使用std::unordered_map。成员函数map和unordered_map虽然都是关联容器用于存储键值对但它们的内置函数并不完全相同。尽管它们有许多相似的成员函数但由于底层实现和设计目标的不同它们在某些函数上存在差异。1. 共有的成员函数map和unordered_map都继承自associative_container或unordered_associative_container因此它们有许多共有的成员函数例如begin()和end()返回迭代器分别指向容器的开始和结束位置。size()和empty()分别返回容器中元素的数量和判断容器是否为空。clear()清空容器中的所有元素。find()查找指定键的元素返回一个迭代器。count()统计指定键的元素数量map中每个键只能有一个元素unordered_map也是如此。insert()插入元素。erase()删除元素。operator[]和at()访问指定键的值。上述函数的使用方法请参阅C map容器总结2.unordered_map独有的成员函数load_factor()和max_load_factor()load_factor()返回当前的负载因子元素数量除以哈希表的大小。max_load_factor()获取或设置最大负载因子。当负载因子超过最大值时容器会自动重新哈希rehash。unordered_mapint, string myMap {{1, Apple}, {2, Banana}, {3, Cherry}}; cout Current load factor: myMap.load_factor() endl; myMap.max_load_factor(0.75); // 设置最大负载因子rehash()手动重新哈希调整哈希表的大小以适应当前的负载因子。示例myMap.rehash(10); // 将哈希表大小调整为至少10bucket_count()和bucket_size()bucket_count()返回哈希表的桶bucket数量。bucket_size(bucket_index)返回指定桶中的元素数量。示例cout Number of buckets: myMap.bucket_count() endl; cout Size of bucket 0: myMap.bucket_size(0) endl;bucket(key)返回指定键所在的桶的索引。示例cout Bucket index for key 2: myMap.bucket(2) endl;插入和删除函数的差异虽然std::map和std::unordered_map都有insert()、erase()和emplace()等函数但它们的行为和效率有所不同insert()std::map插入操作的时间复杂度为O(log n)因为它需要在红黑树中查找插入位置。std::unordered_map平均时间复杂度为O(1)但在最坏情况下大量哈希冲突可能退化到O(n)。erase()std::map删除操作的时间复杂度为O(log n)因为它需要在红黑树中查找并调整树结构。std::unordered_map平均时间复杂度为O(1)但在最坏情况下可能退化到O(n)。emplace()std::map直接在红黑树中构造元素避免拷贝或移动时间复杂度为O(log n)。std::unordered_map直接在哈希表中构造元素平均时间复杂度为O(1)但在最坏情况下可能退化到O(n)。迭代器行为的差异std::map迭代器是双向迭代器支持双向遍历和--。遍历顺序是按键值的升序或自定义的比较顺序。std::unordered_map迭代器是前向迭代器仅支持单向遍历。遍历顺序是无序的取决于哈希表的结构。std::unordered_map 是 C11 引入的基于哈希表的关联容器存储键值对平均情况下插入、查找、删除均为 O(1)。它**不保证元素顺序**适合需要快速查找而不关心顺序的场景。常用函数速查与使用方法构造与初始化#include unordered_map #include string std::unordered_mapstd::string, int m1; // 空构造 std::unordered_mapstd::string, int m2{{a,1},{b,2}}; // 初始化列表 std::unordered_mapstd::string, int m3(m2); // 拷贝构造插入元素auto ret m.insert({a, 1}); if (!ret.second) { // 键已存在ret.first 指向已有元素 }访问元素int v1 m[key]; // 键不存在时自动插入默认值慎用于只读场景 int v2 m.at(key); // 键不存在时抛 std::out_of_range注意operator[]在键不存在时会创建新元素如果只想查询是否存在应使用 find 或 count。查找元素// find返回迭代器未找到返回 end() auto it m.find(key); if (it ! m.end()) { std::cout it-first - it-second; } // count返回 0 或 1unordered_map 键唯一 if (m.count(key)) { /* 存在 */ } // C20: contains if (m.contains(key)) { /* 存在 */ }at() 和 find() 都用于只读查询不会插入新元素但它们在键不存在时的行为和返回类型不同。核心区别对比代码示例std::unordered_mapstd::string, int m{{a, 1}}; // at键不存在直接抛异常 try { int v m.at(a); // OK, v 1 int x m.at(missing); // 抛出 std::out_of_range } catch (const std::out_of_range e) { std::cout not found: e.what() \n; } // find键不存在返回 end()可安全判断 auto it m.find(missing); if (it ! m.end()) { std::cout it-second; // 存在时才访问 } else { std::cout not found\n; // 走这里 }使用场景选择用at()的场景你确定键一定存在例如前面已用 find/count 检查过或逻辑上保证存在想直接拿到值的引用代码更简洁// 已知 a 一定在 map 中 int val m.at(a); val 1; // 可直接修改因为返回引用用find()的场景键可能不存在需要根据存在与否走不同分支或需要同时访问 key 和 valueauto it m.find(key); if (it ! m.end()) { // 存在使用 it-first, it-second } else { // 不存在插入或做其他处理 m[key] defaultValue; }关键注意点1.at() 返回的是引用可以修改值m.at(a) 100; 是合法的前提是键存在。find() 返回迭代器通过 it-second 修改。2.at() 用于只读查询是安全的不会像 operator[] 那样在键不存在时偷偷插入元素——它只是抛异常。这是 at() 相对 operator[] 的核心优势。3.find() 不会抛异常是查询存在性的首选at() 更适合我知道它存在直接给我值的表达。4. 三者对比记忆-operator[]不存在 → 插入默认值有副作用-at()不存在 → 抛异常-find()不存在 → 返回 end()无副作用、无异常删除元素m.erase(key); // 按 key 删除返回删除个数 m.erase(it); // 按迭代器删除 m.clear(); // 清空所有元素容量与遍历m.empty(); // 是否为空 m.size(); // 元素个数 // 遍历顺序不确定 for (const auto [key, val] : m) { std::cout key : val \n; }代码模板竞赛/日常通用#include iostream #include unordered_map #include string int main() { std::unordered_mapstd::string, int mp; // 插入 mp[apple] 3; mp.insert({banana, 5}); mp.emplace(orange, 2); // 查找 访问 auto it mp.find(banana); if (it ! mp.end()) { std::cout it-first it-second \n; } // 不存在时插入常见模式 if (mp.find(grape) mp.end()) { mp[grape] 10; } // 遍历 for (const auto p : mp) { std::cout p.first : p.second \n; } // 删除 mp.erase(apple); mp.clear(); return 0; }关键注意事项1.不要依赖遍历顺序unordered_map 的迭代顺序由哈希函数和桶数量决定不同编译器、不同运行环境可能不同。2.自定义类型作为键需要提供 std::hash 特化或传入自定义哈希函数否则无法编译。3.operator[] 的副作用只读访问时优先用 find 或 at避免无意插入新元素。4.最坏情况退化哈希冲突严重时操作可能退化为 O(n)但正常使用下平均 O(1)。 
长河君 · 2026/10/20 2:32:46 · 阅读 1.2k C++ unordered_map 容器总结
简介底层实现基于哈希表实现。元素的存储顺序是无序的取决于哈希函数和哈希表的结构。插入、删除和查找操作的平均时间复杂度为O(1)但在最坏情况下如大量哈希冲突可能退化到O(n)。查找性能平均查找效率为O(1)适合频繁查找的场景尤其是当数据量较大时性能优势更明显。插入和删除性能平均情况下插入和删除操作的时间复杂度为O(1)但在大量哈希冲突时可能退化。键的有序性键是无序的元素的存储和遍历顺序取决于哈希函数和哈希表的结构。如果需要按键值顺序遍历需要额外排序。内粗使用内存使用可能比std::map稍高因为哈希表需要额外的空间来处理哈希冲突如开放寻址法或链表法。但可以通过调整负载因子load factor来优化内存使用。使用场景适用于需要频繁查找、插入和删除的场景尤其是当数据量较大时。哈希冲突和负载因子哈希表的性能高度依赖于哈希函数的质量和负载因子。负载因子load factor定义为元素数量 / 哈希表大小。当负载因子过高时哈希冲突会增加性能会下降。可以通过rehash方法调整哈希表的大小或者通过max_load_factor方法设置最大负载因子。与map容器的比较特性std::mapstd::unordered_map底层实现红黑树哈希表查找效率O(log n)平均O(1)最坏O(n)插入/删除效率O(log n)平均O(1)最坏O(n)键的有序性有序无序内存使用相对紧凑可能稍高使用场景需要按键值有序存储需要频繁查找、插入和删除如果需要按键值有序存储或频繁进行范围查找使用std::map。如果需要高效的查找、插入和删除操作且对键值的顺序没有要求使用std::unordered_map。成员函数map和unordered_map虽然都是关联容器用于存储键值对但它们的内置函数并不完全相同。尽管它们有许多相似的成员函数但由于底层实现和设计目标的不同它们在某些函数上存在差异。1. 共有的成员函数map和unordered_map都继承自associative_container或unordered_associative_container因此它们有许多共有的成员函数例如begin()和end()返回迭代器分别指向容器的开始和结束位置。size()和empty()分别返回容器中元素的数量和判断容器是否为空。clear()清空容器中的所有元素。find()查找指定键的元素返回一个迭代器。count()统计指定键的元素数量map中每个键只能有一个元素unordered_map也是如此。insert()插入元素。erase()删除元素。operator[]和at()访问指定键的值。上述函数的使用方法请参阅C map容器总结2.unordered_map独有的成员函数load_factor()和max_load_factor()load_factor()返回当前的负载因子元素数量除以哈希表的大小。max_load_factor()获取或设置最大负载因子。当负载因子超过最大值时容器会自动重新哈希rehash。unordered_mapint, string myMap {{1, Apple}, {2, Banana}, {3, Cherry}}; cout Current load factor: myMap.load_factor() endl; myMap.max_load_factor(0.75); // 设置最大负载因子rehash()手动重新哈希调整哈希表的大小以适应当前的负载因子。示例myMap.rehash(10); // 将哈希表大小调整为至少10bucket_count()和bucket_size()bucket_count()返回哈希表的桶bucket数量。bucket_size(bucket_index)返回指定桶中的元素数量。示例cout Number of buckets: myMap.bucket_count() endl; cout Size of bucket 0: myMap.bucket_size(0) endl;bucket(key)返回指定键所在的桶的索引。示例cout Bucket index for key 2: myMap.bucket(2) endl;插入和删除函数的差异虽然std::map和std::unordered_map都有insert()、erase()和emplace()等函数但它们的行为和效率有所不同insert()std::map插入操作的时间复杂度为O(log n)因为它需要在红黑树中查找插入位置。std::unordered_map平均时间复杂度为O(1)但在最坏情况下大量哈希冲突可能退化到O(n)。erase()std::map删除操作的时间复杂度为O(log n)因为它需要在红黑树中查找并调整树结构。std::unordered_map平均时间复杂度为O(1)但在最坏情况下可能退化到O(n)。emplace()std::map直接在红黑树中构造元素避免拷贝或移动时间复杂度为O(log n)。std::unordered_map直接在哈希表中构造元素平均时间复杂度为O(1)但在最坏情况下可能退化到O(n)。迭代器行为的差异std::map迭代器是双向迭代器支持双向遍历和--。遍历顺序是按键值的升序或自定义的比较顺序。std::unordered_map迭代器是前向迭代器仅支持单向遍历。遍历顺序是无序的取决于哈希表的结构。std::unordered_map 是 C11 引入的基于哈希表的关联容器存储键值对平均情况下插入、查找、删除均为 O(1)。它**不保证元素顺序**适合需要快速查找而不关心顺序的场景。常用函数速查与使用方法构造与初始化#include unordered_map #include string std::unordered_mapstd::string, int m1; // 空构造 std::unordered_mapstd::string, int m2{{a,1},{b,2}}; // 初始化列表 std::unordered_mapstd::string, int m3(m2); // 拷贝构造插入元素auto ret m.insert({a, 1}); if (!ret.second) { // 键已存在ret.first 指向已有元素 }访问元素int v1 m[key]; // 键不存在时自动插入默认值慎用于只读场景 int v2 m.at(key); // 键不存在时抛 std::out_of_range注意operator[]在键不存在时会创建新元素如果只想查询是否存在应使用 find 或 count。查找元素// find返回迭代器未找到返回 end() auto it m.find(key); if (it ! m.end()) { std::cout it-first - it-second; } // count返回 0 或 1unordered_map 键唯一 if (m.count(key)) { /* 存在 */ } // C20: contains if (m.contains(key)) { /* 存在 */ }at() 和 find() 都用于只读查询不会插入新元素但它们在键不存在时的行为和返回类型不同。核心区别对比代码示例std::unordered_mapstd::string, int m{{a, 1}}; // at键不存在直接抛异常 try { int v m.at(a); // OK, v 1 int x m.at(missing); // 抛出 std::out_of_range } catch (const std::out_of_range e) { std::cout not found: e.what() \n; } // find键不存在返回 end()可安全判断 auto it m.find(missing); if (it ! m.end()) { std::cout it-second; // 存在时才访问 } else { std::cout not found\n; // 走这里 }使用场景选择用at()的场景你确定键一定存在例如前面已用 find/count 检查过或逻辑上保证存在想直接拿到值的引用代码更简洁// 已知 a 一定在 map 中 int val m.at(a); val 1; // 可直接修改因为返回引用用find()的场景键可能不存在需要根据存在与否走不同分支或需要同时访问 key 和 valueauto it m.find(key); if (it ! m.end()) { // 存在使用 it-first, it-second } else { // 不存在插入或做其他处理 m[key] defaultValue; }关键注意点1.at() 返回的是引用可以修改值m.at(a) 100; 是合法的前提是键存在。find() 返回迭代器通过 it-second 修改。2.at() 用于只读查询是安全的不会像 operator[] 那样在键不存在时偷偷插入元素——它只是抛异常。这是 at() 相对 operator[] 的核心优势。3.find() 不会抛异常是查询存在性的首选at() 更适合我知道它存在直接给我值的表达。4. 三者对比记忆-operator[]不存在 → 插入默认值有副作用-at()不存在 → 抛异常-find()不存在 → 返回 end()无副作用、无异常删除元素m.erase(key); // 按 key 删除返回删除个数 m.erase(it); // 按迭代器删除 m.clear(); // 清空所有元素容量与遍历m.empty(); // 是否为空 m.size(); // 元素个数 // 遍历顺序不确定 for (const auto [key, val] : m) { std::cout key : val \n; }代码模板竞赛/日常通用#include iostream #include unordered_map #include string int main() { std::unordered_mapstd::string, int mp; // 插入 mp[apple] 3; mp.insert({banana, 5}); mp.emplace(orange, 2); // 查找 访问 auto it mp.find(banana); if (it ! mp.end()) { std::cout it-first it-second \n; } // 不存在时插入常见模式 if (mp.find(grape) mp.end()) { mp[grape] 10; } // 遍历 for (const auto p : mp) { std::cout p.first : p.second \n; } // 删除 mp.erase(apple); mp.clear(); return 0; }关键注意事项1.不要依赖遍历顺序unordered_map 的迭代顺序由哈希函数和桶数量决定不同编译器、不同运行环境可能不同。2.自定义类型作为键需要提供 std::hash 特化或传入自定义哈希函数否则无法编译。3.operator[] 的副作用只读访问时优先用 find 或 at避免无意插入新元素。4.最坏情况退化哈希冲突严重时操作可能退化为 O(n)但正常使用下平均 O(1)。