数据结构: unordered_map与unordered_set

目录

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

效果: