概述
本文对hash_table进行封装，以模仿SGI STL对unordered系列容器进行简单实现，旨在加深对C++封装与泛型技法的体会与理解。阅读本文之前，建议先对哈希表进行学习。本文是以hash_table的实现为基础的，建议与关联式数据结构_哈希表剖析 #C++进行结合阅读。
unordered_map
与map一样，unordered_map的所有元素类型都是pair，pair的第一个成员为Key，第二个成员为Value。因为Key在任何情况下都不允许被修改，所以Key在pair中其实是被const修饰的。使用unordered_map的目的是根据键值快速搜寻元素，unordered_map底层是散列表，不具有对元素自动排序的功能。总体上来说，unordered_map的期望搜索效率相比map更高。从使用方面来讲，unordered_map与map的用法完全相同。
template<class Key, class Value>
class unordered_map
{
/*…………*/
private:
hash_table<Key, pair<const Key, Value>, MapKeyOfT> _hash_table;
};MapKeyOfT
MapKeyOfT仿函数的设计目的与在map中的一样，均是为了拿到元素中的Key值，只不过在这里拿到Key值的目的是以Key计算元素的索引，将元素放到合适的桶中。
struct MapKeyOfT
{
const Key& operator()(const pair<const Key, Value>& kv)
{
return kv.first;
}
};在hash_table层面，MapKeyOfT被视为模板参数KeyOfT，以同时兼容unordered_map和unordered_set，而不必关心hash_table的具体使用者及具体函数的内部实现细节。
迭代器
对于unordered_map，可以通过迭代器修改元素的Value，但不允许通过迭代器修改元素的Key，这是因为任意修改Key会破坏hash_table的组织。unordered_map的迭代器直接对hash_table进行复用即可。
public:
typedef typename hash_table<Key, pair<const Key, Value>, MapKeyOfT>::iterator iterator;
typedef typename hash_table<Key, pair<const Key, Value>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _hash_table.begin();
}
iterator end()
{
return _hash_table.end();
}
const_iterator begin() const
{
return _hash_table.begin();
}
const_iterator end() const
{
return _hash_table.end();
}在对unordered_map进行插入操作时，不存在迭代器失效问题；进行删除操作时，被删除的元素的迭代器失效。
元素操作
unordered_map的大部分接口，直接对hash_table的接口进行复用即可。
//插入元素
pair<iterator, bool> insert(const pair<Key, Value>& kv)
{
return _hash_table.insert(std::make_pair(kv.first, kv.second));
}
//删除元素
iterator erase(const Key& key)
{
return _hash_table.erase(key);
}
//查找元素
iterator find(const Key& key) const
{
return _hash_table.find(key);
}operator[]是unordered_map特有的接口，本质是对hash_table的insert接口的复用，支持用户方便地通过Key对对应元素的Value进行修改。
Value& operator[](const Key& key)
{
pair<iterator, bool> retInsert = insert(make_pair(key, Value()));
return retInsert.first->second;
}
const Value& operator[](const Key& key) const
{
pair<iterator, bool> retInsert = insert(make_pair(key, Value()));
return retInsert.first->second;
}unordered_set
unordered_set的元素不像unordered_map那样同时拥有Key和Value，可以认为，unordered_set的Key就是Value，Value就是Key。
template<class Key>
class unordered_set
{
/*…………*/
private:
hash_table<Key, Key, SetKeyOfT> _hash_table;
};SetKeyOfT
对于unordered_set的KeyOfT仿函数，只需要直接返回元素的Key值即可。unordered_set的KeyOfT的设计目的完全是为了迁就unordered_map，以进行兼容。
struct SetKeyOfT
{
const Key& operator()(const Key& key)
{
return key;
}
};迭代器
同理，不能通过unordered_set的迭代器修改键值，为了杜绝修改操作，可以直接将hash_table的const迭代器作为unordered_set的普通迭代器。unordered_set的迭代器是一种const iterators。
typedef typename hash_table<Key, Key, SetKeyOfT>::const_iterator iterator;
typedef typename hash_table<Key, Key, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _hash_table.begin();
}
iterator end() const
{
return _hash_table.end();
}在对unordered_set进行插入操作时，不存在迭代器失效问题；进行删除操作时，被删除的元素的迭代器失效。
元素操作
unordered_set的大部分接口可以直接复用hash_table的接口。
iterator erase(const Key& key)
{
return _hash_table.erase(key);
}
iterator find(const Key& key) const
{
typename HashBucket::hash_table<Key, Key, SetKeyOfT>::iterator ret = _hash_table.find(key);
return iterator(ret);
}对于insert接口，与set同理，由于返回值类型不一致，需要进行一层转换，支持转换的关键是，在__hash_table_iterator中额外搞一个构造函数。
template<class Key, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
struct __hash_table_iterator
{
private:
typedef __hash_table_iterator<Key, T, T&, T*, KeyOfT, HashFunc> iterator;
public:
//对于iterator，这个函数是拷贝构造
//对于const_iterator，这个函数是构造
//使用iterator构造const_iterator
__hash_table_iterator(Node* node, const HashTable* hash_table)
:_node(node),
_hash_table(hash_table)
{ }
/*…………*/
};完成这个迭代器的构造函数之后，就可以对hash_table::insert的返回值进行转化，与unordered_set::insert进行匹配。
pair<iterator, bool> insert(const Key& key)
{
pair<typename HashBucket::hash_table<Key, Key, SetKeyOfT>::iterator, bool> ret =
_hash_table.insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}