模拟实现unordered_set和unordered_map

改造哈希表结构

1. 模板参数列表的改造

// K:关键码类型
// V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是
unordered_set,V 为 K
// KeyOfValue: 因为V的类型不同，通过value取key的方式就不同，详细见
unordered_map/set的实现
// Hash: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
class HashBucket;

2. 增加迭代器操作

// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	template<class K, class V, class KeyOfValue, class HF>
	class HashBucket;
	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	template <class K, class V, class KeyOfValue, class HF>
	struct HBIterator
	{
		typedef HashBucket<K, V, KeyOfValue, HF> HashBucket;
		typedef HashBucketNode<V>* PNode;
		typedef HBIterator<K, V, KeyOfValue, HF> Self;
		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr);
		Self& operator++()
		{
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_pNext)
				_pNode = _pNode->_pNext;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode -
> _data)) + 1;
				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
				{
					if (_pNode = _pHt->_ht[bucketNo])
						break;
				}
			}
			return *this;
		}
		Self operator++(int);
		V& operator*();
		V* operator->();
		bool operator==(const Self& it) const;
		bool operator!=(const Self& it) const;
		PNode _pNode;       // 当前迭代器关联的节点
		HashBucket* _pHt;     // 哈希桶--主要是为了找下一个空桶时候方便
	};

 3. 增加通过key获取value操作

template<class K, class V, class KeyOfValue, class HF = DefHashF<T> >
	class HashBucket
	{
		friend HBIterator<K, V, KeyOfValue, HF>;
		// ......
	public:
		typedef HBIterator<K, V, KeyOfValue, HF> Iterator;
		//
		  // ...
		// 迭代器
		Iterator Begin()
		{
			size_t bucketNo = 0;
			for (; bucketNo < _ht.capacity(); ++bucketNo)
			{
				if (_ht[bucketNo])
					break;
			}
			if (bucketNo < _ht.capacity())
				return Iterator(_ht[bucketNo], this);
			else
				return Iterator(nullptr, this);
		}
		Iterator End() { return Iterator(nullptr, this); }
		Iterator Find(const K& key);
		Iterator Insert(const V& data);
		Iterator Erase(const K& key);
 
		// 为key的元素在桶中的个数
		size_t Count(const K& key)
		{
			if (Find(key) != End())
				return 1;
 
			return 0;
		}
 
		size_t BucketCount()const { return _ht.capacity(); }
		size_t BucketSize(size_t bucketNo)
		{
			size_t count = 0;
			PNode pCur = _ht[bucketNo];
			while (pCur)
			{
				count++;
				pCur = pCur->_pNext;
			}
 
			return count;
		}
 
		// ......
	};

unordered_map&unordered_set/哈希表封装unordered_xxx系列 · 杰编程/CPlusPlus - 码云 - 开源中国 (gitee.com)