网站流量统计工具有哪些,哪家代运营公司比较好,中国住房城乡建设厅网站,官方模板关键字生成的代码添加在网站的什么地方?哈希表模拟实现unordered_set和unordered_map 一、定义哈希表的结点结构二、定义哈希表的迭代器三、定义哈希表的结构3.1 begin()和end()的实现3.2 默认成员函数的实现3.2.1 构造函数的实现3.2.2 拷贝构造函数的实现#xff08;深拷贝#xff09;3.2.3 赋值运算符重载函数的实… 哈希表模拟实现unordered_set和unordered_map 一、定义哈希表的结点结构二、定义哈希表的迭代器三、定义哈希表的结构3.1 begin()和end()的实现3.2 默认成员函数的实现3.2.1 构造函数的实现3.2.2 拷贝构造函数的实现深拷贝3.2.3 赋值运算符重载函数的实现现代写法3.2.4 析构函数的实现 四、实现哈希表的相关接口4.1 查找结点4.2 插入结点4.3 删除结点 五、针对除留余数法的取模问题六、unordered_set的模拟实现七、unordered_map的模拟实现八、完整代码8.1 HashTable.h8.2 UnorderedSet.h8.3 UnorderedMap.h8.4 test.cpp 一、定义哈希表的结点结构 这里直接拿自己写的开散列原先是KV模型改造下使其既可兼容K模型也可兼容KV模型 哈希表里面具体存的是什么类型的元素是由模板参数T来决定
如果是unordered_set传给T就是Key如果是unordered_map传给T的就是pairconst Key, V
哈希表结点结构 templateclass Tstruct HashNode{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr),_data(data){}};二、定义哈希表的迭代器
迭代器的结构 注意哈希表迭代器封装的是结点指针和哈希表指针因为要在哈希表中找下一个桶所以要用到哈希表指针
templateclass K, class T, class KeyOfT, class Hash class HashTable;templateclass K, class T,class Ref,class Ptr, class KeyOfT, class Hash struct __HashIterator{typedef HashNodeT Node;/*templateclass K, class T, class KeyOfT, class Hash HashFuncKclass HashTable*/typedef HashTableK, T, KeyOfT, Hash HT;typedef __HashIterator K, T,Ref,Ptr,KeyOfT, Hash Self;typedef __HashIterator K, T,T,T*,KeyOfT, Hash Iterator;Node* _node;const HT* _ht;
};在构造正向迭代器时我们不仅需要对应哈希结点的指针还需要该哈希结点所在哈希表的地址。
__HashIterator(Node* node,const HT* ht):_node(node),_ht(ht)
{}__HashIterator(const Iterator it):_node(it._node), _ht(it._ht)
{}当对正向迭代器进行解引用操作时我们直接返回对应结点数据的引用即可
Ref operator*()
{return _node-_data;
}当对正向迭代器进行-操作时我们直接返回对应结点数据的地址即可
Ptr operator-()
{return _node-_data;
}当我们需要比较两个迭代器是否相等时只需要判断这两个迭代器所封装的结点是否是同一个即可。
bool operator!(const Self s)
{return _node!s._node;
}运算符重载函数的实现逻辑并不是很难我们只需要知道如何找到当前结点的下一个结点即可。
若当前结点不是当前哈希桶中的最后一个结点则后走到当前哈希桶的下一个结点。若当前结点是当前哈希桶的最后一个结点则后走到下一个非空哈希桶的第一个结点。
Self operator(){if (_node-_next ! nullptr){_node _node-_next;}else{//找下一个不为空的桶KeyOfT kot;Hash hash;//算出我当前的桶位置size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}else{hashi;}}//没有找到不为空的桶if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}三、定义哈希表的结构 一个数组数组中存储着各个链表头结点的地址。 注意 这里有一个私有成员访问的问题我们在哈希表迭代器中封装了一个哈希表指针当一个桶遍历完成时用来在哈希表中找下一个桶但哈希表_tables是私有成员无法访问所以需要将迭代器类模板声明为友元 templateclass K,class T,class KeyOfT,class HashHashFuncKclass HashTable{templateclass K,class T,class Ref,class Ptr,class KeyOfT,class Hashfriend struct __HashIterator;typedef HashNodeT Node;public:typedef __HashIteratorK, T, T,T*,KeyOfT, Hash iterator;typedef __HashIteratorK, T, const T,const T*,KeyOfT, Hash const_iterator;private:vectorNode* _tables; //指针数组size_t _n0; //存储有效数据个数};3.1 begin()和end()的实现
注意this指针指向当前调用begin()成员函数的哈希表对象
begin函数返回哈希表中第一个非空哈希桶中的第一个结点的正向迭代器。end函数返回空指针的正向迭代器。
iterator begin(){Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}3.2 默认成员函数的实现
3.2.1 构造函数的实现 哈希表中有两个成员变量当我们实例化一个对象时
_table会自动调用vector的默认构造函数进行初始化_n会根据我们所给的缺省值被设置为0
vectorNode* _table; //哈希表
size_t _n 0; //哈希表中的有效元素个数因此我们不需要编写构造函数使用默认生成的构造函数就足够了但是由于我们后面需要编写拷贝构造函数编写了拷贝构造函数后默认的构造函数就不会生成了此时我们需要使用default关键字显示指定生成默认构造函数。
//构造函数
HashTable() default; //显示指定生成默认构造函数3.2.2 拷贝构造函数的实现深拷贝 哈希表在拷贝时需要进行深拷贝否则拷贝出来的哈希表和原哈希表中存储的都是同一批结点。 哈希表的拷贝函数实现逻辑如下
1.将哈希表的大小调整为ht._table的大小 2.将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中 3.更改哈希表当中的有效数据个数
//拷贝构造函数
HashTable(const HashTable ht)
{//1、将哈希表的大小调整为ht._table的大小_table.resize(ht._table.size());//2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中深拷贝for (size_t i 0; i ht._table.size(); i){if (ht._table[i]) //桶不为空{Node* cur ht._table[i];while (cur) //将该桶的结点取完为止{Node* copy new Node(cur-_data); //创建拷贝结点//将拷贝结点头插到当前桶copy-_next _table[i];_table[i] copy;cur cur-_next; //取下一个待拷贝结点}}}//3、更改哈希表当中的有效数据个数_n ht._n;
}3.2.3 赋值运算符重载函数的实现现代写法 实现赋值运算符重载函数时可以通过参数间接调用拷贝构造函数之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可当赋值运算符重载函数调用结束后拷贝构造出来的哈希表会因为出了作用域而被自动析构此时原哈希表之前的数据也就顺势被释放了。
//赋值运算符重载函数
HashTable operator(HashTable ht)
{//交换哈希表中两个成员变量的数据_table.swap(ht._table);swap(_n, ht._n);return *this; //支持连续赋值
}3.2.4 析构函数的实现 因为哈希表当中存储的结点都是new出来的因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要一次取出非空的哈希桶遍历哈希桶当中的结点并进行释放即可。
~HashTable(){for (auto cur : _tables){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}四、实现哈希表的相关接口
4.1 查找结点 查找结点接口中需要获取不同类型元素的关键码key因为元素间的比较是通过key值来比较的以及通过元素关键码key取模计算出哈希位置。 所以需要借助两个仿函数类 仿函数类KeyOfT获取不同类型的data中的关键码key值如果data是key就取key如果是pair就取first仿函数类Hash有些元素关键码key的类型不能直接取模需要将其转换成可以取模的size_t类型 iterator Find(const K key){if (_tables.size() 0)return end();KeyOfT kot;Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur,this);}cur cur-_next;}return end();}4.2 插入结点 插入结点接口中需要获取不同类型元素的关键码key因为元素间的比较是通过key值来比较的以及通过元素关键码key取模计算出哈希位置。 所以需要借助两个仿函数类 仿函数类KeyOfT获取不同类型的data中的关键码key值如果data是key就取key如果是pair就取first仿函数类Hash有些元素关键码key的类型不能直接取模需要将其转换成可以取模的size_t类型 函数的返回值为pairiterator,bool类型对象 目的是为了在unordered_set和unordered_map中模拟实现operator[]运算符重载函数 插入元素接口功能插入元素前会通过该元素的关键码key检查该元素是否已在哈希表中不允许冗余 如果在返回pair指向该元素的迭代器false如果不在先插入结点再返回pair指向该元素的迭代器true pair iterator, bool Insert(const T data){KeyOfT kot;iterator it Find(kot(data));if (it!end()){return make_pair(it,false);}Hash hash;//负载因子1时扩容if (_n _tables.size()){/*size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newht._tables);*/size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;vectorNode* newtables(newsize, nullptr);//for(Node* cur:_tables)for (auto cur : _tables){/*for (size_t i0;i_tables.size();i){Node* cur _tables[i];*/while (cur){Node* next cur-_next;size_t hashi hash(kot(cur-_data)) % newtables.size();//头插到新表cur-_next newtables[hashi];newtables[hashi] cur;cur next;}}_tables.swap(newtables);}size_t hashi hash(kot(data)) % _tables.size();//头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode,this),false);}4.3 删除结点 删除结点接口中需要获取不同类型元素的关键码key因为元素间的比较是通过key值来比较的以及通过元素关键码key取模计算出哈希位置。 所以需要借助两个仿函数类 仿函数类KeyOfT获取不同类型的data中的关键码key值如果data是key就取key如果是pair就取first仿函数类Hash有些元素关键码key的类型不能直接取模需要将其转换成可以取模的size_t类型 bool Erase(const K key){Hash hash;KeyOfT kot;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}五、针对除留余数法的取模问题 实现哈希表计算元素关键码对应哈希位置的哈希函数采用的是除留余数法需要传仿函数将不能取模的类型转换成可以取模的size_t类型。 这里给出针对普通类型取模和string类型取模的仿函数放到全局域中方便模拟unordered_set和unordered_map时使用。
templateclass Kstruct HashFunc{size_t operator()(const K key){return key;}};//特化templatestruct HashFuncstring{//BKDRsize_t operator()(const string s){//return s[0];size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}};六、unordered_set的模拟实现 实现unordered_set的各个接口时就只需要调用底层哈希表对应的接口就行了
#pragma once
#include HashTable.hnamespace set
{templateclass Kclass unordered_set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename HashBucket::HashTableK, K, SetKeyOfT::const_iterator iterator;typedef typename HashBucket::HashTableK, K, SetKeyOfT::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();}pair iterator, bool insert(const K key){return _ht.Insert(key);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, K, SetKeyOfT _ht;};void print(const unordered_setint s){unordered_setint::const_iterator it s.begin();while (it ! s.end()){//*it 1;cout *it ;it;}cout endl;}void test_unordered_set(){int a[] { 3,33,2,13,5,12,1002 };unordered_setint s;for (auto e : a){s.insert(e);}s.insert(103);unordered_setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;print(s);}
}七、unordered_map的模拟实现 实现unordered_map的各个接口时也是调用底层哈希表对应的接口就行了此外还需要实现[ ]运算符的重载
#pragma once
#include HashTable.hnamespace map
{templateclass K,class Vclass unordered_map{public:struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public:typedef typename HashBucket::HashTableK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename HashBucket::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();}pair iterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, pairconst K,V, MapKeyOfT _ht;};void test_unordered_map1(){unordered_mapint,int m;m.insert(make_pair(1,1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_mapint, int::iterator it m.begin();while (it ! m.end()){/*it-first 1;it-second 1;*/cout it-first : it-second endl;it;}cout endl;}void test_unordered_map2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };unordered_mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}}
}八、完整代码
8.1 HashTable.h
#pragma once
#include vectornamespace OpenAddress
{enum State{EMPTY,EXIST,DELETE};template class K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class Vclass HashTable{public:bool Insert(const pairK, V kv){if (Find(kv.first))return false;//负载因子超过0.7就扩容//if((double)_n/(double)_tables.size()0.7)//if (_tables.size()0 || _n * 10 / _tables.size() 7)//{// 1、表为空扩不上去// 2、光扩容无法访问size没变// //_tables.reserve(_tables.capacity() * 2); //不能这么做// size_t newsize _tables.size() 0 ? 10 : _tables.size()*2;// //_tables.resize(newsize); //有问题// vectorHashData newtables(newsize);// //遍历旧表重新映射到新表// for (auto data : _tables)// {// if (data._stateEXIST)// {// //重新算在新表的位置// size_t i 1;// size_t index hashi;// while (newtables[hashi]._state EXIST)// {// index hashi i;// index % newtables.size();// i;// }// newtables[index]._kv data._kv;// newtables[index]._state EXIST;// }// }// _tables.swap(newtables);if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V newht;newht._tables.resize(newsize);//遍历旧表重新映射到新表for (auto data : _tables){if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hashi kv.first % _tables.size();//线性探测size_t i 1;size_t index hashi;while (_tables[index]._state EXIST){index hashi i;index % _tables.size();i;}_tables[index]._kv kv;_tables[index]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){if (_tables.size() 0){return nullptr;}size_t hashi key % _tables.size();//线性探测size_t i 1;size_t index hashi;while (_tables[index]._state ! EMPTY){if (_tables[index]._state EXIST _tables[index]._kv.first key){return _tables[index];}index hashi i;index % _tables.size();i;//如果已经查找一圈那么说明全是存在删除if (index hashi){break;}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n 0; //存储的数据个数/*HashData* tables;size_t size;size_t _capacity;*/};void TestHashTable1(){int a[] { 3,33,2,13,5,12,1002 };HashTableint, int ht;for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));if (ht.Find(13)){cout 13在 endl;}else{cout 13不在 endl;}ht.Erase(13);if (ht.Find(13)){cout 13在 endl;}else{cout 13不在 endl;}}
}namespace HashBucket
{templateclass Tstruct HashNode{HashNodeT* _next;T _data;HashNode(const T data):_next(nullptr),_data(data){}};templateclass Kstruct HashFunc{size_t operator()(const K key){return key;}};//特化templatestruct HashFuncstring{//BKDRsize_t operator()(const string s){//return s[0];size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}};//前置声明templateclass K, class T, class KeyOfT, class Hash class HashTable;templateclass K, class T,class Ref,class Ptr, class KeyOfT, class Hash struct __HashIterator{typedef HashNodeT Node;/*templateclass K, class T, class KeyOfT, class Hash HashFuncKclass HashTable*/typedef HashTableK, T, KeyOfT, Hash HT;typedef __HashIterator K, T,Ref,Ptr,KeyOfT, Hash Self;typedef __HashIterator K, T,T,T*,KeyOfT, Hash Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node,const HT* ht):_node(node),_ht(ht){}__HashIterator(const Iterator it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node!s._node;}//itSelf operator(){if (_node-_next ! nullptr){_node _node-_next;}else{//找下一个不为空的桶KeyOfT kot;Hash hash;//算出我当前的桶位置size_t hashi hash(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()){if (_ht-_tables[hashi]){_node _ht-_tables[hashi];break;}else{hashi;}}//没有找到不为空的桶if (hashi _ht-_tables.size()){_node nullptr;}}return *this;}};templateclass K,class T,class KeyOfT,class HashHashFuncKclass HashTable{templateclass K,class T,class Ref,class Ptr,class KeyOfT,class Hashfriend struct __HashIterator;typedef HashNodeT Node;public:typedef __HashIteratorK, T, T,T*,KeyOfT, Hash iterator;typedef __HashIteratorK, T, const T,const T*,KeyOfT, Hash const_iterator;iterator begin(){Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur nullptr;for (size_t i 0; i _tables.size(); i){cur _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}~HashTable(){for (auto cur : _tables){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}iterator Find(const K key){if (_tables.size() 0)return end();KeyOfT kot;Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur,this);}cur cur-_next;}return end();}bool Erase(const K key){Hash hash;KeyOfT kot;size_t hashi hash(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}pair iterator, bool Insert(const T data){KeyOfT kot;iterator it Find(kot(data));if (it!end()){return make_pair(it,false);}Hash hash;//负载因子1时扩容if (_n _tables.size()){/*size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;HashTableK, V newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newht._tables);*/size_t newsize _tables.size() 0 ? 10 : _tables.size() * 2;vectorNode* newtables(newsize, nullptr);//for(Node* cur:_tables)for (auto cur : _tables){/*for (size_t i0;i_tables.size();i){Node* cur _tables[i];*/while (cur){Node* next cur-_next;size_t hashi hash(kot(cur-_data)) % newtables.size();//头插到新表cur-_next newtables[hashi];newtables[hashi] cur;cur next;}}_tables.swap(newtables);}size_t hashi hash(kot(data)) % _tables.size();//头插Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode,this),false);}size_t MaxBucketSize(){size_t max 0;for (size_t i0;i_tables.size();i){auto cur _tables[i];size_t size 0;while (cur){size;cur cur-_next;}printf([%d]-%d\n, i,size);if (size max){max size;}}return max;}private:vectorNode* _tables; //指针数组size_t _n0; //存储有效数据个数};//void TestHashTable1()//{// int a[] { 3,33,2,13,5,12,1002 };// HashTableint, int ht;// for (auto e : a)// {// ht.Insert(make_pair(e, e));// }// ht.Insert(make_pair(15, 15));// ht.Insert(make_pair(25, 25));// ht.Insert(make_pair(35, 35));// ht.Insert(make_pair(45, 45));//}//void TestHashTable2()//{// int a[] { 3,33,2,13,5,12,1002 };// HashTableint, int ht;// for (auto e : a)// {// ht.Insert(make_pair(e, e));// }// ht.Erase(12);// ht.Erase(3);// ht.Erase(33);//}//struct HashStr//{// //BKDR// size_t operator()(const string s)// {// //return s[0];// size_t hash 0;// for (auto ch : s)// {// hash ch;// hash * 31;// }// return hash;// }//};//void TestHashTable3()//{// //HashTablestring, string, HashStr ht;// HashTablestring, string ht;// ht.Insert(make_pair(sort, 排序));// ht.Insert(make_pair(string, 字符串));// ht.Insert(make_pair(left, 左边));// ht.Insert(make_pair(right, 右边));// ht.Insert(make_pair(, 右边));// HashStr hashstr;// cout hashstr(abcd) endl;// cout hashstr(bcda) endl;// cout hashstr(aadd) endl;// cout hashstr(eat) endl;// cout hashstr(ate) endl;//}//void TestHashTable4()//{// size_t N 10000;// HashTableint, int ht;// srand(time(0));// for (size_t i 0; i N; i)// {// size_t x rand();// ht.Insert(make_pair(x, x));// }// cout ht.MaxBucketSize() endl;//}增删改查的时间复杂度O11.负载因子控制1.单个桶超过一定长度这个桶改成挂红黑树}8.2 UnorderedSet.h
#pragma once
#include HashTable.hnamespace set
{templateclass Kclass unordered_set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename HashBucket::HashTableK, K, SetKeyOfT::const_iterator iterator;typedef typename HashBucket::HashTableK, K, SetKeyOfT::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();}pair iterator, bool insert(const K key){return _ht.Insert(key);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, K, SetKeyOfT _ht;};void print(const unordered_setint s){unordered_setint::const_iterator it s.begin();while (it ! s.end()){//*it 1;cout *it ;it;}cout endl;}void test_unordered_set(){int a[] { 3,33,2,13,5,12,1002 };unordered_setint s;for (auto e : a){s.insert(e);}s.insert(103);unordered_setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;print(s);}
}8.3 UnorderedMap.h
#pragma once
#include HashTable.hnamespace map
{templateclass K,class Vclass unordered_map{public:struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public:typedef typename HashBucket::HashTableK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename HashBucket::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();}pair iterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:HashBucket::HashTableK, pairconst K,V, MapKeyOfT _ht;};void test_unordered_map1(){unordered_mapint,int m;m.insert(make_pair(1,1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_mapint, int::iterator it m.begin();while (it ! m.end()){/*it-first 1;it-second 1;*/cout it-first : it-second endl;it;}cout endl;}void test_unordered_map2(){string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };unordered_mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}}
}8.4 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include iostream
#includeunordered_set
#includeunordered_map
#includestring
using namespace std;#include UnorderedMap.h
#include UnorderedSet.hint main()
{//set::test_unordered_set();map::test_unordered_map1();return 0;
}
