国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<thead id="vhsjx"><s id="vhsjx"></s></thead>

<p id="vhsjx"><noscript id="vhsjx"></noscript></p>

<p id="vhsjx"></p>

<ol id="vhsjx"></ol>

<noscript id="vhsjx"><ins id="vhsjx"><var id="vhsjx"></var></ins></noscript>

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn)

2年前作者：LuckyRich1分類：Toy博客閱讀(26)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【C++】unordered_map，unordered_set模擬實(shí)現(xiàn)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

喜歡的點(diǎn)贊，收藏，關(guān)注一下把！

上一篇文章我們把unordered_map和unordered_set底層哈希桶的知識(shí)也都說清楚了，今天就根據(jù)哈希桶模擬實(shí)現(xiàn)出unordered_map和unordered_set。

這里如果看過以前文章【C++】map和set的模擬實(shí)現(xiàn)，應(yīng)該會(huì)覺得簡單。

因?yàn)閡nordered_map和unordered_set底層都是哈希桶，因此我們只需要一個(gè)哈希桶就好了。所以哈希桶的代碼我們做一下修改，讓它能夠同時(shí)滿足unordered_map和unordered_set的需求。

unordered_map是KV模型，unordered_set是K模型，因此先把鏈表節(jié)點(diǎn)改一下，傳個(gè)T，這個(gè)T既可以是KV，也可以是K。

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

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

插入這里也要改一下，因?yàn)閒ind我們只要key，但是unordered_map是pair，我們要把key取出來，因此HashTable需要增加一個(gè)模板參數(shù)，這個(gè)模板參數(shù)分別由unordered_set、unordered_map傳過來一個(gè)仿函數(shù)。作用是把key取出來

bool Insert(const T& data)
{
	KeyOfT kot;//不知道T是key還是pair
	if (Find(kot(data))//仿函數(shù)把key取出來
		return false;

	//負(fù)載因子控制在1,超過就擴(kuò)容
	if (_n == _tables.size())
	{

		vector<Node*> newtable;
		//newtable.resize(_tables.size() * 2);
		newtable.resize(__stl_next_prime(_tables.size()));
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			//頭插到新表
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = Hash()(kot(data)) % newtable.size();
				cur->_next = newtable[hashi];
				newtable[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtable);//舊表和新表交換一下
	}

	//匿名對(duì)象去調(diào)用仿函數(shù),算在第幾個(gè)桶里面
	int hashi = Hash()(kot(data)) % _tables.size();
	//頭插
	Node* newnode = new Node(data);//調(diào)用Node的構(gòu)造,因此Node寫個(gè)構(gòu)造
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

然后再說這個(gè)模板參數(shù)Hash的問題

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

可以看見keyOfT寫在Hash后面，Hash報(bào)錯(cuò)了，因?yàn)樗腥笔≈祂eyOfT沒有。當(dāng)然你也可以把Hash放在keyOfT后面，但是這里的問題不是這個(gè)。因?yàn)镠ash在HashTable不應(yīng)該有缺省值，應(yīng)該是由它的上層unordered_map和unordered_set傳過去。為什么？

因?yàn)椴灰姷媚阋院髮懸粋€(gè)vector< string >這樣類似的自定義類型底層可以把它轉(zhuǎn)成整數(shù)，還是要由調(diào)用的unordered_map和unordered_set人傳一個(gè)能把這樣類型轉(zhuǎn)成整數(shù)的仿函數(shù)。所以把Hash的缺省值放在unordered_map和unordered_set的模板參數(shù)中。

下面我們把unordered_map和unordered_set模擬實(shí)現(xiàn)大框架搭建出來

//UnorderedMap.h
namespace wdl
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:

	private:
		//第二個(gè)參數(shù)決定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

//UnorderedSet.h
namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

插入

復(fù)用哈希桶的插入

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

//UnorderedSet.h
bool insert(const K& key)
{
	return _ht.Insert(key);
}

插入很簡單，但注意到庫里的插入返回的是pair，插入成功是返回指向這個(gè)節(jié)點(diǎn)的指針和true，插入失敗也就是插入的是相同的值返回指向這個(gè)相同節(jié)點(diǎn)的指針和false

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

所以下面我們先實(shí)現(xiàn)迭代器在把插入完善

普通迭代器

思考這樣一個(gè)問題，++怎么走，如何做到把一個(gè)桶走完了找到下一個(gè)桶？

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

可不可以把這些桶都鏈接起來？

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

這樣遍歷起來就方便了，找到第一個(gè)桶的第一個(gè)位置然后next往下走就像單鏈表一樣遍歷就走完了。如果查找的話給每個(gè)桶最后一個(gè)節(jié)點(diǎn)標(biāo)記位這樣也可以解決找別的桶去了的問題。
但是真正麻煩的是插入怎么辦？

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

插入13，要找到上一個(gè)桶的最后一個(gè)節(jié)點(diǎn)連接起來，再找到下一個(gè)桶的第一個(gè)節(jié)點(diǎn)連接起來。

刪除怎么辦？

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

刪除13，不還是要找到上一個(gè)桶最后一個(gè)節(jié)點(diǎn)和下一個(gè)桶第一個(gè)節(jié)點(diǎn)然后連接起來嗎。

其實(shí)哈希桶的遍歷也很簡單，無非就是當(dāng)前桶走完了找下一個(gè)桶，如果我們有這個(gè)表的話，當(dāng)前桶走完遍歷一下找到下一個(gè)桶不就好了嗎。因此我們不僅要有這個(gè)節(jié)點(diǎn)的指針，還要有這個(gè)表。庫里就是這樣的實(shí)現(xiàn)方式。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++
通過哈希表的指針找到這張表。

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	Node* _node;//節(jié)點(diǎn)的指針

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % ;//計(jì)算當(dāng)前在那個(gè)桶
		}
	}
};

要模表長，因此把表的指針傳過去，當(dāng)然也可以只把vector傳過去。

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	Node* _node;//節(jié)點(diǎn)的指針
	HT* _ht;//哈希表的指針


	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
		}
	}
};

但是vector在HashTable可是私有成員。這里不能直接用。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

因此在HashTable聲明一下__HTIterator是HashTable的友元類就可以用HashTable私有成員

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

Self& operator++()
{
	//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
	if (_node->_next)
	{
		_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
	}
	else
	{
		//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		Hash hf;
		KeyOfT kot;
		size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
		++hashi;//從下一個(gè)桶開始找
		while (hashi < _ht->_tables.size())
		{
			if (_ht->_tables[hashi])
			{
				_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
				break;
			}
			else
			{
				++hashi;
			}
		}

		//走到表的結(jié)束,沒找到下一個(gè)桶
		if (hashi == _ht->_tables.size())
		{
			_node == nullptr;
		}
	}
	return *this;
}

接下來我們把剩下的都補(bǔ)充一下，

template<class K, class T, class Hash, class KeyOfT>
class __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	Node* _node;//節(jié)點(diǎn)的指針
	HT* _ht;//哈希表的指針
	
public:
	__HTIterator(Node* node,HT* ht)
		:_node(node)
		,_ht(ht)
	{}

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

	T* operator->()
	{
		return &_node->_data;
	}
	
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	Self& operator++()
	{
		//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
			++hashi;//從下一個(gè)桶開始找
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
					break;
				}
				else
				{
					++hashi;
				}
			}

			//走到表的結(jié)束,沒找到下一個(gè)桶
			if (hashi == _ht->_tables.size())
			{
				_node == nullptr;
			}
		}
		return *this;
	}
};

在把哈希桶的begin和end寫一下。

template<class K, class T, class Hash ,class KeyOfT>
class HashTable
{
	typedef HashNode<T> Node;

	//友元類
	template<class K, class T, class Hash, class KeyOfT>
	friend class __HTIterator;
public:
	typedef __HTIterator<K, T, Hash, KeyOfT> iterator;
	
public:
	iterator begin()
	{
		//找第一個(gè)桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return iterator(_tables[i], this);//哈希表對(duì)象的指針通過this得到
		}
		return iterator(nullptr, this);
	}

	iterator end()
	{
		//走到最后一個(gè)桶的最后一個(gè)節(jié)點(diǎn)在++就是nullptr
		return iterator(nullptr, this);
	}
	//。。。
}

但是這里還有問題，會(huì)編譯報(bào)錯(cuò)。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

因?yàn)檫@里存在相互引用的問題，

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

迭代器要哈希表，哈希表要迭代器。
以前是容器要迭代器，迭代器在前面，容器就可以直接用迭代器了。但是現(xiàn)在存在相互引用的問題。
解決方法：把哈希表放在前面前置聲明一下

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

這樣就沒問題了。

把unordered_map和unordered_set加上迭代器

//UnorderedMap.h
namespace wdl
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

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

	private:
		//第二個(gè)參數(shù)決定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

//UnorderedSet.h
namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

HashTable沒有實(shí)例化不能區(qū)分iterator是一個(gè)靜態(tài)變量還是內(nèi)置類型，因?yàn)殪o態(tài)變量也可以這樣用，因此加個(gè)typename告訴編譯器這是一個(gè)類型，先不要報(bào)錯(cuò)等實(shí)例化之后在去取。

跑一下unordered_set的迭代器看一眼效果

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

能正常跑是沒錯(cuò)。

但真的沒問題嗎？

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

K模型竟然可以改變key值。
這里就如同模擬實(shí)現(xiàn)set一樣的問題。所以u(píng)nordered_set迭代器都改成const迭代器。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

const迭代器

這里先和以前一樣的實(shí)現(xiàn)。const迭代器和普通迭代器共用一個(gè)模板，因?yàn)閰?shù)傳的不同，所以同一份模板可以實(shí)例化出不同對(duì)象

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

template<class K, class T,class Ref,class Ptr, class Hash, class KeyOfT>
class __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	Node* _node;//節(jié)點(diǎn)的指針
	HT* _ht;//哈希表的指針

public:
	__HTIterator(Node* node,HT* ht)
		:_node(node)
		,_ht(ht)
	{}

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

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

	Self& operator++()
	{
		//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
			++hashi;//從下一個(gè)桶開始找
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
					break;
				}
				else
				{
					++hashi;
				}
			}

			//走到表的結(jié)束,沒找到下一個(gè)桶
			if (hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

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

template<class K, class T, class Hash ,class KeyOfT>
class HashTable
{
	typedef HashNode<T> Node;

	//友元類
	template<class K, class T,class Ref,class Ptr, class Hash, class KeyOfT>
	friend class __HTIterator;

public:
	typedef __HTIterator<K, T,T&,T*, Hash, KeyOfT> iterator;
	typedef __HTIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;
	
public:
	iterator begin()
	{
		//找第一個(gè)桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return iterator(_tables[i], this);
		}
		return iterator(nullptr, this);
	}

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

	const_iterator begin() const
	{
		//找第一個(gè)桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return const_iterator(_tables[i], this);
		}
		return const_iterator(nullptr, this);
	}

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

再把unordered_set的迭代器修改一下

namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;

		//加上const普通對(duì)象和const對(duì)象都能調(diào)用begin
		//但是因此對(duì)象不同所以調(diào)用哈希表的begin也是不同的
		//普通對(duì)象走普通的begin，const對(duì)象走const的begin
		iterator begin() const
		{
			return _ht.begin();
		}

		iterator end() const
		{
			return _ht.end();
		}

		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}

	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

但是走const迭代器報(bào)了上面的錯(cuò)誤。
無構(gòu)造函數(shù)可以接受原類型，或者構(gòu)造函數(shù)重載不明確。這是為什么？
難道哈希表的const迭代器寫錯(cuò)了？我們看看庫怎么寫的。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

注意到庫里是把普通迭代器和const迭代器分開寫的。并且const迭代器的成員變量都加了const修飾。而且構(gòu)造的的參數(shù)都加上const了。

而我們const迭代器和普通迭代器用的是同一個(gè)模板，但是這個(gè)模板在調(diào)用的是const迭代器構(gòu)造的時(shí)候卻沒有const修飾參數(shù)。
【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

問題的原因在于：
當(dāng)const對(duì)象調(diào)用begin的時(shí)候走的是下面的begin。而我們?cè)谶@個(gè)begin加了const修飾。這里面隱藏的this指針就變成了 ----> const HashTable* const this。const修飾*this不就是修飾對(duì)象本身嗎，也就是說對(duì)象從一個(gè)普通對(duì)象變成了const對(duì)象。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

再看這個(gè)，調(diào)用的是vector的[ ]

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

你是const對(duì)象，那你調(diào)用vector的[ ]返回的就是const，所以說vector里面的也是const

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

然后調(diào)用const_iterator的構(gòu)造，但是它和普通迭代器用的是同一個(gè)構(gòu)造

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

以前說過，指針和引用賦值的權(quán)限只能平移或者縮小。但是現(xiàn)在你傳過去權(quán)限相當(dāng)于放大了。所以造成了錯(cuò)誤！所以const迭代器的構(gòu)造第一個(gè)參數(shù)要有const修飾，這樣在傳過去就是權(quán)限平移。不會(huì)有問題。并且表的指針也要加上const。

因?yàn)閠his也是const。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

const迭代器成員變量也是const的原因是因?yàn)椋@里構(gòu)造的時(shí)候也涉及了權(quán)限的平移。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

不過這里const迭代器還差一點(diǎn)點(diǎn)東西，我們現(xiàn)在回頭把插入寫完再說。

template<class K, class T, class Hash, class KeyOfT>
class __HTConstIterator
{
	typedef HashNode<T> Node;
	typedef __HTConstIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	const Node* _node;//節(jié)點(diǎn)的指針
	const HT* _ht;//哈希表的指針

public:
	__HTConstIterator(const Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{}

	const T& operator*()
	{
		return _node->_data;
	}

	const T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
			++hashi;//從下一個(gè)桶開始找
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
					break;
				}
				else
				{
					++hashi;
				}
			}

			//走到表的結(jié)束,沒找到下一個(gè)桶
			if (hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

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

現(xiàn)在有了迭代器，我們先把哈希表要用的到迭代器的插入和查找改一下

pair<iterator,bool> Insert(const T& data)
{
	KeyOfT kot;
	iterator it = Find(kot(data));
	if (it != end())
		return make_pair(it, false);//插入失敗返回指向這個(gè)節(jié)點(diǎn)的指針和false

	//負(fù)載因子控制在1,超過就擴(kuò)容
	if (_n == _tables.size())
	{

		vector<Node*> newtable;
		//newtable.resize(_tables.size() * 2);
		newtable.resize(__stl_next_prime(_tables.size()));
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			//頭插到新表
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = Hash()(kot(data)) % newtable.size();
				cur->_next = newtable[hashi];
				newtable[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_tables.swap(newtable);//舊表和新表交換一下
	}

	//匿名對(duì)象去調(diào)用仿函數(shù),算在第幾個(gè)桶里面
	int hashi = Hash()(kot(data)) % _tables.size();
	//頭插
	Node* newnode = new Node(data);//調(diào)用Node的構(gòu)造,因此Node寫個(gè)構(gòu)造
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return make_pair(iterator(newnode,this),true);//插入返回新節(jié)點(diǎn)的指針和true
}


iterator Find(const K& key)
{
	size_t hashi = Hash()(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (KeyOfT()(cur->_data) == key)
			return iterator(cur,this);//找到返回指向這個(gè)節(jié)點(diǎn)的指針
		else
			cur = cur->_next;
	}
	return end();//沒找到返回nullptr
}

再把unordered_set和unordered_map的插入修改一下

namespace wdl
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
	//。。。
	private:
		//第二個(gè)參數(shù)決定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

//UnorderedSet.h
namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
		//。。。

	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

unordered_set的插入又報(bào)了老錯(cuò)誤，返回類型不匹配的問題，因?yàn)閡nordered_set的迭代器都是const迭代器，而哈希表插入返回的普通迭代器。這里和庫的解決方法一樣。在const迭代器寫一個(gè)拷貝構(gòu)造函數(shù)，把iterator構(gòu)造成const_iterator。

【C++】unordered_map，unordered_set模擬實(shí)現(xiàn),C++從入門到精通,哈希算法,算法,c++

template<class K, class T, class Hash, class KeyOfT>
class __HTConstIterator
{
	typedef HashNode<T> Node;
	typedef  __HTConstIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	typedef __HTIterator< K, T, Hash, KeyOfT > iterator;
	const Node* _node;//節(jié)點(diǎn)的指針
	const HT* _ht;//哈希表的指針

public:
	__HTConstIterator(const Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{}

	//拷貝構(gòu)造，把iterator構(gòu)造成const_iterator
	__HTConstIterator(const iterator& it)
		:_node(it._node)
		,_ht(it._ht)
	{}

	//。。。
};

自此我們的const徹底寫完了。

現(xiàn)在unordered_set的插入就沒問題了，順便也把unordered_map的插入補(bǔ)上

//UnorderedSet.h
namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const K& key)
		{
			//先用同一類型接收
			pair<typename HashTable<K, K, Hash, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
			//在把iterator構(gòu)造成const_iterator
			return pair<iterator, bool>(ret.first, ret.second);
		}
	//。。。
	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
	
//UnorderedMap.h
namespace wdl
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		//。。。
		private:
		//第二個(gè)參數(shù)決定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

unordered_map的插入直接返回就可以，因?yàn)橛玫氖莍terator，并且pair里面的K由const修飾，使用普通迭代器不能改變K。

unordered_map的[ ]接口實(shí)現(xiàn)

這個(gè)在【C++】map和set的使用及注意事項(xiàng)中map有詳細(xì)介紹，這里不再敘述文章來源地址http://www.zghlxwxcb.cn/news/detail-812312.html

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

查找+修改

//UnorderedMap.h
iterator find(const K& key)
{
	return _ht.Find(key);//這里直接返回
}

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

//UnorderedSet.h
iterator find(const K& key)
{
	 return _ht.Find(key);//這里在返回的時(shí)候調(diào)用一下const_iterator的拷貝構(gòu)造
}

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

哈希桶完整代碼

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

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

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

template<class K, class T,class Hash, class KeyOfT>
class __HTIterator
{
	typedef HashNode<T> Node;
	typedef __HTIterator<K, T,Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
public:
	Node* _node;//節(jié)點(diǎn)的指針
	HT* _ht;//哈希表的指針

public:
	__HTIterator(Node* node,HT* ht)
		:_node(node)
		,_ht(ht)
	{}


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

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

	Self& operator++()
	{
		//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
			++hashi;//從下一個(gè)桶開始找
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
					break;
				}
				else
				{
					++hashi;
				}
			}

			//走到表的結(jié)束,沒找到下一個(gè)桶
			if (hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

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

template<class K, class T, class Hash, class KeyOfT>
class __HTConstIterator
{
	typedef HashNode<T> Node;
	typedef  __HTConstIterator<K, T, Hash, KeyOfT> Self;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	typedef __HTIterator< K, T, Hash, KeyOfT > iterator;
	const Node* _node;//節(jié)點(diǎn)的指針
	const HT* _ht;//哈希表的指針

public:
	__HTConstIterator(const Node* node, const HT* ht)
		:_node(node)
		, _ht(ht)
	{}

	__HTConstIterator(const iterator& it)
		:_node(it._node)
		,_ht(it._ht)
	{}

	const T& operator*()
	{
		return _node->_data;
	}

	const T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		//_node最開始指向第一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
		if (_node->_next)
		{
			_node = _node->_next;//遍歷當(dāng)前桶的所有節(jié)點(diǎn)
		}
		else
		{
			//當(dāng)前桶走完,要找下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(kot(_node->_data)) % _ht->_tables.size();//計(jì)算當(dāng)前在那個(gè)桶
			++hashi;//從下一個(gè)桶開始找
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_node = _ht->_tables[hashi];//找到下一個(gè)存數(shù)據(jù)桶的第一個(gè)節(jié)點(diǎn)
					break;
				}
				else
				{
					++hashi;
				}
			}

			//走到表的結(jié)束,沒找到下一個(gè)桶
			if (hashi == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

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

template<class K, class T, class Hash ,class KeyOfT>
class HashTable
{
	typedef HashNode<T> Node;

	//友元類
	template<class K, class T, class Hash, class KeyOfT>
	friend class __HTIterator;

	template<class K, class T, class Hash, class KeyOfT>
	friend class __HTConstIterator;


public:
	typedef __HTIterator<K, T,Hash, KeyOfT> iterator;
	typedef __HTConstIterator<K, T, Hash, KeyOfT> const_iterator;
	
public:
	iterator begin()
	{
		//找第一個(gè)桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return iterator(_tables[i], this);
		}
		return iterator(nullptr, this);
	}

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

	const_iterator begin() const
	{
		//找第一個(gè)桶
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
				return const_iterator(_tables[i], this);
		}
		return const_iterator(nullptr, this);
	}

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

	HashTable()
		:_n(0)//這里雖然沒有明確寫調(diào)用vector構(gòu)造,但是編譯器會(huì)按照聲明順序去調(diào)用的,所以會(huì)自動(dòng)調(diào)用vecto的構(gòu)造
	{
		//_tables.resize(10);//調(diào)用HashNode的構(gòu)造
		_tables.resize(__stl_next_prime(0));
	}

	~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;
		}
	}//走到這里會(huì)自動(dòng)調(diào)用vector的析構(gòu)

	HashTable(const HashTable<K,T,Hash,KeyOfT>& ht)
		:_n(ht._n)
	{
		_tables.resize(ht._tables.size());
		for (size_t i = 0; i < ht._tables.size(); ++i)
		{
			Node* cur = ht._tables[i];
			if (cur)
			{
				Node* copy = new Node(cur->_kv);
				_tables[i] = copy;

				while (cur->_next)
				{
					cur = cur->_next;
					//尾插
					copy->_next = new Node(cur->_kv);
					copy = copy->_next;
				}
			}
		}
	}

	//賦值重載現(xiàn)代寫法 復(fù)用拷貝構(gòu)造
	HashTable<K, T, Hash, KeyOfT>& operator=(HashTable<K, T, Hash, KeyOfT> ht)
	{
		_n = ht._n;
		_tables.swap(ht._tables);
		return *this;
	}


	pair<iterator,bool> Insert(const T& data)
	{
		KeyOfT kot;
		iterator it = Find(kot(data));
		if (it != end())
			return make_pair(it, false);

		//負(fù)載因子控制在1,超過就擴(kuò)容
		if (_n == _tables.size())
		{

			vector<Node*> newtable;
			//newtable.resize(_tables.size() * 2);
			newtable.resize(__stl_next_prime(_tables.size()));
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				//頭插到新表
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = Hash()(kot(data)) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newtable);//舊表和新表交換一下
		}

		//匿名對(duì)象去調(diào)用仿函數(shù),算在第幾個(gè)桶里面
		int hashi = Hash()(kot(data)) % _tables.size();
		//頭插
		Node* newnode = new Node(data);//調(diào)用Node的構(gòu)造,因此Node寫個(gè)構(gòu)造
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;
		return make_pair(iterator(newnode,this),true);
	}


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

	bool Erase(const K& key)
	{
		size_t hashi = Hash()(key) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;//記錄被刪節(jié)點(diǎn)前一個(gè)位置
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (cur == _tables[hashi])//被刪節(jié)點(diǎn)是頭一個(gè)節(jié)點(diǎn)
				{
					_tables[hashi] = cur->_next;
				}
				else 
				{
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			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
		};//最大質(zhì)數(shù)取得是靠近整型最大數(shù)得質(zhì)數(shù)

		for (size_t i = 0; i < __stl_num_primes; ++i)
		{
			if (__stl_prime_list[i] > n)
				return __stl_prime_list[i];
		}
		//不用擔(dān)心會(huì)哈希表會(huì)擴(kuò)到最大質(zhì)數(shù),因?yàn)檫@時(shí)對(duì)于整型來說都已經(jīng)差不多48G了
		return __stl_prime_list[__stl_num_primes - 1];
	}


private:
	vector<Node*> _tables;
	size_t _n;
};

unordered_map完整代碼

template<class K>
struct HashFunc
{
	//凡是能轉(zhuǎn)成整型的就轉(zhuǎn)成整型 如負(fù)數(shù),如指針,如浮點(diǎn)數(shù)
	//string不能轉(zhuǎn)
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//模板特化
template<>
struct HashFunc<string>
{
	//BKDR
	size_t operator()(const string& key)
	{
		size_t num = 0;
		for (auto& ch : key)
		{
			num *= 131;
			num += ch;
		}
		return num;
	}
};

namespace wdl
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::const_iterator const_iterator;

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

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

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

		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		const_iterator begin() const
		{
			return _ht.begin();
		}

		const_iterator end() const
		{
			return _ht.end();
		}

	private:
		//第二個(gè)參數(shù)決定是KV模型
		HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;
	};
}

unordered_set完整代碼

template<class K>
struct HashFunc
{
	//凡是能轉(zhuǎn)成整型的就轉(zhuǎn)成整型 如負(fù)數(shù),如指針,如浮點(diǎn)數(shù)
	//string不能轉(zhuǎn)
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//模板特化
template<>
struct HashFunc<string>
{
	//BKDR
	size_t operator()(const string& key)
	{
		size_t num = 0;
		for (auto& ch : key)
		{
			num *= 131;
			num += ch;
		}
		return num;
	}
};

namespace wdl
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> insert(const K& key)
		{
			pair<typename HashTable<K, K, Hash, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
		}

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

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

		iterator begin() const
		{
			return _ht.begin();
		}

		iterator end() const
		{
			return _ht.end();
		}


	private:
		//第二個(gè)參數(shù)決定是K模型
		HashTable<K, K, Hash, SetKeyOfT> _ht;
	};
}

到了這里，關(guān)于【C++】unordered_map，unordered_set模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

C++進(jìn)階--使用哈希表實(shí)現(xiàn)unordered_map和unordered_set的原理與實(shí)例
本文將介紹如何使用哈希表來實(shí)現(xiàn)C++ STL庫中的unordered_map和unordered_set容器。我們將會(huì)解釋哈希表的基本原理，并給出具體的代碼示例，幫助讀者更好地理解和應(yīng)用哈希表。哈希原理講解–鏈接入口 set和map的實(shí)現(xiàn)的文章，與unordered_map實(shí)現(xiàn)類似 unordered_set是一種集合存儲(chǔ)的容器
2024年04月09日
瀏覽(22)
【C++學(xué)習(xí)】哈希表的底層實(shí)現(xiàn)及其在unordered_set與unordered_map中的封裝
??個(gè)人名片： ??作者簡介：一名樂于分享在學(xué)習(xí)道路上收獲的大二在校生 ??個(gè)人主頁??：GOTXX ??個(gè)人WeChat：ILXOXVJE ??本文由GOTXX原創(chuàng)，首發(fā)CSDN?????? ??系列專欄：零基礎(chǔ)學(xué)習(xí)C語言----- 數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)之路----C++的學(xué)習(xí)之路 ??每日一句：如果沒有特別幸運(yùn)，那就請(qǐng)?zhí)?/p>
2024年04月16日
瀏覽(38)
【C++】unordered_map和unordered_set的使用
文章目錄前言一、unordered_map的使用及性能測(cè)試二、unordered_set的使用 1.習(xí)題練習(xí) 總結(jié) unordered 系列關(guān)聯(lián)式容器：在 C++98 中， STL 提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時(shí)效率可達(dá)到O（logN），即最差情況下需要比較紅黑樹的高度次，當(dāng)樹中的節(jié)點(diǎn)非常多時(shí)，
2024年02月06日
瀏覽(31)
【C++】unordered_set與unordered_map的封裝
??個(gè)人主頁：平凡的小蘇 ??學(xué)習(xí)格言：命運(yùn)給你一個(gè)低的起點(diǎn)，是想看你精彩的翻盤，而不是讓你自甘墮落，腳下的路雖然難走，但我還能走，比起向陽而生，我更想嘗試逆風(fēng)翻盤。 ?? C++專欄： C++內(nèi)功修煉基地家人們更新不易，你們的??點(diǎn)贊??和?關(guān)注?真的對(duì)我真
2024年02月08日
瀏覽(23)
【C++】unordered_set 和 unordered_map 使用 | 封裝
unordered_map官方文檔 unordered_set 官方文檔 set / map與unordered_set / unordered_map 使用功能基本相同，但是兩者的底層結(jié)構(gòu)不同 set/map底層是紅黑樹 unordered_map/unordered_set 底層是哈希表紅黑樹是一種搜索二叉樹，搜索二叉樹又稱為排序二叉樹，所以迭代器遍歷是有序的而哈希表對(duì)應(yīng)的
2024年02月06日
瀏覽(24)
C++進(jìn)階--unordered_set、unordered_map的介紹和使用
??在C++98中，STL提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時(shí)效率可達(dá)到 l o g 2 N log_2N l o g 2 ? N ，即最差情況下需要比較紅黑樹的高度次，當(dāng)樹中的節(jié)點(diǎn)非常多時(shí)，查詢效率也不理想。最好的查詢是，進(jìn)行很少的比較次數(shù)就能夠?qū)⒃卣业剑虼嗽贑++11中，STL又
2024年01月16日
瀏覽(47)
【C++】unordered_map和unordered_set的使用及 OJ練習(xí)
在前面的文章中，我們已經(jīng)學(xué)習(xí)了STL中底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器——set/multiset 和 map/multimap（C++98）在C++98中，STL提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時(shí)效率可達(dá)到 l o g 2 N log_2 N l o g 2 ? N ，即最差情況下需要比較紅黑樹的高度次。在C++11中，
2024年02月11日
瀏覽(19)
C++利用開散列哈希表封裝unordered_set,unordered_map
1.之前我們已經(jīng)實(shí)現(xiàn)了開散列的哈希表,今天我們來用它封裝unordered_set,unordered_map 2.本文的封裝比利用紅黑樹封裝set和map更加復(fù)雜建議大家先去看我的紅黑樹封裝set和map再來看本文因?yàn)橛泻芏嗟胤礁t黑樹封裝set和map時(shí)是同樣的思路和方法,所以本文不會(huì)太去贅述一遍因?yàn)閡n
2024年03月24日
瀏覽(20)
C++ 哈希+unordered_map+unordered_set+位圖+布隆過濾器（深度剖析）
想象一下，你有一個(gè)巨大的圖書館，里面擺滿了成千上萬本書。如果你想要找到其中一本特定的書，你會(huì)怎么做？如果你按照書的編號(hào)來有序地排列它們，找到特定的書本可能會(huì)很容易。但是，如果書籍是隨機(jī)地?cái)[放，你可能需要逐本地查找，這個(gè)過程會(huì)非常耗時(shí)。而哈希函
2024年02月21日
瀏覽(24)
【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]
歡迎各位大佬們的關(guān)顧，本文將介紹unordered系列容器以及其中的兩個(gè)重要成員： unordered_map 和 unordered_set 。unordered_map是一種無序的關(guān)聯(lián)容器，它使用哈希表來存儲(chǔ)鍵值對(duì)，并提供高效的插入、查找和刪除操作。在本文中，我們將首先介紹unordered_map的基本概念和特點(diǎn)，然后詳
2024年02月08日
瀏覽(19)

<td id="449v9"></td>

<menu id="449v9"></menu>

<thead id="449v9"></thead>