【STL】用一张哈希表封装unordered_set和unordered_map

哈希表源代码

这里是使用开散列实现的哈希表,为了和库里的哈希表进行区分,我将哈希表放入到了命名空间中

//确保取余运算符两边是正整数,下标不能是负整数
template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//模板的特化, 让哈希表可以使用string类型
template<>
struct DefaultHashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){//使用上一个ASCII码乘以131,避免得到相同的值,注意并不能完全避免,如果数据量大还是会有相同的数hash = hash * 131 + ch;}return hash;}
};//开散列:拉链法/哈希桶
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 HashFunc>class HashTable;//哈希表迭代器(单向迭代器)template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc = DefaultHashFunc<K>>struct __Hash_iterator{typedef HashNode<T> Node;typedef __Hash_iterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;typedef __Hash_iterator<K, T, T&, T*, KeyOfT> iterator;typedef __Hash_iterator<K, T, const T&, const T*, KeyOfT> iterator;Node* _node;//HashTable<K, T, KeyOfT, HashFunc>* _pht;const HashTable<K, T, KeyOfT, HashFunc>* _pht;//为了可以使用const迭代器我们使用const类型接收__Hash_iterator(const iterator& it):_node(it._node),_pht(it._pht){}__Hash_iterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){if (_node->next){_node = _node->next;return *this;}else{KeyOfT kot;HashFunc kov;size_t Hashi = kov(kot(_node->_data)) % _pht->_table.size();++Hashi;while (Hashi < _pht->_table.size()){if (_pht->_table[Hashi]){_node = _pht->_table[Hashi];return *this;}++Hashi;}}_node = nullptr;return *this;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}};size_t GetNextPrime(size_t prime){static const int PRIMECOUNT = 28;static const unsigned long primeList[PRIMECOUNT] ={53,         97,         193,       389,       769,1543,       3079,       6151,      12289,     24593,49157,      98317,      196613,    393241,    786433,1572869,    3145739,    6291469,   12582917,  25165843,50331653,   100663319,  201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i = 0;for (; i < PRIMECOUNT; ++i){if (primeList[i] > prime)return primeList[i];}return primeList[i];}template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<T> Node;//友元声明。类模板也需要写,注意和前置声明一样不能有缺省值template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>friend struct __Hash_iterator;public:typedef __Hash_iterator<K, T, T&, T*, KeyOfT> iterator;typedef __Hash_iterator<K, T, const T&, const T*, KeyOfT> const_iterator;iterator begin(){size_t Hashi = 0;while (_table[Hashi] == nullptr)++Hashi;return iterator(_table[Hashi], this);}const_iterator begin() const{size_t Hashi = 0;while (_table[Hashi])++Hashi;return const_iterator(_table[Hashi], this);}iterator end(){return iterator(nullptr, this);}const_iterator end() const//const * const this{//这里的this指针被加了const,我们手动加上的const是修饰this指向的内容,所以在迭代器类中我们需要使用一个const类型的参数接收,不然会导致类型不一致//如果const修饰的this指针本身的话就没事,因为在迭代器类中我们只需要去读它并不需要去写它return const_iterator(nullptr, this);}HashTable(){_table.resize(10, nullptr);}HashTable(const HashTable<K, T, KeyOfT, HashFunc>& H){HashFunc kov;KeyOfT kot;size_t n = H._table.size();_table.resize(n);for (size_t i = 0; i < n; ++i){Node* cur = H._table[i];while (cur){size_t Hashi = kov(kot(cur->_data)) % n;Node* newnode = new Node(H._table[Hashi]->_data);//头插newnode->next = _table[i];_table[i] = newnode;cur = cur->next;}}}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->next;delete cur;cur = next;}_table[i] = nullptr;}}iterator Find(const K& key){HashFunc kov;KeyOfT kot;size_t Hashi = kov(key) % _table.size();Node* cur = _table[Hashi];while (cur != nullptr){Node* next = cur->next;if (kot(cur->_data) == key)return iterator(cur, this);cur = next;}return end();}pair<iterator, bool> insert(const T& data){HashFunc kov;KeyOfT kot;if (Find(kot(data))._node)return make_pair(Find(kot(data)), false);//负载因子处理扩容//为1进行扩容if (_n == _table.size()){size_t newSize = GetNextPrime(_table.size());vector<Node*> newtable;newtable.resize(newSize, nullptr);//哈希桶上链接的结点位置是任意的,头插,尾插都可以for(size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];//将cur上哈希桶的每个结点都给链接到_table上//将旧哈希桶上的元素重新映射到新哈希表上while (cur){Node* next = cur->next;size_t Hashi = kov(kot(cur->_data)) % newSize;//头插操作,将cur理解为一个新结点头插到这个newtable上cur->next = newtable[Hashi];newtable[Hashi] = cur;cur = next;}}_table.swap(newtable);}size_t hashi = kov(kot(data)) % _table.size();//头插Node* newnode = new Node(data);newnode->next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}bool erase(const K& key){if (Find(key) == nullptr)return false;HashFunc kov;KeyOfT kot;size_t Hashi = kov(key) % _table.size();Node* cur = _table[Hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[Hashi] = cur->next;}else{prev->next = cur->next;}delete cur;return true;}prev = cur;cur = cur->next;}return false;}private:vector<Node*> _table;size_t _n = 0;};
}

1.创建unordered_set和unordered_map,unordered_set和unordered_map分别是Key,Key模型和Key,Value模型,使用一张哈希表封装这两个的容器的话,我们需要同时兼容这两种模型

哈希表的结点类

这里为了能根容易的兼容set和map,我们将结点类的模板参数从 K V 改为了T,至于为什么改为一个模板参数,我们来看看后面的设计

template<class T>
struct HashNode
{T _data;HashNode<T>* next;HashNode(const T& data):_data(data),next(nullptr){}
};

哈希表类

由于我们改变了模板类的模板参数,为了更好的配合结点类,这里我们将哈希表的第二个模板参数

也改为T

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{typedef HashNode<T> Node;
public://...
private:vector<Node*> _table;size_t _n; //哈希表中有效元素的个数
}

map 

哈希表的上层容器如果是map,那么哈希表模板参数接收的类型就是Key和Value组成的键值对

template<class K, class V>
class UnOrderMap
{struct MapKeyOfT{const K& operator()(const pair<K, V>& key){return key.first;}};
public://...
private:Hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _t;
};

set

哈希表的上层容器如果是set,那么哈希表模板参数接收的类型就是Key和Key组成的键值对

template<class K>
class UnOrderSet
{struct MapKeyOfT{const K& operator()(const K& key){return key;}};
public://...
private:Hash_bucket::HashTable<K, K, SetKeyOfT> _t;
};

从上图可以看到,模板参数T的类型是由它的上层容器所决定的,至于这里unordered_set和unordered_map为什么需要单独的传给哈希表仿函数,因为对于底层的哈希表而言它并不知道它将会接收什么样类型由于这个问题,我们干脆直接在它的上层容器中创建一个仿函数,使用unordered_set时就传给它set的仿函数,利用这个仿函数拿到unordered_set的Key值并且使用它,同理unordered_map也是一样

其实对于unordered_set而言它是Key, Key类型,处理不处理都一样,创建仿函数的主要原因是因为unordered_map传入哈希表中T实例化的类型是Key-Value的键值对,在底层哈希表中时我们大部分场景都需要使用它的Key值,由于这个原因,我们给unordered_map创建了仿函数,为了接收unordered_map的仿函数,底层的哈希表不得不增加模板参数来接收,这时如果unordered_set不传也不合适,所以为了将就unordered_map,unordered_set也创建了一个仿函数来配合

哈希表迭代器的创建

这里的思路:先处理好哈希表的迭代器,然后处理unordered_map,unordered_set的迭代器

哈希表迭代器的前置++

创建哈希表迭代器需要用到两个元素,使其向后寻找下一个位置

1.链表指针:遍历哈希桶找到它的下一个结点,所以需要它的指针

2.哈希表指针:当所给指针的下一个位置为空时,我们需要继续向后遍历哈希表,寻找其下一个位置,直到哈希表为空结束,所以哈希表指针的作用就是定位到该桶所在位置的下标往后找下一个位置

情况一:所给结点下一个位置不为空

情况二:当所给结点下一个位置为空时

情况三:一直遍历到最后都没有找到,我这里的处理是直接返回nullptr

说明一下迭代器器所需要的模板参数,因为我们需要使用哈希表指针,哈希表的模板参数需要全带过来,然后再加上迭代器所需要的参数,一叠加这里就有六个模板参数

迭代器代码实现

其他的实现都比较简单这里就全部给出来了

//哈希表迭代器(单向迭代器)
template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
struct __Hash_iterator
{typedef HashNode<T> Node;typedef __Hash_iterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;Node* _node;HashTable<K, T, KeyOfT, HashFunc>* _pht;__Hash_iterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){if (_node->next){_node = _node->next;return *this;}else{KeyOfT kot;HashFunc kov;size_t Hashi = kov(kot(_node->_data)) % _pht->_table.size();++Hashi;while (Hashi < _pht->_table.size()){if (_pht->_table[Hashi]){_node = _pht->_table[Hashi];return *this;}++Hashi;}}_node = nullptr;return *this;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}
};

普通迭代器

begin()

遍历哈希表找到第一个不为空的结点即可

iterator begin()
{size_t Hashi = 0;while (_table[Hashi] == nullptr)++Hashi;return iterator(_table[Hashi], this);
}

end()

使用nullptr构造一个end迭代器就可以了

iterator end()
{return iterator(nullptr, this);
}

const迭代器

begin()

const_iterator begin() const
{size_t Hashi = 0;while (_table[Hashi])++Hashi;return const_iterator(_table[Hashi], this);
}

end()

我们知道再接口右侧增加const代表这里的this指针被加了const,我们手动加上的const是修饰this指向的内容,所以在迭代器类中我们需要使用一个const类型的参数接收,不然会导致类型不一致而报错,(它默认的const修饰的是this指针本身)

const_iterator end() const
//const * const this
{return const_iterator(nullptr, this);
}

对迭代器类的修改:

template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
struct __Hash_iterator
{typedef HashNode<T> Node;typedef __Hash_iterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;__Hash_iterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}//...
};

我们只需要在哈希表类型前面加上cons,加上const之后我们即可传const类型也可以传普通类型正好符合我们的需求(在迭代器类中我们需要一个哈希表指针,它在该类中的作用只需要可读就行并不需要写,加上const反而更好)

迭代器创建好了之后会引发几个问题,第一个问题 哈希表中使用迭代器,迭代器里有哈希表会造成迭代器和哈希表的互相依赖,在使用迭代器类时需要实例化哈希表类,反之,也是同理

如下图所示:

解决方法:使用 前置说明 告诉编译器我的某个类定义过

//解决迭代器和哈希表互相依赖问题
//前置声明(告诉编译器我的这个类定义过)
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
struct __Hash_iterator
{typedef HashNode<T> Node;typedef __Hash_iterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;__Hash_iterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}//...
};

注意:前置声明的参数不能带缺省值

第二个问题,我们使用前置声明之后,_pht确实能实例化了,但是它的_table成员是私有的,在迭代器类中不可使用,所以我们需要在哈希表类中进行迭代器类的友元声明

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{typedef HashNode<T> Node;//友元声明。类模板也需要写template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>friend struct __Hash_iterator;public:typedef __Hash_iterator<K, T, T&, T*, KeyOfT> iterator;typedef __Hash_iterator<K, T, const T&, const T*, KeyOfT> const_iterator;//...
};

注意:和前置声明一样不能有缺省值

unordered_set和unordered_map中迭代器的实现

unordered_set

为了防止set的Key值被修改,这里我们将它的普通迭代器也设置为const迭代器

template<class K>
class UnOrderSet
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}//...
private:Hash_bucket::HashTable<K, K, SetKeyOfT> _t;
};

unordered_map

和unordered_set一样为防止set被修改,这里我们也做了细节处理,将pair类型中的K加上了const,这样来既防止Key值被修改了又可以通过迭代器来修改value值

template<class K, class V>
class UnOrderMap
{struct MapKeyOfT{const K& operator()(const pair<K, V>& key){return key.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>::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();}//...
private:Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _t;
};

unrodered_map和unordered_set insert实现

unordered_set

pair<iterator, bool> insert(const K& key)
{ pair<typename Hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _t.insert(key);return pair<iterator, bool>(ret.first, ret.second); //利用pair的构造函数
}

其实还有第二种写法:

pair<iterator, bool> insert(const K& key)
{ return _t.insert(key); //使用这种方法需要在迭代器中实现(普通迭代器转const迭代器)
}

这里涉及到一个类型转换,普通迭代器转换为const迭代器,实现这个功能需要我们在迭代器类中创建一个特殊的构造函数

便于理解,演示一段代码,为以上图示的简易版本:

template< class T, class Ref>
class A
{
public:A(Ref a):_a(a){}private:int _a; 
};int main()
{int x = 2;A<int, int&> a1(x);A<int, const int&> a2(2);A<int, const int&> a3 = a1;return 0;
}

加上这段代码之后,就可与实现普通迭代器和const迭代器的转换了

template< class T, class Ref>
class A
{
public:A(Ref a):_a(a){}A(const A<T, T&>& a) //参数是对象:_a(a._a){}int _a;
};int main()
{int x = 2;A<int, int&> a1(x);A<int, const int&> a2(2);A<int, const int&> a3 = a1;return 0;
}

注意:我们需要将_a设置为共有,因为 A<T, T&>模板类实例化之后是一个新的类,在这个类中使用A类的私有成员会报错

unrodered_map

pair<iterator, bool> insert(const pair<K, V>& key)
{return _t.insert(key);
}

unordered_map  operator[]的实现

V& operator[](const K& key)
{pair<iterator, bool> ret = _t.insert(make_pair(key, V()));return ret.first._node->_data.second;
}

使用一个哈希表封装unordered_map和unorder_set整体代码:

hash.h

//确保取余运算符两边是正整数,下标不能是负整数
template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//模板的特化, 让哈希表可以使用string类型
template<>
struct DefaultHashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){//使用上一个ASCII码乘以131,避免得到相同的值,注意并不能完全避免,如果数据量大还是会有相同的数hash = hash * 131 + ch;}return hash;}
};//开散列:拉链法/哈希桶
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 HashFunc>class HashTable;//哈希表迭代器(单向迭代器)template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc = DefaultHashFunc<K>>struct __Hash_iterator{typedef HashNode<T> Node;typedef __Hash_iterator<K, T, Ref, Ptr, KeyOfT, HashFunc> self;typedef __Hash_iterator<K, T, T&, T*, KeyOfT> iterator;typedef __Hash_iterator<K, T, const T&, const T*, KeyOfT> iterator;Node* _node;//HashTable<K, T, KeyOfT, HashFunc>* _pht;const HashTable<K, T, KeyOfT, HashFunc>* _pht;//为了可以使用const迭代器我们使用const类型接收__Hash_iterator(const iterator& it):_node(it._node),_pht(it._pht){}__Hash_iterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){if (_node->next){_node = _node->next;return *this;}else{KeyOfT kot;HashFunc kov;size_t Hashi = kov(kot(_node->_data)) % _pht->_table.size();++Hashi;while (Hashi < _pht->_table.size()){if (_pht->_table[Hashi]){_node = _pht->_table[Hashi];return *this;}++Hashi;}}_node = nullptr;return *this;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}};size_t GetNextPrime(size_t prime){static const int PRIMECOUNT = 28;static const unsigned long primeList[PRIMECOUNT] ={53,         97,         193,       389,       769,1543,       3079,       6151,      12289,     24593,49157,      98317,      196613,    393241,    786433,1572869,    3145739,    6291469,   12582917,  25165843,50331653,   100663319,  201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i = 0;for (; i < PRIMECOUNT; ++i){if (primeList[i] > prime)return primeList[i];}return primeList[i];}template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<T> Node;//友元声明。类模板也需要写,注意和前置声明一样不能有缺省值template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>friend struct __Hash_iterator;public:typedef __Hash_iterator<K, T, T&, T*, KeyOfT> iterator;typedef __Hash_iterator<K, T, const T&, const T*, KeyOfT> const_iterator;iterator begin(){size_t Hashi = 0;while (_table[Hashi] == nullptr)++Hashi;return iterator(_table[Hashi], this);}const_iterator begin() const{size_t Hashi = 0;while (_table[Hashi])++Hashi;return const_iterator(_table[Hashi], this);}iterator end(){return iterator(nullptr, this);}const_iterator end() const//const * const this{//这里的this指针被加了const,我们手动加上的const是修饰this指向的内容,所以在迭代器类中我们需要使用一个const类型的参数接收,不然会导致类型不一致//如果const修饰的this指针本身的话就没事,因为在迭代器类中我们只需要去读它并不需要去写它return const_iterator(nullptr, this);}HashTable(){_table.resize(10, nullptr);}HashTable(const HashTable<K, T, KeyOfT, HashFunc>& H){HashFunc kov;KeyOfT kot;size_t n = H._table.size();_table.resize(n);for (size_t i = 0; i < n; ++i){Node* cur = H._table[i];while (cur){size_t Hashi = kov(kot(cur->_data)) % n;Node* newnode = new Node(H._table[Hashi]->_data);//头插newnode->next = _table[i];_table[i] = newnode;cur = cur->next;}}}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->next;delete cur;cur = next;}_table[i] = nullptr;}}iterator Find(const K& key){HashFunc kov;KeyOfT kot;size_t Hashi = kov(key) % _table.size();Node* cur = _table[Hashi];while (cur != nullptr){Node* next = cur->next;if (kot(cur->_data) == key)return iterator(cur, this);cur = next;}return end();}pair<iterator, bool> insert(const T& data){HashFunc kov;KeyOfT kot;if (Find(kot(data))._node)return make_pair(Find(kot(data)), false);//负载因子处理扩容//为1进行扩容if (_n == _table.size()){size_t newSize = GetNextPrime(_table.size());vector<Node*> newtable;newtable.resize(newSize, nullptr);//哈希桶上链接的结点位置是任意的,头插,尾插都可以for(size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];//将cur上哈希桶的每个结点都给链接到_table上//将旧哈希桶上的元素重新映射到新哈希表上while (cur){Node* next = cur->next;size_t Hashi = kov(kot(cur->_data)) % newSize;//头插操作,将cur理解为一个新结点头插到这个newtable上cur->next = newtable[Hashi];newtable[Hashi] = cur;cur = next;}}_table.swap(newtable);}size_t hashi = kov(kot(data)) % _table.size();//头插Node* newnode = new Node(data);newnode->next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}bool erase(const K& key){if (Find(key) == nullptr)return false;HashFunc kov;KeyOfT kot;size_t Hashi = kov(key) % _table.size();Node* cur = _table[Hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[Hashi] = cur->next;}else{prev->next = cur->next;}delete cur;return true;}prev = cur;cur = cur->next;}return false;}private:vector<Node*> _table;size_t _n = 0;};
}

unordered_set

namespace HashSet
{template<class K>class UnOrderSet{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}//pair<const_iterator, bool>pair<iterator, bool> insert(const K& key){ //return _t.insert(key); //使用这种方法需要在迭代器中实现(普通迭代器转const迭代器)//模板实例化只需要类型就可以pair<typename Hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _t.insert(key);return pair<iterator, bool>(ret.first, ret.second); //利用pair的构造函数}private:Hash_bucket::HashTable<K, K, SetKeyOfT> _t;};
}

unordered_map

namespace HashMap
{template<class K, class V>class UnOrderMap{struct MapKeyOfT{const K& operator()(const pair<K, V>& key){return key.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>::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();}V& operator[](const K& key){pair<iterator, bool> ret = _t.insert(make_pair(key, V()));return ret.first._node->_data.second;}pair<iterator, bool> insert(const pair<K, V>& key){return _t.insert(key);}void Print(){_t.Print();}private:Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _t;};
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/34318.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

搜索二维矩阵 II

搜索二维矩阵 II 编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9…

嵌入式入门Day24

数据结构Day5 树形结构相关概念二叉树相关概念二叉树的状态二叉树性质二叉树的存储二叉树根据已有序列推出树的结构练习 算法相关概念算法特性算法的设计要求时间复杂度排序算法冒泡排序&#xff08;改良版&#xff09;选择排序&#xff08;O(n^2)&#xff09;直接插入排序&…

百度网盘qzxing-master.zip

qzxing 这是一个针对 ZXing 条形码图像处理库的 Qt/QML 封装库。 支持以下类型的条形码解码&#xff1a; UPC-AUPC-EEAN-8EAN-13ITFCode 39Code 93Code 128&#xff08;GS1&#xff09;Codabar二维码数据矩阵Aztec&#xff08;测试版&#xff09;PDF 417 支持以下类型的条形…

Ping32与天锐绿盾加密软件对比:哪款防泄密软件适合您的企业?

企业数据泄漏事故层出不穷&#xff0c;为了有效防止机密信息的泄露&#xff0c;选择一款合适的防泄密软件显得尤为重要。Ping32和天锐绿盾加密软件都是市场上比较受欢迎的防泄密工具&#xff0c;那么它们各自的优势和差异是什么呢&#xff1f;让我们一起来了解。 1. 安全性&…

PDF拆分之怎么对批量的PDF文件进行分割-免费PDF编辑工具分享

>>更多PDF文件处理应用技巧请前往 96缔盟PDF处理器 主页 查阅&#xff01; ——————————————————————————————————————— 当然了&#xff0c;单个文件或者其他任意的文件个数的拆分也是支持的&#xff01; 序言 我之前的文章也有…

简易url解码器(定义python单行函数工具)

被%编码的url如同天书&#xff0c;自拟一个单行函数解析还原&#xff0c;方便相认。 (笔记模板由python脚本于2024年12月05日 15:14:17创建&#xff0c;本篇笔记适合学习Url的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&…

JavaWeb项目打包、部署至Tomcat并启动的全程指南(图文详解)

前言 我们想要部署一个javaWeb项目到tomcat上&#xff0c;需要了解一些概念 什么是tomcat&#xff1f; Tomcat 是 Apache 软件基金会&#xff08;Apache Software Foundation&#xff09;下的一个开源项目&#xff0c;主要用于实现 Java Servlet、JavaServer Pages&#xff08;…

【笔记2-5】ESP32:freertos消息队列

主要参考b站宸芯IOT老师的视频&#xff0c;记录自己的笔记&#xff0c;老师讲的主要是linux环境&#xff0c;但配置过程实在太多问题&#xff0c;就直接用windows环境了&#xff0c;老师也有讲一些windows的操作&#xff0c;只要代码会写&#xff0c;操作都还好&#xff0c;开发…

亚马逊云科技大语言模型加速OCR应用场景发展

目录 前言Amazon Bedrock关于OCR解决方案Amazon Bedrock进行OCR关键信息提取方案注册亚马逊账号API调用环境搭建 总结 前言 大语言模型是一种基于神经网络的自然语言处理技术&#xff0c;它能够学习和预测自然语言文本中的规律和模式&#xff0c;可以理解和生成自然语言的人工…

贪心算法 part03

文章参考来源代码随想录 134. 加油站 方法一分类讨论&#xff1a; 情况一&#xff1a;如果gas的总和小于cost总和&#xff0c;那么无论从哪里出发&#xff0c;一定是跑不了一圈的 情况二&#xff1a;rest[i] gas[i]-cost[i]为一天剩下的油&#xff0c;i从0开始计算累加到最…

【JAVA练习】力扣860.柠檬水找零

题目&#xff1a; 解题思路&#xff1a; 可能面临3种面额&#xff0c; 5美元&#xff0c;不找还&#xff0c;5美元钞票数量加110美元&#xff0c;找还5美元&#xff0c;5美元钞票数量减1&#xff0c;10美元钞票加120美元&#xff0c;找还15美元&#xff0c;分为一张10美元 一…

Telnet不安全?如何配置使用更安全的STelnet远程登录华为AR1000V路由器?

在上一篇文章中&#xff0c;我们介绍了如何配置一台全新的AR1000V&#xff0c;来实现通过Telnet远程登录设备&#xff08;如何配置使用Telnet远程登录华为AR1000V路由器&#xff1f;&#xff09;。其实&#xff0c;在之前的文章中&#xff0c;我们已经介绍过Telnet是一种不安全…

UE----Ios打包笔记

UE 打包 IOS 软件 1.前期准备 1.1. 首先我们需要 一台装有Xcode 的MAC笔记本&#xff08;知道开机密码 最好是空的笔记本 剩余内存要大 &#xff09; 1.2. 一台IOS手机 1.3. 一个申请了开发者账户的 Apple ID (苹果账号) 知晓账号与密码最好 因为很麻烦 1.4. UE 需要 的 兼…

计算机毕业设计Python轨道交通客流预测分析可视化 智慧交通 机器学习 深度学习 人工智能 爬虫 交通大数据

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

windows10电脑缺少dll文件的解决方案,系统缺少dll修复指南

在使用Windows 10操作系统时&#xff0c;有时会遇到由于缺少某些动态链接库&#xff08;Dynamic Link Library, 简称DLL&#xff09;文件而导致程序无法正常运行的问题。本指南将介绍几种解决此类问题的方法。 什么是DLL文件&#xff1f; DLL文件是Windows系统中的一种特殊类型…

并发编程(15)——基于同步方式的线程安全的栈和队列

文章目录 十四、day141. 线程安全的栈1.1 存在隐患的栈容器1.2 优化后的栈容器 2. 线程安全的队列2.1 基于智能指针的线程安全的队列2.2 不同互斥量管理队首、队尾的队列 十四、day14 在并发编程&#xff08;1&#xff09;并发编程&#xff08;5&#xff09;中&#xff0c;我们…

装箱问题的三种解法

有一个箱子容量为V&#xff08;正整数&#xff0c;0≤v≤20000&#xff09;&#xff0c;同时有n个物品&#xff08;0< n ≤30&#xff09;&#xff0c;每个物品有一个体积&#xff08;正整数&#xff09;。 要求n个物品中&#xff0c;任取若干个装入箱内&#xff0c;使箱子的…

万物可爬(以爬取浏览器井盖图片为例)

我们以爬取 井盖图片 这个链接中的图片为例&#xff1a; 点击F12 并选中其中一张图片 &#xff0c;得到它的信息。具体如下&#xff1a;我们可以编写对应的正则表达式&#xff1a; <img[^>]*src"(.*?)"[^>]*alt"井盖图片 的图像结果"[^>]*&g…

【AI系统】轻量级CNN模型新进展

CNN 模型小型化&#xff08;下&#xff09; 在本文会接着介绍 CNN 模型的小型化&#xff0c;除了第二篇文章提到的三个模型外&#xff0c;在本章节会继续介绍 ESPNet 系列&#xff0c;FBNet 系列&#xff0c;EfficientNet 系列和 GhostNet 系列。 ESPNet 系列 ESPNetV1 ESP…

Day06:缓存持久化

缓存持久化 redis做为缓存&#xff0c;数据的持久化是怎么做的&#xff1f; 在Redis中提供了两种数据持久化的方式&#xff1a;1、RDB 2、AOF 方式一&#xff1a;RDB RDB(Redis Database Backup file)&#xff0c;redis数据备份文件&#xff0c;也叫Redis数据快照&#xff…