技術文章 » C++進階（unordered_set+unordered_map模擬實現）

C++進階（unordered_set+unordered_map模擬實現）

2022-12-25 18:00:29

unordered_set

  • unordered_set是以無特定順序儲存唯一元素的容器，並且允許根據它們的值快速檢索單個元素，是一種K模型。
  • 在unordered_set中，元素的值同時是它的key，它唯一地標識它。鍵值是不可變的，因unordered_set中的元素不能在容器中修改一次 ，但是可以插入和刪除它們。
  • 在內部，unordered_set中的元素不是按任何特定順序排序的（無序），而是根據它們的雜湊值組織成桶，以允許直接通過它們的值快速存取單個元素，時間複雜度可以達到O(1)。
  • unordered_set容器比set容器更快地通過它們的key存取單個元素，儘管它們通常對於通過其元素的子集進行範圍迭代的效率較低。
  • 容器中的迭代器至少是單向迭代器。

使用

建構函式

unordered_set<string> uset;//建構函式
unordered_set<string> uset2(++uset.begin(),uset.end());//，如果不想全部拷貝，可以使用 unordered_set 類別範本提供的迭代器，在現有 unordered_set 容器中選擇部分割區域內的元素，為新建 unordered_set 容器初始化
unordered_set ( const unordered_set& ust );//拷貝構造

容量和大小

empty();//若容器為空，則返回 true；否則 false
size();//返回當前容器中存有元素的個數

迭代器

begin();//返回指向容器中第一個元素的正向迭代器
end();//返回指向容器中最後一個元素之後位置的正向迭代器
cbegin();//和begin()功能相同，只不過其返回的是const型別的正向迭代器
cend();//和end()功能相同，只不過其返回的是const型別的正向迭代器

元素的存取和查詢

find(key);//查詢以值為 key 的元素，如果找到，則返回一個指向該元素的正向迭代器；反之，則返回一個指向容器中最後一個元素之後位置的迭代器（如果end()方法返回的迭代器）
count(key);//在容器中查詢值為 key 的元素的個數
equal_range(key);//返回一個pair物件，其包含2個迭代器，用於表明當前容器中值為key的元素所在的範圍

元素的插入和刪除

emplace();//向容器中新增新元素，效率比insert()方法高
emplace_hint();//向容器中新增新元素，效率比 nsert()方法高
insert();//向容器中新增新元素
erase();//刪除指定元素
clear();//清空容器，即刪除容器中儲存的所有元素
swap();//交換2個 unordered_set 容器儲存的元素，前提是必須保證這 2 個容器的型別完全相等

範例演示：

void test_unordered_set()
{
	unordered_set<int> us;
	set<int> s;

	int arr[] = { 4,2,3,1,6,8,9,3 };

	for (auto e : arr)
	{
		us.insert(e);
		s.insert(e);
	}

	unordered_set<int>::iterator usit = us.begin();
	set<int>::iterator sit = s.begin();

	cout << "unordered_set:" << endl;
	while (usit != us.end())
	{
		cout << *usit << " ";
		++usit;
	}
	cout << endl;
	
	cout << "set:" << endl;
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;
}

unordered_map

介紹

  • unordered_map是儲存<key, value>鍵值對（KV模型）的關聯式容器，其允許通過keys快速的索引到與其對應的value。
  • 在unordered_map中，鍵值通常用於唯一地標識元素，而對映值是一個物件，其內容與此鍵關聯。鍵和對映值的型別可能不同。
  • 在內部，unordered_map沒有對<key, value>按照任何特定的順序排序（無序）, 為了能在常數範圍內找到key所對應的value，unordered_map將相同雜湊值的鍵值對放在相同的桶中。
  • unordered_map容器通過key存取單個元素要比map快，但它通常在遍歷元素子集的範圍迭代方面效率較低。
  • unordered_map實現了直接存取操作符(operator[])，它允許使用key作為引數直接存取value。
  • 它的迭代器是一個單向迭代器。

使用

建構函式

unordered_map<string,string> umap//建構函式： 可以不初始化地構造，也可以用一個容器的迭代器去構造
unordered_map ( const unordered_map& ump );//拷貝構造

容量和大小

empty();//判斷容器是否為空,，若容器為空，則返回 true；否則 false
size();//返回容器中的元素個數

迭代器

begin();//返回指向容器中第一個鍵值對的正向迭代器
end();//返回指向容器中最後一個鍵值對之後位置的正向迭代器
cbegin();//和 begin() 功能相同，只不過在其基礎上增加了 const 屬性，即該方法返回的迭代器不能用於修改容器記憶體儲的鍵值對
cend();//和 end() 功能相同，只不過在其基礎上，增加了 const 屬性，即該方法返回的迭代器不能用於修改容器記憶體儲的鍵值對

元素的存取和查詢

operator[key];//該模板類中過載了 [] 運運算元，其功能是可以向存取陣列中元素那樣，只要給定某個鍵值對的鍵 key，就可以獲取該鍵對應的值。注意，如果當前容器中沒有以 key 為鍵的鍵值對，則其會使用該鍵向當前容器中插入一個新鍵值對
at(key);//返回容器中儲存的鍵 key 對應的值，如果key不存在，則會丟擲 out_of_range 異常
find(key);//查詢以key為鍵的鍵值對，如果找到，則返回一個指向該鍵值對的正向迭代器；反之，則返回一個指向容器中最後一個鍵值對之後位置的迭代器（如果end()方法返回的迭代器）

元素的插入和刪除

emplace();//向容器中新增新鍵值對，效率比 insert()方法高
emplace_hint();//向容器中新增新鍵值對，效率比insert()方法高
insert();//向容器中新增新鍵值對
erase();//刪除指定鍵值對
clear();//清空容器，即刪除容器中儲存的所有鍵值對
swap();//交換2個unordered_map容器儲存的鍵值對，前提是必須保證這2個容器的型別完全相等

void test_unordered_map()
{
	unordered_map<int, int> um;
	map<int, int> m;

	int arr[] = { 4,2,3,1,6,8,9,3 };

	for (auto e : arr)
	{
		um.insert(make_pair(e, e));
		m.insert(make_pair(e, e));
	}

	unordered_map<int, int>::iterator umit = um.begin();
	map<int, int>::iterator mit = m.begin();

	cout << "unordered_map:" << endl;
	while (umit != um.end())
	{
		cout << umit->first << ":" << umit->second << endl;
		++umit;
	}
	cout << "map:" << endl;
	while (mit != m.end())
	{
		cout << mit->first << ":" << mit->second << endl;
		++mit;
	}
}

unordered_map和unordered_set的實現

整體概述

這裡我們用上一篇的部落格中的雜湊桶來封裝出unordered_map和unordered_set兩個容器

雜湊桶程式碼：HashTable.h檔案

#pragma once
#include<iostream>
#include<vector>
using namespace std;
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, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};
//仿函數，獲取key值
template<class K, class V>
struct KeyOfValue
{
	const K& operator()(const K& key)
	{
		return key;
	}
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;
	}
};
namespace CLOSE_HASH
{
	//閉雜湊，需要三種狀態
	enum State
	{
		EMPTY,
		EXITS,
		DELETE
	};
	//定義節點
	template <class T>
	struct HashData
	{
		//這裡的data物件是匿名物件轉化的，被const修飾不能修改，就是傳參的關係，你傳入了一個物件
		//被const修飾，就代表傳入的那個物件不能被修改，你自己的內容還是可以修改的
		HashData(const T& data = T(), const State& state = EMPTY)
			: data(data)
			, state(state){}
		T data;
		State state;
	};
	//雜湊表
	template<class K, class T, class KOFV>
	class HashTable
	{
		typedef HashData<T> HashData;
	public:
		HashTable(size_t capacity = 10)
			: table(capacity)
			, size(0)
		{}
		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)
		{
			return key % table.size();
		}
		//插入元素
		bool Insert(const T& data)
		{
			/*
			1.首先要判斷是否需要增容，當裝填因子>0.7的時候增容（裝填因子 = 資料個數/雜湊表大小）
			2.建立一個新表，把舊錶的元素重新放到新表當中，因為表的大小發生變化，所以資料在舊錶中的位置和新表的位置不一樣，需要重新調整
			3.利用swap將兩個表進行交換，函數結束的時候，舊錶被自動解構
			4.增容之後，插入元素，採用線性探測，插入元素
			*/
			KOFV kofv;
			if (size * 10 / table.size() >= 7)//增容
			{
				//增容的大小按照別人算好的近似兩倍的素數來增，這樣效率更高，也可以直接2倍或者1.5倍。
				//使用了vector預設的有參建構函式vector(size_type n, const value_type& val = value_type())//有參構造用n個val構造並初始化容器
				//const value_type& val = value_type()這段程式碼是匿名物件型別轉換
				vector<HashData> newTable(getNextPrime(size));
				for (size_t i = 0; i < table.size(); i++)
				{
					//將舊錶中的元素對映到新表當中
					if (table[i].state == EXITS)
					{
						int index = HashFunc(kofv(table[i].data));
						while (newTable[index].state == EXITS)
						{
							//不可能存在重複元素，因為舊錶中不可能有重複元素
							index++;
							if (index == newTable.capacity())
							{
								index = 0;
							}
						}
						newTable[index]=table[i];

					}
				}
				table.swap(newTable);//交換兩個表
			}
			//用雜湊函數計算出對映的位置
			size_t index = HashFunc(kofv(data));
			//int start = index;
			//int i = 1;
			while (table[index].state == EXITS)
			{
				if (table[index].data == data)
					return false;
				// 二次探測
				/*index = start + pow(i, 2);
				index %= _tables.size();
				++i;*/
				++index;
				// 走到末尾置0
				if (index == table.size())
					index = 0;
			}
			// DELETE和EMPTY的位置都可以插入資料
			table[index].data = data;
			table[index].state = EXITS;
			++size;
			return true;
		}
		//查詢元素
		HashData* Find(const K& key)
		{
			KOFV kofv;
			size_t index = HashFunc(key);
			int start = index;
			while (table[index].state != EMPTY)
			{
				if (kofv(table[index].data) == key)
				{
					if (table[index].state == EXITS)
					{
						return &table[index];
					}
					// table[index].state == DELETE
					else
					{
						//表示你要找的元素已經被刪除了
						return nullptr;
					}
					
				}
				++index;
				if (index == table.size())
					index = 0;
				// 找完一遍沒有就退出  這裡其實是不必要的，這裡面一定有空的位置，所以一定會退出
				if (index == start)
				{
					return nullptr;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData* ret = Find(key);
			//找到了，進行刪除
			if (ret != nullptr)
			{
				ret->state = DELETE;
				size--;
				return true;
			}
			else
			{
				//沒找到
				return false;
			}
		}
	private:
		vector<HashData> table;
		int size = 0;
	};
	void TestHashTable1()
	{
		HashTable<int, int, KeyOfValue<int, int>> ht;
		// HashTable<int, pair<int, int>, KeyOfValue<int, int>> ht;

		int arr[] = { 10,20,14,57,26,30,49,72,43,55,82 };
		for (auto e : arr)
		{
			if (e == 72)
			{
				int a = 0;
			}
			ht.Insert(e);
		}

		for (auto e : arr)
		{
			ht.Erase(e);
		}
	}

	void TestHashTable2()
	{
		HashTable<int, pair<int, int>, KeyOfValue<int, int>> ht;

		int arr[] = { 15,23,57,42,82,26,30,49,72,43,55 };
		for (auto e : arr)
		{
			ht.Insert(make_pair(e, e));
		}

		/*for (auto e : arr)
		{
			ht.Erase(e);
		}*/
	}

}
namespace OPEN_HASH
{
	template<class T>
	struct HashNode
	{
		HashNode(const T&data):data(data),next(nullptr){}
		T data;
		HashNode<T>* next;
	};
	template<class K>
	struct _Hash
	{
		// 大多樹的型別就是是什麼型別就返回什麼型別
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	// 特化string
	template<>
	struct _Hash<string>
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			// 把字串的所有字母加起來   hash = hash*131 + key[i]
			for (size_t i = 0; i < key.size(); ++i)
			{
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};
	//前置宣告
	template<class K, class T, class KOFV, class Hash = _Hash<K>>
	class HashBucket;
	//迭代器的實現
	template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
	struct HashBucket_Iterator
	{
		typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
		typedef HashNode<T> Node;
		typedef HashBucket<K, T, KOFV, Hash> HashBucket;

		Node* node;
		HashBucket* _phb;
		HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
		//操作符過載
		Ref operator*()
		{
			return node->data;
		}
		Ptr operator->()
		{
			return &node->data;
		}
		Self& operator++()
		{
			if (node->next)
			{
				node = node->next;
				return *this;
			}
			else
			{
				KOFV kofv;
				size_t index = _phb->HashFunc(kofv(node->data));

				for (size_t i = index + 1; i < _phb->tables.size(); ++i)
				{
					if (_phb->tables[i])
					{
						node = _phb->tables[i];
						return *this;
					}
				}
				node = nullptr;
				return *this;
			}
		}

		bool operator==(const Self& self) const
		{
			return node == self.node
				&& _phb == self._phb;
		}

		bool operator!=(const Self& self) const
		{
			return !this->operator==(self);
		}
	};
	template<class K, class T, class KOFV, class Hash>
	class HashBucket
	{
		typedef HashNode<T> Node;
		friend struct HashBucket_Iterator<K, T, T&, T*, KOFV, Hash>;
	public:
		typedef HashBucket_Iterator<K, T, T&, T*, KOFV, Hash> iterator;
		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) % tables.size();
		}
		iterator begin()
		{
			for (size_t i = 0; i < tables.size(); ++i)
			{
				if (tables[i] != nullptr)
					return iterator(tables[i], this);// 雜湊桶的第一個節點 
			}
			return end();// 沒有節點返回最後一個迭代器
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		~HashBucket()
		{
			Clear();
		}
		void Clear()
		{
			for (size_t i = 0; i < tables.size(); ++i)
			{
				Node* cur = tables[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}
		pair<iterator, bool> Insert(const T& data)
		{
			KOFV kofv;
			//負載因子為1就增容
			if (size == tables.size())
			{
				vector<Node*> newTable(getNextPrime(size));
				for (size_t i = 0; i < tables.size(); i++)
				{
					Node* prev = nullptr;
					Node* cur = tables[i];
					//把一個位置的所有節點轉移，然後換下一個位置
					while (cur)
					{
						//記錄下一個節點的位置
						Node* next = cur->next;
						size_t index = HashFunc(kofv(cur->data));
						//把cur連線到新表上
						cur->next = newTable[index];
						newTable[index] = cur;
						//cur會發生變化，需要提前記錄next
						cur = next;
					}
				}
				tables.swap(newTable);
			}
			size_t index = HashFunc(kofv(data));
			// 先查詢該條連結串列上是否有要插入的元素
			Node* cur = tables[index];
			while (cur)
			{
				if (kofv(cur->data) == kofv(data))
					return make_pair(iterator(cur, this), false);
				cur = cur->next;
			}
			// 插入資料，選擇頭插（也可以尾插）
			Node* newnode = new Node(data);
			newnode->next = tables[index];
			tables[index] = newnode;
			++size;
			return make_pair(iterator(newnode, this), true);
		}
		iterator Find(const K& key)
		{
			KOFV kofv;
			int index = HashFunc(key) ;
			Node* cur = tables[index];

			while (cur)
			{
				if (key == kofv(cur->data))
				{
					return iterator(cur, this);
				}
				cur = cur->next;
			}
			return iterator(nullptr);
		}

		bool Erase(const K& key)
		{
			KOFV kofv;
			int index = HashFunc(key) ;

			Node* prev = nullptr;
			Node* cur = tables[index];

			while (cur)
			{
				if (key == kofv(cur->data))
				{
					// 刪第一個節點時
					if (prev == nullptr)
					{
						tables[index] = cur->next;
					}
					else
					{
						prev->next = cur->next;
					}

					size--;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->next;
			}
			return false;
		}
	private:
		vector<Node*> tables;
		int size = 0;
	};
	void TestHashBucket2()
	{
		HashBucket<int, int, KeyOfValue<int, int>> ht;
		int arr[] = { 15,23,57,42,82,26,30,49,72,43,55 };
		for (auto e : arr)
		{
			ht.Insert(e);
		}

		for (auto e : arr)
		{
			HashBucket<int, int, KeyOfValue<int, int>>::iterator it = ht.begin();

			while (it != ht.end())
			{
				cout << *it << " ";
				++it;
			}
			cout << endl;
			ht.Erase(e);
		}
	}

	void TestHashBucket3()
	{
		HashBucket<string, string, KeyOfValue<string, string>> ht;

		ht.Insert("solleHas");
		ht.Insert("apple");
		ht.Insert("sort");
		ht.Insert("pass");
		ht.Insert("cet6");
		HashBucket<string, string, KeyOfValue<string, string>>::iterator it = ht.begin();
		while (it != ht.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

改造雜湊表

整體框架

這裡用的是雜湊桶來封裝unordered_map和unordered_set兩個容器

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, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};
template<class T>
struct HashNode
{
	HashNode(const T&data):data(data),next(nullptr){}
	T data;
	HashNode<T>* next;
};
template<class K>
struct _Hash
{
	// 大多樹的型別就是是什麼型別就返回什麼型別
	const K& operator()(const K& key)
	{
		return key;
	}
};
// 特化string
template<>
struct _Hash<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		// 把字串的所有字母加起來   hash = hash*131 + key[i]
		for (size_t i = 0; i < key.size(); ++i)
		{
			hash *= 131;
			hash += key[i];
		}
		return hash;
	}
};
template<class K, class T, class KOFV, class Hash>
class HashBucket
{
private:
		vector<Node*> tables;
		int size = 0;// 記錄表中的資料個數
};

為了讓雜湊表能夠跑起來，我們這裡實現一個迭代器的操作
迭代器的框架： 這裡有兩個成員，一個是節點指標，還有一個是雜湊表的指標，只要就是為了方便實現迭代器++遍歷雜湊表的操作。模板參數列的前四個主要是為了實現普通迭代器和const迭代器，第五個引數就是為了獲得T中的key值，是一個仿函數（前幾篇部落格都有提到過），最後一個模板引數是雜湊函數，為了構造出雜湊表指標而存在

template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
struct HashBucket_Iterator
{
	typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
	typedef HashNode<T> Node;
	typedef HashBucket<K, T, KOFV, Hash> HashBucket;

	Node* node;
	HashBucket* _phb;
	HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
}

迭代器基本操作的實現：

//迭代器的實現
	template<class K, class T, class Ref, class Ptr, class KOFV, class Hash>
	struct HashBucket_Iterator
	{
		typedef HashBucket_Iterator<K, T, Ref, Ptr, KOFV, Hash> Self;
		typedef HashNode<T> Node;
		typedef HashBucket<K, T, KOFV, Hash> HashBucket;

		Node* node;
		HashBucket* _phb;
		HashBucket_Iterator(Node *node, HashBucket* phb):node(node),_phb(phb){}
		//操作符過載
		Ref operator*()
		{
			return node->data;
		}
		Ptr operator->()
		{
			return &node->data;
		}
		Self& operator++()
		{
			if (node->next)
			{
				node = node->next;
				return *this;
			}
			else
			{
				KOFV kofv;
				size_t index = _phb->HashFunc(kofv(node->data));

				for (size_t i = index + 1; i < _phb->tables.size(); ++i)
				{
					if (_phb->tables[i])
					{
						node = _phb->tables[i];
						return *this;
					}
				}
				node = nullptr;
				return *this;
			}
		}

		bool operator==(const Self& self) const
		{
			return node == self.node
				&& _phb == self._phb;
		}

		bool operator!=(const Self& self) const
		{
			return !this->operator==(self);
		}
	};

雜湊表內部改造：

template<class K, class T, class KOFV, class Hash>
	class HashBucket
	{
		typedef HashNode<T> Node;
		friend struct HashBucket_Iterator<K, T, T&, T*, KOFV, Hash>;
	public:
		typedef HashBucket_Iterator<K, T, T&, T*, KOFV, Hash> iterator;
		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) % tables.size();
		}
		iterator begin()
		{
			for (size_t i = 0; i < tables.size(); ++i)
			{
				if (tables[i] != nullptr)
					return iterator(tables[i], this);// 雜湊桶的第一個節點 
			}
			return end();// 沒有節點返回最後一個迭代器
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		~HashBucket()
		{
			Clear();
		}
		void Clear()
		{
			for (size_t i = 0; i < tables.size(); ++i)
			{
				Node* cur = tables[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
			}
		}
	};

封裝unordered_map和unordered_set

unordered_set.h標頭檔案

#pragma once
#include"HashTable.h"
using namespace OPEN_HASH;
namespace Simulation
{
template<class K, class Hash = _Hash<K>>
class unordered_set
{
	struct SetKeyOfValue
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	// 告訴編譯器這只是一個型別
	typedef HashBucket<K, K, SetKeyOfValue, Hash> HashBucket;
public:
	// 告訴編譯器這只是一個型別
	typedef typename HashBucket::iterator iterator;

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

	pair<iterator, bool> insert(const K& kv)
	{
		return _ht.Insert(kv);
	}
	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}
	iterator find(const K& key)
	{
		return _ht.Find(key);
	}
private:
	HashBucket _ht;
};
void test_unordered_set1()
{
	unordered_set<int> s;

	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(2);
	s.insert(4);

	s.erase(3);
	for (auto e : s)
	{
		cout << e << endl;
	}
}

void test_unordered_set2()
{
	unordered_set<string> s;

	s.insert("sort");
	s.insert("pass");
	s.insert("cet6");
	s.insert("pass");
	s.insert("cet6");

	s.erase("sort");

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

unordered_map.h標頭檔案

#pragma once
#include"HashTable.h"
using namespace OPEN_HASH;
namespace Simulation
{
	template<class K, class V, class Hash = _Hash<K>>
	class unordered_map
	{
		struct MapKeyOfValue
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

		typedef HashBucket<K, pair<K, V>, MapKeyOfValue, Hash> HashBucket;
	public:
		// 告訴編譯器這只是一個型別
		typedef typename HashBucket::iterator iterator;

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

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		HashBucket _ht;
	};
	void test_unordered_map1()
	{
		unordered_map<int, int> um;

		um.insert(make_pair(1, 1));
		um.insert(make_pair(3, 3));
		um.insert(make_pair(2, 2));
		um.insert(make_pair(4, 4));

		for (auto& e : um)
		{
			cout << e.first << ":" << e.second << endl;
		}

		/*unordered_map<int, int>::iterator it = um.begin();
		++it;
		cout << it->first << endl;*/
	}

	void test_unordered_map2()
	{
		unordered_map<string, string> um;

		um.insert(make_pair("string", "字串"));
		um.insert(make_pair("sort", "排序"));
		um.insert(make_pair("pass", "通過"));
		um.insert(make_pair("program", "程式"));

		for (auto& e : um)
		{
			cout << e.first << ":" << e.second << endl;
		}

		/*unordered_map<int, int>::iterator it = um.begin();
		++it;
		cout << it->first << endl;*/
	}

	void test_unordered_map3()
	{
		unordered_map<string, int> countMap;

		string strArr[] = { "香蕉","香蕉" ,"水蜜桃","西瓜","蘋果","西瓜","香蕉" ,"蘋果","西瓜","蘋果","蘋果","香蕉" ,"水蜜桃" };

		for (auto& e : strArr)
		{
			countMap[e]++;
		}

		countMap["芒果"] = 10;

		for (auto& e : countMap)
		{
			cout << e.first << ":" << e.second << endl;
		}
	}
}

typedef詳解

搞懂了c++創始人寫的< the design and evolution of cpp >中的下面這個例子, 有助於你理解typdef:

typedef int P();
typedef int Q();
class X {
    static P(Q); // 等價於static int Q(), Q在此作用域中不再是一個型別
    static Q(P); // 等價於static int Q(int ()), 定義了一個名為Q的function
};

隱藏技能：typedef 定義的新型別, 使用時可以省略括號

typedef int NUM;
NUM a = 10; // 也可寫成`NUM(a) = 10;`
NUM(b) = 12; // 也可寫成`NUM b = 12;`

官方定義
初次接觸此類typedef用法的程式設計師直觀上理解這個例子比較困難, 我們來看一下typedef的官方定義:

Typedef does not work like typedef [type] [new name]. The [new name] part does not always come at the end.

You should look at it this way: if [some declaration] declares a variable, typedef [same declaration] would define a type

看我標黑的這句話, 總結一下就是: 任何宣告變數的語句前面加上typedef之後，原來是變數的都變成一種型別。不管這個宣告中的識別符號號出現在中間還是最後

舉個例子：

初級：

typedef int x; // 定義了一個名為x的int型別
typedef struct { char c; } s; // 定義名為s的struct型別
typedef int *p; //定義了一個名為p的指標型別, 它指向int (中文描述指標好累)

高階：（注意識別符號不一定在最後）

typedef int A[];  // 定義一個名為A的int陣列的型別
typedef int f(); // 定義一個名為f, 引數為空, 返回值為int的函數型別
typedef int g(int); // 定義一個名為g, 含一個int引數, 返回值為int的函數型別

這時候我們回頭看一開始的那個例子：

typedef int P();
static P(Q);

這樣就比較好理解了吧，typedef定義了一個名叫P，引數為空，返回值是int的函數型別，根據我上面介紹的隱藏技能，P(Q)就等價於P Q，宣告Q是一個返回值為int

這玩意有什麼用呢?
我們都知道C++語言裡, 函數都是先宣告後使用的(除非在使用之前定義), 看以下例子:

#include <iostream>
#include <stdio.h>
#include <string>
 
typedef int P(); // 簡單的
typedef void Q(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true); // 複雜的
class X {
public:
    P(eat_shit); // 等價於宣告`int eat_shit();`
    Q(bullshit); // 等價於宣告`void bullshit(int *p, const string& s1, const string& s2, size_t size, bool is_true);`
};
 
int main() {
    X *xx;
    printf("shit ret: %d\n", xx->eat_shit());
    int a[] = {1, 3, 4, 5, 7};
    xx->bullshit(a, "foo", "bar", sizeof(a)/sizeof(int), true);
}
 
int X::eat_shit() {
    return 888;
}
 
void X::bullshit(int *p, const std::string& s1, const std::string& s2, size_t size, bool is_true) {
    std::cout << "s1: " << s1 << ", s2: " << s2 << ", size: " << size << std::endl;
    printf("elems:\n");
    for(int i = 0; i < size; i++) {
        printf("%d %s",  *p++, (i == size-1) ? "" : ",");
    }
    printf("\n");
}

總結:

  • type (var)(...); // 變數名var與結合，被圓括號括起來，右邊是參數列。表明這是函數指標
  • type (var)[]; //變數名var與結合，被圓括號括起來，右邊是[]運運算元。表示這是陣列指標
  • type (*var[])...; // 變數名var先與[]結合，說明這是一個陣列（至於陣列包含的是什麼，由旁邊的修飾決定）

typename詳解

"typename"是一個C++程式設計語言中的關鍵字。當用於泛型程式設計時是另一術語"class"的同義詞。這個關鍵字用於指出模板宣告（或定義）中的非獨立名稱（dependent names）是型別名，而非變數名

typename 的作用就是告訴 c++ 編譯器，typename 後面的字串為一個型別名稱，而不是成員函數或者成員變數，這個時候如果前面沒有 typename，編譯器沒有任何辦法知道 T::LengthType 是一個型別還是一個成員名稱(靜態資料成員或者靜態函數)，所以編譯不能夠通過。
舉個例子：假設你現在要針對某一種容器設定一個操作函數

template <class T>
void func (){
    T::iteartor * testpt;
}

看到這段程式碼的時候我們大多數情況下都是可以看出來，這一段程式碼中的操作是定義了一個容器的迭代器指標型別的變數。但是模版是在編譯期間展開的，只有在模版範例化的時候編譯器才可以推匯出其型別。這段程式碼對於編譯器來說很有可能產生錯誤的理解，因為我們能快速的根據iteartor是一個迭代器想到這是定義了一個變數，但是對於編譯器來說，它怎麼會知道一定知道T::iteartor一定是一個迭代器型別，或者一定知道這是一個型別？因為能表示成這樣形式的程式碼有三種情況：

  • 在T作用域中存在一個iteartor的靜態變數
  • 在T作用域中存在一個iteartor的靜態成員函數
  • 是T型別的成員變數

以上三種含義均可以表示成例子中的樣子，編譯器怎麼知道這是哪一種。在實踐過程中，編譯器會直接對testpt報錯，而且在模板範例化之前，完全沒有辦法來區分它們，這絕對是滋生各種bug的溫床。這時C++標準委員會再也忍不住了，與其到範例化時才能知道到底選擇哪種方式來解釋以上程式碼，委員會決定引入一個新的關鍵字，這就是typename

typename真正的用途

編譯期間模版的推導有一個這樣的規則：如果解析器在template推導期間遇到了巢狀從屬名稱，那麼不指定他為一個型別，解析器就一定不會把它當成一個型別。

什麼是巢狀從屬型別？

事實上型別T::const_iterator依賴於模板引數T， 模板中依賴於模板引數的名稱稱為從屬名稱（dependent name）， 當一個從屬名稱巢狀在一個類裡面時，稱為巢狀從屬名稱（nested dependent name）。 其實T::const_iterator還是一個巢狀從屬型別名稱（nested dependent type name）。巢狀從屬名稱是需要用typename宣告的，其他的名稱是不可以用typename宣告的。

總結：巢狀從屬名稱是需要用typename宣告的，其他的名稱是不可以用typename宣告的

T::iteartor這種，這也就是為什麼編譯器會對testpt報錯的原因。那要怎樣指定testpt為一個型別，這就回到了開頭的那個問題，我們可以這樣解決

template <class T>
void func (){
    typename T::iteartor * testpt;
}

加上了typename之後我們就可以知道T::iteartor是一個型別，編譯器也可以根據這個進行型別推導了