正文開始前給大家推薦個網(wǎng)站，前些天發(fā)現(xiàn)了一個巨牛的人工智能學(xué)習(xí)網(wǎng)站，通俗易懂，風(fēng)趣幽默，忍不住分享一下給大家。點(diǎn)擊跳轉(zhuǎn)到網(wǎng)站。
unordered_map是存的是pair是K，V型的，而unordered_set是K型的，里面只存一個值，那我們?nèi)绾卫靡粋€數(shù)據(jù)結(jié)構(gòu)將他們都封裝出來呢？
我們知道哈希表我們實(shí)現(xiàn)的是存pair的，我們可以使用最笨的方法直接復(fù)制一份，把存pair的改為存Key的，但是我們可以參考一下大佬的做法，大佬直接把存的東西弄成一個模版參數(shù)，這個東西具體存的啥由用戶來決定，用戶傳什么就存什么，所以改造后的哈希表的第二個類型模版參數(shù)就是我們要存的類型！
template <class T>
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
: _data(data)
, _next(nullptr)
{}
};
template <class K, class V,class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<V> Node;
private:
KeyOfT kt;
vector<Node*> _tables;
size_t _n = 0;
Hash hs;
};
我們可以看到V是什么類型，那么這個哈希表中存的就是什么，但是會有下一個問題，我們在取余時，不管是unordered_map還是unordered_set都是對Key取余，但是這里我們不知道他是Key還是pair，那怎么辦呢？
我們可以通過仿函數(shù)解決這個問題，我們每個需要用Key計(jì)算的地方都走一層仿函數(shù)，然后unordered_set的就直接返回key就行，unordered_map則需要返回pair的first。我們會看到上面的結(jié)果多了個KeyOfT的模版，這個就是返回Key的仿函數(shù)。
unordered_map
template<class K, class V>
class unordered_map
{
struct MapKOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
private:
hash_bucket::HashTable<K, pair<K,V>,MapKOfT> _ht;
};
unordered_set
template<class K>
class unordered_set
{
struct SetKOfT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
hash_bucket::HashTable<K, K,SetKOfT> _ht;
};
至此我們最簡單的框架就搭建出來了。需要注意的是所有需要用Key的地方都要走一層仿函數(shù)。
插入刪除什么的直接復(fù)用哈希表的就可以，就下來主要就是實(shí)現(xiàn)迭代器。
迭代器
迭代器的結(jié)構(gòu)應(yīng)該是什么樣子的？
節(jié)點(diǎn)的指針肯定是必須的，但是如果我們當(dāng)前的桶走完了，如何++到下一個桶呢？
所以我們需要這張哈希表，用來找當(dāng)前桶走完以后的下一個桶。這里不傳這張哈希表也是可以的，因?yàn)槲覀兊哪康氖钦蚁乱粋€桶，所以把哈希表中的vector傳過來也是可以的。
那么迭代器如何++呢？
如果他的下一個節(jié)點(diǎn)是空，那么就說明這個桶走完了，我們需要找下一個桶，所以我們需要當(dāng)前的位置，所以我們可以直接把當(dāng)前桶的位置傳過來，也可以當(dāng)場計(jì)算桶的位置，這兩種方法都是可以的，但是如果這張表走完了還沒找到下一個桶，那就說明這張表走完了，我們直接把節(jié)點(diǎn)的指針改為nullptr即可。
如果它的下一個節(jié)點(diǎn)不為空，那直接讓它等于它的next即可。
const的迭代器我們可以和之前一樣，直接用兩個模版參數(shù)來決定它是普通迭代器還是const迭代器。
template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
struct __HTIterator
{
typedef HashNode<V> Node;
typedef __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, V, KeyOfT, Hash>* _pht;
size_t hashi;
__HTIterator(Node* node,const HashTable<K, V, KeyOfT, Hash>* pht,size_t i)
: _node(node)
, _pht(pht)
, hashi(i)
{}
Self operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
++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;
}
bool operator!= (const Self& s)
{
return _node != s._node;
}
bool operator== (const Self& s)
{
return _node == s._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
};
但是這里會有一個相互依賴的問題，就是哈希表需要用迭代器，迭代器需要用哈希表，如果哈希表在前面我們就需要前置聲明一下迭代器，迭代器同理，我們需要在前面聲明一個哈希表，但是解決完這個問題以后還存在一個問題，就是哈希表中的vector是私有成員，迭代器不能直接訪問，所以我們需要把迭代器聲明為哈希表的友元。
把迭代器實(shí)現(xiàn)好以后，接下來就是解決Key不能修改的問題。
unordeted_set和unordeted_map如何實(shí)現(xiàn)Key不能修改呢？
我們通過觀察原碼會發(fā)現(xiàn)unordeted_set迭代器和const迭代器都是const迭代器，它是通過這樣的方式來實(shí)現(xiàn)的。unordeted_map是Key不能修改而Value是可以修改的，所以它的pair是pair<const K,V>它把Key設(shè)置為const，這樣就能夠保證Key不能修改，Value可以修改。
接下來需要實(shí)現(xiàn)的是unordered_map的[]重載，要實(shí)現(xiàn)這個重載我們就需要對哈希表的插入進(jìn)行修改，它的返回值不能再是一個bool值，而是一個pair，這個pair的first是iterator迭代器，second是bool類型代表是否插入成功。改造完以后，就可以實(shí)現(xiàn)[]重載，但是對應(yīng)容器的插入的返回值也需要變一下，[]重載主要就是存在就插入不存在就不插入，但是都會返回Val的是可以別被我們修改。
當(dāng)改造完插入以后，我們會發(fā)現(xiàn)unordered_set的插入編譯編不過，這是因?yàn)閡nordered_set的迭代器都是const迭代器，而哈希表的插入返回的是普通的迭代器，這里的iterator無法轉(zhuǎn)化為const_iterator，所以編譯錯誤，有兩種方式可以解決，我們可以支持const迭代器轉(zhuǎn)化為普通迭代器，我們也可以直接用const中的東西來構(gòu)造新的普通迭代器。此時我們的封裝差不多就完善了。
改造后的哈希表
namespace hash_bucket
{
template <class T>
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
: _data(data)
, _next(nullptr)
{}
};
template <class K, class V, class KeyOfT, class Hash>
class HashTable;
template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
struct __HTIterator
{
typedef HashNode<V> Node;
typedef __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, V, KeyOfT, Hash>* _pht;
size_t hashi;
__HTIterator(Node* node,const HashTable<K, V, KeyOfT, Hash>* pht,size_t i)
: _node(node)
, _pht(pht)
, hashi(i)
{}
Self operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
++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;
}
bool operator!= (const Self& s)
{
return _node != s._node;
}
bool operator== (const Self& s)
{
return _node == s._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
};
template <class K, class V,class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<V> Node;
template <class K, class V,class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HTIterator;
public:
typedef __HTIterator<K, V, V&, V*, KeyOfT, Hash> iterator;
typedef __HTIterator<K, V, const V&,const V*,KeyOfT, Hash> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this, i);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this, -1);
}
const_iterator begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return const_iterator(_tables[i], this, i);
}
}
return end();
}
const_iterator end() const
{
return const_iterator(nullptr, this, -1);
}
HashTable()
{
_tables.resize(10);
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<iterator,bool> Insert(const V& data)
{
iterator ret = Find(kt(data));
if (ret!=end())
{
return make_pair(ret,false);
}
if (_n == _tables.size())
{
//需要擴(kuò)容
vector<Node*> newtables;
newtables.resize(2 * _tables.size());
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(kt(cur->_data))% newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kt(data)) % _tables.size();
Node* cur = new Node(data);
cur->_next = _tables[hashi];
_tables[hashi] = cur;
_n++;
return make_pair(iterator(cur,this,hashi), true);
}
//__HTIterator<K, V, V&, V*, KeyOfT, Hash>
// __HTIterator<K, V,Ref,Ptr, KeyOfT, Hash>
iterator Find(const K& k)
{
size_t hashi = hs(k) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kt(cur->_data) == k)
{
return iterator(cur,this,hashi);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& k)
{
size_t hashi = hs(k) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == k)
{
if (prev==nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
cur = cur->_next;
}
return false;
}
private:
KeyOfT kt;
vector<Node*> _tables;
size_t _n = 0;
Hash hs;
};
}
封裝的unordered_map文章來源：http://www.zghlxwxcb.cn/news/detail-771179.html
template<class K, class V>
class unordered_map
{
struct MapKOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKOfT>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKOfT>::const_iterator const_iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K,V>,MapKOfT> _ht;
};
封裝的unordered_set文章來源地址http://www.zghlxwxcb.cn/news/detail-771179.html
template<class K>
class unordered_set
{
struct SetKOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKOfT>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKOfT>::const_iterator const_iterator;
iterator begin() const
{
return _ht.begin();
}
iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
auto ret = _ht.Insert(key);
return make_pair(iterator(ret.first._node, ret.first._pht,ret.first.hashi), ret.second);
}
private:
hash_bucket::HashTable<K, K,SetKOfT> _ht;
};
到了這里，關(guān)于改造哈希表，封裝unordered_map和unordered_set的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
