C++进阶（unordered_set+unordered_map模拟实现）

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: %dn", 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是一个类型，编译器也可以根据这个进行类型推导了