在C STL中关联式容器一直承担着高效数据管理的重要角色。根据底层实现方式的不同它们通常可以分为两类一类是基于红黑树实现的有序关联容器如set、map另一类则是基于哈希表实现的无序关联容器如unordered_set、unordered_map。前面我们已经学习过set、map等容器它们最大的特点是能够自动维护元素的有序性。但在很多实际开发场景中我们并不关心元素的排列顺序而更加关注数据的快速查找和访问效率。此时基于哈希表实现的unordered系列容器就展现出了更大的优势。与红黑树相比哈希表通过哈希函数将数据映射到对应的位置使得元素的插入、删除和查找操作在平均情况下可以达到O(1)的时间复杂度。因此unordered_set、unordered_map等容器在大量数据检索、快速映射等场景中得到了广泛应用。不过效率的提升也伴随着设计上的变化。由于底层结构不同unordered系列容器在Key的要求、迭代器类型、遍历顺序以及性能特点等方面都与set、map存在明显差异。只有理解这些区别才能在实际开发中根据需求选择更加合适的容器。本文将围绕C STL中的unordered_set、unordered_map以及支持重复Key的多重哈希容器展开介绍深入分析它们的使用特点以及与传统关联式容器之间的差异。unordered_set和unordered_multiset参考⽂档unordered_set - C Reference目录一、unordered_set系列的使用类的介绍1.1 unordered_set类的介绍1.2 unordered_set的声名1.3 unordered_set和set的使用差异1.3.1 对Key的要求不同1.3.2 迭代器不同。1.3.3 性能不同二、unordered_map系列的使用类的介绍2.1 unordered_map类的介绍2.2 unordered_map的声名2.3.1 对 Key 的要求不同2.3.2 迭代器不同2.3.3 性能不同三、unordered_multimap/unordered_multiset3.1 unordered_multimap/unordered_multiset和multimap/multiset的主要差异3.1.1 对Key的要求不同3.1.2 迭代器及遍历顺序不同3.1.3 性能不同3.2 unordered_multimap/unordered_multiset的声明3.2.1 unordered_multiset的声明3.2.2 unordered_multimap的声明一、unordered_set系列的使用类的介绍1.1 unordered_set类的介绍unordered_set的声明形式如下其中Key表示unordered_set底层关键字的类型。unordered_set默认要求Key能够转换为整型如果不支持或者你希望按照自己的规则来处理就可以自行实现一个将Key转换为整型的仿函数并将其作为第二个模板参数传入。它还默认要求Key之间能够进行相等比较如果这一点不满足或者你想自定义比较方式也可以编写一个判断相等的仿函数传给第三个模板参数。至于底层数据存储所需的内存unordered_set是通过空间配置器申请的如果有特殊需求也可以自己实现内存池作为第四个模板参数传入。不过在实际开发中这三个模板参数一般都不需要手动指定使用默认配置通常就足够了。unordered_set底层采用哈希桶实现增删查的平均时间复杂度都可以达到O(1)效率非常高。但它的迭代器遍历结果不再保持有序这也是它和set的一个重要区别。也正因为如此它被命名为unordered_set意在强调“无序”这一特性。前面我们已经学习过set容器的用法。set和unordered_set的功能非常相近区别主要在于底层结构不同因此在性能表现和使用习惯上也会存在一些差异。接下来我们重点来看它们之间的这些不同之处。1.2 unordered_set的声名template class Key, // 关键字类型也就是unordered_set底层存储的元素类型 class Hash hashKey, // 哈希函数对象用于把Key映射成哈希值 class Pred equal_toKey, // 相等比较函数对象用于判断两个Key是否相等 class Alloc allocatorKey // 空间配置器用于管理底层内存的申请与释放 class unordered_set;1.3 unordered_set和set的使用差异查看文档可以发现unordered_set也支持增、删、查而且接口用法和set基本一模一样。关于具体的基本用法这里就不再重复演示了下面直接看它们之间的差异。1.3.1 对Key的要求不同set要求Key支持“小于比较”也就是能够按照大小关系进行排序而unordered_set要求Key能够转换为整型并且支持相等比较。这个“转成整型”和“判断相等”的要求单看接口可能不太好理解后面我们结合哈希表的底层实现再来分析就能明白这其实是哈希结构本身决定的。1.3.2 迭代器不同。set的迭代器是双向迭代器而unordered_set的迭代器是单向迭代器。除此之外set底层是红黑树红黑树本质上是二叉搜索树因此按中序遍历得到的结果是有序的所以set的遍历结果具有“有序 去重”的特点。而unordered_set底层是哈希表元素的存放顺序和插入顺序、数值大小都没有直接关系所以遍历结果是“无序 去重”的。1.3.3 性能不同在大多数场景下unordered_set的增、删、查通常会更快一些。因为红黑树的增删查改时间复杂度是O(log N)而哈希表的增删查平均时间复杂度可以达到O(1)。当然这只是平均情况具体表现还要看数据分布和哈希冲突情况。下面通过一段代码简单对比一下它们的性能差异#include unordered_set #include unordered_map #include set #include iostream using namespace std; int test_set2() { const size_t N 1000000; unordered_setint us; // 哈希表实现的无序集合 setint s; // 红黑树实现的有序集合 vectorint v; // 用来存放测试数据 v.reserve(N); srand(time(0)); for (size_t i 0; i N; i) { // v.push_back(rand()); // N 较大时重复值比较多 v.push_back(rand() i); // 重复值相对少 // v.push_back(i); // 没有重复并且有序 } //set插入测试 size_t begin1 clock(); for (auto e : v) { s.insert(e); } size_t end1 clock(); cout set insert: end1 - begin1 endl; //unordered_set插入测试 size_t begin2 clock(); us.reserve(N); // 预留空间减少扩容带来的开销 for (auto e : v) { us.insert(e); } size_t end2 clock(); cout unordered_set insert: end2 - begin2 endl; //set查找测试 int m1 0; size_t begin3 clock(); for (auto e : v) { auto ret s.find(e); if (ret ! s.end()) { m1; } } size_t end3 clock(); cout set find: end3 - begin3 - m1 endl; //unordered_set查找测试 int m2 0; size_t begin4 clock(); for (auto e : v) { auto ret us.find(e); if (ret ! us.end()) { m2; } } size_t end4 clock(); cout unordered_set find: end4 - begin4 - m2 endl; cout 插入数据个数 s.size() endl; cout 插入数据个数 us.size() endl endl; //set删除测试 size_t begin5 clock(); for (auto e : v) { s.erase(e); } size_t end5 clock(); cout set erase: end5 - begin5 endl; //unordered_set删除测试 size_t begin6 clock(); for (auto e : v) { us.erase(e); } size_t end6 clock(); cout unordered_set erase: end6 - begin6 endl endl; return 0; } int main() { test_set2(); return 0; }二、unordered_map系列的使用类的介绍2.1 unordered_map类的介绍unordered_map是C标准库中非常常用的关联式容器之一它用来存储键值对数据。和map一样unordered_map也强调“键”和“值”的对应关系不过和map不同的是unordered_map底层并不是红黑树而是通过哈希表来实现的。在unordered_map中Key表示键T表示映射的值类型。也就是说容器里的每个元素都可以理解为一组“Key - Value”的对应关系。由于键具有唯一性所以同一个Key不能重复出现但不同的Key可以对应不同的Value。这也是unordered_map在实际开发中非常适合用来做“查表”“统计”“映射关系维护”的原因。和unordered_set 一样unordered_map的查找、插入和删除在平均情况下都能达到较高效率通常可以认为是 O(1)。不过它也有一个很明显的特点遍历结果是无序的。也就是说元素在容器中的存放顺序并不反映键的大小关系也不反映插入顺序这一点和map是完全不同的。从使用角度来看unordered_map的接口也比较直观。我们可以通过键直接访问对应的值也可以通过迭代器遍历整个容器。在很多场景下它都能提供比map更快的访问速度尤其是在数据量较大、并且对顺序没有要求的时候unordered_map往往会更合适。unordered_map可以看作是一个“无序的键值对容器”它以哈希表为底层结构强调高效访问和快速查找。接下来我们就来具体学习它的声明、接口以及常见使用方式。2.2 unordered_map的声名template class Key, // 键的类型 class T, // 映射值的类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // 键相等比较函数对象 class Alloc allocatorpairconst Key, T // 空间配置器 class unordered_map;2.3 unordered_map和map的使用差异查看文档可以发现unordered_map同样支持增、删、查、改而且它的接口设计和map基本一致。也就是说从“怎么用”的角度来看两者非常接近很多代码几乎可以直接平移过去。因此这里我们就不再重复演示基础用法了重点看它们之间的差异。2.3.1 对 Key 的要求不同map要求Key支持“小于比较”也就是必须能够比较大小这样它才能把元素按照一定顺序组织起来。而unordered_map要求Key能够转换成整型并且还要支持相等比较。这个要求单看接口可能有点抽象但本质上其实是哈希表的底层需求先通过哈希函数把键映射成哈希值再通过相等比较来判断是否是同一个键。unordered_map对Key的要求严格来说并不是“随便什么类型都能直接用”而是要满足哈希结构的规则。后面我们学习哈希表底层实现时这一点就会更好理解。2.3.2 迭代器不同map的迭代器是双向迭代器而unordered_map的迭代器是单向迭代器。除此之外两者的遍历效果也完全不一样。map底层是红黑树而红黑树本质上是二叉搜索树所以它按中序遍历得到的结果天然就是有序的。因此map迭代器遍历时表现为Key有序去重。unordered_map底层则是哈希表元素存放的位置主要由哈希值决定和 Key 的大小关系没有直接联系所以它的遍历结果表现为Key无序去重。这一点在实际开发中很重要如果你希望遍历结果保持顺序那就更适合用map如果你更在意查找效率而不关心顺序那么unordered_map往往更合适。2.3.3 性能不同整体来看在大多数场景下unordered_map的增、删、查、改通常会更快一些。原因很直接map底层是红黑树增删查改的时间复杂度是O(log N)而unordered_map底层是哈希表增删查改的平均时间复杂度可以达到O(1)。当然这里的O(1)指的是平均情况并不是绝对情况。如果哈希冲突比较严重性能也会受到影响。但在大多数常规场景下unordered_map的效率优势还是很明显的。map和unordered_map的功能非常接近但由于底层结构不同它们在Key的要求、迭代器特性以及性能表现上都有明显区别。简单记就是map更偏向“有序”unordered_map更偏向“高效”。下面可以通过一段代码来简单对比它们在插入、查找和删除上的表现差异。#include map #include unordered_map #include vector #include iostream #include ctime #include cstdlib using namespace std; void test_map_vs_unordered_map() { const size_t N 1000000; mapint, int m; unordered_mapint, int um; vectorpairint, int v; v.reserve(N); srand((unsigned)time(nullptr)); // 构造测试数据 for (size_t i 0; i N; i) { // 键和值都设置得比较分散尽量减少重复 v.push_back(make_pair(rand() i, rand())); } //map插入测试 size_t begin1 clock(); for (auto e : v) { m.insert(e); } size_t end1 clock(); cout map insert: end1 - begin1 endl; //unordered_map插入测试 size_t begin2 clock(); um.reserve(N); // 预留空间减少扩容带来的开销 for (auto e : v) { um.insert(e); } size_t end2 clock(); cout unordered_map insert: end2 - begin2 endl; //map查找测试 int cnt1 0; size_t begin3 clock(); for (auto e : v) { auto ret m.find(e.first); if (ret ! m.end()) { cnt1; } } size_t end3 clock(); cout map find: end3 - begin3 - cnt1 endl; //unordered_map查找测试 int cnt2 0; size_t begin4 clock(); for (auto e : v) { auto ret um.find(e.first); if (ret ! um.end()) { cnt2; } } size_t end4 clock(); cout unordered_map find: end4 - begin4 - cnt2 endl; cout map size: m.size() endl; cout unordered_map size: um.size() endl endl; //map删除测试 size_t begin5 clock(); for (auto e : v) { m.erase(e.first); } size_t end5 clock(); cout map erase: end5 - begin5 endl; //unordered_map删除测试 size_t begin6 clock(); for (auto e : v) { um.erase(e.first); } size_t end6 clock(); cout unordered_map erase: end6 - begin6 endl; } int main() { test_map_vs_unordered_map(); return 0; }三、unordered_multimap/unordered_multisetunordered_multimap和 unordered_multiset的功能可以分别对应理解为multimap和multiset的无序版本。它们和multimap、multiset一样都支持Key冗余也就是说同一个Key可以重复出现这一点和map、set这种“去重容器”是不一样的。从使用角度来看unordered_multimap/unordered_multiset和multimap/multiset的接口也非常接近增、删、查等基本操作的写法基本一致所以这里我们不再重复演示具体用法。它们之间真正值得关注的还是底层结构带来的差异。整体来说这两类容器和multimap/multiset的差异主要体现在三个方面。3.1 unordered_multimap/unordered_multiset和multimap/multiset的主要差异3.1.1 对Key的要求不同multimap和multiset依赖红黑树实现因此要求Key支持小于比较而unordered_multimap和 unordered_multiset底层是哈希表因此要求Key能够转换成整型并且支持相等比较。换句话说前者更关注“大小关系”后者更关注“哈希映射”和“相等判断”。这也是它们底层结构决定的本质差异。3.1.2 迭代器及遍历顺序不同multimap和multiset底层是红黑树树结构天然支持有序遍历因此迭代器遍历时元素是按照一定顺序排列的。而unordered_multimap和unordered_multiset底层是哈希表元素的存放位置主要由哈希值决定所以遍历结果是无序的。不过它们也有一个共同点都支持Key冗余也就是允许重复元素存在只是一个是“有序重复”一个是“无序重复”。3.1.3 性能不同一般情况下unordered_multimap和unordered_multiset的增、删、查效率会更高一些。因为红黑树的相关操作时间复杂度通常是O(log N)而哈希表在平均情况下可以做到O(1)。当然这里的 O(1)仍然是平均意义上的结果如果哈希冲突比较严重性能也会受到影响。但在大多数常规场景下哈希结构的效率优势还是比较明显的尤其是在数据量较大、并且对顺序没有强需求的时候unordered_multimap和unordered_multiset往往更合适。简单总结一下unordered_multimap和unordered_multiset可以看作是“支持重复元素的无序关联容器”。它们保留了多重容器支持重复Key的特点同时又利用哈希表提升了平均访问效率。和 multimap、multiset 相比它们更偏向高效查找和map、set相比它们则多了一层“允许冗余”的特性。3.2 unordered_multimap/unordered_multiset的声明unordered_multiset和unordered_multimap的模板声明与前面介绍的unordered_set、unordered_map基本一致最大的区别在于它们允许Key重复因此插入相同Key的元素时不会去重。3.2.1 unordered_multiset的声明template class Key, // 关键字类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // Key相等比较函数对象 class Alloc allocatorKey // 空间配置器 class unordered_multiset;可以看到unordered_multiset的模板参数与unordered_set完全一致。Key关键字类型也是容器中存储的数据类型。Hash哈希函数对象用于计算Key的哈希值从而确定元素应该存放到哪个哈希桶Bucket中。Pred相等比较函数对象用于判断两个Key是否相等。Alloc空间配置器负责底层内存的申请和释放。在实际开发中后面三个模板参数几乎都使用默认值即可只有当Key是自定义类型或者需要自定义哈希规则时才需要手动指定。3.2.2 unordered_multimap的声明template class Key, // 键的类型 class T, // 映射值类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // Key相等比较函数对象 class Alloc allocatorpairconst Key, T // 空间配置器 class unordered_multimap;与unordered_map一样unordered_multimap中每个元素本质上都是一个pairconst Key, T。其中Key表示键KeyT表示键对应的值ValueHash负责计算Key的哈希值Pred用于判断两个Key是否相等Alloc用于管理底层存储空间。由于底层采用哈希表实现因此unordered_multimap同样要求Key能够计算哈希值并支持相等比较。到这里unordered系列容器的使用方式和特点就介绍完了。可以发现它们的接口设计与对应的树形容器高度一致因此真正需要掌握的并不是接口而是底层数据结构带来的行为差异。很多时候我们之所以能够熟练使用一个容器并不是因为记住了它有哪些成员函数而是知道它为什么这样设计、为什么具有这样的时间复杂度以及在什么场景下最适合使用。下一篇我们将不再停留在STL容器的使用层面而是从零开始实现哈希表一起深入理解unordered系列容器背后的核心原理。
C++ STL unordered系列容器详解：从unordered_set到unordered_map
在C STL中关联式容器一直承担着高效数据管理的重要角色。根据底层实现方式的不同它们通常可以分为两类一类是基于红黑树实现的有序关联容器如set、map另一类则是基于哈希表实现的无序关联容器如unordered_set、unordered_map。前面我们已经学习过set、map等容器它们最大的特点是能够自动维护元素的有序性。但在很多实际开发场景中我们并不关心元素的排列顺序而更加关注数据的快速查找和访问效率。此时基于哈希表实现的unordered系列容器就展现出了更大的优势。与红黑树相比哈希表通过哈希函数将数据映射到对应的位置使得元素的插入、删除和查找操作在平均情况下可以达到O(1)的时间复杂度。因此unordered_set、unordered_map等容器在大量数据检索、快速映射等场景中得到了广泛应用。不过效率的提升也伴随着设计上的变化。由于底层结构不同unordered系列容器在Key的要求、迭代器类型、遍历顺序以及性能特点等方面都与set、map存在明显差异。只有理解这些区别才能在实际开发中根据需求选择更加合适的容器。本文将围绕C STL中的unordered_set、unordered_map以及支持重复Key的多重哈希容器展开介绍深入分析它们的使用特点以及与传统关联式容器之间的差异。unordered_set和unordered_multiset参考⽂档unordered_set - C Reference目录一、unordered_set系列的使用类的介绍1.1 unordered_set类的介绍1.2 unordered_set的声名1.3 unordered_set和set的使用差异1.3.1 对Key的要求不同1.3.2 迭代器不同。1.3.3 性能不同二、unordered_map系列的使用类的介绍2.1 unordered_map类的介绍2.2 unordered_map的声名2.3.1 对 Key 的要求不同2.3.2 迭代器不同2.3.3 性能不同三、unordered_multimap/unordered_multiset3.1 unordered_multimap/unordered_multiset和multimap/multiset的主要差异3.1.1 对Key的要求不同3.1.2 迭代器及遍历顺序不同3.1.3 性能不同3.2 unordered_multimap/unordered_multiset的声明3.2.1 unordered_multiset的声明3.2.2 unordered_multimap的声明一、unordered_set系列的使用类的介绍1.1 unordered_set类的介绍unordered_set的声明形式如下其中Key表示unordered_set底层关键字的类型。unordered_set默认要求Key能够转换为整型如果不支持或者你希望按照自己的规则来处理就可以自行实现一个将Key转换为整型的仿函数并将其作为第二个模板参数传入。它还默认要求Key之间能够进行相等比较如果这一点不满足或者你想自定义比较方式也可以编写一个判断相等的仿函数传给第三个模板参数。至于底层数据存储所需的内存unordered_set是通过空间配置器申请的如果有特殊需求也可以自己实现内存池作为第四个模板参数传入。不过在实际开发中这三个模板参数一般都不需要手动指定使用默认配置通常就足够了。unordered_set底层采用哈希桶实现增删查的平均时间复杂度都可以达到O(1)效率非常高。但它的迭代器遍历结果不再保持有序这也是它和set的一个重要区别。也正因为如此它被命名为unordered_set意在强调“无序”这一特性。前面我们已经学习过set容器的用法。set和unordered_set的功能非常相近区别主要在于底层结构不同因此在性能表现和使用习惯上也会存在一些差异。接下来我们重点来看它们之间的这些不同之处。1.2 unordered_set的声名template class Key, // 关键字类型也就是unordered_set底层存储的元素类型 class Hash hashKey, // 哈希函数对象用于把Key映射成哈希值 class Pred equal_toKey, // 相等比较函数对象用于判断两个Key是否相等 class Alloc allocatorKey // 空间配置器用于管理底层内存的申请与释放 class unordered_set;1.3 unordered_set和set的使用差异查看文档可以发现unordered_set也支持增、删、查而且接口用法和set基本一模一样。关于具体的基本用法这里就不再重复演示了下面直接看它们之间的差异。1.3.1 对Key的要求不同set要求Key支持“小于比较”也就是能够按照大小关系进行排序而unordered_set要求Key能够转换为整型并且支持相等比较。这个“转成整型”和“判断相等”的要求单看接口可能不太好理解后面我们结合哈希表的底层实现再来分析就能明白这其实是哈希结构本身决定的。1.3.2 迭代器不同。set的迭代器是双向迭代器而unordered_set的迭代器是单向迭代器。除此之外set底层是红黑树红黑树本质上是二叉搜索树因此按中序遍历得到的结果是有序的所以set的遍历结果具有“有序 去重”的特点。而unordered_set底层是哈希表元素的存放顺序和插入顺序、数值大小都没有直接关系所以遍历结果是“无序 去重”的。1.3.3 性能不同在大多数场景下unordered_set的增、删、查通常会更快一些。因为红黑树的增删查改时间复杂度是O(log N)而哈希表的增删查平均时间复杂度可以达到O(1)。当然这只是平均情况具体表现还要看数据分布和哈希冲突情况。下面通过一段代码简单对比一下它们的性能差异#include unordered_set #include unordered_map #include set #include iostream using namespace std; int test_set2() { const size_t N 1000000; unordered_setint us; // 哈希表实现的无序集合 setint s; // 红黑树实现的有序集合 vectorint v; // 用来存放测试数据 v.reserve(N); srand(time(0)); for (size_t i 0; i N; i) { // v.push_back(rand()); // N 较大时重复值比较多 v.push_back(rand() i); // 重复值相对少 // v.push_back(i); // 没有重复并且有序 } //set插入测试 size_t begin1 clock(); for (auto e : v) { s.insert(e); } size_t end1 clock(); cout set insert: end1 - begin1 endl; //unordered_set插入测试 size_t begin2 clock(); us.reserve(N); // 预留空间减少扩容带来的开销 for (auto e : v) { us.insert(e); } size_t end2 clock(); cout unordered_set insert: end2 - begin2 endl; //set查找测试 int m1 0; size_t begin3 clock(); for (auto e : v) { auto ret s.find(e); if (ret ! s.end()) { m1; } } size_t end3 clock(); cout set find: end3 - begin3 - m1 endl; //unordered_set查找测试 int m2 0; size_t begin4 clock(); for (auto e : v) { auto ret us.find(e); if (ret ! us.end()) { m2; } } size_t end4 clock(); cout unordered_set find: end4 - begin4 - m2 endl; cout 插入数据个数 s.size() endl; cout 插入数据个数 us.size() endl endl; //set删除测试 size_t begin5 clock(); for (auto e : v) { s.erase(e); } size_t end5 clock(); cout set erase: end5 - begin5 endl; //unordered_set删除测试 size_t begin6 clock(); for (auto e : v) { us.erase(e); } size_t end6 clock(); cout unordered_set erase: end6 - begin6 endl endl; return 0; } int main() { test_set2(); return 0; }二、unordered_map系列的使用类的介绍2.1 unordered_map类的介绍unordered_map是C标准库中非常常用的关联式容器之一它用来存储键值对数据。和map一样unordered_map也强调“键”和“值”的对应关系不过和map不同的是unordered_map底层并不是红黑树而是通过哈希表来实现的。在unordered_map中Key表示键T表示映射的值类型。也就是说容器里的每个元素都可以理解为一组“Key - Value”的对应关系。由于键具有唯一性所以同一个Key不能重复出现但不同的Key可以对应不同的Value。这也是unordered_map在实际开发中非常适合用来做“查表”“统计”“映射关系维护”的原因。和unordered_set 一样unordered_map的查找、插入和删除在平均情况下都能达到较高效率通常可以认为是 O(1)。不过它也有一个很明显的特点遍历结果是无序的。也就是说元素在容器中的存放顺序并不反映键的大小关系也不反映插入顺序这一点和map是完全不同的。从使用角度来看unordered_map的接口也比较直观。我们可以通过键直接访问对应的值也可以通过迭代器遍历整个容器。在很多场景下它都能提供比map更快的访问速度尤其是在数据量较大、并且对顺序没有要求的时候unordered_map往往会更合适。unordered_map可以看作是一个“无序的键值对容器”它以哈希表为底层结构强调高效访问和快速查找。接下来我们就来具体学习它的声明、接口以及常见使用方式。2.2 unordered_map的声名template class Key, // 键的类型 class T, // 映射值的类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // 键相等比较函数对象 class Alloc allocatorpairconst Key, T // 空间配置器 class unordered_map;2.3 unordered_map和map的使用差异查看文档可以发现unordered_map同样支持增、删、查、改而且它的接口设计和map基本一致。也就是说从“怎么用”的角度来看两者非常接近很多代码几乎可以直接平移过去。因此这里我们就不再重复演示基础用法了重点看它们之间的差异。2.3.1 对 Key 的要求不同map要求Key支持“小于比较”也就是必须能够比较大小这样它才能把元素按照一定顺序组织起来。而unordered_map要求Key能够转换成整型并且还要支持相等比较。这个要求单看接口可能有点抽象但本质上其实是哈希表的底层需求先通过哈希函数把键映射成哈希值再通过相等比较来判断是否是同一个键。unordered_map对Key的要求严格来说并不是“随便什么类型都能直接用”而是要满足哈希结构的规则。后面我们学习哈希表底层实现时这一点就会更好理解。2.3.2 迭代器不同map的迭代器是双向迭代器而unordered_map的迭代器是单向迭代器。除此之外两者的遍历效果也完全不一样。map底层是红黑树而红黑树本质上是二叉搜索树所以它按中序遍历得到的结果天然就是有序的。因此map迭代器遍历时表现为Key有序去重。unordered_map底层则是哈希表元素存放的位置主要由哈希值决定和 Key 的大小关系没有直接联系所以它的遍历结果表现为Key无序去重。这一点在实际开发中很重要如果你希望遍历结果保持顺序那就更适合用map如果你更在意查找效率而不关心顺序那么unordered_map往往更合适。2.3.3 性能不同整体来看在大多数场景下unordered_map的增、删、查、改通常会更快一些。原因很直接map底层是红黑树增删查改的时间复杂度是O(log N)而unordered_map底层是哈希表增删查改的平均时间复杂度可以达到O(1)。当然这里的O(1)指的是平均情况并不是绝对情况。如果哈希冲突比较严重性能也会受到影响。但在大多数常规场景下unordered_map的效率优势还是很明显的。map和unordered_map的功能非常接近但由于底层结构不同它们在Key的要求、迭代器特性以及性能表现上都有明显区别。简单记就是map更偏向“有序”unordered_map更偏向“高效”。下面可以通过一段代码来简单对比它们在插入、查找和删除上的表现差异。#include map #include unordered_map #include vector #include iostream #include ctime #include cstdlib using namespace std; void test_map_vs_unordered_map() { const size_t N 1000000; mapint, int m; unordered_mapint, int um; vectorpairint, int v; v.reserve(N); srand((unsigned)time(nullptr)); // 构造测试数据 for (size_t i 0; i N; i) { // 键和值都设置得比较分散尽量减少重复 v.push_back(make_pair(rand() i, rand())); } //map插入测试 size_t begin1 clock(); for (auto e : v) { m.insert(e); } size_t end1 clock(); cout map insert: end1 - begin1 endl; //unordered_map插入测试 size_t begin2 clock(); um.reserve(N); // 预留空间减少扩容带来的开销 for (auto e : v) { um.insert(e); } size_t end2 clock(); cout unordered_map insert: end2 - begin2 endl; //map查找测试 int cnt1 0; size_t begin3 clock(); for (auto e : v) { auto ret m.find(e.first); if (ret ! m.end()) { cnt1; } } size_t end3 clock(); cout map find: end3 - begin3 - cnt1 endl; //unordered_map查找测试 int cnt2 0; size_t begin4 clock(); for (auto e : v) { auto ret um.find(e.first); if (ret ! um.end()) { cnt2; } } size_t end4 clock(); cout unordered_map find: end4 - begin4 - cnt2 endl; cout map size: m.size() endl; cout unordered_map size: um.size() endl endl; //map删除测试 size_t begin5 clock(); for (auto e : v) { m.erase(e.first); } size_t end5 clock(); cout map erase: end5 - begin5 endl; //unordered_map删除测试 size_t begin6 clock(); for (auto e : v) { um.erase(e.first); } size_t end6 clock(); cout unordered_map erase: end6 - begin6 endl; } int main() { test_map_vs_unordered_map(); return 0; }三、unordered_multimap/unordered_multisetunordered_multimap和 unordered_multiset的功能可以分别对应理解为multimap和multiset的无序版本。它们和multimap、multiset一样都支持Key冗余也就是说同一个Key可以重复出现这一点和map、set这种“去重容器”是不一样的。从使用角度来看unordered_multimap/unordered_multiset和multimap/multiset的接口也非常接近增、删、查等基本操作的写法基本一致所以这里我们不再重复演示具体用法。它们之间真正值得关注的还是底层结构带来的差异。整体来说这两类容器和multimap/multiset的差异主要体现在三个方面。3.1 unordered_multimap/unordered_multiset和multimap/multiset的主要差异3.1.1 对Key的要求不同multimap和multiset依赖红黑树实现因此要求Key支持小于比较而unordered_multimap和 unordered_multiset底层是哈希表因此要求Key能够转换成整型并且支持相等比较。换句话说前者更关注“大小关系”后者更关注“哈希映射”和“相等判断”。这也是它们底层结构决定的本质差异。3.1.2 迭代器及遍历顺序不同multimap和multiset底层是红黑树树结构天然支持有序遍历因此迭代器遍历时元素是按照一定顺序排列的。而unordered_multimap和unordered_multiset底层是哈希表元素的存放位置主要由哈希值决定所以遍历结果是无序的。不过它们也有一个共同点都支持Key冗余也就是允许重复元素存在只是一个是“有序重复”一个是“无序重复”。3.1.3 性能不同一般情况下unordered_multimap和unordered_multiset的增、删、查效率会更高一些。因为红黑树的相关操作时间复杂度通常是O(log N)而哈希表在平均情况下可以做到O(1)。当然这里的 O(1)仍然是平均意义上的结果如果哈希冲突比较严重性能也会受到影响。但在大多数常规场景下哈希结构的效率优势还是比较明显的尤其是在数据量较大、并且对顺序没有强需求的时候unordered_multimap和unordered_multiset往往更合适。简单总结一下unordered_multimap和unordered_multiset可以看作是“支持重复元素的无序关联容器”。它们保留了多重容器支持重复Key的特点同时又利用哈希表提升了平均访问效率。和 multimap、multiset 相比它们更偏向高效查找和map、set相比它们则多了一层“允许冗余”的特性。3.2 unordered_multimap/unordered_multiset的声明unordered_multiset和unordered_multimap的模板声明与前面介绍的unordered_set、unordered_map基本一致最大的区别在于它们允许Key重复因此插入相同Key的元素时不会去重。3.2.1 unordered_multiset的声明template class Key, // 关键字类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // Key相等比较函数对象 class Alloc allocatorKey // 空间配置器 class unordered_multiset;可以看到unordered_multiset的模板参数与unordered_set完全一致。Key关键字类型也是容器中存储的数据类型。Hash哈希函数对象用于计算Key的哈希值从而确定元素应该存放到哪个哈希桶Bucket中。Pred相等比较函数对象用于判断两个Key是否相等。Alloc空间配置器负责底层内存的申请和释放。在实际开发中后面三个模板参数几乎都使用默认值即可只有当Key是自定义类型或者需要自定义哈希规则时才需要手动指定。3.2.2 unordered_multimap的声明template class Key, // 键的类型 class T, // 映射值类型 class Hash hashKey, // 哈希函数对象 class Pred equal_toKey, // Key相等比较函数对象 class Alloc allocatorpairconst Key, T // 空间配置器 class unordered_multimap;与unordered_map一样unordered_multimap中每个元素本质上都是一个pairconst Key, T。其中Key表示键KeyT表示键对应的值ValueHash负责计算Key的哈希值Pred用于判断两个Key是否相等Alloc用于管理底层存储空间。由于底层采用哈希表实现因此unordered_multimap同样要求Key能够计算哈希值并支持相等比较。到这里unordered系列容器的使用方式和特点就介绍完了。可以发现它们的接口设计与对应的树形容器高度一致因此真正需要掌握的并不是接口而是底层数据结构带来的行为差异。很多时候我们之所以能够熟练使用一个容器并不是因为记住了它有哪些成员函数而是知道它为什么这样设计、为什么具有这样的时间复杂度以及在什么场景下最适合使用。下一篇我们将不再停留在STL容器的使用层面而是从零开始实现哈希表一起深入理解unordered系列容器背后的核心原理。
