C++ 基于哈希表封装 unordered_map 与 unordered_set 模拟实现

C++ 基于哈希表封装 unordered_map 与 unordered_set 模拟实现

1. 源码及框架分析

SGI STL 30 版本源代码中没有 unordered_map 和 unordered_set，这两个容器是 C++11 之后才更新的。但是 SGI STL 实现了哈希表，只是容器的名字是 hash_map 和 hash_set，它是作为非标准的容器出现的。

hash_map 和 hash_set 的实现结构框架核心部分如下：

// stl_hash_set
template<class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc>
class hash_set {
private:
    typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef typename ht::value_type value_type;
    // ... 省略部分代码
};

// stl_hash_map
template<class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map {
private:
    typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;
    ht rep;
public:
    // ... 省略部分代码
};

通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 的完全类似，复用同一个 实现 和 结构。需要注意的是源码里面命名风格比较乱，下面模拟实现一份自己的出来，统一风格。