【C++】STL-哈希表封装unorder_set和unordered_map
·
目录
2、unordered_set和unordered_map的插入
1、实现哈希表的泛型
我们先引入上一节中的哈希表，这里使用的是开散列的哈希表
namespace hash_bucket
{
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K,V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> // 对string类型进行特化
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash *= 31;
hash += e;
}
return hash;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
Hash hs;
size_t hashi = hs(kv.first) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(cur->_kv.first) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(kv);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
--_n;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 表中存储数据个数
};
}在这个哈希表中，结点中默认存储的类型是pair，这是unordered_map中的数据类型，并不符合unordered_set.通过观察STL源码可知，unordered_set和unordered_map使用的是同一个哈希表类模板，所以我们需要对哈希表进行改造，使哈希表可以通过模板参数来控制结点中存放的数据类型
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> // 对string类型进行特化
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash *= 31;
hash += e;
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
public:
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
bool Insert(const T& data)
{
Hash hs;
KeyOfT kot;
if (Find(kot(data)))
return false;
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
--_n;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 表中存储数据个数
};
}unordered_set和unordered_map类定义为
namespace cxf
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}namespace cxf
{
template<class K, class V>
class nuordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
private:
hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};
}2、unordered_set和unordered_map的插入
在上面，我们以及给哈希表增加了模板参数KeyOfT。这个模板参数是一个仿函数，就是为了当结点的数据类型是pair时，取出里面的first来计算，当结点数据类型是Key时，则不进行操作
unordered_set
bool insert(const K& key)
{
return _ht.Insert(key);
}unordered_map
bool insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}3、迭代器
3.1 operator++
unordered_set和unordered_map都是单向迭代器，所以只有operator++，没有operator--
我们先来了解一下operator++是怎么运行的。假设迭代器中是一个结点的指针，若当前桶不为空，则进入这个桶，++一次走一个结点，直到当前桶遍历完，再去下一个桶，若当前桶为空，则不会进去遍历，继续向后找不为空的桶。那遍历完一个桶后，要如何找到下一个桶的第一个结点呢？
会发现，若迭代器中只有一个结点的指针是做不到的，因为迭代器需要能够拿到哈希表。此时可以将哈希表内部的vector传过去，也可以传一个哈希表对象过去。我们这里采用的是传一个哈希表对象过去。所以迭代器的成员变量有结点的指针和哈希表对象的指针
template<class K, class T, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node; // 结点指针
HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表对象指针
HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
: _node(node)
, _pht(pht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
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])
break;
hashi++;
}
// 若哈希表遍历完也没找到不为空的桶
if (hashi == _pht->_tables.size())
{
_node = nullptr; // end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
};迭代器类模板需要这么多个模板参数是因为成员变量有哈希表对象的指针
哈希表中创建迭代器对象需要传一个哈希表对象，此时传this即可
typedef HTIterator<K, T, KeyOfT, Hash> Iterator;
Iterator Begin()
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}此时会存在相互依赖的问题，因为迭代器类中有哈希表对象，哈希表类中有迭代器对象，没办法把一个放到另外一个前面，此时可以将迭代器对象放在前面，如何在迭代器对象前加一个前置声明。注意，前置声明时不能有缺省参数，因为定义时已经有缺省参数了。并且迭代器类中使用了_tables，这在哈希表类中是私有的，此时有两种方法，可以写一个GetTables，还可以将迭代器类变成哈希表类的友元。注意，将类模板变成友元不能只在类名前加friend，还需要写模板参数
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node; // 结点指针
HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表对象指针
HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
: _node(node)
, _pht(pht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
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])
break;
hashi++;
}
// 若哈希表遍历完也没找到不为空的桶
if (hashi == _pht->_tables.size())
{
_node = nullptr; // end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> // 对string类型进行特化
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash *= 31;
hash += e;
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 友元
template<class K, class T, class KeyOfT, class Hash>
friend struct HTIterator;
public:
typedef HTIterator<K, T, KeyOfT, Hash> Iterator;
Iterator Begin()
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
bool Insert(const T& data)
{
Hash hs;
KeyOfT kot;
if (Find(kot(data)))
return false;
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
--_n;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 表中存储数据个数
};
}3.2 const迭代器
哈希表的const迭代器
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
Node* _node; // 结点指针
HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表对象指针
HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
: _node(node)
, _pht(pht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
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])
break;
hashi++;
}
// 若哈希表遍历完也没找到不为空的桶
if (hashi == _pht->_tables.size())
{
_node = nullptr; // end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> // 对string类型进行特化
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash *= 31;
hash += e;
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 友元
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
}
~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;
}
}
bool Insert(const T& data)
{
Hash hs;
KeyOfT kot;
if (Find(kot(data)))
return false;
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
--_n;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 表中存储数据个数
};
}接下来实现Unordered_set和unordered_map的迭代器，这里与set和map是类似的，需要将参数修改为const，防止通过普通迭代器修改其值
namespace cxf
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::ConstIterator 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();
}
bool insert(const K& key)
{
return _ht.Insert(key);
}
private:
hash_bucket::HashTable<K, const K, SetKeyOfT> _ht;
};
}namespace cxf
{
template<class K, class V>
class nuordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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();
}
bool insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}此时使用const迭代器时，会报错，因为我们迭代器里面的哈希表对象的指针是普通类型的，而当const对象调用Begin或End时，传过去的this是const的，属于权限放大，会报错，所以，我们需要将迭代器中的哈希表对象的指针修改为const的
Node* _node; // 结点指针
const HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表对象指针
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
: _node(node)
, _pht(pht)
{}4、find
修改哈希表的Find，使之返回迭代器
Iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return Iterator(cur, this);
cur = cur->_next;
}
return Iterator(nullptr, this);
}还可以使用Find修改I女色让他，使容器内不会冗余
bool Insert(const T& data)
{
Hash hs;
KeyOfT kot;
if (Find(kot(data)) != End())
return false;
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return true;
}5、unordered_map的operator[]
首先，需要修改Insert，使之返回值为pair
pair<Iterator, bool> Insert(const T& data)
{
Hash hs;
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return make_pair(it, false);
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return make_pair(Iterator(newNode, this), true);
}V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}6、对于无法取模的类型
在哈希表中，对于不可取模的类型我们是使用仿函数来将不可取模的类型转为整型，使之能够取模，但是，我们控制的仿函数都在底层的哈希表，unordered_set和unordered_map并不能控制，这是不行的，所以我们需要将缺省值放到unordered_set和unordered_map的类模板中，而不是底层的哈希表
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
Node* _node; // 结点指针
const HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表对象指针
HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
: _node(node)
, _pht(pht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
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])
break;
hashi++;
}
// 若哈希表遍历完也没找到不为空的桶
if (hashi == _pht->_tables.size())
{
_node = nullptr; // end()
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> // 对string类型进行特化
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto e : s)
{
hash *= 31;
hash += e;
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
// 友元
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
Iterator End()
{
return Iterator(nullptr, this);
}
ConstIterator Begin() const
{
// 寻找第一个不为空的桶的第一个结点
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
// 若都为空则返回End
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
}
~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 T& data)
{
Hash hs;
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return make_pair(it, false);
size_t hashi = hs(kot(data)) % _tables.size();
// 负载因子==1，扩容
if (_n == _tables.size())
{
vector<Node*> newtables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表中的结点，挪动到新表重新映射的位置
size_t hashi = hs(kot(cur->_data)) % newtables.size();
// 头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
// 原来的桶取完后要置空
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// 头插
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return make_pair(Iterator(newNode, this), true);
}
Iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return Iterator(cur, this);
cur = cur->_next;
}
return Iterator(nullptr, this);
}
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
return true;
}
prev = cur;
--_n;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 表中存储数据个数
};
}namespace cxf
{
template<class K, class Hash = hash_bucket::HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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 K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}namespace cxf
{
template<class K, class V, class Hash = hash_bucket::HashFunc<K>>
class nuordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
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>, MapKeyOfT, Hash> _ht;
};
}此时可以写一个自定义类型来验证，注意这个自定义类型一定要重载operator==，并且operator==最好写为const的
struct Date
{
int _year;
int _month;
int _day;
bool operator==(const Date & d) const
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
};
struct HashDate
{
size_t operator()(const Date& key)
{
return (key._year * 31 + key._month) * 31 + key._day;
}
};
void test_unordered_set()
{
cxf::unordered_set<Date, HashDate> us;
us.insert({ 2024,8,3 });
us.insert({ 2024,8,4 });
}7、介绍unordered_set的几个函数
unordered_map与unordered_set是一样的
7.1 bucket_count
返回unordered_set中桶的数量(包括空桶)
7.2 bucket_size
返回unordered_set第n个桶的数据个数
7.3 bucket
返回这个值在哪一个桶
7.4 reserve
提前开辟好空间，可以避免扩容时的时间损耗
更多推荐
18
0- 0
已为社区贡献3条内容
所有评论(0)