C++ unordered_set 和 unordered_map 无序容器深度解析

1 unordered_set

1.1 容器介绍

unordered_set 的声明如下，Key 就是 unordered_set 底层关键字的类型。

template < class Key, // unordered_set::key_type/value_type class Hash = hash<Key>, // unordered_set::hasher class Pred = equal_to<Key>, // unordered_set::key_equal class Alloc = allocator<Key> // unordered_set::allocator_type > class unordered_set;

unordered_set 默认要求 Key 支持转换为整型，如果不支持或者想按自己的需求走可以自行实现支持将 Key 转成整型的仿函数传给第二个模板参数。unordered_set 默认要求 Key 支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将 Key 比较相等的仿函数传给第三个模板参数。unordered_set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数。

一般情况下，我们都不需要传后三个模板参数。

unordered_set 底层是用哈希桶实现，增删查平均效率是 O(1)，迭代器遍历不再有序，为了跟 set 区分，所以取名 unordered_set。

前面部分我们已经学习了 set 容器的使用，set 和 unordered_set 的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。

1.2 unordered_set 和 set 的使用差异

通过查看文档，我们会发现：unordered_set 容器支持增删查，且其使用跟 set 的使用一模一样。

pair<iterator,bool> insert ( const value_type& val ); size_type erase ( const key_type& k ); iterator find ( const key_type& k );

关于使用我们不再赘述。

unordered_set 和 set 的第一个差异是对 key 的要求不同，set 要求 Key 支持小于比较，而 unordered_set 要求 Key 支持转成整形且支持等于比较，要理解 unordered_set 的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

unordered_set 和 set 的第二个差异是迭代器的差异，set 的 iterator 是双向迭代器，unordered_set 是单向迭代器，并且 set 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 set 迭代器遍历是有序 + 去重；而 unordered_set 底层是哈希表，迭代器遍历是无序 + 去重。两者鲜明的的区别就是一个无序一个有序，其它的区别等我们介绍完底层再了解。

unordered_set 和 set 的第三个差异是性能的差异，大多数场景下，unordered_set 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。

注意：哈希表性能有波动——插入时大量扩容，会导致某几次的效率不高，不稳定，时间复杂度平均 O(N)；红黑树时间复杂度稳定 O(logN)。

2 unordered_map

2.1 容器介绍

2.2 unordered_map 和 map 的使用差异

查看文档我们会发现 unordered_map 的支持增删查改且跟 map 的使用一模一样，关于使用我们这里就不再赘述和演示了。

unordered_map 和 map 的第一个差异是对 key 的要求不同，map 要求 Key 支持小于比较，而 unordered_map 要求 Key 支持转成整型且支持等于比较，要理解 unordered_map 的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

unordered_map 和 map 的第二个差异是迭代器的差异，map 的 iterator 是双向迭代器，而 unordered_map 是单向迭代器，其次 map 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 map 迭代器遍历是 Key 有序 + 去重。而 unordered_map 底层是哈希表，迭代器遍历是 Key 无序 + 去重。

unordered_map 和 map 的第三个差异是性能的差异，整体而言大多数场景下，unordered_map 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。

pair<iterator,bool> insert ( const value_type& val ); size_type erase ( const key_type& k ); iterator find ( const key_type& k ); mapped_type& operator[] ( const key_type& k );

2.3 unordered_multimap 和 unordered_multiset

unordered_multimap / unordered_multiset 跟 multimap / multiset 功能完全类似，支持 Key 冗余。

unordered_multimap / unordered_multiset 跟 multimap / multiset 的差异也是三个方面的差异，key 的要求的差异、迭代器 iterator 及遍历顺序的差异、性能的差异。

2.4 拓展：unordered_xxx 的哈希相关接口

Buckets 和 Hashpolicy 系列的接口分别是跟哈希桶和负载因子相关的接口，我们现在不用特别关注这些，等了解完哈希的底层，这些系列的接口我们就能一目了然了。

3 C++17 切换（配置环境）

结构化绑定是 C++17 之后的新特性，之前已经介绍过了，这里不再赘述。

光改 Debug 版本还不够，我们切换到 release 版本运行会通不过——

release 版本也要跟着改——

而且默认是 C++14，每次使用结构化绑定的时候应该在进入 VS 时检查一下 C++ 版本。

4 算法题实战

力扣链接：884. 两句话中的不常见单词

题目描述：

4.1 C++ 算法实现

class Solution { public: vector<string> uncommonFromSentences(string s1, string s2) { unordered_map<string,int> count; // 1、分割 s1 string word; for(auto c : s1) { if(c == ' ') { if(!word.empty()) { count[word]++; word.clear(); } } else { word += c; } } if(!word.empty()) count[word]++; // 2、分割 s2 word.clear(); for(auto c : s2) { if(c == ' ') { if(!word.empty()) { count[word]++; word.clear(); } } else { word += c; } } if(!word.empty()) count[word]++; // 收集结果 vector<string> ret; for(const auto& pair : count) { if(pair.second == 1) { ret.push_back(pair.first); } } return ret; } };

完整代码示例与实践演示

Test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #include<set> #include<vector> #include<unordered_set> #include<unordered_map> int Test_set1() { 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); //sv.push_back(i); // 没有重复，有序 } size_t begin1 = clock(); for (auto e : v) { s.insert(e); } size_t end1 = clock(); cout << "set insert:" << end1 - begin1 << endl; 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; 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; 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; size_t begin5 = clock(); for (auto e : v) { s.erase(e); } size_t end5 = clock(); cout << "set erase:" << end5 - begin5 << endl; 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() { //// 只去重，遍历无序 //unordered_set<int> s; //s.insert(4); //s.insert(1); //s.insert(2); //s.insert(4); //s.insert(5); //for (auto e : s) //{ // cout << e << " "; //} //cout << endl; string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","香蕉","苹果","香蕉" }; unordered_map<string, int> countMap; for (auto& e : arr) { countMap[e]++; } for (auto& [k, v] : countMap) { cout << k << ":" << v << endl; } cout << endl; Test_set1(); return 0; }

运行结果一

运行结果二