STL(七) unordered_set 与 unordered_map 基本用法 + 模拟实现
目录
unordered_set 与 unordered_map 模拟实现
unordered_set 和 unordered_map 提供迭代器接口
前置知识：数据结构(十一) 哈希表
unordered_set 使用
#include <iostream> #include <unordered_set> using namespace std; void test1() { unordered_set<int> st; st.insert(1); st.insert(3); st.insert(2); st.insert(4); unordered_set<int>::iterator it = st.begin(); while (it != st.end()) { cout << *it << " "; ++it; } cout << endl; it = st.find(3); if (it != st.end()) cout << *it << "存在" << endl; st.erase(1); if (st.count(1)) cout << "1存在" << endl; } // unordered_set 的负载因子最大是1 void test2() { unordered_set<int> st; st.insert(1); st.insert(3); st.insert(2); st.insert(4); cout << st.load_factor() << endl; //0.5 cout << st.max_load_factor() << endl; //1 st.insert(6); st.insert(8); cout << st.load_factor() << endl; //0.75 cout << st.max_load_factor() << endl; //1 st.insert(5); st.insert(7); cout << st.load_factor() << endl; //1 cout << st.max_load_factor() << endl; //1 } void test3() { unordered_set<int> st; for (int i = 0; i < 100000; i++) st.insert(rand() + i); cout << "当前桶数: " << st.bucket_count() << endl; cout << "最大桶数: " << st.max_bucket_count() << endl; // 安全的检查桶大小 if (33 < st.bucket_count()) { cout << "33号桶的大小: " << st.bucket_size(33) << endl; } // 安全的查找元素33 auto it = st.find(33); if (it != st.end()) { cout << "元素33在桶" << st.bucket(33) << "中" << endl; } else { cout << "元素33不存在" << endl; } } int main() { test1(); test2(); test3(); return 0; }unordered_map 使用
#include <iostream> #include <unordered_map> using namespace std; void test1() { unordered_map<int, int> mp; mp.insert(make_pair(1, 1)); mp.insert(make_pair(5, 5)); mp.insert(make_pair(2, 2)); mp.insert(make_pair(4, 4)); mp.insert(make_pair(3, 3)); unordered_map<int, int>::iterator it = mp.begin(); while (it != mp.end()) { cout << it->first << ":" << it->second << endl; it++; } it = mp.find(3); if (it != mp.end()) { cout << "找到了 " << it->first << ":" << it->second << endl; } mp.erase(it); if (!mp.count(3)) { cout << "没有找到3" << endl; } mp[3] = 5; cout << mp[3] << endl; } void test2() { string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; unordered_map<string, int> mp; for (auto& e : arr) { unordered_map<string, int>::iterator ret = mp.find(e); if (ret != mp.end()) { ret->second++; } else { mp.insert(make_pair(e, 1)); } } for (auto& e : mp) { cout << e.first << " " << e.second << endl; } } int main() { test1(); test2(); return 0; }unordered_set 与 unordered_map 模拟实现
前置知识：STL(六) set 与 map 基本用法 + 模拟实现
模拟实现的整体思路与 set & map 的模拟实现非常类似，因此很多相同的地方就不过多展开介绍了
哈希桶节点的改造
底层哈希桶并不知道封装自己的是 unordered_map 还是 unordered_set，因此将数据类型设为 T
template<class T> class HashNode { public: T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} };封装整体逻辑
1. 将 底层哈希表的 Hash模板参数的缺省值作为上层的 unoredered_set / unoredered_map的模板参数的缺省值 更合理
2. 哈希表查找 / 删除，直接需要 key 值，因此上层的 unoredered_set / unoredered_map还要有第一个模板参数 K
3.在哈希表 插入 / 查找 时会用到 key 值，因此还需要 KeyOfT 仿函数，获取 key值
迭代器
哈希表的迭代器依旧是一个类，类中封装了节点指针，从而使得迭代器对象可以模拟指针的行为
template<class T, class Ref, class Ptr> struct __HTIterator { typedef HashNode<T> Node; typedef __HTIterator<T, Ref, Ptr> self; Node* _node; __HTIterator(Node* node) :_node(node) { } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } };重点来了，迭代器++如何实现？ 迭代器++的本质是找下一个节点，而哈希表中如何找当前节点的下一个节点呢？由于我们底层使用的是哈希桶结构，因此找下一个节点分为两种情况：
1. 当前节点的下一个节点不为空，那么直接 _node = _node->_next;
2. 当前节点的下一个节点为空，说明当前桶已经遍历完了，因此需要寻找下一个有元素的桶，而寻找下一个有元素的桶，显然需要用到 哈希表中的 _tables 数组，
因此我们需要在迭代器中再加入一个成员，那就是哈希表：HashTable<K, T, KeyOfT, Hash>* _pht
因此我们需要将 哈希表的模版参数全部加到 迭代器的模版参数上
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator { //哈希表迭代器的3个成员变量 Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; size_t _hashi; //当前节点所在桶的编号 } 此时我们在编译的时候会报错，因为迭代器类 是位于 哈希表类之前的，而迭代器类中也用到了 哈希表类，会有"相互依赖的"问题，也就是编译器在编译 迭代器类的代码时还不认识 哈希表呢，因此需要在迭代器类之前添加哈希表前置声明：
//迭代器和哈希表相互依赖, 需要前置声明 template<class K, class T, class KeyOfT, class Hash> class HashTable;此外，由于我们在迭代器内部会使用到 哈希表的 私有成员_tables，因此还需要将 迭代器类声明为 哈希表的 友元类:
template<class K, class T, class KeyOfT, class Hash> class HashTable { //迭代器内部用到了 哈希表的私有成员 _tables, 需要友元声明 template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator; };operator++：如果下一个节点为空，需要寻找下一个有元素的桶，因此还需要知道当前桶的编号，我们可以通过下面一行代码来计算出当前桶的编号，但确实比较麻烦，因此我们在迭代器中再加入一个成员：当前节点所在桶的编号：_hashi
size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();那么在构造迭代器时就需要初始化三个成员
__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node) , _pht(pht) , _hashi(hashi) { }operator++ 的实现如下：
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self; self& operator++() { if (_node->_next) { _node = _node->_next; } else //当前桶遍历完了, 寻找下一个有元素的桶 { _hashi++; while (_hashi < _pht->_tables.size()) { if (_pht->_tables[_hashi]) { _node = _pht->_tables[_hashi]; break; } _hashi++; } if (_hashi == _pht->_tables.size()) { _node = nullptr; } } return *this; }注：需要说明的是我们提供的迭代器访问顺序是 按照桶的编号顺序，而库中迭代器访问顺序是 按照元素的插入顺序
哈希表内部提供迭代器接口
template<class K, class T, class KeyOfT, class Hash> class HashTable { typedef HashNode<T> Node; //迭代器内部用到了 哈希表的私有成员 _tables, 需要友元声明 template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator; public: typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator; //普通迭代器 typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator; //const迭代器 public: //迭代器接口 iterator begin() //返回第一个桶的第一个元素 { for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return iterator(_tables[i], this, i); } } return end(); } iterator end() { return iterator(nullptr, this, -1); } const_iterator begin() const { for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return const_iterator(_tables[i], this, i); } } return end(); } const_iterator end() const { return const_iterator(nullptr, this, -1); } };注意，此时编译会有问题，const 版本的 begin 和 end 接口在返回的时候 构造迭代器 会有权限放大的问题
因此我们将构造函数的参数以及 _pht 成员都加上 const
unordered_set 和 unordered_map 提供迭代器接口
unordered_set：内部元素不能修改，因此无论是 普通迭代器，还是 const 迭代器，底层封装的都是哈希表的 const 迭代器
namespace dck { 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, K, SetKeyOfT, Hash>::const_iterator iterator; typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator; const_iterator begin() const { return _ht.begin(); } const_iterator end() const { return _ht.end(); } private: hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht; }; }unordered_map：普通迭代器的 key不能修改，value可以修改，const 迭代器 的 key 和 value 都不能修改，因此 普通迭代器底层是哈希表的普通迭代器，const 迭代器底层是哈希表的 const的 迭代器，给 pair 中的 key 带上 const 确保无论是普通迭代器还是 const迭代器，key都无法修改
namespace dck { 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>::const_iterator 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(); } private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; }; }查找接口
哈希表的 Find 接口的返回值我们需要从 bool 改造成 iterator，也要在需要用到 key 的地方将仿函数套上去
iterator Find(const K& key) { Hash hf; KeyOfT kot; size_t hashi = hf(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this, hashi); cur = cur->_next; } return end(); }unordered_set / unordered_map 的 find 接口：
iterator find(const K& key) { return _ht.Find(key); }插入接口
哈希表的 Insert 接口的返回值我们需要从 bool 改造成 pair<iterator，bool>，也要在需要用到 key 的地方将仿函数套上去
pair<iterator, bool> Insert(const T& data) { KeyOfT kot; iterator it = Find(kot(data)); if (it != end()) return make_pair(it, false); Hash hf; if (_n == _tables.size()) //哈希桶的负载因子我们设置为1 { size_t newSize = _tables.size() * 2; vector<Node*> newTables; newTables.resize(newSize); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hf(kot(cur->_data)) % newSize; cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } //头插新节点 size_t hashi = hf(kot(data)) % _tables.size(); Node* newNode = new Node(data); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return make_pair(iterator(newNode, this, hashi), true); }unordered_map 的 insert 接口：
pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }unordered_set 的 insert 接口：
pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }注意，unordered_set 的 insert 接口 采用上面这种写法会直接编译报错
正确的写法：
使用返回的 普通迭代器的三个成员变量构造出 const 迭代器即可
pair<iterator, bool> insert(const K& key) { auto ret = _ht.Insert(key); return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second); }删除接口
bool Erase(const K& key) { Hash hf; size_t hashi = hf(key) % _tables.size(); // 映射位置 Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) // 处理删除第一个节点的情况 { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; return true; } prev = cur; cur = cur->_next; } return false; }unordered_set / unordered_map 的 erase 接口：
iterator erase(const K& key) { return _ht.Erase(key); }unordered_map 的 [ ] 接口
V& operator[](const K& key) { pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; }测试接口
#include <unordered_set> #include "MyUnorderedSet.h" #include "MyUnorderedMap.h" void test_unordered_set() { dck::unordered_set<int> st; st.insert(4); st.insert(1); st.insert(2); st.insert(3); dck::unordered_set<int>::iterator it = st.begin(); while (it != st.end()) { cout << *it << " "; ++it; } cout << endl; //1 2 3 4 (我们自己迭代器的实现按照桶的顺序） unordered_set<int> st1; st1.insert(4); st1.insert(1); st1.insert(2); st1.insert(3); unordered_set<int>::iterator it1 = st1.begin(); while (it1 != st1.end()) { cout << *it1 << " "; //4 1 2 3 (库中迭代器的实现按照插入顺序) ++it1; } cout << endl; } //测试 unordered_map 的 const 迭代器 void print(const dck::unordered_map<int, int>& mp) { dck::unordered_map<int, int>::const_iterator it = mp.begin(); while (it != mp.end()) { cout << it->first << " " << it->second << endl; ++it; } cout << endl; } void test_unordered_map() { dck::unordered_map<int, int> mp; mp.insert(make_pair(4, 4)); mp.insert(make_pair(1, 1)); mp.insert(make_pair(2, 2)); mp.insert(make_pair(3, 3)); print(mp); dck::unordered_map<int, int>::iterator it = mp.begin(); while (it != mp.end()) { it->first++; //err it->second++; cout << it->first << " " << it->second << endl; ++it; } string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; dck::unordered_map<string, int> countMap; for (auto x : arr) countMap[x]++; for (auto t : countMap) { cout << t.first << " " << t.second << endl; } cout << endl; } int main() { test_unordered_set(); test_unordered_map(); return 0; }哈希桶效率测试
哈希桶中提供 Some 接口测试 哈希桶使用情况、最大桶长度、平均桶长度等指标。
void Some() { size_t bucketSize = 0; size_t maxBucketLen = 0; size_t sum = 0; double averageBucketLen = 0; for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { ++bucketSize; } size_t bucketLen = 0; while (cur) { ++bucketLen; cur = cur->_next; } sum += bucketLen; if (bucketLen > maxBucketLen) { maxBucketLen = bucketLen; } } averageBucketLen = (double)sum / (double)bucketSize; printf("all bucketSize:%d\n", _tables.size()); //表的大小 printf("bucketSize:%d\n", bucketSize); //使用了多少个桶 printf("maxBucketLen:%d\n", maxBucketLen); //最长的桶挂了多少个元素 printf("averageBucketLen:%lf\n\n", averageBucketLen); //平均桶长度 }#include <set> #include <unordered_set> #include "HashTable.h" void test() { const size_t N = 1000000; unordered_set<int> us; set<int> s; hash_bucket::HashTable<int, int> ht; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; ++i) { //v.push_back(rand()); // N比较大时，重复值比较多 v.push_back(rand() + i); // 重复值相对少 //v.push_back(i); // 没有重复，有序 } // 21:15 size_t begin1 = clock(); for (auto e : v) { s.insert(e); } size_t end1 = clock(); cout << "set insert:" << end1 - begin1 << endl; size_t begin2 = clock(); for (auto e : v) { us.insert(e); } size_t end2 = clock(); cout << "unordered_set insert:" << end2 - begin2 << endl; size_t begin10 = clock(); for (auto e : v) { ht.Insert(make_pair(e, e)); } size_t end10 = clock(); cout << "HashTbale insert:" << end10 - begin10 << endl << endl; size_t begin3 = clock(); for (auto e : v) { s.find(e); } size_t end3 = clock(); cout << "set find:" << end3 - begin3 << endl; size_t begin4 = clock(); for (auto e : v) { us.find(e); } size_t end4 = clock(); cout << "unordered_set find:" << end4 - begin4 << endl; size_t begin11 = clock(); for (auto e : v) { ht.Find(e); } size_t end11 = clock(); cout << "HashTable find:" << end11 - begin11 << endl << endl; cout << "插入数据个数：" << us.size() << endl << endl; ht.Some(); size_t begin5 = clock(); for (auto e : v) { s.erase(e); } size_t end5 = clock(); cout << "set erase:" << end5 - begin5 << endl; size_t begin6 = clock(); for (auto e : v) { us.erase(e); } size_t end6 = clock(); cout << "unordered_set erase:" << end6 - begin6 << endl; size_t begin12 = clock(); for (auto e : v) { ht.Erase(e); } size_t end12 = clock(); cout << "HashTable Erase:" << end12 - begin12 << endl << endl; } int main() { test(); return 0; }
可以看到，在数据量比较大的情况下，unordered_set 的插入、查找、删除等性能都是高于 set 的，并且最长的桶下面只挂了两个元素，平均桶长度只有 1.28 左右，时间复杂度接近 O(1)，而我们实现的哈希表之所以比STL库的哈希表还快的主要原因是 库中哈希表的迭代器遍历是按照插入顺序实现的，因此还要额外维护一些信息，执行一些操作，时间复杂度就比较高了
附实现代码
HashTable.h：
#pragma once #include <iostream> #include <vector> using namespace std; //哈希函数(默认, 整数) template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; //将负数转化为正数 } }; //类模板特化 template<> struct HashFunc<string> { //字符串不能直接取模，先用字符串映射一个整形, 就能取模了! size_t operator()(const string& key) { size_t hash = 0; for (auto& e : key) { hash *= 31; //解决字母完全一样但是顺序不一样而导致冲突的问题 hash += e; } return hash; } }; //仿函数 //struct HashFuncString //{ // size_t operator()(const string& key) // { // size_t hash = 0; // for (auto& e : key) // { // hash *= 31; //解决字母完全一样但是顺序不一样而导致冲突的问题 // hash += e; // } // cout << key << ":" << hash << endl; // return hash; // } //}; //哈希桶 namespace hash_bucket { template<class T> class HashNode { public: 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 Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator { typedef HashNode<T> Node; typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self; Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; size_t _hashi; //构造函数 __HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node) ,_pht(pht) ,_hashi(hashi) { } //找下一个节点 self& operator++() { if (_node->_next) { _node = _node->_next; } else //当前桶遍历完了, 寻找下一个有元素的桶 { _hashi++; while (_hashi < _pht->_tables.size()) { if (_pht->_tables[_hashi]) { _node = _pht->_tables[_hashi]; break; } _hashi++; } if (_hashi == _pht->_tables.size()) { _node = nullptr; } } 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 { typedef HashNode<T> Node; //迭代器内部用到了 哈希表的私有成员 _tables, 需要友元声明 template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator; public: typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator; //普通迭代器 typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator; //const迭代器 public: //迭代器接口 iterator begin() //返回第一个桶的第一个元素 { for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return iterator(_tables[i], this, i); } } return end(); } iterator end() { return iterator(nullptr, this, -1); } const_iterator begin() const { for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return const_iterator(_tables[i], this, i); } } return end(); } const_iterator end() const { return const_iterator(nullptr, this, -1); } public: //构造函数 HashTable() { _tables.resize(10); } //析构函数 ~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; } } //查找函数 iterator Find(const K& key) { Hash hf; KeyOfT kot; size_t hashi = hf(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return iterator(cur, this, hashi); cur = cur->_next; } return end(); } pair<iterator, bool> Insert(const T& data) { KeyOfT kot; iterator it = Find(kot(data)); if (it != end()) return make_pair(it, false); Hash hf; if (_n == _tables.size()) //哈希桶的负载因子我们设置为1 { size_t newSize = _tables.size() * 2; vector<Node*> newTables; newTables.resize(newSize); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hf(kot(cur->_data)) % newSize; cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } //头插新节点 size_t hashi = hf(kot(data)) % _tables.size(); Node* newNode = new Node(data); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return make_pair(iterator(newNode, this, hashi), true); } //删除函数 bool Erase(const K& key) { Hash hf; size_t hashi = hf(key) % _tables.size(); // 映射位置 Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) // 处理删除第一个节点的情况 { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; size_t _n; //当前哈希表中的元素个数 }; }MyUnorderedSet.h：
#pragma once #include "HashTable.h" namespace dck { 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, K, SetKeyOfT, Hash>::const_iterator iterator; typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator; pair<iterator, bool> insert(const K& key) { auto ret = _ht.Insert(key); return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second); } iterator find(const K& key) { return _ht.Find(key); } iterator erase(const K& key) { return _ht.Erase(key); } const_iterator begin() const { return _ht.begin(); } const_iterator end() const { return _ht.end(); } private: hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht; }; } MyUnorderedMap.h：
#pragma once #include "HashTable.h" namespace dck { 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>::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); } iterator 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: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; }; } 
