数据结构: unordered"/>
数据结构: unordered
目录
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 + findbool 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
效果:
更多推荐
数据结构: unordered
发布评论