三、迭代器
迭代器需要前置声明HashTable，因为HashTable类中使用了__HTIterator迭代器，且__HTIterator中使用了HashTable类的指针，为什么要用指针呢？
因为C++编译器自上而下编译源文件的时候，对每一个数据的定义，需要知道定义的数据类型的大小。在预先声明语句class HashTable;之后，编译器已经知道HashTable是一个类，但是其中的数据却是未知的，因此HashTable类型的大小也不知道，这样就造成了编译失败；将__HTIterator中的_node更改为HashTable指针类型之后，由于在特定的平台上，指针所占的空间是一定的（在Win32平台上是4字节，在64位平台上是8字节），这样可以通过编译。
迭代器的参数包含哈希节点和哈希表：
1. // 前置声明 2. template<class K, class T, class KeyOfT, class HashFunc> 3. class HashTable; 4. 5. // 迭代器 6. template<class K, class T, class KeyOfT, class HashFunc = Hash<K>> 7. struct __HTIterator 8. { 9. typedef HashNode<T> Node;//哈希节点 10. typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;//实现++、-- 11. typedef HashTable<K, T, KeyOfT, HashFunc> HT;//哈希表 12. Node* _node; 13. HT* _pht; 14. 15. __HTIterator(Node* node, HT* pht) 16. :_node(node)//哈希节点 17. , _pht(pht)//哈希表 18. {} 19. };
1.operator++( )
如下图，operator++ 分两种情况：
①当前节点不是哈希表当前位置的最后一个节点，如2、53，返回当前节点的next节点
②当前节点是哈希表当前位置的最后一个节点，如852、63，需要返回下一个非空位置的第一个节点
1. Self& operator++() 2. { 3. //不是当前位置最后一个节点 4. if (_node->_next) 5. { 6. _node = _node->_next; 7. } 8. else//是当前位置最后一个节点 9. { 10. KeyOfT kot; 11. HashFunc hf; 12. 13. size_t index = hf(kot(_node->_data)) % _pht->_table.size(); 14. 15. //找哈希表中下一个不为空的位置 16. ++index; 17. while (index < _pht->_table.size()) 18. { 19. if (_pht->_table[index])//不为空 20. { 21. _node = _pht->_table[index]; 22. return *this; 23. } 24. else//为空 25. { 26. ++index; 27. } 28. } 29. _node = nullptr;//后面的所有位置都为空，_node置空，返回当前位置即可 30. } 31. 32. return *this; 33. }
2.operator*( )
取_data即可：
1. T& operator*() 2. { 3. return _node->_data; 4. }
3.operator->( )
取_data的地址即可：
1. T* operator->() 2. { 3. return &_node->_data; 4. }
4.operator !=( )
将s的_node和_node进行比较：
1. bool operator != (const Self& s) const 2. { 3. return _node != s._node; 4. }
5.operator ==( )
将s的_node和_node进行比较：
1. bool operator == (const Self& s) const 2. { 3. return _node == s._node; 4. }
四、封装unordered_set和unordered_map
1.封装unordered_set
unordered_set的成员就是哈希表，不过要传模板参数，SetKeyOfT就是传给哈希表的仿函数
1. #pragma once 2. #include "HashTable.h" 3. 4. namespace delia 5. { 6. template<class K> 7. class unordered_set 8. { 9. 10. private: 11. OpenHash::HashTable<K, K, SetKeyOfT> _ht ; 12. 13. }; 14. }
（1）仿函数SetKeyOfT
set直接取k:
1. //set就取k 2. struct SetKeyOfT 3. { 4. const K& operator()(const K& k) 5. { 6. return k; 7. } 8. };
（2）迭代器
对于unordered_set的迭代器，如果不加typename，类模板里面找迭代器的类型找不到，因为OpenHash::HashTable<K, K, SetKeyOfT>::iterator没有实例化，因此编译器并不知道它是类型还是成员函数或成员变量，编译无法通过。
用typename表明OpenHash::HashTable<K, K, SetKeyOfT>::iterator是一个类型，不是成员函数或成员变量，不需要等到实例化时才能确定。
unordered_set的迭代器都调用哈希表的迭代器进行操作：
1. public: 2. typedef typename OpenHash::HashTable<K, K, SetKeyOfT>::iterator iterator; 3. 4. iterator begin() 5. { 6. return _ht.begin(); 7. } 8. 9. iterator end() 10. { 11. return _ht.end(); 12. } 13. 14. pair<iterator, bool> Insert(const K& k) 15. { 16. return _ht.Insert(k); 17. }
（3）实例
向unordered_set中插入一些数据，并打印：
1. void test_unordered_set1() 2. { 3. unordered_set<int> us; 4. us.Insert(100); 5. us.Insert(5); 6. us.Insert(6); 7. us.Insert(32); 8. us.Insert(8); 9. us.Insert(14); 10. us.Insert(65); 11. us.Insert(27); 12. us.Insert(39); 13. 14. unordered_set<int>::iterator it = us.begin(); 15. while (it != us.end()) 16. { 17. cout << *it << " "; 18. ++it; 19. } 20. cout << endl; 21. }
2.封装unordered_map
unordered_map的成员就是哈希表，不过要传模板参数，MapKeyOfT就是传给哈希表的仿函数 :
1. #pragma once 2. #include "HashTable.h" 3. 4. namespace delia 5. { 6. template<class K,class V> 7. class unordered_map 8. { 9. 10. 11. private: 12. OpenHash::HashTable<K, pair<K, V>, MapKeyOfT> _ht; 13. 14. };
（1）仿函数MapKeyOfT
map就取kv的first:
1. //map就取kv的first 2. struct MapKeyOfT 3. { 4. const K& operator()(const pair<K,V>& kv) 5. { 6. return kv.first; 7. } 8. };
（2）迭代器
同unordered_set的迭代器定义一样，前面要加上typename，unordered_map的迭代器都调用哈希表的迭代器进行操作：
1. public: 2. typedef typename OpenHash::HashTable<K, pair<K,V>, MapKeyOfT>::iterator iterator; 3. 4. iterator begin() 5. { 6. return _ht.begin(); 7. } 8. 9. iterator end() 10. { 11. return _ht.end(); 12. } 13. 14. pair<iterator, bool> Insert(const pair<K,V>& kv) 15. { 16. return _ht.Insert(kv); 17. } 18. 19. V& operator[](const K& key) 20. { 21. pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); 22. return ret.first->iterator; 23. }
（3）实例
1. void test_unordered_map1() 2. { 3. unordered_map<string,string> um; 4. um.Insert(make_pair("spring", "春天")); 5. um.Insert(make_pair("summer", "夏天")); 6. um.Insert(make_pair("autumn", "秋天")); 7. um.Insert(make_pair("winter", "冬天")); 8. 9. unordered_map<string,string>::iterator it = um.begin(); 10. while (it != um.end()) 11. { 12. cout << it->first << ":" << it->second << endl; 13. ++it; 14. } 15. }
