目录
1.框架
2.结构
unordered_map
unordered_set
3.对HashTable的修改
更改模板参数
4.增加迭代器
a.结构
b.运算符重载
c.HashTable封装迭代器
d.unordered_map与unordered_set的迭代器
1.框架
1.复用HashTable ~~> 增加模板参数KeyOfT 来获取 Key值
unordered_map传K,V unordered_set传K
2.增加迭代器: HashNode + HashTable ~~> ++,[ ]的实现, 普通迭代器构造const迭代器
3.若是要处理自定义类型转换为整型, 在外面写仿函数传给unordered_map或unordered_set
2.结构
unordered_map
template<class K,class V,class Hash = HashFunc<V>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
private:
HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT,Hash> _ht;
};unordered_set
template<class K,class Hash = HashFunc<K>>
class unordered_Set
{
public:
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& k)
{
return k;
}
};
//接口: insert + erase + find
bool insert(const K& key)
{
return _ht.Insert(key);
}
private:
HashBucket::HashTable<K, K, SetKeyOfT,Hash> _ht;
};3.对HashTable的修改
更改模板参数
1.增加KeyOfT仿函数-->让unordered_map与unordered_set同时复用HashTable
2.增加模板参数K-->区别unordered_map (K,V) 与 unordered_set(K)
~~>所有涉及到取data值的都改为 , 使用仿函数KeyOfT去取 (插入 + 查找 + 删除)
4.增加迭代器
a.结构
//2.迭代器
//重载 : * -> ++ == !=
template<class K,class T,class KeyOfT,class Hash>
struct __HashIterator
{
typedef HashNode<T> Node;
typedef HashTable< K, T, KeyOfT, Hash> HT;
typedef __HashIterator< K, T, KeyOfT, Hash> Self;
//节点 + 哈希表
Node* _node;
const HT* _ht;
//构造函数
__HashIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}
//重载运算符
};b.运算符重载
* -> == !=
//重载运算符 T& operator*() { return _node->_data; } T* operator->() { return &(_node->_data); } bool operator==(const Self& it) { return _node == it._node; } bool operator!=(const Self& it) { return _node != it._node; }
++
思路:1.如果下一个节点不为nullptr,返回下一个节点
2.如果下一个节点为nullptr,找下一个桶
--先根据节点里面的data,获取key值,来算当前桶的位置
--找下一个不为空的桶
如果这个桶不为空, 把节点给它
如果这个桶为空,++hashi
算当前桶的位置: 获取key + 将非整型数据转换为整型 + 获取哈希桶的个数 + 哈希表
~~>仿函数 + HashTable提供接口获取 或者 友元
Self& operator++() { //1.如果下一个节点不为nullptr返回下一个节点 if (_node->_next) { _node = _node->_next; } //2.找下一个不为空的桶 else { //计算当前桶的位置 Hash hash; KeyOfT kot; size_t hashi = hash(kot(_node->_data)) % _ht->GetCapacity(); vector<Node*> tables = _ht->GetTables(); ++hashi; //找到不为空的桶 while (hashi < _ht->GetCapacity()) { if (tables[hashi]) { _node = tables[hashi]; break; } else { ++hashi; } } //找完没有下一个节点就返回空指针 if (hashi == _ht->GetCapacity()) _node = nullptr; } return *this; } };效果:
c.HashTable封装迭代器
begin
思路:
1.找到第一个有元素的桶
iterator begin()
{
//找第一个有元素的哈希桶
size_t hashi = 0;
while (hashi < GetCapacity())
{
if (_tables[hashi] != nullptr)
{
return iterator(_tables[hashi], this);
}
++hashi;
}
return iterator(nullptr,this);
}end
iterator end()
{
return iterator(nullptr,this);
}d.unordered_map与unordered_set的迭代器
unordered_map与unordered_set的迭代器~~>调用HashTable的迭代器
unordered_map~~> K,V类型允许V被修改~~>const迭代器与普通迭代器
unordered_set~~> K类型不允许被修改 ~~>const迭代器与普通迭代器都是const迭代器
增加const迭代器与普通迭代器~~> 修改迭代器的模板参数 + 修改HashTable的传参
迭代器的模板参数修改
HashTable传参的修改
unordered_map
unordered_set
提供普通迭代器构造const迭代器
普通对象调用begin函数,返回普通迭代器,但是定义的普通迭代器是const迭代器,会发生隐式类型转换~~>因此需要提供普通迭代器构造const迭代器
[]的实现: a.insert返回类型改为pair<iterator,bool>
1.调用insert函数~~>若没有这个K值就将其插入到哈希表中
2.返回V
效果:
