企业服务app,济南官网seo技术厂家,站酷网logo素材图库,前端外包公司【数据结构】【C】封装哈希表模拟实现unordered_map和unordered_set容器 一.哈希表的完成二.改造哈希表(泛型适配)三.封装unordered_map和unordered_set的接口四.实现哈希表迭代器(泛型适配)五.封装unordered_map和unordered_set的迭代器六.解决key不能修改问题七.实… 【数据结构】【C】封装哈希表模拟实现unordered_map和unordered_set容器 一.哈希表的完成二.改造哈希表(泛型适配)三.封装unordered_map和unordered_set的接口四.实现哈希表迭代器(泛型适配)五.封装unordered_map和unordered_set的迭代器六.解决key不能修改问题七.实现map[]运算符重载 一.哈希表的完成
在上一篇哈希表的模拟实现中已经将哈希表实现完毕这里不再分析。
#pragma once
using namespace std;
#include vector
#includeiostream//哈希桶//1.第一哈希表的完成//哈希结点
template class K,class V
struct HashNode
{pairK, V _kv;//存储的数据HashNodeK, V* _next;//指向下一个结点的指针HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}
};template class K
struct defaulthashfunc//默认的仿函数可以让数据模
{size_t operator()(const K key){return (size_t)key;//将key强行类型转化//这样作的意义可以负数也可以进行模了}
};
template
//模板的特化当数据类型是int的时候就默认使用defaulthashfuncint,当数据类型是string类型时就默认使用defaulthashfuncstring
struct defaulthashfuncstring
{size_t operator()(const string str){//为了减少冲突我们将字符串的每个字符的值相加size_t hash 0;for (auto it : str){hash * 131;hash it;}return hash;}
};//要写一个仿函数 因为不是所有的数据类型都可以模的
// 一般整数是可以模的string类型是无法模的
// 所以我们要写一个仿函数来达到传的数据可以模
//这样也就是增加了哈希表的一个模板参数l
templateclass K,class V,class HashfuncdefaulthashfuncK
//哈希表
class Hash_table
{typedef HashNodeK, V Node;//哈希需要将写析构函数虽然自定义类型vector会自动调用默认析构但它里面的成员是内置类型没有默认构造//所以需要我们自己析构每个结点
public:~Hash_table(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;//要先保存起来delete cur;cur next;}_table[i] nullptr;}}Hash_table(){//构造_table.resize(10, nullptr);//首先开出十个空间每个空间值为空}bool insert(const pairK, V _kv){Hashfunc hf;//仿函数可以使数据模//在插入之前确认一下表里是否已经有了这个值如果有了就不用插入了if (find(_kv.first)){return false;}//我们自己控制扩容逻辑虽然vector会自己扩容但我们要控制。因为扩容完有的key会冲突有的值又不冲突了。//如果不扩容那么冲突多了就根单链表一样了//当负载因子大约等于1时就要扩容平均每个桶里有一个数据if (n _table.size()){//异地扩容重新开空间size_t newSize _table.size() * 2;vectorNode* newtable;newtable.resize(newSize, nullptr);//不能再复用下面的方法这样不好因为就又重开空间然后又要释放//我们应该将原来的结点拿过来使用//所以我们遍历旧表将旧表的结点拿过来签到新表上for (size_t i 0; i _table.size(); i){//扩容后空间size变大了有的数据就可能会存到不同的桶里了//拿下来的结点要重新计算放进哪个位置Node* cur _table[i];//cur后面可能还有链接的结点while (cur){size_t hashi hf(cur-_kv.first) % newtable.size();Node* next cur-_next;//头插到新表cur-_next newtable[hashi];//头插 这个结点的 接到插入结点的前面对吧//那么next就接到newtavle[i]newtable[hashi] cur;//往后走接着拿走cur next;}//当前桶里的结点被拿光后就置为空_table[i] nullptr;}//这个新表就是我们想要的表那么我们利用vector、的交换让旧表和新表交换_table.swap(newtable);}size_t hashi hf(_kv.first) % _table.size();Node* newnode new Node(_kv);newnode-_next _table[hashi];_table[hashi] newnode;//将新结点头插到哈希桶里n;return true;}Node* find(const K key){Hashfunc hf;size_t hashi hf(key)% _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key)return cur;elsecur cur-_next;}return nullptr;}void Print(){for (int i 0; i _table.size(); i){printf([%d], i);Node* cur _table[i];while (cur){cout cur-_kv.first ;cur cur-_next;}cout endl;}}bool erase(const K key){Hashfunc hf;//可以复用find吗先用find找到key然后删除key呢4//不可以因为删除一个结点需要找到这个结点的前面和后面的位置但这里只有key的位置所以不能直接复用find但是复用其中的步骤size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key)//找到要删除的结点后{//将前面的结点的指针指向后面的前面//还有一种可能cur就是桶里的第一个那么就是头删了prev就是nullptrif (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;//每次先记录一下前面的结点位置cur cur-_next;}}return false;}
private://底层封装的是一个数组//数组里的指针指向的都是哈希结点vectorNode* _table;//底层还封装一个大小n表示实际表中的数据个数size_t n0;///用来计算负载因子
};
二.改造哈希表(泛型适配)
我们要对哈希表进行改造因为unordered_map和unordered_set底层用的都是哈希表虽然不是同一个哈希表但是是同一个模板实例化出来的哈希表。我们要让哈希表可以适配存储不同的数据类型因为unordered_set里面存的是K类型而unordered_map里面存的是pairK,V类型。 所以我们一开始并不知道哈希表里存的数据是什么类型那么就用T表示。当传的模板参数是K类型哈希表就实例化存的就是K类型当传的模板参数是pairK,V类型哈希表实例化存的就是pairK,V类型所以我们可以通过传不同的模板参数来决定哈希表里存的是什么数据类型。 所以我们需要改造哈希表将里面的数据都改成T类型修改成T类型的原因是我们不知道是什么数据类型根据传的模板参数决定。 template class T
//定义哈希结点
struct HashNode
{T _data;//存储的数据是T类型根据传过来的模板参数确定HashNodeT* _next;//指向下一个结点的指针HashNode(const T data):_data(data), _next(nullptr){}
};
// [问题]一旦泛型后我们就不知道数据的具体类型了那么我们要利用除留余数法计算哈希地址时(我们都是利用key来进行取模的而我们不知道具体的类型是K类型还是pairK,V类型)就要写一个仿函数这个仿函数根据map和set传过来的然后实例化出哈希表中的仿函数。获取数据中的key让key进行计算c
templateclass K, class T
//哈希表
class Hash_table
{typedef HashNodeT Node;public:~Hash_table(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-_next;//要先保存起来delete cur;cur next;}_table[i] nullptr;}}Hash_table(){//构造_table.resize(10, nullptr);//首先开出十个空间每个空间值为空}bool insert(const T data){…………………}bool find(const K key){………………}bool erase(const K key){……………… }
private:vectorNode* _table;//底层还封装一个大小n表示实际表中的数据个数size_t n 0;//用来计算负载因子
};
存在问题 这里不管是插入还是查找还是删除第一步都是需要将数据的哈希地址找到而哈希地址是利用除留余数法计算得到的是利用key值进行取模的但这里一旦适配泛型后我们就不知道具体的类型是K类型还是pairK,V类型如果是K类型那么就可以直接取模如果是pairK,V类型那是不可以直接取模的需要将里面的key值取出来。 解决方法 我们可以利用一个仿函数这个仿函数的功能是可以将数据里的Key类型数据取出来。那么我们可以给哈希表增加一个模板参数给仿函数用。一旦遇到要计算哈希地址或者比较的操作时我们就可以将数据里的K值取出来进行计算比较。 仿函数实现的原理当T类型是K类型数据时直接返回K值即可当T类型是pairK,V数据时返回里面的first数据即可(就是K值)。
templateclass K, class T, class KeyOfT,class Hashfunc defaulthashfuncK
//哈希表
class Hash_table
{typedef HashNodeT Node;
public:Hash_table(){//构造_table.resize(10, nullptr);//首先开出十个空间每个空间值为空}bool insert(const T data){KeyOfT kt;Hashfunc hf;//仿函数可以使数据模//在插入之前确认一下表里是否已经有了这个值如果有了就不用插入了if (find(kt(data))){return false;}if (n _table.size()){//异地扩容重新开空间size_t newSize _table.size() * 2;vectorNode* newtable;newtable.resize(newSize, nullptr);for (size_t i 0; i _table.size(); i){Node* cur _table[i];//cur后面可能还有链接的结点while (cur){size_t hashi hf(kt(cur-_data)) % newtable.size();Node* next cur-_next;cur-_next newtable[hashi];newtable[hashi] cur;//往后走接着拿走cur next;}//当前桶里的结点被拿光后就置为空_table[i] nullptr;}//这个新表就是我们想要的表那么我们利用vector、的交换让旧表和新表交换_table.swap(newtable);}size_t hashi hf(kt(data)) % _table.size();//这里有两个仿函数kt是用来获取data数据里的key值//hf是用来适配不同的K值,因为string类型无法取模Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;//将新结点头插到哈希桶里n;return true;}iterator find(const K key){Hashfunc hf;KeyOfT kt;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kt(cur-_data) key)return iterator(cur,this);elsecur cur-_next;}return iterator(nullptr,this);}bool erase(const K key){Hashfunc hf;KeyOfT kt;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){//这里仿函数kt是用来获取data数据里的key值if (kt(cur-_data) key)//找到要删除的结点后{//将前面的结点的指针指向后面的前面//还有一种可能cur就是桶里的第一个那么就是头删了prev就是nullptrif (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--n;return true;}else{prev cur;//每次先记录一下前面的结点位置cur cur-_next;}}return false;}
private:vectorNode* _table;//底层还封装一个大小n表示实际表中的数据个数size_t n 0;//用来计算负载因子
};三.封装unordered_map和unordered_set的接口
封装set,内部实现仿函数然后底层封装的是存储K值(结点指针)的哈希表。
#includeHash.h
namespace tao
{templateclass Kclass set{struct setoft//仿函数用来获取数据的key值{const K operator()(const K key){return key;}};public:bool insert(const K key){return _ht.insert(key);}private://底层封装一个哈希表哈希表里存的是K类型Hash_tableK, K, setoft _ht;};
};
封装map实现仿函数底层存储的是pairK,V类型的(结点指针)哈希表。
#includeHash.h
namespace tao
{templateclass K, class Vclass map{struct mapoft//仿函数获取数据中的key值{const K operator()(const pairK, V kv){return kv.first;}};public:bool insert(const pairK, V kv){return _ht.insert(kv);}private://底层封装一个哈希表,哈希表里的数据是pairK,V类型Hash_tableK, pairconst K, V, mapoft _ht;};
};
四.实现哈希表迭代器(泛型适配)
哈希表的迭代器是一个自定义类型因为原生的结点指针不能满足我们想要的操作所以我们就直接将结点的指针封装起来然后自定义一个类型对这个结点指针增加一些操作来完成我们想要的效果。 首先哈希表的迭代器里肯定要封装一个结点的指针后找到下一个结点在一个哈希桶里就代表着找链表下面的结点即可那么如果该结点就是链表最后一个结点呢怎么找到下一个不为空的桶呢又或者你是如何找到第一个不为空的桶的呢 所以这里我们还需要一个指向哈希表的指针这样我们才可以找到桶与桶之间的关系而结点指针是用来找结点与结点之间的关系的。 哈希表的迭代器里封装两个对象一个是结点指针一个哈希表指针。 1.迭代器有普通迭代器和const迭代器普通迭代很好实现那么const迭代器如何实现呢 与链表的const迭代器实现原理一样我们通过三个模板参数(template class T,class Ref,class Ptr)来控制函数的返回值从而控制返回的是普通类型的迭代器还是const类型的迭代器。这里也就是泛型适配适配多种类型 。 Ref控制解引用函数的返回值当Ref为T时返回的就是普通迭代器当Ref为const T时返回的就是const迭代器。 Ptr控制的-重载函数的返回值当Ptr为T时返回的就是普通迭代器当Ptr为const T时返回的就是const迭代器。 2.哈希表迭代器的实现原理 ①假设当前结点在一个桶里这个桶还没走完那么直接找下一个结点即可 ②如果这个结点是桶里最后一个原生即桶走完了那么我们就要找下一个不为空的桶 ③如何找到下一个不为空的桶呢首先将当前结点的哈希地址计算出来然后将哈希地址再利用一个循环查找后面的桶是否为空如果不为空那么这个桶就是最终结果如果为空就再找后面的桶。 //泛型适配--适配普通迭代器和const迭代器
templateclass K, class T,class Ref,class Ptr, class KeyOfT, class Hashfunc
//哈希表的迭代器里面肯定封装一个结点的指针但还需要通过表来找到下一个桶因为我们需要遍历先找到第一个桶当这个桶遍历完后怎么找到下一个不为空的桶呢
//需要通过这个哈希表来找到桶所以我们还需要一个指向哈希表的指针struct HSIterator
{typedef HashNodeT Node;/typedef HSIteratorK, T,Ref,Ptr,KeyOfT, Hashfunc Self;Node* _node;//底层封装着一个结点指针const Hash_table K,T, KeyOfT,Hashfunc* _pht;//底层还封装着一个哈希表指针//这里可以加const因为我们不是根据pht来找到哈希表来修改哈希表里的内容HSIterator(Node* node, Hash_tableK, T, KeyOfT,Hashfunc* hs):_node(node), _pht(hs){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_next)//当前桶没有走完那么直接找下一个即可{_node _node-_next;}else//当前桶走到空了就要找下一个不为空的桶{KeyOfT kof;Hashfunc hf;size_t hashi hf(kof(_node-_data)) % _pht-_table.size();//这里我们在外面去调用了哈希表的私有成员所以我们需要让迭代器成为哈希表的友元//找到当前桶的位置hashi;//找下一个桶不为空while (hashi_pht-_table.size()){if (_pht-_table[hashi]){_node _pht-_table[hashi];return *this;}else{hashi;}}//走到这里就说明桶走走光了还没找到_node nullptr;}return *this;}bool operator!(const Self s){return _node ! s._node;}};
【存在问题1】 这里存在一个相互依赖关系问题因为在哈希表里我们使用了迭代器在迭代器里我们又使用了哈希表。我们需要在这里使用前置声明告诉编译器我们是有哈希表只不过哈希表在后面。这样就不会报错啦。
//这里存在问题迭代器里要用哈希哈希里面要有迭代器相互依赖关系
//我们这里用前置声明告诉编译器我们要是有哈希表这个表是存在的在后面
templateclass K, class T, class KeyOfT, class Hashfunc
class Hash_table;
templateclass K, class T,class Ref,class Ptr, class KeyOfT, class Hashfuncstruct HSIterator
{………………………………………………………………………………………………………………………………
};
【存在问题2】: 在迭代器的里我们在计算当前结点的哈希地址时取模时利用哈希指针找到了哈希表里的vectorNode* _table元素并访问了它的函数这里我们在外面调用哈希表的私有成员这样是不可行所以我们需要让迭代器成为哈希表的友元类这样在迭代器里就可以使用哈希表的私有成员了。
迭代器实现之后我们就可以在哈希表里来实现迭代器的begin()和end()了。 begin()就是找哈希表里第一个不为空的桶。 end()就是找最后一个不为空的桶的下一个位置也就是空。
templateclass K, class T, class KeyOfT,class Hashfunc defaulthashfuncK
//哈希表
class Hash_table
{typedef HashNodeT Node;templateclass K, class T, class Ref,class Ptr,class KeyOfT, class Hashfuncfriend struct HSIterator;//让迭代器成为哈希表的友元
public:typedef HSIteratorK, T,T,T*, KeyOfT, Hashfunc iterator;//适配普通迭代器typedef HSIteratorK, T, const T, const T*, KeyOfT, Hashfunc const_iterator;//适配const迭代器iterator begin(){//找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){if (cur){return iterator(cur, this);//这里this就是哈希表的指针}}}//最后没有找到return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{//找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){if (cur){return const_iterator(cur, this);}}}//最后没有找到return const_iterator(nullptr, this);}const_iterator end()const{return const_iterator(nullptr, this);}bool insert(const T data){…………………………}bool erase(const K key){…………………………}
private:vectorNode* _table;//底层还封装一个大小n表示实际表中的数据个数size_t n 0;//用来计算负载因子
};
这样哈希表的迭代器就完成啦。不过这里还有一个问题喔确实封装哈希表确实比较恶心比封装红黑树还复杂。 这里的问题在于const修饰begin()和const修饰end()这里是编译不过的。为什么呢这里提醒没有构造函数可以接收或者构造函数重载不明确。 这里的原因是因为const修饰了this指针导致指向哈希表的指针变成const类型了而迭代器的构造里是用普通迭代器构造的。所以当this指针传过去构造时const是不能传给普通类型的权限放大了。所以这里我们只需要重载一个参数类型是const类型的哈希表指针即可。 HSIterator(Node* node, Hash_tableK, T, KeyOfT,Hashfunc* hs)//hs是普通的类型:_node(node), _pht(hs){}//当传过来的哈希表指针是普通指针就走上面--权限的缩小//重载一个当传过来的是const修饰的哈希表指针就走这里---权限的平移HSIterator(Node* node, const Hash_tableK, T, KeyOfT, Hashfunc* hs)//hs是普通的类型:_node(node), _pht(hs){}五.封装unordered_map和unordered_set的迭代器
只有哈希表里的迭代器完成了才可以封装map和set里的迭代器。 封装set的迭代器本质就是调用哈希表的迭代器接口。 1.不过要注意的是在重命名红黑树里的迭代器时需要在类名前面加上typename如果不加上typename是不行的因为这时类模板还没有实例化出对象出来就算实例化了也有部分类型没有实例因为编译器也不知道这个是内置类型还是静态变量加上是告诉编译器这个是类型这个类型在类模板里定义等类模板实例化后再找。 2.定义好普通迭代和const迭代器后就可以实现begin()和end()了。 namespace tao
{templateclass Kclass set{struct setoft{const K operator()(const K key){return key;}};public:typedef typename Hash_tableK, K, setoft::iterator iterator;typedef typename Hash_tableK, K, setoft::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}bool insert(const K key){return _ht.insert(key);}private://底层封装一个哈希表哈希表里存的是K类型Hash_tableK, K, setoft _ht;};
};
封装map的迭代器本质上就是调用哈希表里的迭代器接口。
#includeHash.h
namespace tao
{templateclass K, class Vclass map{struct mapoft{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename Hash_tableK, pairK, V, mapoft::iterator iterator;typedef typename Hash_tableK, pair K, V, mapoft::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}bool insert(const pairK, V kv){return _ht.insert(kv);}private://底层封装一个哈希表,哈希表里的数据是pairK,V类型Hash_tableK, pair K, V, mapoft _ht;};
};
六.解决key不能修改问题
set里面存储的Key值是不能被修改的map里的存储的K值也是不能被修改但是Value值是可以被修改 如果解决这个问题呢 问题set里的key值不能被修改。map里的key值不能被修改value值可以被修改。 set解决原理 1.set里存储的值就只有Key值索性我们直接让这个存储的数据无法被修改只能访问读取无法修改。即使用const修饰。而我们是通过迭代器来访问到这个数据的所以我们让普通迭代器变成const迭代器即可。所以在set里普通迭代器和const迭代器最终都是const迭代器。 2.那么迭代器都是const的了最终都只会调用const修饰的begin()和end()函数了普通的begin()和end()就不需要写了。 3.不过这样处理又会出现一个很难搞的问题这个就是set的insert的返回值问题我们后面要实现map的[]运算符重载就会讲到。 set的解决方法public:typedef typename Hash_tableK, K, setoft::const_iterator iterator;//为了解决set的key不能被修改所以我们让普通迭代器变成const迭代器typedef typename Hash_tableK, K, setoft::const_iterator const_iterator;//因为普通迭代器也是const所以我们只用写const的begin和end即可。iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}//这里的pairconst_iterator,bool类型的bool insert(const K key){//return _ht.insert(key);}private://底层封装一个哈希表哈希表里存的是K类型Hash_tableK, K, setoft _ht;};
}; map的解决原理 1.在存储的时候就让K值无法修改。 2.因为我们知道map里存储的数据是pairKV类型我们不能想set那个让普通迭代器变成const迭代器因为map要求Value的值还是可以修改的所以不让pairK,V类型无法修改而是单纯的让里面的K值无法修改也就是在里面用const修饰K那么这样K值就不能被修改V值可以被修改。 3.pair是可以修改的但是里面的K是无法被修改的 map的解决方法public:typedef typename Hash_tableK, pairconst K, V, mapoft::iterator iterator;typedef typename Hash_tableK, pairconst K, V, mapoft::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}bool insert(const pairK, V kv){return _ht.insert(kv);}private://底层封装一个哈希表,哈希表里的数据是pairK,V类型Hash_tableK, pairconst K, V, mapoft _ht;};
};
七.实现map[]运算符重载
map的[ ]运算符重载底层实现本质是调用了insert函数。然后通过insert函数返回的pairiterator,bool类型数据来找到Value值。
所以在实现[ ]运算符重载时我们需要对哈希表里的insert进行改造因为原来的insert的返回值是布尔值我们需要pair类型返回值。
pairiterator,bool insert(const T data){KeyOfT kt;Hashfunc hf;//仿函数可以使数据模//在插入之前确认一下表里是否已经有了这个值如果有了就不用插入了iterator it find(kt(data));if (it!end()){return make_pair(it,false);}if (n _table.size()){//异地扩容重新开空间size_t newSize _table.size() * 2;vectorNode* newtable;newtable.resize(newSize, nullptr);//不能再复用下面的方法这样不好因为就又重开空间然后又要释放//我们应该将原来的结点拿过来使用//所以我们遍历旧表将旧表的结点拿过来签到新表上for (size_t i 0; i _table.size(); i){//扩容后空间size变大了有的数据就可能会存到不同的桶里了//拿下来的结点要重新计算放进哪个位置Node* cur _table[i];//cur后面可能还有链接的结点while (cur){size_t hashi hf(kt(cur-_data)) % newtable.size();Node* next cur-_next;//头插到新表cur-_next newtable[hashi];//头插 这个结点的 接到插入结点的前面对吧//那么next就接到newtavle[i]newtable[hashi] cur;//往后走接着拿走cur next;}//当前桶里的结点被拿光后就置为空_table[i] nullptr;}//这个新表就是我们想要的表那么我们利用vector、的交换让旧表和新表交换_table.swap(newtable);}size_t hashi hf(kt(data)) % _table.size();Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;//将新结点头插到哈希桶里n;return make_pair(iterator(newnode,this),true);}iterator find(const K key){Hashfunc hf;KeyOfT kt;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kt(cur-_data) key)return iterator(cur,this);elsecur cur-_next;}return iterator(nullptr,this);}哈希表的insert改造后那么set和map里的insert都需要修改因为底层用的就是调用用哈希表的insert。 这样修改是对的吗有没有什么问题呢 但是这时会出现一个问题set里面的insert报错。这是为什么呢 问题在于我们之前让普通迭代变成const迭代器而这里的pairiterator,bool中的iterator其实本质上是const_iterator。 是pairconst_itearto,bool类型的。而哈希表里的insert返回的是普通迭代器也就是pairiterator,bool类型的。这是两个不同的类型无法直接将pairiterator,bool类型转换成pairconst_itearto,bool类型的。所以会报错。 · 解决方法 1.迭代器的拷贝函数是浅拷贝我们不需要写编译器自动生成的拷贝就可以用编译器自动生成的拷贝函数只能实现普通迭代器拷贝给普通迭代器const迭代器拷贝给const迭代器。(原理就是拷贝函数的对象类型就是调用这个函数的类型当普通迭代器调用拷贝时那么拷贝对象就是普通类型当const迭代器调用拷贝时那么拷贝对象就是const类型) 2.而我们需要的是让普通迭代器能够拷贝给const迭代器。所以我们需要自己增加拷贝函数。 3.库里的设计很妙库里重新定义了一个iterator作为拷贝对象而这个iterator固定了就是普通的迭代器不会随着调用对象而改变类型。所以当普通迭代器调用时就会将普通iterator拷贝给它。当const迭代器调用时就会将普通迭代器iterator拷贝给它。 4.所以我们需要对哈希表的迭代器添加拷贝构造。用普通迭代器iteartor作为拷贝对象。 struct HSIterator
{typedef HashNodeT Node;typedef HSIteratorK, T, T, T*, KeyOfT, Hashfunc iterator;typedef HSIteratorK, T,Ref,Ptr,KeyOfT, Hashfunc Self;Node* _node;const Hash_table K,T, KeyOfT,Hashfunc* _pht;//没有取这个类里面的内嵌类型就不需要加typenameHSIterator(Node* node, Hash_tableK, T, KeyOfT,Hashfunc* hs)//hs是普通的类型:_node(node), _pht(hs){}//当传过来的哈希表指针是普通指针就走上面--权限的缩小//重载一个当传过来的是const修饰的哈希表指针就走这里---权限的平移HSIterator(Node* node, const Hash_tableK, T, KeyOfT, Hashfunc* hs)//hs是普通的类型:_node(node), _pht(hs){}//普通的拷贝构造就是 const迭代器拷贝给const迭代器普通迭代器拷贝给普通迭代器//而我们写的拷贝构造可以同时支持两个当调用对象是普通迭代器时用普通迭代器拷贝也就是相当于赋值//当调用对象是const迭代器时也是用普通迭代器拷贝。这样就支持了普通迭代器转化成const迭代器了HSIterator(const iterator it):_node(it._node),_pht(it._pht){}……………………………………………………};
这样处理后我们再利用pairiterator,bool类型的构造函数将普通迭代器转换成const迭代器。 1.先将insert返回类型利用ret接收 2.利用pairiteartor,bool构造将ret里的普通迭代器转换为const迭代器。 pairiterator,bool insert(const K key){//return _ht.insert(key);//set调用的insert传回来的pairiteratorbool类型的pairiterator,bool与pairconst_iterator,bool是两个不同的类型//正常的的迭代器拷贝构造我们不需要写因为迭代器是指针拷贝构造就是浅拷贝编译器自动生成的拷贝就可以//但是这里我们需要自己写拷贝构造 因为需要将pairiteartor,bool类型转化成pairconst_iterator,bool类型,如何转化的呢pairtypename Hash_tableK, K, setoft::iterator, bool it _ht.insert(key);return pairiterator, bool(it.first, it.second);}最后insert的改造到这里就结束了insert改造完后就可以实现[ ]运算符重载了。
V operator[](const Kkey){pairiterator, bool ret _ht.insert(make_pair(key,V()));//插入的数据是pair类型要用make_pair构造return ret.first-second;}
