unordered_se和unordered_map的底层都是哈希桶。 哈希桶之前已经模拟实现过->哈希表的开散列和闭散列 但是之前并没有实现哈希表的迭代器，接下来将会实现。
一.哈希表迭代器的实现
模板参数的设计
因为 set存储的是key，而map存储的是 K-V 键值对，两个数据类型不一样，但底层又用的都是哈希表，所以在哈希表的模板参数中直接写成 T，但是还需要一个 K 模板参数，因为实际用map或是set的Find接口的时候，都是传的 Key，所以这个用于 Find 接口的实现
- 如果是 set ，那么 T 实例化成 Key
- 如果是 map ，那么 T 实例化成 pair<K,V>
但是当数据类型是 T 的时候，它可能是 K ，也可能是 pair<K,V> ，该 K 倒是没关系，
那 pair<K,V> 该怎么对它取余呢？
解决方法是使用仿函数 KeyofT ！
这个 KeyofT 是在 unordered_set 和unordered_map 层传过来的。
代码语言：javascript复制//KeyofT 用于取出 T 中的 K
//HF 是哈希函数，除留余数时用到
template<class K, class T,class Ref,class Ptr, class KeyofT, class HF >关于接口实现
我们需要实现这些接口：运算符重载 * -> != ==
* 和 -> 倒是没什么好说的、非常简单，问题是 ，该如何实现。
实现 时分为两种情况：
- 的下一个节点正好在当前桶
- 的下一个节点不在当前桶，也就是说 为nullptr
第一种情况很简单，第二种情况怎么办？如何找到下一个桶？
所以迭代器在实现时，成员变量中不仅需要一个节点，还需要一个哈希桶指针，帮助找到下一个桶。
代码语言：javascript复制 Node* _node; //节点指针
const HashBucket<K, T, KeyofT, HF>* _pht; //哈希桶指针
Iterator(Node*node, const HashBucket<K, T, KeyofT, HF>* pht)
:_node(node)
,_pht(pht)
{}需要注意的是，这里要使用到哈希桶，哈希桶又需要用到迭代器，那么谁在前谁在后？
此时只需前置声明一下哈希桶就行了。
只有这个 实现稍微有点麻烦，其他的都比较简单，在博主之前的文章里也有讲到过。
源码
代码语言：javascript复制//前置声明
template<class K, class T, class KeyofT, class HF>
class HashBucket;
//KeyofT用来取出 T 中的key
template<class K, class T,class Ref,class Ptr, class KeyofT, class HF >
struct Iterator
{
KeyofT kot;
HF hf;
typedef HashBucketNode<T> Node;
typedef Iterator<K, T,Ref,Ptr, KeyofT, HF > Self;
Node* _node; //节点指针
const HashBucket<K, T, KeyofT, HF>* _pht; //哈希桶指针
Iterator(Node*node, const HashBucket<K, T, KeyofT, HF>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
Self& operator ()
{
KeyofT kot;
HF hf;
if (_node->_pNext != nullptr) // 的下一个节点在当前桶中
_node = _node->_pNext;
else // 的下一个节点不在当前桶中
{
Node* cur = _node;
size_t hashi = hf(kot(cur->_data)) % _pht->_table.size();
hashi ;
while (hashi < _pht->_table.size()) //寻找下一个桶
{
if (_pht->_table[hashi] != nullptr)
{
_node = _pht->_table[hashi];
return *this;
}
else
hashi ;
}
_node = nullptr;
return *this;
}
return *this;
}
};二.哈希表的修改
因为迭代器中要用到哈希表的私有成员，所以在哈希表中声明 迭代器 为友元。
为了适应unordered_set和unordered_map，Insert ，Find，Erase地接口的返回值都要修改。
Insert 的返回值改为 pair<Iterator,bool>
Find和Erase 的返回值改为 Iterator
增加 begin ，end 接口
此时取模的方式也有所变化，先用 KeyofT 从 T 中取出 Key，然后再调用哈希函数。
代码语言：javascript复制namespace OpenHash
{
template<class K,class T, class KeyofT,class HF = HashFunc<K>>
class HashBucket
{
typedef HashBucketNode<T> Node;
typedef HashBucket<K,T,KeyofT,HF> Self;
public:
template<class K, class T, class Ref, class Ptr, class KeyofT, class HF >
friend struct Iterator; //声明迭代器友元
typedef Iterator<K, T, const T&, const T*, KeyofT, HF> const_Iterator;/
typedef Iterator<K, T, T&, T*, KeyofT, HF> Iterator;
Iterator begin()
{
for (size_t i = 0; i < _table.size(); i )
{
if (_table[i] != nullptr)
return Iterator(_table[i], this);
}
return Iterator(nullptr, this);
}
Iterator end()
{
return Iterator(nullptr, this);
}
const_Iterator begin() const
{
for (size_t i = 0; i < _table.size(); i )
{
if (_table[i] != nullptr)
return const_Iterator(_table[i], this);
}
return const_Iterator(nullptr, this);
}
const_Iterator end() const
{
return const_Iterator(nullptr, this);
}
HashBucket()
{
_table.resize(10, nullptr);
_size = 0;
}
~HashBucket()
{
Clear();
}
// 哈希桶中的元素不能重复
pair<Iterator,bool> Insert(const T& data)
{
Iterator ret = Find(data);
if (ret!=end())
return { Iterator(nullptr,this),false};
HF hf;
KeyofT kot;
if (_size == _table.size())
{
size_t newsize = 2 * _table.size();
vector<Node*> newtable(newsize, nullptr);
for (size_t i = 0; i < _table.size(); i )
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_pNext;
size_t hashi = hf(kot(data)) % newsize;
Node* newnode = new Node(cur->_data);
if (newtable[hashi] == nullptr)
newtable[hashi] = newnode;
else
{
newnode->_pNext = newtable[hashi]->_pNext;
newtable[hashi]->_pNext = newnode;
}
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);
}
Node* newnode = new Node(data);
size_t hashi = hf(kot(data)) % _table.size(); //注意取模方式
if (_table[hashi] == nullptr)
_table[hashi] = newnode;
else
{
newnode->_pNext = _table[hashi]->_pNext;
_table[hashi]->_pNext = newnode;
}
_size ;
return { Iterator(newnode,this),true };
}
//删除哈希桶中为data的元素(data不会重复)
Iterator Erase(Iterator pos)
{
HF hf;
KeyofT kot;
Iterator it = begin();
while (it != end())
{
if (it == pos)
{
Iterator tmp = it;
delete it;
return Iterator( tmp, this);
}
it;
}
return Iterator(nullptr, this);
}
Iterator Find(const T& data)
{
HF hf;
KeyofT kot;
size_t hashi = hf(kot(data)) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_data == data)
return Iterator(cur, this);
else
cur = cur->_pNext;
}
return end();
}
private:
size_t HashFunc(const T& data)
{
return HF()(data) % _table.capacity();
}
private:
vector<Node*> _table;
size_t _size; // 哈希表中有效元素的个数
};
}三.unordered_map 的模拟实现
因为 unordered_map 的 Key 是不可以修改的，所以直接写成 const K
但是 unordered_map 的 Value 可以修改。
插入
因为 unordered_map 要实现 [] ，所以 insert 要返回一个 pair<iterator,bool>
代码语言：javascript复制namespace KM
{
template<class K> //哈希函数
struct DefHF
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<class K,class V>
class unordered_map
{
struct MapKeyofT //从 pair 中取出 K
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
//注意这里要使用 typename ，否则编译器无法分清 Iterator 是类型还是函数
typedef typename OpenHash::HashBucket<K, pair<const K, V>, MapKeyofT>::Iterator iterator; //普通迭代器
typedef typename OpenHash::HashBucket<K, pair<const K, V>, MapKeyofT>::const_Iterator const_iterator; //常量迭代器
iterator begin()
{
return _ht.begin(); //调用哈希桶的 begin
}
iterator end()
{
return _ht.end(); //调用哈希桶的 end
}
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
//插入
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
//删除
iterator erase(iterator pos)
{
return _ht.Erase(pos);
}
// Acess
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert({key,V()});
iterator it = ret.first;
return it->second;
}
const V& operator[](const K& key)const
{
pair<const_iterator, bool> ret = _ht.Insert({ key,V() });
const_iterator it = ret.first;
return it->second;
}
// capacity
size_t size()const
{
return _ht.size();
}
bool empty()const
{
return _ht.empty();
}
// lookup
iterator find(const K& key)
{
return _ht.Find(key);
}
size_t count(const K& key)
{
return _ht.Count(key);
}
// bucket
size_t bucket_count()
{
return _ht.BucketCount();
}
size_t bucket_size(const K& key)
{
return _ht.BucketSize(key);
}
private:
//传入 MapKeyofT
OpenHash::HashBucket<K, pair<const K, V>, MapKeyofT> _ht; //底层是哈希桶
};
}四.unordered_set的模拟实现
set 有点麻烦，因为它的 Key 是不允许修改的，所以它的普通迭代器也就是 const 迭代器，const迭代器就是 const 迭代器。
这就会造成一些问题。
因为 insert 接口返回的是一个 pair ，你以为它是普通迭代器，但实际上它是一个 const 迭代器，而底层哈希桶 Insert 接口返回的是一个普通迭代器，这就造成了类型不匹配的问题。该如何解决？
其实，只需要在迭代器的实现中多加一个构造函数
- 当是 iterator 是这个函数就是拷贝构造
- 当时 const_iterator 时，这个函数就是构造，支持普通迭代器构造 const 迭代器
typedef Iterator<K, T, K&, K*, KeyofT, HF> iterator; //普通迭代器
Iterator(const iterator& it)
:_node(it._node)
,_pht(it._pht)
{}namespace KM
{
template<class K>
class unordered_set
{
struct SetKeyofT //unordered——set 的 KeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//普通迭代器其实是 const 迭代器
typedef typename OpenHash::HashBucket<K, K, SetKeyofT>::const_Iterator iterator;
typedef typename OpenHash::HashBucket<K, K, SetKeyofT>::const_Iterator const_iterator;
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair<const_iterator, bool> insert(const K& key)
{
pair<typename OpenHash::HashBucket<K, K, SetKeyofT>::Iterator, bool> ret = _ht.Insert(key);
//普通迭代器构造 const 迭代器
return pair<const_iterator, bool>(ret.first, ret.second);
}
iterator erase(iterator pos)
{
return _ht.Erase(pos);
}
// capacity
size_t size()const
{
return _ht.size();
}
bool empty()const
{
return _ht.empty();
}
// lookup
iterator find(const K& key)
{
return _ht.Find(key);
}
size_t count(const K& key)
{
return _ht.Count(key);
}
// bucket
size_t bucket_count()
{
return _ht.BucketCount();
}
size_t bucket_size(const K& key)
{
return _ht.BucketSize(key);
}
private:
OpenHash::HashBucket<K, K, SetKeyofT> _ht; //底层是哈希桶，传入 SetKeyofT
};
}
