让风恒定：在 unordered 的荒原上种下一棵常数级的树
本文主要介绍了哈希表（HashTable）及其迭代器的实现，以及基于哈希表的unordered_set和unordered_map容器的设计与实现。重点内容包括： 哈希表节点HashNode的模板化改造，使其能够存储不同类型（key或pair<k,v>）的数据。 HashTable类的改进，增加了KeyOfT和HashFunc等模板参数，用于提取键值和计算哈希值。 HTiterator
·
目录
一、HashNode的修改
template<class T>
struct HashNode
{
T _data;//不再是之前的pair<k,v> _kv 了，T有可能是k或者是pair
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};- _data 不再是之前的pair<k,v> _kv 了，,而是依据传过来的T的类型 ，T有可能是k或者是pair
- HashNote要能接收 来自set的k key和来自map的pair<k,v>
- T是哈希表的节点中实际存储的类型
二、哈希表的修改
template<class k,class T,class KeyOfT, class HashFunc = DefaultHashFunc<T>>
class HashTable
{
public:
...
private:
vector<Node*> _table; // 指针数组 ， 此时 _table是存储的是内置类型，vector不会清理除桶头节点以外的的空间 ，而上面的存的是自定义类型，会调用析构函数
size_t _n=0; // 有效个数
}；- 增添了一个仿函数参数 class KeyOfT
- class KeyOfT : 取出哈希表节点中的key (从set中取key，从map的pair<k,v>中取key)
- HashFunc : 节点中的key(关键码)有可能不是整型，有可能是string等等，你要把它转换成整型 ，这样才能被% ，从而得到哈希值 ,(哈希值决定了该元素在哈希表中的存储位置)
三、HTiterator
template<class k, class T,class Ptr,class Ref, class KeyOfT, class HashFunc = DefaultHashFunc<T>>
struct HTiterator// 在使用HTiterator时，把HTiterator看作 data 的指针
{
typedef HashNode<T> Node;
typedef HTiterator<k, T, Ptr, Ref, KeyOfT, HashFunc> Self;
//两个成员函数
Node* _node;
HashTable<k, T, KeyOfT,HashFunc>* _ptr;//_table是private ,"_ptr->_table.size()", 谁想用谁，谁就是谁的朋友
// HTiterator 想用HashiTable的_table, HTiterator就是HashiTable的朋友
HTiterator(Node* node, HashTable<k, T, KeyOfT,HashFunc>* ptr)
:_node(node), _ptr(ptr)
{}
KeyOfT kt;// 取出k 或者 pair<k,v> 中的 k ,反正就是取 k
HashFunc hf;//为了让对象可以被%
Ref operator*()//iterator* 直接返回iterator中的_node->_data的值
{
return _node->_data;
}
Ptr operator->()//iterator-> 直接返回iterator中的_node->_data的地址
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
size_t hashi =hf( kt(_node->_data)) % (_ptr->_table.size());
hashi++;
while (hashi < _ptr->_table.size())
{
if (_ptr->_table[hashi])
{
_node = _ptr->_table[hashi];
return *this;
}
hashi++;
}
_node = nullptr;
}
return *this;
}
};- 增加模板参数Ptr , Ref : 这样既可以传const 类型的值给这个类，也可以传普通类型的值,编译器可以实例化出不同的类 ， 免得写两个类
- 这里相较于红黑树 ，增加了 HashTable<k, T, KeyOfT,HashFunc>* _ptr; 为什么要用哈希表的指针？因为这样我们就可以使用哈希表中的_table ,在++时，我们可能面临着找到下一个桶的难点,可能这个桶的++的位置是空，所以我们要找到下一个不为空的桶的头节点,但是我们不知道ta的地址在哪里？所以需要把哈希表的指针 ，直接传过来，这样就可以用里面的_table,_table是指针数组,ta有每个桶的头节点指针,同时我们还需要，直到_table的size()
- 在++中，如果下一个节点不为空，就直接走到下一个节点 ，返回this
- 如果下一个节点为空的话，我们就要先找到这个节点所在的桶的位置,然后再从这个桶的位置找起,前提是不能超过指针数组_table.size()的大小,直到找到不为空的桶的头节点,那么，这个位置就是++的值,如果走完了size() , 还是没找到，那就说明最后一个节点就是空 ,_node=空即可
四、unorder_set的框架
#pragma once
#include "HashTable.h"
namespace bit
{
template<class K>
class unordered_set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool Insert(const K& key)
{
return _ht.Insert(key);
}
hash_bucket::HashNode<const K>* Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}
- setkeyofT : 取出set中哈希表节点中存的key值
- typename : typename 在这里的作用是：告诉编译器 hash_bucket::HashTable<K, K, SetKeyOfT>::iterator 是一个类型，而不是变量或成员
- Find返回哈希表中的节点，由于这里之前有开散列的open_address命名空间，所以要声明是hash_bucket命名空间的节点
- 返回值用const限制防止外界修改
- 这里_ht少传了个参数Hashfunc，其实是不用传的，因为Hashfunc有缺省值，可以不用传
五、unorder_map的框架
#pragma once
#include "HashTable.h"
namespace bit
{
template<class K, class V>
class unordered_map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool Insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
hash_bucket::HashNode<const pair<K, V>>* Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};
}
- MapKeyOfT : 取出map中哈希表节点pair<k,v> _data中存的first值
- typename : typename 在这里的作用是：告诉编译器 hash_bucket::HashTable<K, K, SetKeyOfT>::iterator 是一个类型，而不是变量或成员
- Find返回哈希表中的节点，由于这里之前有开散列的open_address命名空间，所以要声明是hash_bucket命名空间的节点
- 返回值用const限制防止外界修改
- 这里_ht少传了个参数Hashfunc，其实是不用传的，因为Hashfunc有缺省值，可以不用传
回顾一下pair的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}};六、const_iterator
6.1修改HashTable
template<class k,class T,class KeyOfT, class HashFunc = DefaultHashFunc<T>>
class HashTable
{
typedef HashNode<T> Node;
public:
typedef HTiterator<k, T, T*,T&,KeyOfT, HashFunc> iterator;
typedef HTiterator<k, T, const T*,const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const//
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
return const_iterator(nullptr, this);
}
HashTable()
{
_table.resize(10, nullptr);// 一开始都是空
}
~HashTable()
pair<iterator, bool> Insert(const T& data)// 前插和后插都一样
void Print()
iterator Find(const k& key) // 返回这个位置的节点指针
bool Erase(const k& key)
private:
vector<Node*> _table; // 指针数组 ， 此时 _table是存储的是内置类型，vector不会清理除桶头节点以外的的空间 ，而上面的存的是自定义类型，会调用析构函数
size_t _n=0; // 有效个数
};
}- 增加const的begin()，和const的end()，在函数名后面加const是限定这个对象不能在这个函数中被修改，在返回值的前面加const是表示这个返回值不允许被修改
- 但此时会发现一个问题，在被const修饰后的函数后,这个对象不能修改，也就是说，这个this是const类型的,而用这个值去初始化const_iterator ，const_iterator 类中的构造函数如下 ：
HTiterator(Node* node, HashTable<k, T, KeyOfT,HashFunc>* ptr)
:_node(node), _ptr(ptr)
{} - 其中这个ptr是普通类型的，这就导致const类型传给普通类型权限会遭到放大，所以这里就会出错
- 解决方法 ： HashTable<k, T, KeyOfT,HashFunc>* ptr要加const修饰，让_ptr是const 不就行了，那难道这里要写两个类型的形参的函数，构成重载吗？
HTiterator(Node* node, const HashTable<k, T, KeyOfT,HashFunc>* ptr)
:_node(node), _ptr(ptr)
{}
HTiterator(Node* node, HashTable<k, T, KeyOfT,HashFunc>* ptr)
:_node(node), _ptr(ptr)
{} - 其实不用直接把哈希表指针设置为const类型 , 在HTiterator中反正又不修改哈希表，只是查询了一下_table的size()以及存储的桶的头节点
- 如果是普通的this给ptr ,也没问题，权限是可以缩小的
6.2修改unorder_set
typedef typename hash_bucket::HashTable < k, k, setkeyofT,DefaultHashFunc<k>>::const_iterator iterator;
typedef typename hash_bucket::HashTable < k, k, setkeyofT, DefaultHashFunc<k>>::const_iterator const_iterator;
iterator begin()const
{
return _ht.begin();
}
iterator end()const
{
return _ht.end();
}- unorder_set是不允许被修改的，所以它的普通迭代器以及const迭代器都是由HTiterator中的const迭代器来的
6.3修改unorder_map
typedef typename hash_bucket::HashTable < k, pair<k,v>, mapkeyofT, DefaultHashFunc<k>>::iterator iterator;
typedef typename hash_bucket::HashTable < k, pair<k, v>, mapkeyofT, DefaultHashFunc<k>>::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();
}
- Map中是k是不允许修改的，v是允许修改的
- 同时 ,增加const迭代器，使kv都不能修改
七、完善map
#pragma once
#include"HashTable.h"
namespace bit
{
template<class k,class v>
class unordered_map
{
public:
struct mapkeyofT
{
const k& operator()(const pair<k,v>& key)
{
return key.first;
}
};
typedef typename hash_bucket::HashTable < k, pair<const k,v>, mapkeyofT, DefaultHashFunc<k>>::iterator iterator;
typedef typename hash_bucket::HashTable < k, pair<const k, v>, mapkeyofT, DefaultHashFunc<k>>::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<const k,v>& _kv)
{
return _ht.Insert(_kv);
}
v& operator[](const k& key)
{
pair<iterator, bool> ret = insert(make_pair(key, v()));
return ret.first->second;//ret.first->_node->second，把iterator当 data* 即可
}
private:
hash_bucket::HashTable<k,pair<const k,v>, mapkeyofT,DefaultHashFunc<k>> _ht;
};
}- 为了防止map中的k类型的first被修改, 给所有的k类型都加上了const 修饰 ,同时重载了operator[] , 可以使他的v类型的值通过k类型的值查找到然后修改
- 从而修改map中的insert的返回值为pair<iterator,bool> ，同样也要修改哈希表中的insert ，从而要修改set中的insert
unorder_set:
pair<iterator,bool> insert(const k& key)
{
//先用HashTable中的iterator接受一下普通迭代器，因为_ht.Insert是普通，之所以用HashTable中的iterator
//因为set中的iterator是const的来的，然后再用普通迭代器构造const迭代器
pair<typename hash_bucket::HashTable<k, k, setkeyofT>::iterator, bool> ret = _ht.Insert(key);
return pair<const_iterator, bool>(ret.first, ret.second);
}- 在unordered_set中 ， 由于其普通迭代器和const迭代器都是const迭代器，所以在unordered_set中的Insert的返回值返回的pair<iterator, bool>实际上的迭代器是const迭代器
_ht调用的HashiTable 的 Insert的返回值的是pair<iterator, bool>，其中的迭代器是普通迭代器，那么这里就会出现类型不匹配 ， - 先用HashTable中的iterator接受一下普通迭代器，因为_ht.Insert是普通，之所以用HashTable中的iterator ，是因为unorder_set中的iterator是const的来的，然后再用普通迭代器构造const迭代器
- 那么我们要对HTIterator 类进行修改，添加一个普通迭代器类型，这样能够接收普通iterator 编写一个构造函数，即可以让普通迭代器转化构造出const迭代器
template<class k, class T,class Ptr,class Ref, class KeyOfT, class HashFunc = DefaultHashFunc<T>>
struct HTiterator// 在使用HTiterator时，把HTiterator看作 data 的指针
{
typedef HashNode<T> Node;
typedef HTiterator<k, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTiterator<k, T, T*, T&, KeyOfT, HashFunc> iterator;
//两个成员函数
Node* _node;
const HashTable<k, T, KeyOfT,HashFunc>* _ptr;//_table是private ,"_ptr->_table.size()", 谁想用谁，谁就是谁的朋友
// HTiterator 想用HashiTable的_table, HTiterator就是HashiTable的朋友
HTiterator(Node* node, const HashTable<k, T, KeyOfT,HashFunc>* ptr)//这里会发生const去实例化普通,const实参传给普通形参 权限会放大
:_node(node), _ptr(ptr) //所以要加const修饰，那用const去初始化普通，这也不对啊，那我们
{} //让_ptr是const 不就行了，在HTiterator中反正又不修改_ptr
//如果是普通的this给ptr ,也没问题，权限可以缩小
HTiterator(const iterator& it)//普通迭代器构造const迭代器(HTiterator是const时)
:_node(it._node), _ptr(it._ptr)
{}
....
};
- 那么当迭代器模板类实例化为const迭代器的时候，我们的构造该构造函数就是构造函数，当迭代器模板类实例化为普通迭代器的时候，我们该构造函数就是拷贝构造函数
哈希表中的insert
//如果Insert如果不扩容 ，不断插入，效率得不到保障
//所以开散列必须扩容 ，不过负载因子可以放大一点
pair<iterator, bool> Insert(const T& data)// 前插和后插都一样
{
HashFunc hf;//转换成能被%
KeyOfT kt;//取data的k
iterator it = Find(kt(data));
if (it!=end())
{
return make_pair(it, false);
}
if (_n==_table.size())
{
size_t newsize = _table.size() * 2;
//这里不能直接调用插入 ，因为旧的Hashable还要delete之前开好的空间
//只需要把旧的Hashable的每个桶的头节点给牵过来即可
vector<Node*>newtable;
newtable.resize(newsize, nullptr);
//遍历旧表 ，把每个桶的头节点给牵过来 ，挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;//保存一下cur的下个节点
size_t hashi = hf(kt(cur->_data)) % newsize;//找到cur该在newtable中存储的位置
cur->_next=newtable[hashi];//把 cur 节点给牵过来 ，挂到新表
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);//底层是start , finish ,end 交换
}
size_t hashi = hf(kt(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];// ps : 把_table[hashi]看作一个代理身份
_table[hashi] = newnode;
_n++;
return make_pair(iterator(newnode,this), true);
}
由于insert中调用的fond函数，所以fond的返回值要修改,在erase函数里面又调用了fond的函数，所以，erase也要稍微修改，不过这些修改都直接放在源代码里面了
八、源代码
HashTable.h
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;//不再是之前的pair<k,v> _kv 了，T有可能是k或者是pair
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
//HTiterator中（HTiterator(Node* node, HashTable<k, T, KeyOfT>* ptr)）用到了HashTable ，
//在HashTable又 typedef HTiterator<k, T, KeyOfT, HashFunc> iterator;
//那谁在前谁在后呢
//
//前置声明
template<class k,class T,class KeytOfT,class HashFunc>
class HashTable;
//告诉编译器HashTable<k, T, KeyOfT>是定义了的，不用急着去确认ta ,因为编译器默认向前找
template<class k, class T,class Ptr,class Ref, class KeyOfT, class HashFunc = DefaultHashFunc<T>>
struct HTiterator// 在使用HTiterator时，把HTiterator看作 data 的指针
{
typedef HashNode<T> Node;
typedef HTiterator<k, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTiterator<k, T, T*, T&, KeyOfT, HashFunc> iterator;
//两个成员函数
Node* _node;
const HashTable<k, T, KeyOfT,HashFunc>* _ptr;//_table是private ,"_ptr->_table.size()", 谁想用谁，谁就是谁的朋友
// HTiterator 想用HashiTable的_table, HTiterator就是HashiTable的朋友
HTiterator(Node* node, const HashTable<k, T, KeyOfT,HashFunc>* ptr)//这里会发生const去实例化普通,const实参传给普通形参 权限会放大
:_node(node), _ptr(ptr) //所以要加const修饰，那用const去初始化普通，这也不对啊，那我们
{} //让_ptr是const 不就行了，在HTiterator中反正又不修改_ptr
//如果是普通的this给ptr ,也没问题，权限可以缩小
HTiterator(const iterator& it)//普通迭代器构造const迭代器(HTiterator是const时)
:_node(it._node), _ptr(it._ptr)
{}
KeyOfT kt;// 取出k 或者 pair<k,v> 中的 k ,反正就是取 k
HashFunc hf;//为了让对象可以被%
Ref operator*()//iterator* 直接返回iterator中的_node->_data的值
{
return _node->_data;
}
Ptr operator->()//iterator-> 直接返回iterator中的_node->_data的地址
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
size_t hashi =hf( kt(_node->_data)) % (_ptr->_table.size());
hashi++;
while (hashi < _ptr->_table.size())
{
if (_ptr->_table[hashi])
{
_node = _ptr->_table[hashi];
return *this;
}
hashi++;
}
_node = nullptr;
}
return *this;
}
};
template<class k,class T,class KeyOfT, class HashFunc = DefaultHashFunc<T>>
class HashTable
{
typedef HashNode<T> Node;
template<class k, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTiterator;
public:
typedef HTiterator<k, T, T*,T&,KeyOfT, HashFunc> iterator;
typedef HTiterator<k, T, const T*,const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const//
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
return const_iterator(cur, this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end()const //const是修饰对象本身 : *this,所以this要用const迭代器指针接受
{
return const_iterator(nullptr, this);
}
HashTable()
{
_table.resize(10, nullptr);// 一开始都是空
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur=_table[i];
while (cur)
{
Node* tmp = cur->_next;
delete cur;
cur = tmp;
}
_table[i] = nullptr;
}
}
/*HashTable(const HashTable<k,v> re)
:_table(re._table)
,_n(re._n)
{ }*/
//如果不扩容 ，不断插入，效率得不到保障
//所以开散列必须扩容 ，不过负载因子可以放大一点
pair<iterator, bool> Insert(const T& data)// 前插和后插都一样
{
HashFunc hf;//转换成能被%
KeyOfT kt;//取data的k
iterator it = Find(kt(data));
if (it!=end())
{
return make_pair(it, false);
}
if (_n==_table.size())
{
size_t newsize = _table.size() * 2;
//这里不能直接调用插入 ，因为旧的Hashable还要delete之前开好的空间
//只需要把旧的Hashable的每个桶的头节点给牵过来即可
vector<Node*>newtable;
newtable.resize(newsize, nullptr);
//遍历旧表 ，把每个桶的头节点给牵过来 ，挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;//保存一下cur的下个节点
size_t hashi = hf(kt(cur->_data)) % newsize;//找到cur该在newtable中存储的位置
cur->_next=newtable[hashi];//把 cur 节点给牵过来 ，挂到新表
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);//底层是start , finish ,end 交换
}
size_t hashi = hf(kt(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];// ps : 把_table[hashi]看作一个代理身份
_table[hashi] = newnode;
_n++;
return make_pair(iterator(newnode,this), true);
}
void Print()
{
KeyOfT kt;
for (size_t i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];//桶的头
while (cur)//把这个桶走完
{
cout <<kt(cur->_data) << "->"<<kt(cur->_data)<<"->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
}
iterator Find(const k& key) // 返回这个位置的节点指针
{
HashFunc hf;
KeyOfT kt;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kt(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->_next;
}
return iterator(nullptr,this);
}
bool Erase(const k& key)
{
HashFunc hf;
KeyOfT kt;
iterator it = Find(kt(key));
if (it._node == nullptr)
{
return false;
}
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
Node* tmp = cur;
while (cur)
{
if (kt(cur->_data) == key)
{
if (tmp==cur)//删桶的头节点
{
_table[hashi] = cur->_next;
delete cur;
_n--;
return true;
}
else
{
tmp->_next = cur->_next;
delete cur;
_n--;
return true;
}
}
tmp = cur;
cur = cur->_next;
}
}
private:
vector<Node*> _table; // 指针数组 ， 此时 _table是存储的是内置类型，vector不会清理除桶头节点以外的的空间 ，而上面的存的是自定义类型，会调用析构函数
size_t _n=0; // 有效个数
};
}unorder_set.h
#pragma once
#include"HashTable.h"
namespace bit
{
template<class k>
class unordered_set
{
public:
struct setkeyofT
{
const k& operator()(const k&key)
{
return key;
}
};
typedef typename hash_bucket::HashTable < k, k, setkeyofT,DefaultHashFunc<k>>::const_iterator iterator;
typedef typename hash_bucket::HashTable < k, k, setkeyofT, DefaultHashFunc<k>>::const_iterator const_iterator;
iterator begin()const
{
return _ht.begin();
}
iterator end()const
{
return _ht.end();
}
//
pair<iterator,bool> insert(const k& key)
{
//先用HashTable中的iterator接受一下普通迭代器，因为_ht.Insert是普通，之所以用HashTable中的iterator
//因为set中的iterator是const的来的，然后再用普通迭代器构造const迭代器
pair<typename hash_bucket::HashTable<k, k, setkeyofT>::iterator, bool> ret = _ht.Insert(key);
return pair<const_iterator, bool>(ret.first, ret.second);
}
private:
hash_bucket::HashTable<k, k, setkeyofT, DefaultHashFunc<k>> _ht;
};
}
unorder_map.h
#pragma once
#include"HashTable.h"
namespace bit
{
template<class k,class v>
class unordered_map
{
public:
struct mapkeyofT
{
const k& operator()(const pair<k,v>& key)
{
return key.first;
}
};
typedef typename hash_bucket::HashTable < k, pair<const k,v>, mapkeyofT, DefaultHashFunc<k>>::iterator iterator;
typedef typename hash_bucket::HashTable < k, pair<const k, v>, mapkeyofT, DefaultHashFunc<k>>::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<const k,v>& _kv)
{
return _ht.Insert(_kv);
}
v& operator[](const k& key)
{
pair<iterator, bool> ret = insert(make_pair(key, v()));
return ret.first->second;//ret.first->_node->second，把iterator当 data* 即可
}
private:
hash_bucket::HashTable<k,pair<const k,v>, mapkeyofT,DefaultHashFunc<k>> _ht;
};
}test
#include<iostream>
//#include<unordered_set>
//#include<unordered_map>
//#include<set>
using namespace std;
#include"UnOrderedSet.h"
#include"UnOrderedMap.h"
int main()
{
bit::unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(3);
us.insert(4);
us.insert(5);
us.insert(0);
bit::unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
//*it+=10;
cout << *it << " ";
++it;
}
cout << endl;
bit::unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("sort", "xxx"));
/*dict["sort"] = "排序";
dict["insert"] = "插入";
dict["string"] = "字符串";
dict["left"];*/
for (auto& kv : dict)//kv是pair<k,v>
{
cout << kv.first << ":" << kv.second << endl;
}
return 0;
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)