在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_multiset

3.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 = hash<Key>, // 哈希函数对象，用于把Key映射成哈希值 class Pred = equal_to<Key>, // 相等比较函数对象，用于判断两个Key是否相等 class Alloc = allocator<Key> // 空间配置器，用于管理底层内存的申请与释放 > 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_set<int> us; // 哈希表实现的无序集合 set<int> s; // 红黑树实现的有序集合 vector<int> 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 = hash<Key>, // 哈希函数对象 class Pred = equal_to<Key>, // 键相等比较函数对象 class Alloc = allocator<pair<const 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; map<int, int> m; unordered_map<int, int> um; vector<pair<int, 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_multiset

unordered_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 = hash<Key>, // 哈希函数对象 class Pred = equal_to<Key>, // Key相等比较函数对象 class Alloc = allocator<Key> // 空间配置器 > 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 = hash<Key>, // 哈希函数对象 class Pred = equal_to<Key>, // Key相等比较函数对象 class Alloc = allocator<pair<const Key, T>> // 空间配置器 > class unordered_multimap;

与unordered_map一样，unordered_multimap中每个元素本质上都是一个pair<const Key, T>。

其中：

• Key表示键（Key）；
• T表示键对应的值（Value）；
• Hash负责计算Key的哈希值；
• Pred用于判断两个Key是否相等；
• Alloc用于管理底层存储空间。

由于底层采用哈希表实现，因此unordered_multimap同样要求Key能够计算哈希值，并支持相等比较。

到这里，unordered系列容器的使用方式和特点就介绍完了。可以发现，它们的接口设计与对应的树形容器高度一致，因此真正需要掌握的并不是接口，而是底层数据结构带来的行为差异。很多时候，我们之所以能够熟练使用一个容器，并不是因为记住了它有哪些成员函数，而是知道它为什么这样设计、为什么具有这样的时间复杂度，以及在什么场景下最适合使用。下一篇，我们将不再停留在STL容器的使用层面，而是从零开始实现哈希表，一起深入理解unordered系列容器背后的核心原理。