C++学习记录（20）哈希表封装实现unordered_set和unordered_map
前言
类比于map和set的实现，学习了红黑树就是为了模拟实现map和set，模拟实现的目的是为了对语法进行训练，当然，也可能夹带一些源码阅读之类的考研。
了解了stl底层哈希表，也就是哈希桶形式的哈希表以后，重点就得放到模拟实现上了。
一、源码了解底层结构
1.找源码
还是跟以前一样，库里面往往喜欢包来包去的：
当然，不难从日期中看出来，源码是大概二十年前的，原因之前也解释过了，因为如果直接扒最新的源码，比如直接扒VS的源码：
VS转到定义直接就能看到底层实现，随便找了一个方法，语法又是什么&&，还有throw，大概就是异常的事，noexcept关键字也看不懂。我们学的语法在这里可以说一无是处了，因为还没学这些语法。故而源码还是看稍微早一点的好一点，毕竟那个时候C++标准没有进化到现在这个样子。
话题扯远了昂，还是看回SGI版本的源码：
这个是<hash_set>里的内容，主要unordered系列也说了，C++11才有的，之前的命名没那么一致，这种版本的set底层是哈希表，所以叫个这也无可厚非。
根据map和set源码的经验昂，hash_set和hash_map大概率就是对底层hashtable的接口的封装，重点还是看hashtable的内容，不过还是拿过来瞅瞅。
2.了解大致结构
hash_set
hash_map
为了省事昂，不说什么unordered什么hash了，知道我说的是啥就行。
set和map的源码如上图所示，可以看到：
set的模板参数
template<K,HashFunc,Equal>
map的模板参数
template<K,V,HashFunc,Equal>
当然，库里面的类型命名毕竟太过于久远了，因此可能不太规范，比如可能它的value类型给的T，这个细节之前见到过了，我们心知肚明就可以了。
抛去命名问题来看，其实模板参数和现代stl库里的map和set完全一样：
存储的数据类型K或者K-V；
保证key一定可以被转换成整型值进而保证可以进行哈希映射的哈希函数类，即实现了将存储的key转化为整型值的仿函数类；HashFunc
以及唯一可能需要用到的比较逻辑，==；Equal_Key
equal这个好像没有细讲，大概意思就是：
因为底层哈希表insert直接计算哈希映射再头插用不到判断逻辑。
只有find逻辑用得到或者说类似于find的逻辑，比如erase的前提就是先find，就也能用到。
设计这个倒是真没啥可说的，从使用角度理解每个参数的作用，那么设计的时候自然知道；虽然这话有点倒反天罡吧，毕竟肯定是设计的时候用到了某个逻辑，并且这玩意有可能还得使用者控制，所以才有那个参数，使用的时候当然也是从底层才能理解，才知道某个参数干嘛的，理解就行了。
3.了解如何通过哈希表实现
外层map和set那个壳就不废话了，重点还是看怎么封装哈希表才实现的map和set。
所以重点还是：
set
可以看到底层哈希表传的参数是<K,K,HashFunc,KeyOfValue,equal>。
应该不难理解吧，equal设计哈希表的没管，现在也不加了；
KeyOfValue不用说了吧，因为底层哈希表的角度，泛型编程我哪知道你给我的是key还是pair<key,value>，为了拿到key去insert去find，我必须搞个类型去取出来key，之前花好长时间去理解这一点。
底层是<pair<K,V>,K,HashFunc,KeyOfValue,equal>
其它逻辑没啥，可说的，重提一下为什么都有pair了还搞一个K，在红黑树封装实现map和set的时候，到Find方法的时候我们形参写的是const K& key，所以必须传key的类型，毕竟从pair中能拿出来实例化的key，拿类型颇为麻烦，当然有个typename啥的，但是肯定没必要舍近求远，直接传多简单。
还有就是：
这玩意的顺序有点反人类了以我们现在的理解，毕竟存储的数据习惯性扔到第二个地方了，但是人家扔这你也不能说错了，我们自己实现的时候也不用模仿，逻辑对了就行。
二、实现结构
大致浏览了浏览，先不管方法，先把这几个类的壳，创建的创建，该修改的修改，先弄好。
1.HashTable更新
template <class T>
struct HashNode
{
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
T _data;
struct HashNode* _next;
};
template <class K,class T,class Hash,class KeyOfValue>
class HashTable
{
typedef struct HashNode<T> Node;
HashFunc<K> hash;
KeyOfValue kov;对于模板参数：
多加个keyofvalue；
由于哈希表第二个参数不一定是key还是pair<key,value>，干脆直接搞个T，代表哈希表结点存储的内容的类型；
把哈希函数调到set和map那一层，方便我们自己容器也能实现指定哈希函数，在下面展示；
哈希函数还只跟K相关；
kov到后面肯定得用，干脆先创建个成员变量，方便后面用
2.set更新
template<class K>
class setkov
{
public:
K& operator()(const K& key)
{
return key;
}
};
template <class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template <>
class HashFunc<string>
{
public:
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash += e;
hash *= 131;
}
return hash;
}
};
template<class K,class HashFnc = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, K, HashFunc, setkov<K>> ht;
public:
private:
ht _t;
};大概就是这个样子，因为要给set多一个哈希函数的模板参数，所以把缺省值搞到这里，因此写出来的哈希函数也得搞到这里。
然后实现set层的kof作为参数传给哈希表，这样就能实现到时候取key的泛型编程。
3.map更新
template<class K,class V>
class mapkov
{
public:
K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
template <class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template <>
class HashFunc<string>
{
public:
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash += e;
hash *= 131;
}
return hash;
}
};
template<class K, class V,class HashFnc = HashFunc<K>>
class unordered_map
{
typedef HashTable<K, pair<K,V>, HashFunc, mapkov<K,V>> ht;
public:
bool insert(const pair<K,V>& kv)
{
return _t.Insert(kv);
}
private:
ht _t;
};
template<class K, class V,class HashFnc = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, pair<K,V>, HashFunc, mapkov<K>> ht;
public:
private:
ht _t;
};4.问题
理想上map和set都搞个哈希函数就可以了，但是一旦按照上面那么做了，在测试文件中：
命名空间直接合到一起了，这个时候相当于有两份这个哈希函数，重定义直接造成冲突，所以既然是公共部分，直接提取出来：
//"HashFunc.h"
#include <string>
namespace xx
{
template <class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template <>
class HashFunc<std::string>
{
public:
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash += e;
hash *= 131;
}
return hash;
}
};
}这样的话包就行了：
所以现在：
set
#pragma once
#include "HashTable.h"
#include "HashFunc.h"
namespace xx
{
template<class K>
class setkov
{
public:
const K& operator()(const K& key)
{
return key;
}
};
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, K, Hash, setkov<K>> ht;
public:
private:
ht _t;
};
}map
#pragma once
#include "HashTable.h"
#include "HashFunc.h"
namespace xx
{
template<class K, class V>
class mapkov
{
public:
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
typedef HashTable<K, pair<K, V>, Hash, mapkov<K, V>> ht;
public:
private:
ht _t;
};
}三、完善方法
1.insert方法
一样的道理，重点是完善哈希表的逻辑，外层set和map做的仅仅是封装方法：
重点是实现底层哈希表的Insert方法：
bool Insert(const T& data)
{
if (Find(kov(data))
return false;
//扩容
if (_n == _tables.size())
{
HashTable<K, V> newtable;
newtable._tables.resize(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
while (_tables[i])
{
int hashi = hash(kov(_tables[i]->_data)) % newtable._tables.size();
Node* next = _tables[i]->_next;
//newtable[hashi] _tables[i]
_tables[i]->_next = newtable._tables[hashi];
newtable._tables[hashi] = _tables[i];
_tables[i] = next;
}
}
_tables.swap(newtable._tables);
}
//插入
int hashi = hash(kov(data)) % _tables.size();
//_tables[hashi] newnode
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}大概有以下几点做了修改：
泛型编程，只知道到时候结点里存的肯定是T
去冗余的Find方法要的是key，所以还得套一层kov取出来data的key
扩容的时候，需要把原表里面的所有结点都挂到新表里，那么这个时候就得拿到原表里每个结点的key，所以就得套一层kov，拿到key再算在新表的映射即可
插入的是算一下在表里的映射，肯定得取出来key，所以套一层kov，再套一层hash，保证key计算的时候一定是整型值。
测试代码：
void test_uset()
{
xx::unordered_set<int> s1;
s1.insert(45);
s1.insert(5);
s1.insert(13);
s1.insert(45);
}
void test_umap()
{
xx::unordered_map<string, string> dict;
dict.insert({ "strategy", "策略" });
dict.insert({ "overwhelm", "压垮" });
dict.insert({ "establish", "建立，设立" });
}
int main()
{
test_uset();
test_umap();
return 0;
}截屏不再展示了，说句实话，调试窗口看我们自己实现的内容太折磨了，这几天我回看了之前调试窗口截的图，观看感差的一匹，所以直接贴上代码就算了。
2.Find方法
逻辑不变，需要得到key的地方kov了一下而已：
Node* Find(const K& key)
{
int hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kov(cur->_data) == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
外层依旧套：
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, K, Hash, setkov<K>> ht;
typedef struct HashNode<K> Node;
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
private:
ht _t;
};
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
typedef HashTable<K, pair<K, V>, Hash, mapkov<K, V>> ht;
typedef struct HashNode<pair<K,V>> Node;
public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
private:
ht _t;
};相信也发现了，如果没有迭代器直接套的话，很麻烦，还得返回Node*，所以方法实现完毕以后第一件事就是搞好迭代器，这样返回值才能舒服一点。
3.Erase方法
bool Erase(const K& key)
{
int hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kov(cur->_data) == key)
{
if (prev)
prev->_next = cur->_next;
else
_tables[hashi] = cur->_next;
delete cur;
cur = nullptr;
return true;
}
cur = cur->_next;
}
return false;
}外层还是套：
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, K, Hash, setkov<K>> ht;
typedef struct HashNode<K> Node;
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
private:
ht _t;
};
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
typedef HashTable<K, pair<K, V>, Hash, mapkov<K, V>> ht;
typedef struct HashNode<pair<K,V>> Node;
public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
private:
ht _t;
};
四、源码了解iterator的实现
set
map
还是那个道理噢，其实外面没啥可看的，不管是类型还是方法都是调的底层的哈希表的，所以最重要的点就是研究清楚哈希表的泛型编程。
//源码
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef Value& reference;
typedef Value* pointer;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};不难找到成员变量：
node* cur;
hashtable* ht;
node*的cur倒是可以理解，咋还弄了一个hashtable*的ht呢？
光看这里还是不知道为啥，还是得找找到底哪里用这个玩意了：
//源码
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
const node* old = cur;
cur = cur->next;
if (!cur) {
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size())
cur = ht->buckets[bucket];
}
return *this;
}结果iterator里放眼望去都没有用的，迭代器没有找到的方法实现就只有这个玩意了。
底层有个bkt_num不知道啥玩意：
//类内
private:
vector<node*,Alloc> buckets;
//类外
size_type bkt_num_key(const key_type& key) const
{
return bkt_num_key(key, buckets.size());
}
size_type bkt_num(const value_type& obj) const
{
return bkt_num_key(get_key(obj));
}不是我说，太能套了，当然，人家可能有什么效率或者开发架构的要求。
所以operator++大概啥意思呢？
如果cur的next不为空，operator++就是直接去找下一个结点就行了。
如果cur的next为空，那你理想状态下肯定是去找下一个哈希表存储结点不为nullptr的地方。
源码里给出来的解决方案就是拿到哈希表的指针，有了它以后就能访问到底层的vector，取出来vector底层size，其实也就是哈希表的M，之后进入循环，直到找到第一个哈希表存储结点不为空的地方。
之后其它的操作就没啥可讲的了：
单向迭代器也不用去管啥--；
逻辑运算符和operator*、operator->其实还是那个意思，没啥可说的。
包括之前红黑树实现迭代器封装，重点其实都是operator++的实现。
五、实现iterator
重点还是底层哈希表实现迭代器，所以我就话不多说了，先完善它去。
1.完善哈希表iterator
template <class K, class T, class Hash, class KeyOfValue>
class HashTable;
template <class K,class T,class Hash,class KeyOfValue>
struct Iterator
{
typedef struct HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfValue> ht;
typedef Iterator<K, T, Hash, KeyOfValue> Self;
Iterator(Node* node,ht* t)
:_node(node)
,_t(t)
{}
Node* _node;
ht* _t;
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
bool operator==(const Self& it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
};
先把简单的大致写一写。
有几个因为ht*导致的麻烦事：
Iterator由于需要创建ht*，搞的模板参数长的很，本来其实只存个T就行；
由于需要ht*，得前置声明哈希表，否则编译器向上查找找不到；
逻辑运算符一定是两个迭代器对象相比较，有this指针才一个迭代器对象，还得再写一个对象，但是直接类模板写上去也不行，必须实例化才能当作类型用，索性我就又typedef了一下，弄了个Self。
Self operator++()
{
int hashi = Hash()(KeyOfValue()(_node->_data)) % _t->_tables.size();
_node = _node->_next;
if (!_node)
{
size_t i = hashi + 1;
for (i; i < _t->_tables.size(); i++)
{
if (_t->_tables[i])
{
_node = _t->_tables[i];
break;
}
}
if (i == _t->_tables.size())
_node = nullptr;
}
return *this;
} operator++
重点还是实现++逻辑。
代码思路：
如果_node->_next不为空也不用麻烦了，直接_node = next就行；
如果为空，那就需要去找哈希表里下一个不为空的位置，在此条件下本来一个for循环就够了，但是极端条件下：
如果从这里进入operator++的逻辑，_node->_next == nullptr，往后找，根本进不去for循环，所以再if一下包括这个情况，用nullptr代表哈希表遍历到end了。
大致哈希表底层iterator就是这样的：
template <class K, class T, class Hash, class KeyOfValue>
class HashTable;
template <class K,class T,class Hash,class KeyOfValue>
struct Iterator
{
typedef struct HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfValue> ht;
typedef Iterator<K, T, Hash, KeyOfValue> Self;
Iterator(Node* node,ht* t)
:_node(node)
,_t(t)
{}
Iterator(const Self& it)
:_node(it._node)
, _t(it._t)
{}
Node* _node;
ht* _t;
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
Self operator++()
{
int hashi = Hash()(KeyOfValue()(_node->_data)) % _t->_tables.size();
_node = _node->_next;
if (!_node)
{
size_t i = hashi + 1;
for (i; i < _t->_tables.size(); i++)
{
if (_t->_tables[i])
{
_node = _t->_tables[i];
break;
}
}
if (i == _t->_tables.size())
_node = nullptr;
}
return *this;
}
Self operator++(int)
{
Iterator temp(*this);
++(*this);
return temp;
}
bool operator==(const Self& it)const
{
return _node == it._node;
}
bool operator!=(const Self& it)const
{
return _node != it._node;
}
};
现在编译倒是没毛病，但是之前说过，模板的实例化可不是说只要你给类实例化它就会把所有的内容给实例化，用到的才会实例化，因此呢，该写写，最后测试用到才知道写的有效没有，现在不能断言写的就一定是对的。
2.实现哈希表接口
Iterator Begin()
{
for (size_t i = 0; i < _tables.size(); i++)
if (_tables[i])
return{ _tables[i],this };
return End();
}
Iterator End()
{
return { nullptr,this };
}begin就是找不为空的第一个结点，有可能哈希表为空，为空return end；
以_node == nullptr作为找到末尾的标志。
3.外层map和set封装
typedef typename ht::Iterator iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}其实map和set的迭代器以及与迭代器相关接口都是底层哈希表的实现，只不过为了接口一致，typedef了一下Iterator，并且实现与其他容器迭代器一致的接口。
另外就是再次强调：
这种类域+域访问修饰符可能取出来静态成员也可能取出来类型，如果是成员那不能typedef，所以为了编译器那里过的去，加一个typename，相当于前置声明告诉编译器这就是类型，不用担心。
4.测试代码
写这句话的时候我还没有写测试代码，但是我就提前说，这玩意指不定出啥bug，毕竟我们测试代码中没有用迭代器，迭代器根本就不会被实例化，所以就算有bug，之前没参与编译也检查不出来，做好修bug的心理准备。
测试set没炸竟然，我都做好炸的准备了。
不过也别高兴的太早，map我们的测试样例用的是string，字典场景测试，还不一定能跑的通呢：
还没毛病，666，走狗屎运了。
5.实现const_iterator
说难也不难：
现在我们写的迭代器都支持修改key，key怎么能被允许修改呢，这不是找事呢嘛。
思路：
还是先整底层哈希表的，再在外层封装。
6.底层哈希表Const_Iterator
typedef Iterator<K, T, T&, T*, Hash, KeyOfValue> Iterator;
typedef Iterator<K, T, const T&, const T*, Hash, KeyOfValue> Const_Iterator;
我上来定义了个这，然后出bug，看半天没看出来啥意思。
为啥这么奇怪呢？
最后我是问来又问去，最后得到了一个结论，命名问题，如果Iterator<>在上面已经被typedef过了，到下面自然而然编译器就直接当成完整的类型使用，那我们第二行的typedef就炸了，已经实例化的类型咋还实例化呢？
所以为了杜绝这个命名问题：
template <class K, class T, class Hash, class KeyOfValue>
class HashTable;
template <class K,class T,class Ref,class Ptr,class Hash,class KeyOfValue>
struct HTIterator
{
typedef struct HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfValue> ht;
typedef HTIterator<K, T, Ref, Ptr, Hash, KeyOfValue> Self;
HTIterator(Node* node,ht* t)
:_node(node)
,_t(t)
{}
HTIterator(const Self& it)
:_node(it._node)
, _t(it._t)
{}
Node* _node;
ht* _t;
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
Self& operator++()
{
int hashi = Hash()(KeyOfValue()(_node->_data)) % _t->_tables.size();
_node = _node->_next;
if (!_node)
{
size_t i = hashi + 1;
for (i; i < _t->_tables.size(); i++)
{
if (_t->_tables[i])
{
_node = _t->_tables[i];
break;
}
}
if (i == _t->_tables.size())
_node = nullptr;
}
return *this;
}
Self operator++(int)
{
HTIterator temp(*this);
++(*this);
return temp;
}
bool operator==(const Self& it)const
{
return _node == it._node;
}
bool operator!=(const Self& it)const
{
return _node != it._node;
}
};
typedef HTIterator<K, T, T&, T*, Hash, KeyOfValue> Iterator;
typedef HTIterator<K, T, const T&, const T*, Hash, KeyOfValue> Const_Iterator;
7.外层套壳
set
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
typedef HashTable<K, K, Hash, setkov<K>> ht;
typedef struct HashNode<K> Node;
public:
typedef typename ht::Const_Iterator iterator;
typedef typename ht::Const_Iterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin()const
{
return _t.Begin();
}
const_iterator end()const
{
return _t.End();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
private:
ht _t;
};map
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
typedef HashTable<K, pair<const K, V>, Hash, mapkov<K, V>> ht;
typedef struct HashNode<pair<const K,V>> Node;
public:
typedef typename ht::Iterator iterator;
typedef typename ht::Const_Iterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin()const
{
return _t.Begin();
}
const_iterator end()const
{
return _t.End();
}
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
Node* Find(const K& key)
{
return _t.Find(key);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
private:
ht _t;
};
之后就是经典问题：
如果直接简单对源码进行思路复制，让set的迭代器都是const迭代器，对于const对象毫无影响；
对于非const对象：
底层调用的是哈希表的非const接口，非const接口返回的是Iterator，但是我们要的是Const_Iterator，也就是：
所以为了方便实现，我们做的操作是：
迭代器还是一对一，直接从最根源限制key不能修改。
同理map里也是：
8.测试代码
一旦调用：
template<class Container>
void Printus(const Container& con)
{
auto it = con.begin();
while (it != con.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
抽不抽象，根本没搞initializer list啊。
瞅瞅去：
直接说结论噢，因为能看出来一眼就看出来了，看不出来就只能是一头雾水。
多参数构造函数可以走隐式类型转换，但是如果是const对象，比如const set，那么set底层的hashtable也是const ht，所以this指针是const ht* const this类型的，传给ht* _t能行吗，const到非const，权限的放大。
加上const就都过了，毕竟ht*在迭代器中的作用确实就是访问底层容器得到size，其实也就是只读，不管是const迭代器还是非const迭代器，都可以设置成const ht*。
六、基于iterator完善接口
1.insert方法
有了迭代器以后insert方法的返回值就可以变成最终形态了：
pair<Iterator,bool> Insert(const T& data)
{
Iterator it = Find(kov(data));
if (it != End())
return { it,false };
//扩容
if (_n == _tables.size())
{
HashTable<K,T,Hash,KeyOfValue> newtable;
newtable._tables.resize(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
while (_tables[i])
{
int hashi = hash(kov(_tables[i]->_data)) % newtable._tables.size();
Node* next = _tables[i]->_next;
//newtable[hashi] _tables[i]
_tables[i]->_next = newtable._tables[hashi];
newtable._tables[hashi] = _tables[i];
_tables[i] = next;
}
}
_tables.swap(newtable._tables);
}
//插入
int hashi = hash(kov(data)) % _tables.size();
//_tables[hashi] newnode
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { {newnode,this},true };
}
套壳
//set
pair<iterator,bool> insert(const K& key)
{
return _t.Insert(key);
}
//map
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}2.find方法
Iterator Find(const K& key)
{
int hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kov(cur->_data) == key)
return { cur,this };
cur = cur->_next;
}
return { nullptr,this };
}
Const_Iterator Find(const K& key)const
{
int hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kov(cur->_data) == key)
return { cur,this };
cur = cur->_next;
}
return { nullptr,this };
}套壳
//set
iterator Find(const K& key)
{
return _t.Find(key);
}
const_iterator Find(const K& key)const
{
return _t.Find(key);
}
//map
iterator find(const K& key)
{
return _t.Find(key);
}
const_iterator find(const K& key)const
{
return _t.Find(key);
}
没啥可说的。
3.operator[]
有了pair<iterator,bool>的insert，搞个operator[]轻而易举：
V& operator[](const K& key)
{
return (*(insert({ key,V() }).first)).second;
}
测试代码：
还是测试老三样：插入；修改；插入+修改。
七、补充unordered系列接口
实际中使用容器我们一般用不到这些接口，仅作了解即可。
1.bucket_count
我们自己已经了解了，哈希桶方式解决冲突，并且用哈希桶实现了unordered系列的容器。
看见这个名字就毫无疑问了，代表当前桶的个数，其实大概率也就是底层vector的size。
另外有个max的，其实跟max_size一个道理，算理论能有多少个桶，其实没啥价值也。
2.bucket_size
一看就理解了，给下标，返回对应桶里面有多少个元素、
3.bucket
给个key，返回这个key在第几个桶，返回下标。
4.load_factor
返回底层负载因子大小。
返回哈希桶最大能到的负载因子的大小，因为负载因子超过一定界限就得扩容，所以这个算是扩容的标志，通过这个接口我们可以知道底层设计的策略，实际用起来当然也没啥用。
5.reserve
日常用的到的其实也就是这个接口，基本可以类比以前的reserve，就是大致知道存多少数据，提前开好空间。
不过注意这里的说法：
如果n比现在哈希桶的个数*负载因子大，其实也就是什么，当前实际能存储的元素个数大，扩容；
如果n比现在的还小，跟以前一个道理，也不会说去缩容。
6.rehash
这个接口与reserve接口高度类似，也是提前开空间的接口。
不同点在于这玩意与n作比较的时候不管负载因子，直接跟bucket_count，桶的个数比，其实这样看来的话这个接口没有reserve合适，毕竟插入得考虑负载因子，可能造成扩容，如果reserve的时候不管的话，有可能后面还是得扩容。
比如极端一点的例子，0.1的负载因子，内存不要钱一样，现在目标是存10000个数。10000个哈希桶实际上就只让存1000个数据，如果插入10000个数据，也就减少了几次扩容，不能不扩容，所以reserve的根据负载因子计算才是正确的，如果是reserve直接就开100000个哈希桶了。
不过补充的接口都可以不管，一般用不上，真用上查文档即可。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
18
0- 0
已为社区贡献14条内容
所有评论(0)