文章目錄
-
- 1. 底層哈希桶的實作(支援疊代器)
- 2. unorder_map的實作
- 3. unorder_set的模拟實作
前言:unorder系列的關聯式容器,底層用的是哈希桶來實作的,本章就會用哈希桶來模拟實作unorder_map和unorder_set,裡面的關鍵就是 在于疊代器的實作。
1. 底層哈希桶的實作(支援疊代器)
#include<vector>
#include<string>
using namespace std;
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& key)
{
size_t value = 0;
for (auto ch : key)
{
value *= 31;
value += ch;
}
return value;
}
};
namespace link_hash_table
{
template<class T>
struct HashNode;
template<class K, class T, class keyofT, class Hashfunc>
class link_hashtable;
template<class K, class T, class ref,class ptr,class keyofT, class Hashfunc = Hash<K>>
struct __HIterator
{
typedef HashNode<T> Node;
typedef __HIterator<K, T, ref, ptr, keyofT, Hashfunc> self;
Node* _node;
link_hashtable<K, T, keyofT, Hashfunc>* _hash_table;
__HIterator(HashNode<T>* Node, link_hashtable<K, T, keyofT, Hashfunc>* hashtable)
:_node(Node),
_hash_table(hashtable)
{
}
ref operator*()
{
return _node->_date;
}
ptr operator->()
{
return &_node->_date;
}
self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
keyofT kf;
Hashfunc hf;
size_t index = hf(kf(_node->_date)) % _hash_table->_tables.size();
size_t i = 0;
for (i = index + 1; i < _hash_table->_tables.size(); i++)
{
if (_hash_table->_tables[i] != nullptr)
{
_node = _hash_table->_tables[i];
break;
}
}
if (i == _hash_table->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator != (const self& op)
{
if (this->_node != op._node)
return true;
else
{
return false;
}
}
bool operator == (const self& op)
{
if (this->_node == op._node)
return true;
else
{
return false;
}
}
};
template<class T>
struct HashNode
{
T _date;
HashNode<T>* _next;
HashNode(const T& date)
:_date(date),
_next(nullptr)
{
}
};
template<class K,class T,class keyofT,class Hashfunc>
class link_hashtable
{
typedef HashNode<T> Node;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
friend struct __HIterator;
public:
typedef __HIterator<K, T, T&, T*, keyofT, Hashfunc> iterator;
private:
vector<Node*> _tables;
size_t _n = 0;
public:
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i] != nullptr)
return iterator(_tables[i], this);
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
Node* find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
Hashfunc hf;
keyofT kf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kf(cur->_date)== key)
return cur;
else
cur = cur->_next;
}
return nullptr;
}
bool erase(const K& key)
{
Node* ret = find(key);
if (ret == nullptr)
{
return false;
}
Hashfunc hf;
keyofT kf;
size_t index = hf(key) % _tables.size();
Node* pre = nullptr;
Node* cur = _tables[index];
while (cur)
{
Node* next = cur->_next;
if (kf(cur->_date) == key)
{
if (pre == nullptr)
{
_tables[index] = next;
}
else
{
pre->_next = next;
}
_n -= 1;
delete cur;
return true;
}
else
{
pre = cur;
cur = next;
}
}
return false;
}
bool insert(const T& kv)
{
Hashfunc hf;
keyofT kf;
Node* ret = find(kf(kv));
if (ret)
{
return false;
}
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(kf(cur->_date)) % newTables.size();
// 頭插
cur->_next = newTables[index];
newTables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t index = hf(kf(kv)) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
_n += 1;
}
};
}
以上的哈希桶是支援疊代器的,疊代器的 * -> == != 都是簡單的,難點在于 ++。
- 哈希桶的下一個節點不為空,那還好,就直接跳到下一個節點;
- 哈希桶的下一個節點為空,那就需要跳到下一個桶中。要是後面的桶都為空,那麼就使得++後的結果為空,就好了。
2. unorder_map的實作
template<class K,class V,class hash = Hash<K>>
class unorder_map
{
struct keyofmap
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
private:
link_hash_table::link_hashtable<K, pair<K, V>, keyofmap, hash> _ht;
public:
typedef typename link_hash_table::link_hashtable<K, pair<K,V>, keyofmap, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool insert(const pair<K,V>& kv)
{
return _ht.insert(kv);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
};
3. unorder_set的模拟實作
template<class K,class hash = Hash<K>>
class unorder_set
{
struct keyofset
{
const K& operator()(const K& key)
{
return key;
}
};
private:
link_hash_table::link_hashtable<K, K, keyofset, hash> _ht;
public:
typedef typename link_hash_table::link_hashtable<K, K, keyofset, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool insert(const K& kv)
{
return _ht.insert(kv);
}
bool erase(const K& kv)
{
return _ht.erase(kv);
}
};