- 在学习这个之前,已经学习过,myunordered_map和myunordered_set的基本用法和哈希表怎么用哈希思想模拟实现;因此为了更深入的了解myunordered_map和myunordered_set与哈希表的内容,我们来自己用哈希表模拟实现myunordered_map和myunordered_set;
- 这种模拟实现和之前模拟实现map与set基本无异;细节主意点都一样,也就是底层实现不一样,myunordered 用的是哈希表;map set用的是红黑树;
- 这里建议如果没有了解过myunordered_map和myunordered_set的基本用法可以去相关网站去简单了解一下,如此可以更好理解;
如果对模拟实现map与set 不了解或者忘了的,可以在复习一下(我之前的博客就有)因为这两种方法基本一样,这里的细节可能说的不全;
源码及框架分析
- SGI-STL30版本源代码中没有unordered_map和unordered_set,SGI-STL30版本是C++11之前的STL版本,这两个容器是C++11之后才更新的。
- 但是SGI-STL30实现了哈希表,只容器的名字是hash_map和hash_set,他是作为非标准的容器出现的,非标准是指非C++标准规定必须实现的。
- 虽然不是标准的unordered_map和unordered_set;但对于我这种新学者了解如何实现封装unordered_map和unordered_set已经足够了;
- 源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中(如果需要可以私信我要哦)
以下是我截取的个人认为比较重要的架构
- 通过源码可以看到,结构上hash_map和hash_set跟map和set的完全类似,复用同⼀个hashtable实现key和key/value结构,hash_set传给hash_table的是两个key,hash_map传给hash_table的是pair<const key, value>
- 需要注意的是源码里面跟map/set源码类似,命名风格比较乱,这里比map和set还乱,hash_set模板参数居然用的Value命名,hash_map用的是Key和T命名,可见大佬有时写代码也不规范,乱弹琴。下面模拟⼀份自己的出来,就按自己的风格走。
通过上面的框架我们可以发现,这与mapset,list的封装基本一样,也就底层不一样;
模拟实现unordered_map和unordered_set
实现步骤:
- 实现哈希表(这里的例子解决哈希冲突利用的哈希桶的方法)
- 封装unordered_map和unordered_set的框架 解决KeyOfT
- iterator
- const_iterator
- key不支持修改的问题
- operator[]
实现出复用哈希表的框架,并支持insert
- 参考源码框架,unordered_map和unordered_set复用之前我们实现的哈希表。
- 我们这里相比源码调整⼀下,key参数就⽤K,value参数就用V,哈希表中的数据类型,我们使用V。
- 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点,但是大框架和思路是完全类似的。
因为HashTable实现了泛型不知道T参数导致是K,还是pair<K, V>那么insert内部进行插入时要用K对象转换成整形取模和K比较相等,因为pair的value不参与计算取模,且默认支持的是key和value⼀起比较相等,我们需要时的任何时候只需要比较K对象;
- 所以在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT,然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象,再转换成整形取模和K比较相等
简单来说就是 传一个KeyOfT转化为key类型,然后再用哈希函数比较。
泛型就是这种,是什么类型的值,全靠传什么:
支持iterator的实现
iterator核心源代码
整理过后的
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> struct __hashtable_iterator { typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable; typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator; typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator; typedef __hashtable_node<Value> node; typedef forward_iterator_tag iterator_category; typedef Value value_type; node* cur; hashtable* ht; __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {} __hashtable_iterator() {} reference operator*() const { return cur->val; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ iterator& operator++(); iterator operator++(int); bool operator==(const iterator& it) const { return cur == it.cur; } bool operator!=(const iterator& it) const { return cur != it.cur; } }; template <class V, class K, class HF, class ExK, class EqK, class A> __hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++() { const node* old = cur; cur = cur->next; if (!cur) { size_type bucket = ht->bkt_num(old->val); while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket]; } r eturn* this; }
可以发现,SGI是用了两个模板分别实现iterator const iterator;但是这样太挫了,明明可以一给模板就实现为什么要用两个呢?(参考list sep和map的封装)
iterator实现思路分析
- iterator实现的大框架跟list的iterator思路是一致的,用一个类型封装结点的指针,再通过重载运算符实现,迭代器像指针一样访问的行为,要注意的是哈希表的迭代器是单向迭代器。
- 这里的难点是operator++的实现。
- iterator中有一个指向结点的指针,如果当前桶下面还有结点,则结点的指针指向下一个结点即可。
- 如果当前桶⾛完了,则需要想办法计算找到下⼀个桶。
这⾥的难点是结构设计的问题,参考上面的源码,我们可以看到iterator中成员函数除了有结点的指针,还有哈希表对象的指针,这样当前桶走完了,要计算下⼀个桶就相对容易多了(加哈希表对象指针的主要目的),用key值计算出当前桶位置,依次往后找下⼀个不为空的桶即可。
- begin()返回第一个桶中第一个节点指针构造的迭代器,这里end()返回迭代器可以用空表示。
- 需要注意的一些细节
- unordered_set的iterator也不⽀持修改,我们把unordered_set的第二个模板参数改成const K即可, HashTable<K, const K, SetKeyOfT, Hash> _ht;
- nordered_map的iterator不支持修改key但是可以修改value,我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可, HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;
- 支持完整的迭代器还有很多细节需要修改,具体参考下面的代码
map支持[]
- unordered_map要支持[]主要需要修改insert返回值支持,修改HashTable中的insert返回值为pair<Iterator, bool> Insert(const T& data)
- 有了insert支持持[]实现就很简单了,具体参考下面代码实现
毕竟库里的map[]就是通过insert返回值pair<Iterator, bool> ret,然后返回 ret->first.second 实现 查,修,改的;
注意事项:
- unordered_set的iterator也不⽀持修改,我们把unordered_set的第二个模板参数改成const K即可, HashTable<K, const K, SetKeyOfT, Hash> _ht;
- nordered_map的iterator不支持修改key但是可以修改value,我们把unordered_map的第二个
模板参数pair的第一个参数改成const K即可, HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;
-
迭代器模板中,哈希表的类型要加HT,如:const HT* _ht;
因此迭起器的哈希表成员函数也是const类型的,权限只能缩小,不能放大;
- unordered_set的iterator也不⽀持修改,我们把unordered_set的第二个模板参数改成const K即可, HashTable<K, const K, SetKeyOfT, Hash> _ht;
- 相互依赖型模板;struct HTIterator 模板中调用了class HashTable, class HashTable 也调用了 struct HTIterator;因此,必须加一个前置声明,放在第一个模板前面才能正常调用;
- 同时有源模板有些特殊,需要注意一下
xyrq::unordered_map和xryq::unordered_set代码实现
unordered_map.h
#pragma once
#include"haxi.h"
namespace xryq {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
struct VauleofK
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
//为什么不直接用 Iterator类
typedef typename HashTable<K, pair<const K, V>, VauleofK, Hash>::Iterator iterator;
typedef typename HashTable<K, pair<const K, V>, VauleofK, Hash>::ConstIterator const_iterator;
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
const_iterator begin() const
{
return _ht.Begin();
}
const_iterator end() const
{
return _ht.End();
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
//保证第一个元素不能改变
HashTable<K, pair<const K, V>, VauleofK, Hash> _ht;
};
void test_map1()
{
xryq::unordered_map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "字符串", "string" });
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
//dict["left"] = "左边,剩余";
//dict["insert"] = "插入";
//dict["string"];
//for (auto& kv : dict)
//{
// cout << kv.first << ":" << kv.second << endl;
//}
//cout << endl;
//unordered_map<string, string>::iterator it = dict.begin();
//while (it != dict.end())
//{
// // 不能修改first,可以修改second
// //it->first += 'x';
// it->second += 'x';
// cout << it->first << ":" << it->second << endl;
// ++it;
//}
//cout << endl;
}
}
unordered_set.h
#pragma once
#include"haxi.h"
namespace xryq {
template<class K>
class unordered_set {
struct VauleofK
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _ht.Insert(key);
}
private:
HashTable<K, K, VauleofK, Hash> _ht;
};
void test_set1()
{
int a[] = { 3,11,86,7,88,82,1,881,5,6,7,6 };
unordered_set<int> s;
//for (auto e : a)
//{
// s.insert(e);
//}
//unordered_set<int>::iterator it = s.begin();
//while (it != s.end())
//{
// //*it = 1;
// cout << *it << " ";
// ++it;
//}
//cout << endl;
//for (auto e : s)
//{
// cout << e << " ";
//}
//cout << endl;
//print(s);
}
}
hash.h
#pragma once
#include<string>
#include<vector>
using namespace std;
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct HashData
{
public:
T _t;
HashData* next;
HashData(const T& t)
:_t(t)
, next(nullptr)
{}
};
template<class K>
struct HashFunc {
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//如果不想每次实现都自己传,可以利用全特化,将其设置为默认模板
//以string 为例子
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t num = 0;
for (auto ch : s)
{
num += ch;
//为什么要乘 131
//这涉及到BKDR-哈希表算法
//这可以最大程度避免冲突的情况,具体如何实现可以上网搜索
num *= 131;
}
return num;
}
};
//相互依赖型的类,hashtable typedef了iterator
//iterator typedef了 hashtable
//需要前置声明,才能使用
template<class K, class V, class KvofK, class Hash>
class HashTable;
template<class K, class V, class Ref, class Ptr, class KvofK, class Hash>
struct HTIterator {
typedef HashData<V> Node;
typedef HashTable<K, V, KvofK, Hash> HT;
typedef HTIterator<K, V, Ref, Ptr, KvofK, Hash> Self;
// typedef HTIterator<K, T, Ref, Ptr, KvofK, Hash> Self;
Node* _node;
const HT* _ht;
HTIterator(Node* node,const HT* ht)
:_node(node)
,_ht(ht)
{}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Ref operator*()
{
return _node->_t;
}
Ptr operator->()
{
return &(_node->_t);
}
Self& operator++()
{
if (_node->next)
{
_node = _node->next;
}
else
{
Hash hash;
KvofK kofv;
size_t hash0 = hash(kofv(_node->_t)) % _ht->_tables.size();
size_t i = 1;
size_t hashi = hash0 + i;
//不能这样写,因为,node本身 不是nullptr
//如果要写,需要嘉善下面的;
// _node = _node->next;
//while (!_node && hashi < _ht->_tables.size())
//{
// _node = _ht->_tables[hashi];
// i++;
// hashi = hash0 + i;
//}
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];
if (_node)
break;
else
{
i++;
hashi = hash0 + i;
}
}
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
template<class K, class V, class KvofK ,class Hash>
class HashTable
{
//相互依赖型的类,hashtable typedef了iterator
//iterator typedef了 hashtable
//同时友元模板有些特殊,需要注意一下
template<class K, class V, class Ref, class Ptr, class KvofK, class Hash>
friend struct HTIterator;
public:
typedef HashData<V> Node;
typedef HTIterator<K, V, V&, V*, KvofK, Hash> Iterator;
typedef HTIterator<K, const V, const V&, V*, KvofK, Hash> ConstIterator;
Iterator Begin()
{
if (_n == 0)
return End();
//size_t hash0 = hash(kofv(cur->_t)) & _ht._tables.size();
//size_t hashi = hash0;
//size_t i = 1;
//Node* cur = _tables[hashi];
//while (!cur && hashi < _tables.size())
//{
// i++;
// hashi = hash0 + i;
// cur = _tables[hashi];
//}
//if (hashi == _tables.size())
//{
// rerurn iterator(nullptr, this);
//}
//return iterator(cur, this);
//注意,有容量大小,就可以考虑不用 while 不用自身指针,用for
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
if (_n == 0)
return End();
//注意,有容量大小,就可以考虑不用 while 不用自身指针,用for
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(0))
//:_tables(11)
, _n(0)
{}
pair<Iterator, bool> Insert(const V& key)
{
// 负载因子 == 1时扩容
//
// 这种没必要,有多少节点还有删多少节点,复制多少节点;效率很低;
// 而且vector的默认析构函数还不能将 节点上的全部节点都删掉;还有自己实现
//if (_n == _tables.size())
//{
// HashTable newtb;
// newtb._tables.resize(__stl_next_prime(_tables.size() + 1));
// for (size_t i = 0; i < _tables.size(); i++)
// {
// Node* cur = _tables[i];
// while (cur)
// {
// newtb.Insert(cur->_kv);
// cur = cur->next;
// }
// }
// _tables.swap(newtb._tables);
//}
KvofK kofv;
Iterator it = Find(kofv(key));
if (it != End())
return { it, false };
Hash hash;
//负载因子 == 1时扩容
if (_n == _tables.size())
{
vector<Node*> newtb;
newtb.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->next;
size_t hhash0 = hash(kofv(cur->_t)) % newtb.size();
//头插
cur->next = newtb[hhash0];
newtb[hhash0] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtb);
}
size_t hash0 = hash(kofv(key)) % _tables.size();
//头插
Node* newnode = new Node(key);
newnode->next = _tables[hash0];
_tables[hash0] = newnode;
_n++;
return { Iterator(newnode, this), true };
}
Iterator Find(const K& key)
{
Hash hash;
KvofK kofv;
size_t hash0 = hash(key) % _tables.size();
Node* cur = _tables[hash0];
while (cur)
{
if (kofv(cur->_t) == key)
{
return Iterator(cur, this);
}
else
{
cur = cur->next;
}
}
return Iterator(nullptr, this);
}
bool Erase(const K& key)
{
KvofK kofv;
Hash hash;
size_t hash0 = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hash0];
while (cur)
{
if (kofv(cur->_t) == key)
{
if (prev == nullptr)
{
_tables[hash0] = cur->next;
}
else
{
prev->next = cur->next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->next;
}
}
return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};
测试用例
void test_map1()
{
xryq::unordered_map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "字符串", "string" });
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边,剩余";
dict["insert"] = "插入";
dict["string"];
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
unordered_map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 不能修改first,可以修改second
//it->first += 'x';
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
void test_set1()
{
int a[] = { 3,11,86,7,88,82,1,881,5,6,7,6 };
unordered_set<int> s;
for (auto e : a)
{
s.insert(e);
}
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
//*it = 1;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
print(s);
}
标签:map,set,const,cur,iterator,myunordered,unordered,size
From: https://blog.csdn.net/2302_80253411/article/details/143171385