利用哈希表封装unordered_map和undered_set
我们之前已经实现了一个比较简单的哈希表，我们现在就是要用这个比较简单的哈希表封装一下，自己写一下undered_map和undered_set。如果还没有看过上一篇哈希表的同学，可以点击这里：
如果已经对哈希表比较熟悉的同学，那就接着看下去吧~
改造
我们set和map最主要的区别就是，set是单值，map是键值对。其他的基本上大差没差，我们现在想做的就是用我们这个哈希表封装，写一个自己的unordered_map和undered_set：
为了实现这个功能，我们用我们的哈希桶的版本改造，我们首先我们的一开始定义的链表结点有没有什么问题：
//哈希桶结点
template<class K,class V>
struct Hash_Node
{
//结点
Hash_Node* _next; //下一个结点
std::pair<K, V> _kv;
//构造函数
Hash_Node(const std::pair<K,V> kv)
:_next(nullptr)
,_kv(kv)
{
}
};
我们发现我们的数据直接就是写的pair，按照的是unordered_map的方式来写的，这样对于unordered_set不怎么友好，所以我们这里的pair改为泛型：
//哈希桶结点
template<class T>
struct Hash_Node
{
//结点
Hash_Node* _next; //下一个结点
T _data; //数据抽象
//构造函数
Hash_Node(const T& data)
:_next(nullptr)
,_data(data)
{
}
};
好了，我们现在已经将数据改为泛型，增加了代码的灵活性。但是有一个问题，unordered_map的数据是pair的键值对，unordered_set数据是一个数值，当数据传过来时，我这个底层的哈希桶该怎么分辨呢？
还记得我们之前的仿函数吗？我们创建我们自己的My_underoder_map的头文件：
#pragma once
#include"Hash_bucket.h"
namespace My_underoder_map
{
template<class K,class V>
class unodered_map
{
public:
struct MapOfT //提供识别map数据的方法
{
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
private:
Hash_buckets::HashTable<K, std::pair<K,V>,MapOfT> _ht; //数据类型为键值对
}
然后我们在底层的哈希桶的模板参数中增加一个识别数据的模板参数，这个参数会帮助我们识别传过来的数据是键值对，还是一个值：
template<class K, class T,class KeyOfT,class Hash = HashFuc<K>> //KeyOFT 帮助识别数据类型
这样我们之前写的代码，在需要用到数据的地方，需要先套一层KeyOFT的仿函数，判断数据类型，然后再进行操作：
#pragma once
#include<iostream>
#include<vector>
#include<string>
namespace Hash_buckets
{
//解决字符串转换
template<class K>
struct HashFuc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFuc<std::string>
{
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
//哈希桶结点
template<class T>
struct Hash_Node
{
//结点
Hash_Node* _next; //下一个结点
T _data; //数据抽象
//构造函数
Hash_Node(const T& data)
:_next(nullptr)
,_data(data)
{
}
};
template<class K, class T,class KeyOfT,class Hash = HashFuc<K>>
class HashTable
{
public:
typedef Hash_Node<T> _Node;
//构造函数
HashTable()
{
_tables.resize(10);
}
//析构函数
~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
_Node* cur = _tables[i];
while (cur)
{
_Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
bool Insert(const T& data)
{
Hash hf;
KeyOfT kot; //判断数据类型
if (Find(kot(data)))
return false;
//判断是否需要扩容
if (_n == _tables.size())
{
//新开的大小
size_t newSize = _tables.size() * 2;
HashTable<K,T,KeyOfT> newHT;
newHT._tables.resize(newSize);
//遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
_Node* cur = _tables[i];
while (cur)
{
newHT.Insert(cur->_data);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);
}
//插入
//哈希函数
size_t hashi = hf(kot(data)) % _tables.size();
_Node* newnode = new _Node(data);
//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n; // 个数加一
return true;
}
void ShowHash()
{
KeyOfT kot;
std::cout << "共有" << _tables.size() << "条链" << std::endl;
for (int i = 0; i < _tables.size(); i++)
{
_Node* cur = _tables[i];
while (cur)
{
std::cout << "第" << i << "链上的元素有" << kot(cur->_data) << std::endl;
cur = cur->_next;
}
std::cout << "######################" << std::endl;
}
}
_Node* Find(const K& key)
{
Hash hf;
KeyOfT kot;
//哈希函数
size_t hashi = hf(key) % _tables.size();
_Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
_Node* prve = nullptr;
_Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prve == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prve->_next = cur->_next;
}
delete cur;
}
prve = cur;
cur = cur->_next;
}
return false;
}
private:
//哈希表
std::vector <_Node*> _tables;
size_t _n = 0; //个数
};
}
然后我们简单写一个插入，测试一下我们的unordered_map：
#pragma once
#include"Hash_bucket.h"
namespace My_underoder_map
{
template<class K,class V>
class unodered_map
{
public:
struct MapOfT //提供识别map数据的方法
{
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
bool map_insert(const std::pair<K, V>& kv)
{
return _ht.Insert(kv);
}
void map_show()
{
_ht.ShowHash();
}
private:
Hash_buckets::HashTable<K, std::pair<K,V>,MapOfT> _ht;
};
void test_map()
{
unodered_map<std::string, std::string> dict;
std::string arr[] =
{
"香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
for (auto& e : arr)
{
dict.map_insert(std::make_pair(e, ""));
}
dict.map_show();
}
}
我们的unordered_set也是一样的操作：
#pragma once
#pragma once
#include"Hash_bucket.h"
namespace My_underoder_set
{
template<class K, class V>
class unodered_set
{
public:
struct SetOfT //提供识别map数据的方法
{
const K& operator()(const K& key)
{
return key;
}
};
bool set_insert(const K& key)
{
return _ht.Insert(key);
}
void set_show()
{
_ht.ShowHash();
}
private:
Hash_buckets::HashTable<K, K, SetOfT> _ht;
};
void test_set()
{
int a[] = {
1,22,4,21,56,777,89,6,23,13 };
unodered_set<int, int> _set;
for (auto e : a)
{
_set.set_insert(e);
}
_set.set_show();
}
}
迭代器
完成了上面的改造之后，我们得完成一下迭代器，我们先把壳子装好：
template<class K, class T, class KeyOfT, class Hash = HashFuc<K>>
struct __HTItreator
{
typedef Hash_Node<T> _Node;
typedef __HTItreator<K, T, KeyOfT, Hash> slef;
};
我们首先来实现++：
++
我们现在通过++，实现一个迭代器的迭代功能，问题是，该如何迭代呢？
我们可以把整个哈希表，看成一个瓜架，而哈希桶中的链表，我们看作瓜藤，我们现在要做的是一次性把瓜全部摘下来：
我们的做法是，一个藤一个藤的摘：
好了，我们现在0号藤上的瓜摘完了，现在的问题是，我该怎样跑到下一个有瓜的藤上呢？，毕竟我们这个是指针，不是人的手。
还记的我们之前的哈希函数吗？既然我们拿到这个瓜，我们就可以推算出我在几号藤上，算出来之后，加一，我就到下一根藤上了：
template<class K, class T, class KeyOfT, class Hash = HashFuc<K>>
struct __HTItreator
{
typedef Hash_Node<T> _Node;
typedef __HTItreator<K, T, KeyOfT, Hash> Self;
_Node* _node;
std::vector <_Node*>* _tables; //注意，这里是指针！
__HTItreator(_Node* node, std::vector <_Node*>* tables)
:_node(node)
,_tables(tables)
{
}
//++
Self& operator++()
{
if (_node->_next)
{
//当前瓜还没有摘完，走到下一个瓜
_node = _node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs((kot(_node->_data))) % _tables->size(); //根据当前的瓜的属性，推算我现在在几号藤上
++hashi; //往下一根藤上走
while (hashi < _tables->size())
{
if ((*_tables)[hashi]) //这个藤上有瓜
{
_node = (*_tables)[hashi];
break;
}
++hashi; //没瓜，往下一根藤上走
}
if (hashi == _tables->size())
{
_node = nullptr; //藤都走完了，结束
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
T& operator*()
{
return _node->_data;
}
};
namespace My_underoder_set
{
template<class K>
class unordered_set
{
public:
struct SetOfT //提供识别map数据的方法
{
const K& operator()(const K& key)
{
return key;
}
};
bool set_insert(const K& key)
{
return _ht.Insert(key);
}
void set_show()
{
_ht.ShowHash();
}
//迭代器
typedef typename Hash_buckets::HashTable<K, K, SetOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
Hash_buckets::HashTable<K, K, SetOfT> _ht;
};
我们可以测试一下：
void test_set_02()
{
// 17:05
unordered_set<int> us;
us.set_insert(5);
us.set_insert(15);
us.set_insert(52);
us.set_insert(3);
unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for (auto e : us)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
同样的，我们把unordered_map的迭代器封装好：
namespace My_underoder_map
{
template<class K,class V>
class unordered_map
{
public:
struct MapOfT //提供识别map数据的方法
{
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
//迭代器
typedef typename Hash_buckets::HashTable<K, std::pair<K, V>, MapOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool map_insert(const std::pair<K, V>& kv)
{
return _ht.Insert(kv);
}
void map_show()
{
_ht.ShowHash();
}
private:
Hash_buckets::HashTable<K, std::pair<K,V>,MapOfT> _ht;
};
我们也来测试一下：
void test_map()
{
unordered_map<std::string, int> dict;
std::string arr[] =
{
"香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
for (auto& e : arr)
{
dict.map_insert(std::make_pair(e, 1));
}
unordered_map<std::string, int>::iterator it = dict.begin();
for (auto e : dict)
{
std::cout << e.first << std::endl;
}
}
const 迭代器
我们封装了非const迭代器，我们来封装const迭代器，还是跟以前的一样的，首先增加Ref和Ptr两个模板参数：
template<class K, class T, class KeyOfT,class Ref, class Ptr, class Hash = HashFuc<K>>
struct __HTItreator
{
typedef Hash_Node<T> _Node;
typedef __HTItreator<K, T, KeyOfT,Ref,Ptr,Hash> Self;
_Node* _node;
const std::vector <_Node*>* _tables;
__HTItreator(_Node* node, const std::vector<_Node*>* tables)
:_node(node)
,_tables(tables)
{
}
//++
Self& operator++()
{
if (_node->_next)
{
//当前通还没有走完，走到下一个结点
_node = _node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs((kot(_node->_data))) % _tables->size();
++hashi;
while (hashi < _tables->size())
{
if ((*_tables)[hashi])
{
_node = (*_tables)[hashi];
break;
}
++hashi;
}
if (hashi == _tables->size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};
这里注意一下，我把std::vector <_Node*>* _tables改成了const的，一级构造函数里面的也改成了const 这样是为了在套用const迭代器是不会有权限放大的问题。
然后我们套上unordered_map：
template<class K,class V>
class unordered_map
{
public:
struct MapOfT //提供识别map数据的方法
{
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
//迭代器
typedef typename Hash_buckets::HashTable<K, std::pair<K, V>, MapOfT>::iterator iterator;
typedef typename Hash_buckets::HashTable<K, std::pair<K, V>, MapOfT>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
const_iterator begin() const
{
return _ht.const_begin();
}
iterator end()
{
return _ht.end();
}
const_iterator end() const
{
return _ht.const_end();
}
顺便套上unordered_set
namespace My_underoder_set
{
template<class K>
class unordered_set
{
public:
struct SetOfT //提供识别map数据的方法
{
const K& operator()(const K& key)
{
return key;
}
};
void set_show()
{
_ht.ShowHash();
}
//迭代器
typedef typename Hash_buckets::HashTable<K, K, SetOfT>::const_iterator iterator;
typedef typename Hash_buckets::HashTable<K, K, SetOfT>::const_iterator const_iterator;
std::pair<const_iterator, bool> set_insert(const K& key)
{
auto ret = _ht.Insert(key);
return std::pair<const_iterator,bool>(const_iterator(ret.first._node,ret.first._tables), ret.second);
}
//iterator begin()
//{
// return _ht.begin();
//}
const_iterator begin() const
{
return _ht.begin();
}
//iterator end()
//{
// return _ht.end();
//}
const_iterator end() const
{
return _ht.end();
}
因为set里面的元素插入后不能被修改，所以我们干脆只保留const的版本。
Insert 和 Find 改造
我们之前的insert返回时，返回的是bool值，我们把它改造的和库里的一样，改成返回值为：pair<iterator,bool>
std::pair<iterator,bool> Insert(const T& data)
{
Hash hf;
KeyOfT kot; //判断数据类型
iterator it = Find(kot(data));
if (it != end())
return std::make_pair(it, false);
//判断是否需要扩容
if (_n == _tables.size())
{
//新开的大小
size_t newSize = _tables.size() * 2;
HashTable<K,T,KeyOfT> newHT;
newHT._tables.resize(newSize);
//遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
_Node* cur = _tables[i];
while (cur)
{
newHT.Insert(cur->_data);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);
}
//插入
//哈希函数
size_t hashi = hf(kot(data)) % _tables.size();
_Node* newnode = new _Node(data);
//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n; // 个数加一
return std::make_pair(iterator(newnode, &this->_tables), true);
}
顺便也要把Find重新改造：
iterator Find(const K& key)
{
Hash hf;
KeyOfT kot;
//哈希函数
size_t hashi = hf(key) % _tables.size();
_Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,&this->_tables);
}
cur = cur->_next;
}
return end();
}
unordered_map实现统计次数
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
测试一下：
![[C++]类和对象(中)](https://img-blog.csdnimg.cn/direct/44f175102d294567b64350b56d8b2098.png)
