快捷導(dǎo)航

C++之unordered封裝的實(shí)現(xiàn)

更新時(shí)間：2025年05月06日 09:00:27 作者：孞?￥

本文主要介紹了C++之unordered封裝的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

一、哈希表的修改

注意：這里我們使用哈希桶來(lái)封裝unordered_map和unordered_set。

1.1、哈希表節(jié)點(diǎn)結(jié)構(gòu)

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

因?yàn)槲覀円獜?fù)用哈希表，即使用同一份哈希表代碼來(lái)封裝unordered_map和unordered_set，所以這里將模版參數(shù)改為T，T即要存儲(chǔ)的數(shù)據(jù)類型，對(duì)于unordered_set而言，T直接就是要存儲(chǔ)的數(shù)據(jù)類型；對(duì)于unordered_map而言，T是pair類型的。

在插入方法中，我們使用有參構(gòu)造，在創(chuàng)建節(jié)點(diǎn)時(shí)直接將數(shù)據(jù)通過(guò)構(gòu)造函數(shù)賦值進(jìn)去，所以這里還實(shí)現(xiàn)了一個(gè)構(gòu)造函數(shù)。

1.2、迭代器

iterator核心源碼：

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;

 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; }
};

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實(shí)現(xiàn)思路分析：

iterator實(shí)現(xiàn)的?框架跟list的iterator思路是?致的，??個(gè)類型封裝結(jié)點(diǎn)的指針，再通過(guò)重載運(yùn)算符實(shí)現(xiàn)，迭代器像指針?樣訪問(wèn)的?為，要注意的是哈希表的迭代器是單向迭代器。
這?的難點(diǎn)是operator++的實(shí)現(xiàn)。iterator中有?個(gè)指向結(jié)點(diǎn)的指針，如果當(dāng)前桶下?還有結(jié)點(diǎn)，則結(jié)點(diǎn)的指針指向下?個(gè)結(jié)點(diǎn)即可。如果當(dāng)前桶?完了，則需要想辦法計(jì)算找到下?個(gè)桶。這?的難點(diǎn)是反?是結(jié)構(gòu)設(shè)計(jì)的問(wèn)題，參考上面源碼，我們可以知道iterator中除了有結(jié)點(diǎn)的指針，還有哈希表對(duì)象的指針，這樣當(dāng)前桶?完了，要計(jì)算下?個(gè)桶就相對(duì)容易多了，?key值計(jì)算出當(dāng)前桶位置，依次往后找下?個(gè)不為空的桶即可。
begin()返回第?個(gè)不為空的桶中第?個(gè)節(jié)點(diǎn)指針構(gòu)造的迭代器，這?end()返回迭代器可以?空指針表?。
unordered_map的iterator不?持修改key但是可以修改value，我們把unordered_map的第?個(gè)模板參數(shù)pair的第?個(gè)參數(shù)改成const K即可，HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;（不允許修改Key是因?yàn)閿?shù)據(jù)在哈希表中存儲(chǔ)的地址是通過(guò)Key映射的，如果修改Key，破壞了哈希表的結(jié)構(gòu)）。
unordered_set的iterator也不?持修改，我們把unordered_set的第?個(gè)模板參數(shù)改成const K即可，HashTable<K, const K, SetKeyOfT, Hash> _ht;（和unordered_map同理）。

具體代碼：

	// 前置聲明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				//當(dāng)前桶還有節(jié)點(diǎn)
				_node = _node->_next;
			}
			else
			{
				//當(dāng)前桶走完了，找下一個(gè)不為空的桶
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}

					++hashi;
				}

				if (hashi == _pht->_tables.size())
				{
					_node = nullptr; //end()
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

	};

注意：這里需要對(duì)哈希表進(jìn)行前置聲明，因?yàn)樵诘髦杏玫搅斯１?，但是編譯器編譯時(shí)是向上查找，而哈希表在下面，會(huì)因?yàn)檎也坏蕉鴪?bào)錯(cuò)，將哈希表放到上面也不行，因?yàn)楣１砝镆矔?huì)封裝迭代器，如果哈希表在上面向上查找時(shí)就會(huì)找不到迭代器，總之必須有一個(gè)進(jìn)行前置聲明。另外，迭代器中重載++運(yùn)算符時(shí)為了確定當(dāng)前節(jié)點(diǎn)的位置訪問(wèn)了哈希表的私有成員，所以后面在哈希表中還需要進(jìn)行友元聲明。

1.3、哈希表結(jié)構(gòu)

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		// 友元聲明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node; //節(jié)點(diǎn)不想讓外界訪問(wèn)
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要讓外界訪問(wèn)
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0) //沒(méi)有有效數(shù)據(jù)
			{
				return End();
			}

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}

			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;

			Iterator it = Find(kot(data));
			//去重
			if (it != End())
			{
				return make_pair(it,false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();

			//負(fù)載因子==1  擴(kuò)容
			if (_n == _tables.size())
			{
				// 需要新建節(jié)點(diǎn)和釋放舊節(jié)點(diǎn)，效率較低
				//	HashTable<K, V, Hash> newHT;
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						//舊表中的節(jié)點(diǎn)重新映射在新表中的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}

					//節(jié)點(diǎn)都挪到新表上了，舊表置空
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			//頭插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(Iterator(newnode,this),true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指針數(shù)組
		size_t _n; //表中存儲(chǔ)數(shù)據(jù)個(gè)數(shù)
	};

}

為什么需要KeyOfT模版參數(shù)：

跟map和set相???unordered_map和unordered_set的模擬實(shí)現(xiàn)類結(jié)構(gòu)更復(fù)雜?點(diǎn)，但是?框架和思路是完全類似的。因?yàn)镠ashTable實(shí)現(xiàn)了泛型不知道T參數(shù)是K，還是pair，那么insert內(nèi)部進(jìn)?插?時(shí)要?K對(duì)象轉(zhuǎn)換成整形取模和K?較相等(去重)，因?yàn)閜air的value不需要參與計(jì)算取模，且pair默認(rèn)?持的是key和value?起?較相等，但實(shí)際上我們需要的是任何時(shí)候只需要?較K對(duì)象，所以我們?cè)趗nordered_map和unordered_set層分別實(shí)現(xiàn)?個(gè)MapKeyOfT和SetKeyOfT的仿函數(shù)傳給 HashTable的KeyOfT，然后HashTable中通過(guò)KeyOfT仿函數(shù)取出T類型對(duì)象中的K對(duì)象，再轉(zhuǎn)換成整形取模和K?較相等。

返回值的修改：

這里為了符合unordered_map和unordered_set的使用將Find方法的返回值改為迭代器，為了實(shí)現(xiàn)unordered_map的 [ ] 運(yùn)算符重載，將Insert方法的返回值該為pair類型，其中返回的pair對(duì)象的first屬性的值是新插入節(jié)點(diǎn)/原有節(jié)點(diǎn)的迭代器，second屬性的值是bool類型，代表是否插入成功。

1.4、完整代碼

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 Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				//當(dāng)前桶還有節(jié)點(diǎn)
				_node = _node->_next;
			}
			else
			{
				//當(dāng)前桶走完了，找下一個(gè)不為空的桶
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}

					++hashi;
				}

				if (hashi == _pht->_tables.size())
				{
					_node = nullptr; //end()
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		// 友元聲明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node; //節(jié)點(diǎn)不想讓外界訪問(wèn)
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要讓外界訪問(wèn)
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0) //沒(méi)有有效數(shù)據(jù)
			{
				return End();
			}

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}

			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;

			Iterator it = Find(kot(data));
			//去重
			if (it != End())
			{
				return make_pair(it,false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();

			//負(fù)載因子==1  擴(kuò)容
			if (_n == _tables.size())
			{
				// 需要新建節(jié)點(diǎn)和釋放舊節(jié)點(diǎn)，效率較低
				//	HashTable<K, V, Hash> newHT;
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						//舊表中的節(jié)點(diǎn)重新映射在新表中的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}

					//節(jié)點(diǎn)都挪到新表上了，舊表置空
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			//頭插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(Iterator(newnode,this),true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指針數(shù)組
		size_t _n; //表中存儲(chǔ)數(shù)據(jù)個(gè)數(shù)
	};

}

二、unordered_map的實(shí)現(xiàn)

這里的實(shí)現(xiàn)沒(méi)有什么困難，就是直接套一層殼，所有的調(diào)用最終還是去調(diào)哈希表的方法，所以這里就不在贅述了，直接上代碼。

#include"HashTable.h"

namespace bit
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));

			return ret.first->second;
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};

	void test_map()
	{
		unordered_map<string, string> dict;
		dict.insert({ "sort", "排序" });
		dict.insert({ "left", "左邊" });
		dict.insert({ "right", "右邊" });

		dict["left"] = "左邊，剩余";
		dict["insert"] = "插入";
		dict["string"];

		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			// 不能修改first，可以修改second
			//it->first += 'x';
			it->second += 'x';

			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
}

三、unordered_set的實(shí)現(xiàn)

這里和unordered_map一樣，就是直接套一層殼，所有的調(diào)用最終還是去調(diào)哈希表的方法，所以這里就不在贅述了，直接上代碼。

#include"HashTable.h"

namespace bit
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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 K& key)
		{
			return _ht.Insert(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
	};

	void Print(const unordered_set<int>& s)
	{
		unordered_set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			// *it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;

		bool operator==(const Date& d) const
		{
			return _year == d._year
				&& _month == d._month
				&& _day == d._day;
		}
	};

	struct HashDate
	{
		size_t operator()(const Date& key)
		{
			// 112
			// 121
			return (key._year * 31 + key._month) * 31 + key._day;
		}
	};

	void test_set()
	{
		unordered_set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };
		for (auto e : a)
		{
			s.insert(e);
		}

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;

		unordered_set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			//*it += 1;

			cout << *it << " ";
			++it;
		}
		cout << endl;

		unordered_set<Date, HashDate> us;
		us.insert({ 2024, 7, 25 });
		us.insert({ 2024, 7, 26 });

		Print(s);
	}
}

到此這篇關(guān)于C++之unordered封裝的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ unordered封裝內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: