C++ STL : 模拟实现STL中的关联式容器unordered_map/unordered_set

unordered_map/unordered_set

C++ STL : 模拟实现STL中的关联式容器map和set

这次实现的unordered_map/unordered_set的具体思路和实现的map/set思路差不多，只不过是将底层的数据结构从红黑树修改为哈希桶，因为数据结构的修改，其特性也发生了变化。

unordered_map/unordered_set与map/set的区别

相同点：

都是关联型容器，存储的是以<key, value>的键值对pair

不同点：

底层数据结构。unordered_map/unordered_set的底层容器是哈希桶，map和set底层是红黑树数据是否有序。因为unordered_map/unordered_set的底层容器是哈希桶，数据都是通过映射关系来存储，这就导致了数据是无序的。而map和set底层是红黑树，所以可以通过中序遍历来获取有序的数据。数据访问时间。unordered_map/unordered_set因为其是通过映射关系来存储，所以效率为O（1）。map/set为O（logN）

底层哈希桶的改造

仿函数

在模板中提供了4个模板参数，分别是key值类型、数据类型、key值的获取方法、hash（key）的获取方法

template<class K, class T, class KeyofT, class Hash>

Key值的获取方法

因为需要考虑到代码复用的问题，用一个哈希桶来实现K模型的unordered_set和KV模型的unordered_map。并且对于某些自定义类型作为参数，也需要考虑如何从他传的参数中获取key值，就需要增加一个模板参数，来让使用者自行提供从数据中获取key值的方法。

下面就拿map和set的举例子。

map

struct MapKeyOfValue{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};

set

struct SetKeyOfValue{const K& operator()(const K& key){return key;}};

hash（key）的转换方法

如果key的类型为整型的话还好说，可以直接用来进行哈希函数的映射。但是如果是其他的一些无法进行整型算数运算的类型或者极为庞大的数据，如常用的string或者大数等类型，就需要一种方法来将其转换为可以计算的整型值，但是对于自定义类型我们并不能知道他的转换方法，所以就需要提供一个仿函数，让使用者自行提供转换的方法。

因为常用的key一般都是string和int，这里我就给了默认的整型处理方法以及string的特化方法

template<class K>struct _Hash{const K& operator()(const K& key){return key;}};template<>struct _Hash<std::string>{size_t operator()(const std::string& key){//BKDR字符串哈希函数size_t hash = 0;for (size_t i = 0; i < key.size(); i++){hash *= 131;hash += key[i];}return hash;}};

迭代器

迭代器的实现非常容易，值得一提的就是++的重载。

如果迭代器当前所在的桶中的下一个位置不为空，则直接返回下一个位置。而下一个位置为空，则说明当前桶为空，就需要去到下一个桶中遍历数据。但是光光依靠迭代器是无法获取下一个桶的位置的，所以我就加入了一个哈希桶指针，这样就可以通过指针获取桶的哈希函数来计算出当前映射位置，再通过访问映射位置来找到下一个存有数据的桶，就可以计算出下一个位置。

template<class K, class T, class KeyOfT, class Hash>struct __HashTableIterator{typedef HashNode<T> Node;typedef HashBucket<K, T, KeyOfT, Hash> HB;typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;__HashTableIterator(Node* node, HB* hb): _node(node), _phb(hb){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){//如果下一个节点不为空，直接返回下一个if (_node->_next){_node = _node->_next;}//如果下一个为空，则走到下一个表中else{//通过获取当前数据的key来判断下一个数据的位置KeyOfT koft;size_t pos = _phb->HashFunc(koft(_node->_data));++pos;for (; pos < _phb->_table.size(); pos++){Node* cur = _phb->_table[pos];//如果下一个桶的数据不为空，则返回桶的第一个节点if (cur != nullptr){_node = cur;return *this;}}//剩下的桶都没有数据_node = nullptr;}return *this;}Self operator++(int){Self temp = *this;++this;return temp;}bool operator != (const Self& s){return _node != s._node;}bool operator == (const Self& s){return _node == s._node;}Node* _node;HB* _phb;};

完整代码

#pragma once#include<vector>#include<string>namespace lee{//算法科学家总结出的一个增容质数表，按照这样增容的效率更高const int PRIMECOUNT = 28;const size_t primeList[PRIMECOUNT] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 26611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};/*因为哈希函数的常用方法如直接定地、除留余数、平方取中等方法需要用的key值为整型，而大部分时候我们的key都是string，或者某些自定义类型，这个时候就可以提供一个仿函数的接口给外部，让他自己处理如何将key转换成我们需要的整型*/template<class K>struct _Hash{const K& operator()(const K& key){return key;}};template<>struct _Hash<std::string>{const size_t & operator()(const std::string& key){//BKDR字符串哈希函数size_t hash = 0;for (size_t i = 0; i < key.size(); i++){hash *= 131;hash += key[i];}return hash;}};template<class K>struct SetKeyOfT{const K& operator()(const K& key){return key;}};template<class T>struct HashNode{HashNode(const T& data = T()): _data(data), _next(nullptr){}T _data;HashNode<T>* _next;};template<class K, class T, class KeyofT, class Hash>class HashBucket;template<class K, class T, class KeyOfT, class Hash>struct __HashTableIterator{typedef HashNode<T> Node;typedef HashBucket<K, T, KeyOfT, Hash> HB;typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;__HashTableIterator(Node* node, HB* hb) : _node(node), _phb(hb){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){//如果下一个节点不为空，直接返回下一个if (_node->_next){_node = _node->_next;}//如果下一个为空，则走到下一个表中else{//通过获取当前数据的key来判断下一个数据的位置KeyOfT koft;size_t pos = _phb->HashFunc(koft(_node->_data));++pos;for (; pos < _phb->_table.size(); pos++){Node* cur = _phb->_table[pos];//如果下一个桶的数据不为空，则返回桶的第一个节点if (cur != nullptr){_node = cur;return *this;}}//剩下的桶都没有数据_node = nullptr;}return *this;}Self operator++(int){Self temp = *this;++this;return temp;}bool operator != (const Self& s){return _node != s._node;}bool operator == (const Self& s){return _node == s._node;}Node* _node;HB* _phb;};template<class K, class T, class KeyofT = SetKeyOfT<T>, class Hash = _Hash<K>>class HashBucket{public:typedef __HashTableIterator<K, T, KeyofT, Hash> iterator;typedef HashNode<T> Node;friend struct iterator;HashBucket(size_t capacity = 10): _table(capacity), _size(0){}~HashBucket(){Clear();}iterator begin(){//找到第一个节点for (size_t i = 0; i < _table.size(); i++){//如果节点不为空则返回if (_table[i]){return iterator(_table[i], this);}}return iterator(nullptr, this);}//因为在STL中哈希桶的底层是单链表的结构，所以不支持--操作，end就直接给一个空即可iterator end(){return iterator(nullptr, this);}size_t getNextPrime(size_t num){size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){//返回比那个数大的下一个质数 if (primeList[i] > num){return primeList[i];}}//如果比所有都大，还是返回最后一个，因为最后一个已经是32位最大容量return primeList[PRIMECOUNT - 1];}size_t HashFunc(const K& key){Hash hash;return hash(key) % _table.size();}std::pair<iterator, bool> Insert(const T& data){KeyofT koft;/*因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多，随着数据的增多，就可能会导致某一个桶过重，使得效率过低。所以最理想的情况，就是每个桶都有一个数据。这种情况下，如果往任何一个地方插入，都会产生哈希冲突，所以当数据个数与桶的个数相同时，也就是负载因子为1时就需要进行扩容。*/if (_size == _table.size()){//按照素数表来增容size_t newSize = getNextPrime(_table.size());size_t oldSize = _table.size();std::vector<Node*> newTable(newSize);_table.resize(newSize);//接着将数据重新映射过去for (size_t i = 0; i < oldSize; i++){Node* cur = _table[i];while (cur){//重新计算映射的位置size_t pos = HashFunc(koft(cur->_data));//找到位置后头插进对应位置Node* next = cur->_next;cur->_next = newTable[pos];newTable[pos] = cur;cur = next;}//原数据置空_table[i] = nullptr;}//直接和新表交换，交换过去的旧表会和函数栈帧一块销毁。_table.swap(newTable);}size_t pos = HashFunc(koft(data));Node* cur = _table[pos];//因为哈希桶key值唯一，如果已经在桶中则返回falsewhile (cur){if (koft(cur->_data) == koft(data)){return std::make_pair(iterator(cur, this), false);}else{cur = cur->_next;}}//检查完成，此时开始插入，这里选择的是头插，这样就可以减少数据遍历的次数。Node* newNode = new Node(data);newNode->_next = _table[pos];_table[pos] = newNode;++_size;return std::make_pair(iterator(newNode, this), true);}iterator Erase(const K& key){KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];Node* prev = nullptr;while (cur){if (koft(cur->_data) == key){iterator ret(cur, this);++ret;//如果要删除的是第一个节点，就让下一个节点成为新的头节点，否则直接删除。if (prev == nullptr){_table[pos] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return ret;}else{prev = cur;cur = cur->_next;}}return end();}iterator Find(const K& key){KeyofT koft;size_t pos = HashFunc(key);Node* cur = _table[pos];while (cur){if (koft(cur->_data) == key){return iterator(cur, this);}else{cur = cur->_next;}}return end();}void Clear(){//删除所有节点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;}}private:std::vector<Node*> _table;size_t _size;};};

unordered_set

文档介绍

unordered_set是不按特定顺序存储唯一元素的容器，允许根据元素的值快速检索单个元素。在unordered_set中，元素的值同时也是其唯一标识它的key。key是不可变的，因此，unordered_set中的元素不能在容器中修改,但是可以插入和删除它们。在内部,unordered_set中的元素不按照任何特定的顺序排序, 而是根据它们的哈希值组织成bucket，以便直接通过元素的值快速访问单个元素unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。

代码实现

这里封装的思路和之前的map和set基本一样。

C++ STL : 模拟实现STL中的关联式容器map和set

#include"HashBucket.hpp"namespace lee{template<class K, class Hash = lee::_Hash<K>>class unordered_set{public:struct SetKeyOfValue{const K& operator()(const K& key){return key;}};typedef typename HashBucket<K, K, SetKeyOfValue, Hash>::iterator iterator;iterator begin(){return _hb.begin();}iterator end(){return _hb.end();}iterator find(const K& key){return _hb.Find(key);}iterator erase(const K& key){return _hb.Erase(key);}std::pair<iterator, bool> insert(const K& key){return _hb.Insert(key);}private:HashBucket<K, K, SetKeyOfValue, Hash> _hb;};};

unordered_map

文档介绍

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的 value。在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。它的迭代器至少是前向迭代器。

代码实现

#include"HashBucket.hpp"namespace lee{template<class K, class V, class Hash = _Hash<K>>class unordered_map{public:struct MapKeyOfValue{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};typedef typename HashBucket<K, std::pair<K, V>, MapKeyOfValue, Hash>::iterator iterator;iterator begin(){return _hb.begin();}iterator end(){return _hb.end();}iterator find(const K& key){return _hb.Find(key);}iterator erase(const K& key){return _hb.Erase(key);}std::pair<iterator, bool> insert(const std::pair<K, V>& data){return _hb.Insert(data);}V& operator[](const K& key){std::pair<iterator, bool> ret = _hb.Insert(make_pair(key, V()));return ret.first->second;}private:HashBucket<K, std::pair<K, V>, MapKeyOfValue, Hash> _hb;};};