哈希密钥：解锁unordered容器的极速潜能

目录一.unordered系列关联式容器二:unordered_set1:unordered_set用法详解1.1:模板参数介绍1.2:unordered_set的构造函数1.3:常用接口使用1.3.1:insert与erase1.3.2:find与size与empty1.3.3:clear与swap与count1.3.4:迭代器1.3.5:桶操作三:unordered_map1:unorder_map用法详解1.1:模板参数介绍1.2:unordered_map的接口说明1.2.1:unordered_map的构造函数1.2.2:unordered_map的容量1.2.3:unordered_map的迭代器1.2.4:unordered_map的元素访问1.2.5:unordered_map的查询1.2.6:unordered_map的修改操作1.2.6.1:insert与erase1.2.6.2:clear与swap1.2.7:unordered_map的桶操作四:unordered_set和set的使用差异五:unordered_map和map的使用差异一.unordered系列关联式容器在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到log2N即最差情况下需要比较红黑树的高度次,当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同.二:unordered_setunordered_set是不按特定顺序存储键值的关联式容器其允许通过键值快速的索引到对应的元素。在unordered_set中,元素的值同时也是唯一地标识它的key。在内部unordered_set中的元素没有按照任何特定的顺序排序为了能在常数范围内找到指定的Keyunordered_set将相同哈希值的键值放在相同的桶中。在unordered_set容器通过key访问单个元素要比set快但它通常在遍历元素子集的范围迭代效率较低。它的迭代器至少是前向迭代器。1:unordered_set用法详解1.1:模板参数介绍template class Key, // unordered_set::key_type/value_type class Hash hashKey, // unordered_set::hasher class Pred equal_toKey, // unordered_set::key_equal class Alloc allocatorKey // unordered_set::allocator_type class unordered_set;1.Key键类型用于定义键的数据类型必须是可哈希可比较的2.Hash哈希函数类型默认std::hashKey将键转换为size_t类型的哈希值可以使用stl内置的哈希函数该参数可以缺省如果用unordered_SET存储自定义数据类型则需要自己设置哈希函数.3.KeyEqual键相等比较函数默认std::equal_toKey判断两个键是否相等可以使用stl内置的键相等比较函数该参数可缺省如果用unordered_set存储自定义数据类型则需要自己设计键相等比较函数该函数是实现键值去重和查找必不可少的.4.Allocator分配器类型默认std::allocatorpairconst Key, T管理内存的分配和释放1.2:unordered_set的构造函数构造一个某类型的空容器。拷贝构造某同类型容器的复制品。使用迭代器拷贝构造某一段内容。#include iostream using namespace std; #include unordered_set int main() { vectorint v1 { 1,2,3,4,5,6,7,8,9 }; //构造 unordered_setint s1; //拷贝构造 unordered_setint s2(s1); //迭代器构造 unordered_setint s3(v1.begin(), v1.end()); for (const auto e : s3) cout e ; cout endl; return 0; }1.3:常用接口使用成员函数功能insert插入指定元素erase删除指定元素find查找指定元素size获取容器中元素的个数empty判断容器是否为空clear清空容器swap交换两个容器中的数据count获取容器中指定元素值的元素个数1.3.1:insert与erase#include iostream using namespace std; #include unordered_set void TestInsertAndErase() { unordered_setint us1; us1.insert(1); us1.insert(2); us1.insert(7); us1.insert(5); us1.insert(9); us1.insert(25); us1.insert(4); for (const auto e : us1) cout e ; cout endl; us1.erase(25); us1.erase(9); us1.erase(7); for (const auto e : us1) cout e ; cout endl; } int main() { TestInsertAndErase(); }1.3.2:find与size与empty#include iostream using namespace std; #include unordered_set void TestFindAndSizeAndEmpty() { unordered_setint us1; us1.insert(1); us1.insert(2); us1.insert(7); us1.insert(5); us1.insert(9); us1.insert(25); us1.insert(4); //返回的是该数值的迭代器 cout *(us1.find(5)) endl; cout Size: us1.size() endl; cout us1.empty() endl; } int main() { TestFindAndSizeAndEmpty(); }1.3.3:clear与swap与count#include iostream using namespace std; #include unordered_set void TestInsertAndErase() { unordered_setint us1; us1.insert(1); us1.insert(2); us1.insert(7); us1.insert(5); us1.insert(9); us1.insert(25); us1.insert(4); for (const auto e : us1) cout e ; cout endl; us1.erase(25); us1.erase(9); us1.erase(7); for (const auto e : us1) cout e ; cout endl; } void TestFindAndSizeAndEmpty() { unordered_setint us1; us1.insert(1); us1.insert(2); us1.insert(7); us1.insert(5); us1.insert(9); us1.insert(25); us1.insert(4); //返回的是该数值的迭代器 cout *(us1.find(5)) endl; cout Size: us1.size() endl; cout us1.empty() endl; } void TestClearAndSwapAndCount() { unordered_setint us1; us1.insert(1); us1.insert(2); us1.insert(7); us1.insert(5); us1.insert(9); us1.insert(25); us1.insert(4); unordered_setint us2; us2.insert(6); us2.insert(3); us2.insert(8); us2.insert(11); us2.insert(17); us2.insert(20); us2.insert(20); us2.insert(20); cout 交换前 endl; for (auto e : us1) cout e ; cout endl; for (auto e : us2) cout e ; cout endl; us1.swap(us2); cout 交换后 endl; for (auto e : us1) cout e ; cout endl; for (auto e : us2) cout e ; cout endl; cout us1.count(2): us1.count(2) endl; cout us2.count(20): us1.count(20) endl; us1.clear(); us2.clear(); cout us1:size: us1.size() endl; cout us2:size: us2.size() endl; } int main() { TestClearAndSwapAndCount(); }1.3.4:迭代器#include iostream using namespace std; #include unordered_set void TestIterator() { unordered_setint us1 { 10,20,30,40,50,60 }; unordered_setint::iterator it us1.begin(); while(it ! us1.end()) { cout *it ; it; } cout endl; for (auto element : us1) cout element ; cout endl; } int main() { TestIterator(); }1.3.5:桶操作STL实现哈希表示意图对于哈希值相同的元素STL选择将其用链表链接起来挂到同一个桶上面去。在C STL中unordered_set和unordered_map的默认最大负载因子是 1.0负载因子 插入元素数量 / 桶数量这意味着当容器中的元素数量超过桶的数量时即负载因子 1.0就会触发扩容。#include iostream using namespace std; #include unordered_set void TestBucket() { unordered_setint uset { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; cout bucket_count: uset.bucket_count() endl; // 桶的数量 cout max_bucket_count: uset.max_bucket_count() endl; cout load_factor: uset.load_factor() endl; // 负载因子 cout max_load_factor: uset.max_load_factor() endl; // 最大负载因子 // 遍历桶 for (size_t i 0; i uset.bucket_count(); i) { cout Bucket i has uset.bucket_size(i) elements endl; } // 查找元素所在的桶 int val 5; cout val is in bucket uset.bucket(val) endl; } int main() { TestBucket(); }三:unordered_mapunordered_map是存储key,value键值对的关联式容器其允许通过keys快速的索引到与其对应的value.在unordered_map中键值通常用于唯一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部unordered_map没有对keyvalue按照任何特定的顺序排序为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符operator[],它允许使用key作为参数直接访问value它的迭代器至少是前向迭代器.1:unorder_map用法详解1.1:模板参数介绍template class Key, // unordered_map::key_type class T, // unordered_map::mapped_type class Hash hashKey, // unordered_map::hasher class Pred equal_toKey, // unordered_map::key_equal class Alloc allocator pairconst Key,T // unordered_map::allocator_type class unordered_map;Key键类型定义键的数据类型必须是可哈希和可比较的T值类型定义与键关联的的值的类型.Hash哈希函数类型默认:std::hashKey将键转换为size_t类型的哈希值KeyEqual键相等比较函数默认std::equal_toKey判断两个键是否相等内置数据类型和string类可以使用stl内置的键相等比较函数该参数可缺省如果用unordered_set存储自定义数据类型则需要自己设计键相等比较函数该函数是实现键值去重和查找必不可少的。Allocator分配器类型默认std::allocatorpairconst Key, T管理内存的分配和释放绝大多数情况使用默认分配器特殊场景如嵌入式系统、实时系统可能需要自定义分配器.1.2:unordered_map的接口说明1.2.1:unordered_map的构造函数#include iostream using namespace std; #include unordered_set #include unordered_map void TestConstructor() { unordered_mapstring, int m1{ {abc, 1}, {awb, 2}, {ccd, 3} }; unordered_mapstring, int m2(m1); unordered_mapstring, int m3; } int main() { TestConstructor(); return 0; }1.2.2:unordered_map的容量函数声明功能介绍bool empty() const检测unordered_map是否为空size_t size() const获获取unordered_map的有效元素个数#include iostream using namespace std; #include unordered_set #include unordered_map void TestCapacity() { unordered_mapstring, int m1{ {abc, 1}, {awb, 2}, {ccd, 3} }; cout m1.size() endl; cout m1.empty() endl; } int main() { TestConstructor(); TestCapacity(); return 0; }1.2.3:unordered_map的迭代器函数声明功能介绍begin返回unordered_map第一个元素的迭代器end返回unordered_map最后一个元素下一个位置的迭代器cbegin返回unordered_map第一个元素的const迭代器cend返回unordered_map最后一个元素下一个位置的const迭代器#include iostream using namespace std; #include unordered_set #include unordered_map void TestIterator() { unordered_mapstring,int m1{ {abc, 1}, {awb, 2}, {ccd, 3} }; unordered_mapstring, int::iterator it m1.begin(); while (it ! m1.end()) { cout it-first it-second endl; it; } cout endl; unordered_mapstring, int::const_iterator rit m1.cbegin(); while (rit ! m1.cend()) { cout rit-first rit-second endl; rit; } } int main() { TestIterator(); return 0; }1.2.4:unordered_map的元素访问函数声明功能介绍operator[]返回与key对应的value没有一个默认值注意:该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回.#include iostream using namespace std; #include unordered_set #include unordered_map void TestElementAccess() { unordered_mapstring, int m1 { {abc,1},{awb,2}}; cout m1[abc] endl; cout m1[awb] endl; cout m1[ccd] endl; cout endl; } int main() { TestElementAccess(); return 0; }1.2.5:unordered_map的查询函数声明功能介绍iterator find(const K key)返回key在哈希桶中的位置size_t count(const K key)返回哈希桶中关键码为key的键值对的个数#include iostream using namespace std; #include unordered_set #include unordered_map void TestFindAndCount() { unordered_mapstring, int m1 { {abc,1},{awb,2},{ccd,3},{awd,4} }; unordered_mapstring, int::iterator it m1.find(abc); cout it-first : it-second endl; cout m1.count(abc) endl; } int main() { TestFindAndCount(); return 0; }注意unordered_map中key是不能重复的因此count函数的返回值最大为11.2.6:unordered_map的修改操作函数声明功能介绍insert向容器中插入键值对erase删除容器中的键值对void clear()清空容器中有效元素个数void swap(unordered map)交换两个容器中的元素1.2.6.1:insert与erase#include iostream using namespace std; #include unordered_set #include unordered_map void TestModify() { unordered_mapstring, int m1 { {abc,1},{awb,2}}; m1.insert({ ccd,3 }); m1.insert({ awd,4 }); unordered_mapstring, int::iterator it m1.begin(); while(it ! m1.end()) { cout it-first : it-second endl; it; } cout endl; m1.erase(abc); m1.erase(awd); for (auto e : m1) { cout e.first : e.second endl; } } int main() { TestModify(); return 0; }1.2.6.2:clear与swap#include iostream using namespace std; #include unordered_set #include unordered_map void TestClearAndSwap() { unordered_mapstring, int m1 { {abc,1},{awb,2}}; unordered_mapstring, int m2 { {ccd,3},{awd,4}}; cout 交换前 endl; for (const auto e : m1) { cout e.first : e.second endl; } cout endl; for (const auto e : m2) { cout e.first : e.second endl; } cout 交换后 endl; m1.swap(m2); for (const auto e : m1) { cout e.first : e.second endl; } cout endl; for (const auto e : m2) { cout e.first : e.second endl; } m1.clear(); m2.clear(); cout m1:size: m1.size() endl; cout m2:size: m2.size() endl; } int main() { TestClearAndSwap(); return 0; }1.2.7:unordered_map的桶操作函数声明功能介绍size_t bucket count()const返回哈希桶中桶的总个数size_t bucket size(size_t n) const返回n号桶中有效元素的总个数size_t bucket(const K key)返回元素key所在的桶号#include iostream using namespace std; #include unordered_set #include unordered_map void TestBucketOperation() { unordered_mapstring, int m1 { {abc,1},{awb,2},{ccd,3},{awd,4} }; cout m1.bucket_count() endl; cout m1.bucket_size(2) endl; cout m1.bucket(abc) endl; } int main() { TestBucketOperation(); return 0; }四:unordered_set和set的使用差异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).#include iostream using namespace std; #include unordered_set #include unordered_map #include set void Test() { 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); // 没有重复有序 } 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; } int main() { Test(); return 0; }五: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)具体可以参看下⾯代码的演示的对比差异。#include iostream using namespace std; #include unordered_set #include unordered_map #include map #include set void Test() { const size_t N 1000000; unordered_mapint, int um; mapint, int m; 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); // 没有重复有序 } size_t begin1 clock(); for (auto e : v) { m.insert({e,e}); } size_t end1 clock(); cout map insert: end1 - begin1 endl; size_t begin2 clock(); um.reserve(N); for (auto e : v) { um.insert({e,e}); } size_t end2 clock(); cout unordered_map insert: end2 - begin2 endl; int m1 0; size_t begin3 clock(); for (auto e : v) { auto ret m.find(e); if (ret ! m.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 um.find(e); if (ret ! um.end()) { m2; } } size_t end4 clock(); cout unorered_set find: end4 - begin4 - m2 endl; cout 插入数据个数 m.size() endl; cout 插入数据个数 um.size() endl endl; size_t begin5 clock(); for (auto e : v) { m.erase(e); } size_t end5 clock(); cout map erase: end5 - begin5 endl; size_t begin6 clock(); for (auto e : v) { um.erase(e); } size_t end6 clock(); cout unordered_map erase: end6 - begin6 endl endl; } int main() { Test(); return 0; }