C++ 基于哈希表封装 unordered_map 与 unordered_set

一、源码及框架分析

SGI-STL30 版本源代码中没有 unordered_map 和 unordered_set，SGI-STL30 版本是 C++11 之前的 STL 版本，这两个容器是 C++11 之后才更新的。但是 SGI-STL30 实现了哈希表，只容器的名字是 hash_map 和 hash_set，他是作为非标准的容器出现的，非标准是指非 C++ 标准规定必须实现的，源代码在 hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h 中 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;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::const_iterator iterator;
    typedef typename ht::const_iterator const_iterator;
    hasher hash_funct() const { return rep.hash_funct(); }
    key_equal key_eq() const { return rep.key_eq(); }
};

// stl_hash_map
template<class Key, class ,   = hash<Key>,  EqualKey = equal_to<Key>,  Alloc = alloc>
 hash_map {
:
     hashtable<pair< Key, T>, Key, HashFcn, select1st<pair< Key, T>>, EqualKey, Alloc> ht;
    ht rep;
:
      ht::key_type key_type;
     T data_type;
     T mapped_type;
      ht::value_type value_type;
      ht::hasher hasher;
      ht::key_equal key_equal;
      ht::iterator iterator;
      ht::const_iterator const_iterator;
};


< ,  ,  ,  ,  ,  >
  {
:
     Key key_type;
     Value value_type;
     HashFcn hasher;
     EqualKey key_equal;
:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
     __hashtable_node<Value> node;
    vector<node*, Alloc> buckets;
    size_type num_elements;
:
     __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
    ;
    ;
};

< >
  {
    __hashtable_node* next;
    Value val;
};