数据分析案例网站,商品网站模板,分类目录采用的是什么编目,百度网站app下载本期我们来封装实现unordered系列#xff0c;需要前置知识#xff0c;没有看过哈希的建议先看看哈希#xff0c;而且哈希的代码都在这里面#xff0c;一会要用到 C-哈希Hash-CSDN博客 目录
代码实现
迭代器
const迭代器
全部代码 代码实现 首先我们要把V改为T#xff…本期我们来封装实现unordered系列需要前置知识没有看过哈希的建议先看看哈希而且哈希的代码都在这里面一会要用到 C-哈希Hash-CSDN博客 目录
代码实现
迭代器
const迭代器
全部代码 代码实现 首先我们要把V改为T因为我们不知道他是k结构还是kv结构
//unordered_set.h
namespace bai {templateclass Kclass unordered_set{private:hash_bucket::HashTableK, K _ht;};
}namespace bai {templateclass K,class Vclass unordered_map{private:hash_bucket::HashTableK,pairK,V _ht;};
}然后我们把框架搭好 我们对照着看一下如果是set这里就是keydata就是key如果是map这里就是pairdata就是pair 接下来还要修改insertfind等等这里就因为不知道是pair还是k的原因所以我们需要再次来写KeyOfT struct SetKeyOfT{const K operator()(const K key){return key;}};struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}}; 写完后别忘记加上
bool Insert(const T data){KeyOfT kot;if (Find(kot(data))){return false;}HashFunc hf;//负载因子到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){Node* cur _table[i];while (cur){Node* next cur-_next;//头插到新表size_t hashi hf(kot(cur-_data)) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kot(data)) % _table.size();//头插Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}Node* Find(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return cur;}cur cur-_next;}return nullptr;}bool Erase(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){//头删_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}cur cur-_next;}}
接着我们要修改insertfind和erase的代码下面我们来看看修改了哪里我们按顺序看 大概就是这些地方具体的还要看上面的代码 我们简单测试一下没有问题下面我们来封装迭代器
迭代器 要实现迭代器我们要想想当前桶走完了如何到下一个桶呢也就是2号位的桶完了后如何到6号位
templateclass Tstruct HTiterator{typedef HashNodeT Node;Node* _node;HTiterator(Node* node):_node(node){}operator(){if (_node-_next){_node _node-next;}else{}}};
我们先把框架写好我们来看operator如果当前桶没有走完就让他到下一个位置即可
如果我们知道当前位置是几号桶可以解决吗也不行因为我们还需要哈希表的对象大家想一想他的底层是一个指针数组每一个指针又指向一个单链表我们现在是需要在指针数组里移动 templateclass K, class T, class KeyOfT, class HashFuncstruct HTiterator{typedef HashNodeT Node;typedef HTiteratorK, T, KeyOfT, HashFunc Self;Node* _node;HashTableK, T, KeyOfT, HashFunc* _pht;HTiterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht):_node(node),_pht(pht){}Self operator(){if (_node-_next){//当前桶还没完_node _node-_next;}else{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_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;}};
所以我们需要把整个哈希表传过来传一个pht的指针而且这里和之前一样不一定是可以直接取模需要再套一层hashfunc此时我们就可以计算出当前是第几个桶
接着我们开始找下一个不为空的桶我们先对hashi从下一个位置开始寻找如果当前桶不为空我们就break否则hashi循环结束后是有两种情况的一种是可以找到我们要让it指向下一个桶另一种是我们已经找完了整个表已经走到结尾了我们让nullptr充当end的位置 另外这里可能会有人有疑问为什么这里没有加typename 只有不能区分静态变量和类型时才需要加 T operator*(){return _node-_data;}T* operator-(){return _node-_data;} bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
我们顺手再把这几个也写一下 typedef HTiteratorK, T, KeyOfT, HashFunc iterator;iterator begin(){//找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return iterator(cur,this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}
接着我们在HashTable里加上begin和end我们构造迭代器时第一个传cur找不到传nullptr第二个传this即可this就是哈希表的指针
下面我们再套一层在unordered里封装一层 注意这里就需要加typename了我们之前封装map和set时也是一样的 下面我们要开始解决各种问题了
这里是一个相互依赖的问题 首先我们在哈希表里调用迭代器 迭代器在前没有问题 但是我们在迭代器里又用了哈希表这里谁在前谁在后都不行不过还好这里用的是哈希表的指针如果是对象就不好解决了 这里我们就要用到前置声明了告诉编译器哈希表我们是有定义的只不过可能在后面先不要着急 此时问题就解决了 我们调用一下迭代器再次编译出现了这样的错误我们仔细看可以发现这里是私有的问题 这里在类外边是不能访问私有的 所以这里可以写一个gettable或者使用友元 是迭代器要访问哈希表所以迭代器是哈希表的友元类模板的友元需要带上模板参数 此时我们的迭代器就可以跑起来了 接下来我们需要解决可以修改的问题也就是要实现const迭代器了
const迭代器 和之前一样要实现const迭代器我们需要传T*和T 于是我们修改迭代器的模板参数和self operator*和箭头的返回参数也要修改 友元声明也需要修改 const_iterator begin() const{//找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return const_iterator(cur, this);}}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}
然后要在HashTable里加上begin和end 接着我们对外层的set封装无论是iterator还是const_iterator它们其实都是const_iterator而且只提供了const版本的begin和end和库里面是一样的这里的begin和end的返回值无论是const_iterator还是iterator都是可以的因为普通对象是可以调用const成员函数的 此时我们的第一个问题就解决了 接着我们编译发现这里编译不通过不仅仅是这里上面也是编译不通过的这里报错是无构造函数可以接受源类型 我们来看这里的const修饰的谁
修饰的是*this 所以这里this的类型应该是这样的 我们画出来就是这样的这里权限放大是传不过去的 我们之前写的const迭代器没有遇到这样的问题因为以前的const迭代器是不需要传哈希表的而只需要传一个节点的指针过去即可 我们来看这种方法我们重载了一个构造函数并且直接把_pht改为了const 对于原来的构造函数pht是const变为非const是权限的缩小
那此时我们不要第一个构造只要第二个可以吗
也是可以的普通迭代器传过来只有const权限缩小 我们来看库里面是怎么解决的首先是普通的迭代器 这里有一个 库里面写了两个迭代器用两个迭代器类来实现 这里还都写成const了相当于单独写了一个类来解决
我们的方法和库里面的方法这两种方法都可以解决 map的话和以前一样改为const K 修改这些地方 这样就解决了 下面我们来修改返回值 先修改一下find的返回值 然后是insert的 然后我们把map和set封装的insert也改一下然后就是set这里的问题了 这里看起来是这样的 但是我们看这里 但是它们是不同区域的代码 set不允许修改key所以选择用const迭代器替代普通迭代器
所以这里的两个pair是不一样的pair是一个类模板实例化为两个不一样的类是不一样的类型 也就是说上面的pair是这样的所以会报错
map为什么没报错 因为map的iterator就是iterator
注意set这里的问题和权限缩小之类无关只有指针和引用才有权限缩小的概念这里是类模板实例化不同的模板参数导致它们是不同的类型 我们之前在封装map和set就讲过了这是库里面list的实现办法不太清楚的各位可以去我往期的map和set实现里再看一看我把链接放在下面 map和set模拟实现-CSDN博客 下面这个圈主的函数如果是普通迭代器这里就是拷贝构造是const迭代器时是构造函数是支持普通迭代器转换成const迭代器的构造这是一个有双重意义的函数 我们来用这个举例子我们想用aa1构造aa3 我们要加这样一个构造但是这里报错了一个私有 原因是上面这里是ATRef 这里是ATT
当这里Ref也是T时是同一个类当Ref是const时就不是同一个类了 我们看为什么库里面不报错呢 因为库里面是struct 我们去掉private就好了这些都是细节大家需要注意
现在回到我们的哈希表里 我们也加上这样一个构造
接着我们再次编译发现了几个错误 首先是我们把这里改为it这里之前是写错了 然后是find返回时不能返回nullptr这里返回end()接着编译就可以通过了
我们上次在这里写的和这里是不一样的 这里我们是先接收pair再用pair去调用它的构造
这样写是没问题的这里相当于把两个参数提取了出来单独调用pair构造这里的ret.first是一个普通迭代器在pair的初始化列表里初始化列表对自定义类型会调用构造 而这里屏蔽的我们之前写的是编译器的不严格检查如果检查的严格一点是不通过的 首先这里调用pair的构造
我们上面的aint和aconst int都不是同一个类型这里也是一样的 所以我们把iterator取出来 然后直接调用它的构造就会走它的初始化列表初始化列表对于自定义类型就会调用它的构造 虽然这里两种方法都可以编译通过但是我们还是建议使用方法2不然换一个编译器可能就不通过了 此时我们的问题就解决了 我们上面那么多事情都是因为它
insert要返回pair就引发了普通迭代器转换const迭代器的问题为什么insert要返回pair呢
因为我们要实现operator[ ] 这里都是相关联的 V operator[](const K key){pairiterator,bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}
为什么我们这里接收时可以用iterator 因为map的iterator就是iterator和set不一样 此时我们就可以使用[ ] 了和库里面一样
全部代码
#includeHash.h
//unordered_set.h
namespace bai {templateclass Kclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename hash_bucket::HashTableK, K, SetKeyOfT::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, SetKeyOfT::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pairconst_iterator, bool insert(const K key){//return _ht.Insert(key);pairtypename hash_bucket::HashTableK, K, SetKeyOfT::iterator, bool ret _ht.Insert(key);return pairconst_iterator, bool(ret.first, ret.second);}private:hash_bucket::HashTableK, K, SetKeyOfT _ht;};
}
#includeHash.h
//unordered_map.h
namespace bai {templateclass K,class Vclass unordered_map{struct MapKeyOfT{const K operator()(const pairconst K,V kv){return kv.first;}};public:typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pairiterator,bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator,bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}private:hash_bucket::HashTableK, pairconst K,V, MapKeyOfT _ht;};
}#pragma once
#includevector
#includeiostream
using namespace std;
//Hash.h
templateclass K
struct DefaultHashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct DefaultHashFuncstring
{size_t operator()(const string str){//BKDRsize_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};namespace open_address {enum STATE //状态{EXIST,EMPTY,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;STATE _state EMPTY;};//struct stringHashFunc//{// size_t operator()(const string str)// {// return str[0];// }//};templateclass K, class V, class HashFunc DefaultHashFuncKclass HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pairK, V kv){if(Find(kv.first)){return false;}//扩容//if ((double)_n / _table.size() 0.7)if (_n * 10 / _table.size() 7){size_t newSize _table.size() * 2;//重新映射HashTableK, V, HashFunc newHT;newHT._table.resize(newSize);for (size_t i 0; i _table.size(); i){if (_table[i]._state EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}//线性探测HashFunc hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._state EXIST){hashi;hashi % _table.size();//防止越界这样可以回到数组开头}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}HashDataconst K, V* Find(const K key){//线性探测HashFunc hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return (HashDataconst K, V*) _table[hashi];}hashi;hashi % _table.size();}return nullptr;}bool Erase(const K key){HashDataconst K, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}return false;}private:vectorHashDataK, V _table;size_t _n; //存储有效数据的个数};
}namespace hash_bucket
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data),_next(nullptr){}};//前置声明templateclass K, class T,class KeyOfT, class HashFuncclass HashTable;templateclass K, class T, class Ptr, class Ref,class KeyOfT, class HashFuncstruct HTiterator{typedef HashNodeT Node;typedef HTiteratorK, T, Ptr, Ref, KeyOfT, HashFunc Self;typedef HTiteratorK, T, T*, T, KeyOfT, HashFunc Iterator;Node* _node;const HashTableK, T, KeyOfT, HashFunc* _pht;/*HTiterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht):_node(node),_pht(pht){}*/HTiterator(Node* node,const HashTableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}//普通迭代器时是拷贝构造//cosnt迭代器时是构造HTiterator(const Iterator it):_node(it._node), _pht(it._pht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){if (_node-_next){//当前桶还没完_node _node-_next;}else{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_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;}bool operator(const Self s){return _node s._node;}};//set - hash_bucket::HashTableK, K _ht;//map - hash_bucket::HashTableK, pairK,V _ht;templateclass K,class T,class KeyOfT, class HashFunc DefaultHashFuncKclass HashTable{typedef HashNodeT Node;//友元声明templateclass K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc friend struct HTiterator;public:typedef HTiteratorK, T,T*,T, KeyOfT, HashFunc iterator;typedef HTiteratorK, T,const T*,const T, KeyOfT, HashFunc const_iterator;iterator begin(){//找第一个桶for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return iterator(cur,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];if (cur){return const_iterator(cur, this);}}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}HashTable(){_table.resize(10,nullptr);}~HashTable(){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;}}pairiterator,bool Insert(const T data){KeyOfT kot;iterator it Find(kot(data));if (it!end()){return make_pair(it,false);}HashFunc hf;//负载因子到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){Node* cur _table[i];while (cur){Node* next cur-_next;//头插到新表size_t hashi hf(kot(cur-_data)) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kot(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 kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur,this);}cur cur-_next;}return end();}bool Erase(const K key){HashFunc hf;KeyOfT kot;size_t hashi hf(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){//头删_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}prev cur;cur cur-_next;}--_n;return false;}void Print(){for (size_t i 0; i _table.size(); i){printf([%d]-, i);Node* cur _table[i];while (cur){cout cur-_kv.first : cur-_kv.second -;cur cur-_next;}printf(NULL\n);}cout endl;}private:vectorNode* _table; //指针数组size_t _n 0; //有效数据};
}
以上即为本期全部内容希望大家可以有所收获
如有错误还请指正
