哈希表模板參數(shù)改造
針對(duì)模板參數(shù)V改造
因?yàn)椴煌萜鞯念愋筒煌?如果是unordered_map,V代表一個(gè)鍵值對(duì),如果unordered_set,V代表Key值,而底層哈希表并不知道上層容器所要傳遞的V模板參數(shù)類型,為了與哈希表的模板參數(shù)區(qū)分,我們將哈希表中的V模板參數(shù)改為T.
增加仿函數(shù)獲取具體數(shù)據(jù)類型.
例如: 在哈希表中當(dāng)我們使用Find函數(shù)進(jìn)行查找時(shí):
如果上層傳遞的數(shù)據(jù)類型為Key值,我們就可以直接與查找數(shù)據(jù)比較.
如果上層傳遞的數(shù)據(jù)類型為pair<K,V>鍵值對(duì),我們就不可以直接比較,需要利用仿函數(shù)獲取鍵值對(duì)的first進(jìn)行比較.
unordered_set仿函數(shù)SetKeyOfT代碼:
struct SetKeyOfT //根據(jù)map還是set傳遞不同數(shù)據(jù)類型給底層.
{
const K& operator()(const K& key)
{
return key;
}
};
unordered_map仿函數(shù)MapKeyOfT代碼:
struct MapKeyOfT //根據(jù)map還是set傳遞不同數(shù)據(jù)類型給底層.
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first; //獲取pair<K,V>鍵值對(duì)中的first.
}
};
所以,我們要在哈希表模板參數(shù)中增加一個(gè)仿函數(shù)KeyOfT.
如果是unordered_set,就傳 SetKeyOfT類型的仿函數(shù).
如果是unordered_map,就傳MapKeyOfT類型的仿函數(shù).
模板參數(shù)轉(zhuǎn)換圖示如下:
額外說(shuō)明:
1: 我們對(duì)原先哈希表中的Hash進(jìn)行了修改,不要缺省值,因?yàn)槲覀兛隙ㄊ鞘褂蒙蠈尤萜鱾鬟f不同的仿函數(shù)類型,所以在unordered_set與unordered_map中傳遞仿函數(shù)類型.
哈希表的正向迭代器
正向迭代器中的內(nèi)置成員:
哈希表正向迭代器有兩個(gè)內(nèi)置成員:
1: 結(jié)點(diǎn)指針
2: 哈希表的指針
template < class K, class T, class Hash, class KeyOfT >
class HashTable; //重新聲明哈希表類模板.
//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
typedef HashNode<T> Node; //重新定義哈希結(jié)點(diǎn)的類型為Node.
typedef HashTable<K, T, KeyOfT, HashFunc> HT; //重新定義哈希表的類型為HT.
typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //重新定義正向迭代器的類型為Self.
Node* _node; //結(jié)點(diǎn)指針
HT* _pht; //哈希表指針
};
注意:
因?yàn)榈髦幸褂玫焦１眍愋?所以我們?cè)诠１淼髑懊姹仨毬暶饕幌鹿１眍惸０?
正向迭代器的成員函數(shù)
以下成員函數(shù)較為簡(jiǎn)單,就不另外說(shuō)明:
_HashIterator( Node* node,HT* pht ) //初始化列表
:_node(node)
, _pht(pht)
{
}
T& operator*() //解引用運(yùn)算符重載
{
return _node->_data;
}
T* operator->() //->運(yùn)算符重載
{
return &_node->_data;
}
bool operator!=( const Self& s ) const //外面增加const可以使const對(duì)象也能調(diào)用該成員函數(shù).
{
return _node != s._node; //實(shí)質(zhì)上是迭代器中的_node比較
}
bool operator==( const Self& s )const
{
return _node == s._node;
}
前置++運(yùn)算符重載:
前置++運(yùn)算符重載主要有兩個(gè)步驟:
1: 如果當(dāng)前結(jié)點(diǎn)指針的下一個(gè)結(jié)點(diǎn)存在,則結(jié)點(diǎn)指針指向下一個(gè)結(jié)點(diǎn).
2: 如果當(dāng)前結(jié)點(diǎn)指針的下一個(gè)結(jié)點(diǎn)不存在:
(1): 通過(guò)哈希函數(shù)計(jì)算哈希桶的位置.
(2): 在哈希表中,從哈希桶中的下一個(gè)位置開始遍歷查找.
如果哈希桶存在,則將結(jié)點(diǎn)指針指向該哈希桶.
如果哈希表遍歷完還沒有找到,則說(shuō)明這是哈希表中的最后一個(gè)數(shù)據(jù)的迭代器,則結(jié)點(diǎn)指針指向空,表明最后一個(gè)數(shù)據(jù)的下一個(gè)結(jié)點(diǎn).
Self& operator++()
{
if (_node->_next) //在當(dāng)前桶中迭代
{
_node = _node->_next;
}
//如果該哈希桶迭代完畢，則在哈希表中找下一個(gè)哈希桶迭代尋找．
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器訪問(wèn)哈希表的私有成員
size_t i = hashi + 1;
for (; i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];
break; //++完就退出.
}
}
if (i == _pht->_table.size()) //此時(shí),這也說(shuō)明正式哈希桶迭代器的end.
{
_node = nullptr;
}
}
return *this;
}
哈希表插入函數(shù)的修改(適用于unordered_map)
為了支持unordered_map中的[]操作符重載,我們針對(duì)哈希表中的插入函數(shù)返回值進(jìn)行修改
(1): 如果哈希表中已有所給數(shù)據(jù),則返回已有數(shù)據(jù)的迭代器與插入結(jié)果(失敗)所構(gòu)成的鍵值對(duì).
(2): 如果哈希表沒有所給數(shù)據(jù),則將新數(shù)據(jù)頭插該哈希桶組成的單鏈表上,返回新插入結(jié)點(diǎn)指針構(gòu)造與插入結(jié)果(成功)組成的鍵值對(duì).
插入函數(shù)代碼如下:
pair< Iterator,bool> Insert(const T& data)
{
Hash hash;
KeyOfT kot;
Iterator ret = Find(kot(data));
if (ret != end())
{
return make_pair( ret, false);
}
if (_size == _table.size()) //擴(kuò)容.
{
// size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
vector<Node*> newTable;
newTable.resize(GetNextPrime(_table.size()), nullptr);
Hash hash;
//從舊表結(jié)點(diǎn)移動(dòng)映射新表.
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hash(kot(data)) % _table.size();
Node* newNode = new Node(data);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_size;
return make_pair(Iterator(newNode,this),true); //如果是新插入的數(shù)據(jù),則返回新插入結(jié)點(diǎn)構(gòu)造的迭代器與插入結(jié)果組成的pair.
}
一個(gè)類型K去做set和unordered_set他的模板參數(shù)的必備條件.
set容器模板參數(shù):
(1):set模板參數(shù)要求能夠支持小于比較,例如:二叉搜索樹查找成員函數(shù)中,我們可以利用compare仿函數(shù)將當(dāng)前結(jié)點(diǎn)值與所給值比較,從而決定cur遍歷左子樹還是右子樹,為了能夠支持大于比較的,我們可以交換一下實(shí)參位置,這也間接支持了大于比較.并且條件判斷,進(jìn)而也支持了等于.
unordered_set容器模板參數(shù)要求:
(1)針對(duì)于K類型(指針,打浮點(diǎn)數(shù),有符號(hào)整型)可以轉(zhuǎn)換為無(wú)符號(hào)整數(shù)取模.對(duì)于string,日期類類型,這兩個(gè)類型與整型類型無(wú)關(guān)的,此時(shí)不可以直接強(qiáng)轉(zhuǎn)為整數(shù),需要相應(yīng)的提供將該類型轉(zhuǎn)換為整數(shù)的仿函數(shù).
(2):K類型對(duì)象能夠支持等于比較(因?yàn)樵诓檎抑芯褪且_定存儲(chǔ)的對(duì)象與所傳的對(duì)象是否相等,例如Data日期類),如果不支持需要額外提供等于比較的仿函數(shù).
unordered_set的模擬實(shí)現(xiàn)(完整代碼)
在上述中,我們已經(jīng)將unordered_set重點(diǎn)內(nèi)容講解完畢,剩下的成員函數(shù)只需要復(fù)用哈希表中的就可以了.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-428808.html
namespace yzh
{
//2:因?yàn)槲覀兪褂胢ap,set是將實(shí)參傳給,map,set的所以當(dāng)string類型取模時(shí)要在map,set中寫仿函數(shù).
template < class K,class Hash = HashFunc<K>> //1:由第二個(gè)模板參數(shù)決定要存儲(chǔ)的數(shù)據(jù).
class unordered_set
{
struct SetKeyOfT //根據(jù)map還是set傳遞不同數(shù)據(jù)類型給底層.
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashBucket::HashTable< K,K,Hash,SetKeyOfT>::Iterator iterator; //重新定義一下迭代器類型為iterator.
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> Insert(const K& key)
{
return _ht.Insert(key);
}
private:
HashBucket::HashTable<K,K,Hash,SetKeyOfT> _ht;
};
void test_set() //測(cè)試
{
unordered_set<int> set;
set.Insert(1);
set.Insert(2);
set.Insert(3);
unordered_set<int>::iterator it = set.begin();
while ( it != set.end() )
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
unordered_map的實(shí)現(xiàn)(完整代碼)
在上述中,我們已經(jīng)將unordered_map重點(diǎn)內(nèi)容講解完畢,剩下的成員函數(shù)只需要復(fù)用哈希表中的就可以了.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-428808.html
namespace yzh
{
template < class K, class V, class Hash = HashFunc<K> > //由第二個(gè)模板參數(shù)決定要存儲(chǔ)的數(shù)據(jù)類型,
class unordered_map
{
struct MapKeyOfT //根據(jù)map還是set傳遞不同數(shù)據(jù)類型給底層.
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashBucket::HashTable< K, pair<K, V>, Hash, MapKeyOfT>::Iterator iterator;//重新定義一下迭代器類型為iterator.
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> Insert( const pair<K, V>& kv )
{
return _ht.Insert(kv);
}
V& operator[]( const K& key ) //給一個(gè)key,返回V的引用.
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); //如果插入失敗,返回已有數(shù)據(jù)的迭代器與返回結(jié)果組成的pair. //如果插入成功,返回新插入數(shù)據(jù)的迭代器與返回結(jié)果組成的pair.
return ret.first->second;
}
private:
HashBucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; //map和set都知道傳遞什么來(lái)類型的仿函數(shù),以及要傳遞的數(shù)據(jù)類型.
};
void test_map()
{
unordered_map<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("string", "排序"));
unordered_map<string,string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
}
void testmap1()
{
unordered_map<string, int> countMap;
string arr[] = { "蘋果","西瓜","蘋果","西瓜","蘋果","西瓜","蘋果","香蕉" };
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
適用于unordered_set和unordered_map的哈希表代碼
#include <map>
#include <vector>
#include <string>
#include <string>
#include <iostream>
using namespace std;
template < class K > //仿函數(shù)的默認(rèn)值,如果不顯示傳就會(huì)默認(rèn)調(diào)用.
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template< > //1:對(duì)于常見類型,為了方便,我們可以對(duì)類模板進(jìn)行特化.
struct HashFunc <string> //并且根據(jù)實(shí)參所傳類型,優(yōu)先走特化版本.
{
size_t operator()(const string& key)
{
size_t val = 0;
for (auto& ch : key) //遍歷string,將一個(gè)個(gè)字母替換成ASCI碼進(jìn)行相加.
{
val += ch;
}
return val;
}
};
namespace HashBucket
{
template < class T >
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
template < class K, class T, class Hash, class KeyOfT >
class HashTable;
template < class K, class T, class Hash, class KeyOfT >
struct _HashIterator
{
typedef HashNode<T> Node;
typedef HashTable< K, T, Hash, KeyOfT> HT;
typedef _HashIterator< K, T, Hash, KeyOfT> Self;
Node* _node;
HT* _pht;
_HashIterator( Node* node,HT* pht )
:_node(node)
, _pht(pht)
{
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next) //在當(dāng)前桶中迭代
{
_node = _node->_next;
}
//如果該哈希桶迭代完畢，則在哈希表中找下一個(gè)哈希桶迭代尋找．
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器訪問(wèn)哈希表的私有成員
size_t i = hashi + 1;
for (; i < _pht->_table.size(); ++i)
{
if (_pht->_table[i])
{
_node = _pht->_table[i];
break; //++完就退出.
}
}
if (i == _pht->_table.size()) //此時(shí),這也說(shuō)明正式哈希桶迭代器的end.
{
_node = nullptr;
}
}
return *this;
}
bool operator!=( const Self& s ) const
{
return _node != s._node;
}
bool operator==( const Self& s )const
{
return _node == s._node;
}
};
template < class K, class T, class Hash, class KeyOfT >
struct HashTable
{
typedef HashNode<T> Node;
template < class K, class T, class Hash, class KeyOfT > //為了迭代器能夠訪問(wèn)哈希表的私有成員,我們?cè)O(shè)為迭代器是哈希表的
//友元,類模板聲明友元需要增加類模板.
friend struct _HashIterator;
public:
typedef _HashIterator< K, T, Hash, KeyOfT> Iterator;
Iterator begin()//獲取第一個(gè)迭代器
{
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
return Iterator( _table[i], this );
}
}
return end();
}
Iterator end() //獲取最后一個(gè)迭代器
{
return Iterator(nullptr, this);
}
size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
//素?cái)?shù)序列
const size_t primeList[PRIMECOUNT] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > prime) //從這個(gè)數(shù)組里面取第一個(gè)大于prime的值.
return primeList[i];
}
return primeList[i]; //雖然數(shù)據(jù)不可能那么大,但是也有可能不會(huì)走if判斷,
// 所以從語(yǔ)法上來(lái)說(shuō)還要考慮所給值prime大于素?cái)?shù)數(shù)組整個(gè)數(shù)據(jù)的情況.
}
~HashTable() //vvector會(huì)調(diào)用析構(gòu)函數(shù),但是哈希桶必須自己寫.
{
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
// cout << "~HushTable()" << endl;
}
bool Erase(const K& key)
{
if (_table.size() == 0)
{
return true;
}
Hash hash;
size_t hashi = hash(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_size;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
pair< Iterator,bool> Insert(const T& data)
{
Hash hash;
KeyOfT kot;
//去重
Iterator ret = Find(kot(data)); //如果該數(shù)據(jù)已經(jīng)有了,則返回已有數(shù)據(jù)的迭代器與插入結(jié)果構(gòu)成的pair.
if (ret != end())
{
return make_pair( ret, false);
}
if (_size == _table.size()) //擴(kuò)容.
{
// size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
vector<Node*> newTable;
newTable.resize(GetNextPrime(_table.size()), nullptr); //擴(kuò)容
Hash hash;
//從舊表結(jié)點(diǎn)移動(dòng)映射新表.
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hash(kot(data)) % _table.size();
Node* newNode = new Node(data);
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_size;
return make_pair(Iterator(newNode,this),true); //如果是新插入的數(shù)據(jù),則返回新插入結(jié)點(diǎn)構(gòu)造的迭代器與插入結(jié)果組成的pair.
}
Iterator Find(const K& key)
{
if (_table.size() == 0) //表為空,就返回nullptr.
{
return end();
}
Hash hash;
KeyOfT kot;
size_t hashi = hash(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
size_t size()
{
return _size;
}
size_t TablesSize() //表的長(zhǎng)度
{
return _table.size();
}
size_t BucketNum() //有多少個(gè)桶被用了.
{
size_t Num = 0;
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
++Num;
}
}
return Num;
}
size_t MaxBucketLenth()
{
size_t maxLen = 0;
for (size_t i = 0; i < _table.size(); ++i)
{
size_t len = 0;
Node* cur = _table[i];
while (cur)
{
++len;
cur = cur->_next;
}
if (len > maxLen)
{
maxLen = len;
}
}
return maxLen;
}
private:
vector<Node*> _table;
size_t _size = 0;
};
}
到了這里，關(guān)于C++STL詳解(十) -- 使用哈希表封裝unordered_set和unordered_map的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
