【C++】无序容器unordered_set和unordered_map的使用

1. unordered_set系列的使用

1.1 unordered_set和unordered_multiset参考文档

https://legacy.cplusplus.com/reference/unordered_set/

1.2 unordered_set类的介绍

unordered_set底层是哈希表，而set底层是红黑树

1.3 unordered_set和set的使用差异

void 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); // 重复值相对少 //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 << "unorered_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; }

1.4 unordered_map和map的使用差异

1.5 unordered_multimap/unordered_multiset

• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。
• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅面的差异，
  key的要求的差异，iterator及遍历顺序的差异，性能的差异。

1.6 unordered_xxx的哈希相关接口

Buckets和Hash policy系列的接⼝分别是跟哈希桶和负载因⼦相关的接口，⽇常使用的角度我们不需要太关注，后⾯学习了哈希表底层，我们再来看这个系列的接⼝，一目了然。