【C++】封装unordered_map和unordered_set

封装unordered_map和unordered_set1、unordered_map和unordered_set的基本结构在封装map和set时set的数据类型为keymap的数据类型为pairkey, valueset的数据类型为key在比较时set用key比较map用parkey, map中的key比较所以在用红黑树封装时在map和set中都设计了函数KeyOfT用来提取key值unordered_map和unordered_set采用开散列的方式来实现需要改造哈希表1.1 哈希表的改造templateclassK,classT,classKeyOfT,classHashclassHashTable;K键的类型T如果是unordered_set那么存放的只有key如果是unordered_map那么存放的是键值对pairK, VKeyOfT从T中提取出key的仿函数Hash哈希函数仿函数1.2 unordered_set的基本结构namespaceMySet{templateclassK,classHashHashFuncKclassunordered_set{// 将data转换成keystructSetKeyOfT{constKoperator()(constKkey){returnkey;}};public:private:HashTableK,constK,SetKeyOfT,Hash_t;};}1.3 unordered_map的基本结构namespaceMyMap{templateclassK,classV,classHashHashFuncKclassunordered_map{// 将data转换成keystructMapKeyOfT{constKoperator()(constpairK,Vkv){returnkv.first;}};public:private:HashTableK,pairconstK,V,MapKeyOfT,Hash_t;};}1.4 增加哈希表迭代器哈希表本质是由多个哈希桶组成的哈希表迭代器表示从当前节点走到下一个节点当迭代器走完当前桶时需要跳到下一个桶共有两种情况当前节点不是尾节点next为下一个有效节点当前节点为尾节点next为空需要跳到下一个桶// 前置声明templateclassK,classT,classKeyOfT,classHashclassHashTable;templateclassK,classT,classRef,classPtr,classKeyOfT,classHashstructHTIterator{typedefHashNodeTNode;typedefHashTableK,T,KeyOfT,HashHT;typedefHTIteratorK,T,Ref,Ptr,KeyOfT,HashSelf;Node*_node;constHT*_ht;HTIterator(Node*node,constHT*ht):_node(node),_ht(ht){}Selfoperator(){if(_node-_next)// 当前还有节点{_node_node-_next;}else// 当前桶为空找下一个不为空的桶的第一个{// 取出当前节点存储的数据的key计算当前节点所在桶的下标hashi// KeyOfT()仿函数从存储的数据T里提取出键K// Hash()哈希函数仿函数把K转为哈希数值// % _ht-_tables.size()取模映射到桶数组合法下标size_t hashiHash()(KeyOfT()(_node-_data))%_ht-_tables.size();// 当前桶走完下标1从下一个桶开始查找有效数据hashi;// 如果下一个桶是空的只要桶下标没超过数组最大长度就需要一直循环找非空桶while(hashi!_ht-_tables.size()){// 判断当前下标对应的桶是不是非空链表if(_ht-_tables[hashi]){// 找到第一个有数据的桶迭代器节点指向该桶链表头_node_ht-_tables[hashi];break;}// 当前桶是空的下标继续1检查下一个桶hashi;}// 最后一个桶的最后一个节点已经遍历结束走到end()去nullptr充当end()if(hashi_ht-_tables.size()){_nodenullptr;}}return*this;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}};1.5 修改后的哈希表templateclassK,classT,classKeyOfT,classHashclassHashTable{// 友元声明templateclassK,classT,classRef,classPtr,classKeyOfT,classHashfriendstructHTIterator;typedefHashNodeTNode;public:typedefHTIteratorK,T,T,T*,KeyOfT,HashIterator;typedefHTIteratorK,T,constT,constT*,KeyOfT,HashConstIterator;IteratorBegin(){for(size_t i0;i_tables.size();i){if(_tables[i]){returnIterator(_tables[i],this);}}returnEnd();}IteratorEnd(){returnIterator(nullptr,this);}ConstIteratorBegin()const{for(size_t i0;i_tables.size();i){if(_tables[i]){returnConstIterator(_tables[i],this);}}returnEnd();}ConstIteratorEnd()const{returnConstIterator(nullptr,this);}HashTable():_tables(__stl_next_prime(1),nullptr),_n(0){}~HashTable(){for(size_t i0;i_tables.size();i){Node*cur_tables[i];// 当前桶的节点重新映射挂到新表while(cur){Node*nextcur-_next;deletecur;curnext;}_tables[i]nullptr;}}pairIterator,boolInsert(constTdata){KeyOfT kot;autoitFind(kot(data));if(it!End())return{it,false};Hash hs;// 负载因子1扩容if(_n_tables.size()){vectorNode*newtables(__stl_next_prime(_tables.size()1));for(size_t i0;i_tables.size();i){Node*cur_tables[i];// 当前桶的节点重新映射挂到新表while(cur){Node*nextcur-_next;// 插入到新表size_t hashihs(kot(cur-_data))%newtables.size();cur-_nextnewtables[hashi];newtables[hashi]cur;curnext;}_tables[i]nullptr;}_tables.swap(newtables);}size_t hashihs(kot(data))%_tables.size();// 头插Node*newNodenewNode(data);newNode-_next_tables[hashi];_tables[hashi]newNode;_n;return{Iterator(newNode,this),true};}IteratorFind(constKkey){KeyOfT kot;Hash hs;size_t hashihs(key)%_tables.size();Node*cur_tables[hashi];while(cur){if(kot(cur-_data)key)return{cur,this};curcur-_next;}returnEnd();}boolErase(constKkey){KeyOfT kot;Hash hs;size_t hashihs(key)%_tables.size();Node*prevnullptr;Node*cur_tables[hashi];while(cur){if(kot(cur-_data)key){if(prevnullptr){_tables[hashi]cur-_next;}else{prev-_nextcur-_next;}deletecur;returntrue;}prevcur;curcur-_next;}returnfalse;}private:vectorNode*_tables;size_t _n0;// 实际存储的数据个数};1.6 完成unordered_map和unordered_set1.6.1 unordered_map的operator[]下标重载Voperator[](constKkey){pairiterator,boolretinsert({key,V()});returnret.first-second;}拿传入的 key调用insert构造一个默认空 value的键值对尝试用insert插入拿到对应key的迭代器返回value的引用1.6.2 unordered_map#pragmaonce#includeHashTable.hnamespaceMyMap{templateclassK,classV,classHashHashFuncKclassunordered_map{structMapKeyOfT{constKoperator()(constpairK,Vkv){returnkv.first;}};public:typedeftypenameHashTableK,pairconstK,V,MapKeyOfT,Hash::Iterator iterator;typedeftypenameHashTableK,pairconstK,V,MapKeyOfT,Hash::ConstIterator const_iterator;iteratorbegin(){return_t.Begin();}iteratorend(){return_t.End();}const_iteratorbegin()const{return_t.Begin();}const_iteratorend()const{return_t.End();}pairiterator,boolinsert(constpairK,Vkv){return_t.Insert(kv);}Voperator[](constKkey){pairiterator,boolretinsert({key,V()});returnret.first-second;}boolerase(constKkey){return_t.Erase(key);}iteratorfind(constKkey){return_t.Find(key);}private:HashTableK,pairconstK,V,MapKeyOfT,Hash_t;};voidtest_umap(){unordered_mapstring,stringdict;dict.insert({insert,插入});dict.insert({sort,排序});dict.insert({test,测试});for(auto[k,v]:dict){// k x;coutk:vendl;}dict[string]字符串;dict[key];dict[key]关键字;dict[for];for(auto[k,v]:dict){coutk:vendl;}}};1.6.3 unordered_set#pragmaonce#includeHashTable.hnamespaceMySet{templateclassK,classHashHashFuncKclassunordered_set{structSetKeyOfT{constKoperator()(constKkey){returnkey;}};public:typedeftypenameHashTableK,constK,SetKeyOfT,Hash::Iterator iterator;typedeftypenameHashTableK,constK,SetKeyOfT,Hash::ConstIterator const_iterator;iteratorbegin(){return_t.Begin();}iteratorend(){return_t.End();}const_iteratorbegin()const{return_t.Begin();}const_iteratorend()const{return_t.End();}pairiterator,boolinsert(constKk){return_t.Insert(k);}boolerase(constKkey){return_t.Erase(key);}iteratorfind(constKkey){return_t.Find(key);}private:HashTableK,constK,SetKeyOfT,Hash_t;};voidFunc(constunordered_setints){autoit1s.begin();while(it1!s.end()){// *it1 1;cout*it1 ;it1;}coutendl;}voidtest_uset1(){unordered_setints1;s1.insert(45);s1.insert(5);s1.insert(13);s1.insert(45);s1.insert(452);s1.insert(4513);s1.insert(333);s1.insert(123);Func(s1);autoit1s1.begin();while(it1!s1.end()){//*it1 1;cout*it1 ;it1;}coutendl;}structDate{int_year;int_month;int_day;booloperator(constDated)const{return_yeard._year_monthd._month_dayd._day;}};structDateHashFunc{// BKDRsize_toperator()(constDated){size_t hash0;hashd._year;hash*131;hashd._month;hash*131;hashd._day;hash*131;returnhash;}};voidtest_uset2(){unordered_setDate,DateHashFuncs1;s1.insert({2025,9,15});s1.insert({2025,9,18});}};