我們今天又見面啦，給生活加點impetus！！開啟今天的編程之路！！

今天我們使用前面已經實現過的哈希表來實現myunordered_set和unordered_map
作者：?( ‘ω’ )?260
我的專欄：C++進階，C++初階，數據結構初階，題海探驪，c語言
歡迎點贊，關注！！

使用哈希表封裝myunordered_set和myunordered_map

實現出復用哈希表框架，并支持insert

與map和set相比而言，unordered系列的實現更加復雜。
首先，unoedered_set是key類型，unordered_map是key，value類型，要實現一個底層實現兩種數據結構，我們必須使用模版，這里我們傳遞三個參數，第一個是K，第二個是T，第三個是KeyOfT
三個模版的作用

第一個：傳遞K是為了find和erase接口，因為find和erase接口只能夠使用key作為實參
第二個：代表哈希表中結點的存儲類型
第三個：因為我們來尋找映射位置的時候需要取模，key一般可以直接取，但是pair必須需要取出其中的key

接下來我們來看代碼：

template<class K>
class myunordered_set
{struct SetOfT{const K& operator(const K&key){return key;}}
public:private:HashTable<K,K,SetOfT> _tables;//底層結構是哈希桶
}
template<class K,class V>
class myunordered_map
{struct MapOfT{K& operator()(const pair<K,V>&kv){return kv.first;}}
private:HashTable<K,pair<K,V>,MapOfT> _tables;底層結構是哈希桶
}

因為存儲的數值不確定，所以哈希結點也需要修改：

template<class T>
struct HashNode
{T _data;HashNode<K>*_next;HashNode(const T&data):_data(data),_next(nullptr){}
}

接下來我們來寫insert函數，insert是重點，我們主要還寫寫的是偽代碼。
Insert操作還是主題思路不變。
1：先求key映射的偏移位置（細節：key可能需要取，其次，可能需要轉換成整形）這里會用到兩層仿函數
2：不斷頭插
3：檢查是否需要擴容（細節：定義的是哈希數組，而非一個哈希表，直接把結點給他拿下來就行）
4：注意返回值：我們直接模仿庫中的insert函數返回pair<iterator,bool>類型（為什么我們實現這個insert函數重載？因為為了實現unordered_map支持operator[ ]做準備）

來看代碼實現
注意：此時迭代器里面有兩個成員變量，一個是_node，一個是哈希表，原因會在下面說.

pair<iterator,bool> Insert()(const T&data)
{KeyOfT kot;//取keyHash hs;//轉整形，只有在取模的時候才用iterator it=Find(kot(data));if(it!=End()) return {it,false};//插入失敗+去重if (_n == _tables.size()){//兩種邏輯，優先第二種，第一種是拷貝結點，刪除舊結點，第二種是直接把結點給拿下來//第一種:創建新的哈希表，第二種:創建新的數組//HashTable<K, V, Hash> newht(__stl_next_prime(_tables.size() + 1));//加1才能夠繼續取到更到的素數遍歷舊表，將舊表的數據全部重新映射到新表//for (int i = 0;i < _tables.size();i++)//{//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);//為什么第一種方法會重新再拷貝構造，因為復用的時候會調用new這個關鍵字vector<Node*> newtables(__stl_next_prime(_tables.size() + 1),nullptr);//數組初始化為n個nullptrfor (size_t i = 0;i < _tables.size();i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//這里我們存儲一下cur的下一個位置，因為當我們將cur下一個位置放下來的時候，_next被修改，所以需要提前記錄一下//重新計算映射位置size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}//因為原來的舊鏈表的值已經被使用過了，所以我只直接將其置為nullptr_tables[i] = nullptr;}//底層是數組，例如vector或者string,調用庫中的交換函數_tables.swap(newtables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);//這里不是new Node(kot(data));//pair類型結點里面存的是pair，不是key//優先選擇頭插進入鏈表，尾插需要向后遍歷,頭插分兩種情況，映射位置為空或有數據,下面的代碼兩者都可以適用newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return {Iterator(newnode,this),true};
}

支持迭代器的實現

首先，因為哈希表中成員是一個單鏈表，所以我的的迭代器肯定是單向迭代器，即我們的迭代器只能支持++，不支持- -，同樣也不支持隨機訪問。

迭代器的成員變量肯定是有一個_node。
當我們需要返回下一個位置的迭代器的時候，如果下一個位置不為空，那么迭代器中的指針直接向后走一步就可以了，如果下一個位置為空，就需要遍歷到下一個不為空的位置的桶，返回桶的第一個位置即可。
此時我的cur都在遍歷這個單鏈表了，我們根本找不到哈希表中下一個不為空的位置，那我們應該怎樣找到下一個不為空的桶呢？我們必須傳遞一個哈希表過去！！
來看代碼實現：
細節：這里我直接加上普通迭代器和const迭代器一起實現了，不然等下解釋的太繞了
實現const迭代器的話，就會多2個模版參數，主要是返回值operator*和operator->。
而且，在迭代器內部有this指針，我們只用操作_node的指向即可

template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
struct HTIterator
{typedef HashNode<T> Node;typedef HashTable<K,T,KeyOfT,Hash> HT;typedef HTIterator<K,T,Ref,Ptr,keyofT,Hash>  Self;Node*_node;//成員變量HT*_pht;//成員變量Self& operator++(){if(_node->_next)//指向的下一個不為空{_node=_node->_next;}else{//下一個結點為空，需要向后找到不為空的桶KeyOfT kot;Hash hs;size_t hashi=hs(kot(_node->_data))%_pht->_tables.size();hashi++;//需要跳過當前桶while(hashi<_pht->_tables.size()){if(_pht->_tables[hashi]){_node=_pht->_tables[hashi];break;}++hashi;}if(hashi == _pht->_tables.size())//哈希表遍歷遍歷完了都還沒有找到{_node=nullptr;}}return *this;}
}

接下來我再來實現迭代器中不重要的操作：
直接看代碼即可：

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;
}

const

const迭代器中迭代器部分我們已經完成了，接下來我們來看HashTable的部分。
這里需要解釋Begin()，begin肯定是返回桶中鏈表的第一個結點即可

因為比較簡單，直接來看代碼即可：

Iterator Begin()//返回第一個桶的第一個結點
{if (_n == 0)return End();//此時沒有結點，Begin()就是End()for (size_t i = 0;i < _tables.size();i++){if (_tables[i])return Iterator(_tables[i] ,this);}return End();//語法邏輯上來說必須要加，不能用運行邏輯來概括語法邏輯，萬一里面的程序出錯，可能就沒有返回值了
}Iterator End()
{return Iterator(nullptr, this);
}//錯誤積累：如果報錯不能將initializer list轉換成啥，大概率編譯器是將{}識別成這個作用了，但是我的目的是多參數來進行隱式類型轉換
Const_Iterator Begin() const//返回第一個桶的第一個結點
{if (_n == 0)return End();for (size_t i = 0;i < _tables.size();i++){if (_tables[i]) return Const_Iterator(_tables[i], this);}return End();
}Const_Iterator End()const
{return Const_Iterator(nullptr, this);
}

Key不能被修改

這個也比較簡單，只要將第二個模版參數對應的K修改為const K即可，隨后對應的typedef部分也需要修改一下。

unordered_map支持[ ]

因為前面已經實現過，直接來看代碼：

V& operator[](const K& key)
{pair<iterator, bool> ret = Insert({key,V()});//直接復用上面的Insert，本質上還是調用的底層return ret.first->second;
}

結語

感謝大家閱讀我的博客，不足之處歡迎指正，感謝大家的支持
逆水行舟，楫摧而志愈堅；破繭成蝶，翼濕而心更熾！！加油！