C++ unordered 系列容器使用及模拟实现

一、unordered_map 和 unordered_set 的使用

1. unordered_set 系列的使用

1.1 unordered_set 和 unordered_multiset 参考文档

<unordered_set> - C++ Reference

1.2 unordered_set 类的介绍

• unordered_set 的声明如下，Key 就是 unordered_set 底层关键字的类型。
• unordered_set 默认要求 Key 支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将 Key 转成整形的仿函数传给第二个模板参数。
• unordered_set 默认要求 Key 支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将 Key 比较相等的仿函数传给第三个模板参数。
• unordered_set 底层是用哈希桶实现，增删查平均效率是 O(1)，迭代器遍历无序。

因为 unordered 系列容器底层是通过哈希桶实现，因为要支持哈希函数以及处理哈希冲突的方式，所以 Key 要支持转换成整形并且要求支持比较相等。针对不能转换成整形的类型，支持通过传入仿函数进行转换。

• unordered_set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数，一般情况下，我们都不需要传后三个模板参数。

其实一开始 STL 库先提供了 map/set 容器（红黑树封装实现），不过后来鉴于哈希桶实现的 map 和 set 确实有自身优势，STL 就又提供相关哈希桶实现容器。不过因为 map、set 的命名已经确定了，如果以 hashmap/hashset 新容器命名，无法很好凸显不同容器的特点。因为红黑树实现的 map、set 迭代器遍历有序，哈希表实现的遍历不再有序，所以 STL 中取名为 unordered_set/unordered_map。

前面部分我们已经学习了 set 容器的使用，set 和 unordered_set 的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。

template < class Key, // unordered_set::key_type / value_type 
            class Hash = hash<Key>, // unordered_set::hasher 
            class Pred = equal_to<Key>, // unordered_set::key_equal 
            class Alloc = allocator<Key> // unordered_set::allocator_type 
           > 
class unordered_set;

1.3 unordered_set 和 set 的使用差异

• 查看文档我们会发现 unordered_set 的支持增删查且跟 set 的使用一模一样，关于使用我们这里就不再赘述和演示了。
• unordered_set 和 set 的第一个差异是对 key 的要求不同，set 要求 Key 支持小于比较，而 unordered_set 要求 Key 支持转成整形且支持等于比较，要理解 unordered_set 的这个两点要求要结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
• unordered_set 和 set 的第二个差异是迭代器的差异，set 的 iterator 是双向迭代器，unordered_set 是单向迭代器。其次 set 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 set 迭代器遍历是有序 + 去重。而 unordered_set 底层是哈希表，迭代器遍历是无序 + 去重。
• unordered_set 和 set 的第三个差异是性能的差异，整体而言大多数场景下，unordered_set 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。具体可以参看下面代码的演示的对比差异。

#include <iostream>
#include <vector>
#include <ctime>
#include <unordered_set>
#include <set>
using namespace std;

int test_set2() {
    const size_t N = 1000000;
    unordered_set<int> us;
    set<int> s;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; ++i) {
        v.push_back(rand() + i); // 重复值相对少
    }
    
    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();
    us.reserve(N);
    for (auto e : v) { us.insert(e); }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;
    
     m1 = ;
     begin3 = ();
     ( e : v) {
         ret = s.(e);
         (ret != s.()) { ++m1; }
    }
     end3 = ();
    cout <<  << end3 - begin3 <<  << m1 << endl;
    
     m2 = ;
     begin4 = ();
     ( e : v) {
         ret = us.(e);
         (ret != us.()) { ++m2; }
    }
     end4 = ();
    cout <<  << end4 - begin4 <<  << m2 << endl;
    
    cout <<  << s.() << endl;
    cout <<  << us.() << endl << endl;
    
     begin5 = ();
     ( e : v) { s.(e); }
     end5 = ();
    cout <<  << end5 - begin5 << endl;
    
     begin6 = ();
     ( e : v) { us.(e); }
     end6 = ();
    cout <<  << end6 - begin6 << endl << endl;
     ;
}

{
    ();
     ;
}

1.4 unordered_map 和 map 的使用差异

• 查看文档我们会发现 unordered_map 的支持增删查改且跟 map 的使用一模一样，关于使用我们这里就不再赘述和演示了。
• unordered_map 和 map 的第一个差异是对 key 的要求不同，map 要求 Key 支持小于比较，而 unordered_map 要求 Key 支持转成整形且支持等于比较，要理解 unordered_map 的这个两点要求得后续结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
• unordered_map 和 map 的第二个差异是迭代器的差异，map 的 iterator 是双向迭代器，unordered_map 是单向迭代器。其次 map 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 map 迭代器遍历是 Key 有序 + 去重。而 unordered_map 底层是哈希表，迭代器遍历是 Key 无序 + 去重。
• unordered_map 和 map 的第三个差异是性能的差异，整体而言大多数场景下，unordered_map 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而哈希表增删查平均效率是 O(1)。

pair<iterator, bool> insert(const value_type& val);
size_type erase(const key_type& k);
iterator find(const key_type& k);
mapped_type& operator[] (const key_type& k);

1.5 unordered_multimap/unordered_multiset

• unordered_multimap/unordered_multiset 跟 multimap/multiset 功能完全类似，支持 Key 冗余。
• unordered_multimap/unordered_multiset 跟 multimap/multiset 的差异也是三个方面的差异：key 的要求的差异，iterator 及遍历顺序的差异，性能的差异。

1.6 unordered_xxx 的哈希相关接口

Buckets 和 Hash policy 系列的接口分别是跟哈希桶和负载因子相关的接口，日常使用的角度我们不需要太关注。

Buckets	接口说明
bucket_count	返回容器中的桶数量
max_bucket_count	返回容器可以拥有的最大桶数
bucket_size	返回桶 n 中的元素数量
bucket	返回元素值 k 所在的桶号

Hash policy	接口说明
load_factor	返回容器中的当前负载因子
max_load_factor	获取或设置最大负载因子
rehash	将容器中的桶数量设置为 n 或更多，如果 n 大于容器中当前的桶数量（bucket_count），则会强制执行重新散列。新的桶数量可以等于或大于 n；如果 n 小于容器中当前的桶数量（bucket_count），该函数可能对桶数量没有影响，也可能不会强制执行重新散列，这取决于底层实现。rehash 是哈希表的重建：容器中的所有元素将根据其哈希值重新排列到新的桶集中。这可能改变容器内元素的迭代顺序，当容器的负载因子即将超过其最大负载因子时，容器会自动执行 rehash，请注意，此函数需要桶的数量作为参数。存在一个类似的函数 unordered_set::reserve，它需要容器中元素的数量作为参数。
reserve	将容器中的桶数量（bucket_count）设置为最适合至少包含 n 个元素的数量，如果 n 大于当前 bucket_count 乘以 max_load_factor，则容器中的 bucket_count 会增加，并强制进行重新哈希，如果 n 小于这个值，该函数可能没有任何效果 (这取决于底层实现)。

二、用哈希表封装 myunordered_map 和 myunordered_set

1. 源码及框架分析

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 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< 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;
};

• 这里我们就不再画图分析了，通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 的完全类似，复用同一个 hashtable 实现 key 和 key/value 结构，hash_set 传给 hash_table 的是两个 key，hash_map 传给 hash_table 的是 pair<const key, value>。
• 需要注意的是源码里面跟 map/set 源码类似，命名风格比较乱。下面我们模拟一份自己的出来，就按自己的风格走了。

2. 模拟实现 unordered_map 和 unordered_set

2.1 实现出复用哈希表的框架，并支持 insert

• 参考源码框架，unordered_map 和 unordered_set 复用之前我们实现的哈希表。
• 我们这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型，我们使用 T。
• 其次跟 map 和 set 相比而言 unordered_map 和 unordered_set 的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为 HashTable 实现泛型时从内部无法知道模版参数 T 是 K，还是 pair<K, V>，并且 insert 内部进行插入时要用 K 对象转换成整形取模和 K 比较相等，因为 pair 的 value 不参与计算取模，且默认支持的是 key 和 value 一起比较相等，我们任何时候只需要比较 K 对象，所以我们在 unordered_map 和 unordered_set 层分别实现一个 MapKeyOfT 和 SetKeyOfT 的仿函数传给 HashTable 的 KeyOfT，然后 HashTable 中通过 KeyOfT 仿函数取出 T 类型对象中的 K 对象，再转换成整形取模和 K 比较相等，具体细节参考如下代码实现。

// MyUnorderedSet.h
namespace my_lib {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) { return key; }
    };
public:
    bool insert(const K& key) { return _ht.Insert(key); }
private:
    hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}

// MyUnorderedMap.h
namespace my_lib {
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:
    bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
private:
    hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};
}

// HashTable.h
template<class K> struct HashFunc {
    {  ()key; }
};

 hash_bucket {
< >   {
    T _data;
    HashNode<T>* _next;
    ( T& data) :_data(data), _next() {}
};

< ,  ,  ,  >
  {
     HashNode<T> Node;
       __stl_next_prime(  n) {
           __stl_num_primes = ;
            __stl_prime_list[__stl_num_primes] = { 
            , , , , , , , , , , , , 
            , , , , , , , , 
            , , , , , , 
            ,  
        };
          * first = __stl_prime_list;
          * last = __stl_prime_list + __stl_num_primes;
          * pos = (first, last, n);
         pos == last ? *(last - ) : *pos;
    }
:
    () { _tables.(__stl_next_prime(_tables.()), ); }
    ~() {
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {
                Node* next = cur->_next;
                 cur;
                cur = next;
            }
            _tables[i] = ;
        }
    }
    {
        KeyOfT kot;
         (((data)))  ;
        Hash hs;
         hashi = ((data)) % _tables.();
        
         (_n == _tables.()) {
            ;
             ( i = ; i < _tables.(); i++) {
                Node* cur = _tables[i];
                 (cur) {
                    Node* next = cur->_next;
                     hashi = ((cur->_data)) % newtables.();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = ;
            }
            _tables.(newtables);
        }
        
        Node* newnode =  (data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
         ;
    }
:
    vector<Node*> _tables;
     _n = ;
};
}

2.2 支持 iterator 的实现

iterator 核心源代码

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
    typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
    typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
    typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
    typedef __hashtable_node<Value> node;
    typedef forward_iterator_tag iterator_category;
    typedef Value value_type;
    node* cur;
    hashtable* ht;
    __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
    __hashtable_iterator() {}
    reference operator*() const { return cur->val; }
    pointer operator->() const { return &(operator*()); }
    iterator& operator++();
    iterator operator++(int);
    bool operator==(const iterator& it) const { return cur == it.cur; }
    bool operator!=(const iterator& it) const { return cur != it.cur; }
};

template <class V,  ,  ,  ,  ,  >
__hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::++() {
     node* old = cur;
    cur = cur->next;
     (!cur) {
        size_type bucket = ht->(old->val);
         (!cur && ++bucket < ht->buckets.()) cur = ht->buckets[bucket];
    }
     *;
}

iterator 实现思路分析

• iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
• 这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。
• begin()返回第一个桶中第一个节点指针构造的迭代器，我们需要遍历找到第一个节点然后返回，这里我们可以判断下如果哈希表内没有节点直接结束。这里**end() 返回迭代器可以用空表示**。
• unordered_set 的 iterator 也不支持修改，因此这里我们就参考前面 set/map 的设计，我们把**unordered_set 的第二个模板参数改成 const K 即可， HashTable<K, const K, SetKeyOfT, Hash> _ht**。
• unordered_map 的 iterator 不支持修改 key 但是可以修改 value，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可， HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht。

在封装迭代器时，与前文 map/set 中不同，这里因为 operator++() 遍历，我们需要根据哈希表的数组、哈希函数确定桶的位置，而后面封装的哈希表接口又会返回迭代器，所以这里实际上相互包含，我们需要在迭代器上方声明一下哈希表。

// HashTable.h
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 *= 131;
            hash += e;
        }
        return hash;
    }
};

// 封装的哈希桶
namespace hash_bucket {
template<class T> struct HashNode {
    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,  ,  ,  ,  ,  >
  {
     HashNode<T> Node;
     HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
    Node* _node;
     HashTable<K, T, KeyOfT, Hash>* _pht;
    (Node* node,  HashTable<K, T, KeyOfT, Hash>* pht) :_node(node), _pht(pht) {}
    Ref *() {  _node->_data; }
    Ptr ->() {  &_node->_data; }
     !=( Self& s) {  _node != s._node; }
    Self& ++() {
         (_node->_next) {
            _node = _node->_next;
        }  {
            KeyOfT kot;
            Hash hs;
             hashi = ((_node->_data)) % _pht->_tables.();
            ++hashi;
             (hashi < _pht->_tables.()) {
                 (_pht->_tables[hashi]) { ; }
                ++hashi;
            }
             (hashi == _pht->_tables.()) {
                _node = ; 
            }  {
                _node = _pht->_tables[hashi];
            }
        }
         *;
    }
};

< ,  ,  ,  >
  {
    < ,  ,  ,  ,  ,  >
      ;
     HashNode<T> Node;
:
     HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
     HTIterator<K, T,  T*,  T&, KeyOfT, Hash> ConstIterator;
    {
         (_n == )  ();
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {  (cur, ); }
        }
         ();
    }
    {  (, ); }
    {
         (_n == )  ();
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {  (cur, ); }
        }
         ();
    }
    {  (, ); }
       __stl_next_prime(  n) {
           __stl_num_primes = ;
            __stl_prime_list[__stl_num_primes] = { 
            , , , , , , , , , , , , 
            , , , , , , , , 
            , , , , , , 
            ,  
        };
          * first = __stl_prime_list;
          * last = __stl_prime_list + __stl_num_primes;
          * pos = (first, last, n);
         pos == last ? *(last - ) : *pos;
    }
    () { _tables.(__stl_next_prime(_tables.()), ); }
    ~() {
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {
                Node* next = cur->_next;
                 cur;
                cur = next;
            }
            _tables[i] = ;
        }
    }
    {
        KeyOfT kot;
        Iterator it = ((data));
         (it != ())  (it, );
        Hash hs;
         hashi = ((data)) % _tables.();
         (_n == _tables.()) {
            ;
             ( i = ; i < _tables.(); i++) {
                Node* cur = _tables[i];
                 (cur) {
                    Node* next = cur->_next;
                     hashi = ((cur->_data)) % newtables.();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = ;
            }
            _tables.(newtables);
        }
        Node* newnode =  (data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
         ((newnode, ), );
    }
    {
        KeyOfT kot;
        Hash hs;
         hashi = (key) % _tables.();
        Node* cur = _tables[hashi];
         (cur) {
             ((cur->_data) == key) {  (cur, ); }
            cur = cur->_next;
        }
         ();
    }
    {
        KeyOfT kot;
        Hash hs;
         hashi = (key) % _tables.();
        Node* prev = ;
        Node* cur = _tables[hashi];
         (cur) {
             ((cur->_data) == key) {
                 (prev == ) { _tables[hashi] = cur->_next; }
                 { prev->_next = cur->_next; }
                 cur;
                --_n;
                 ;
            }
            prev = cur;
            cur = cur->_next;
        }
         ;
    }
:
    vector<Node*> _tables;
     _n = ;
};
}

2.3 map 支持 []

• unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为 pair<Iterator, bool> Insert(const T& data)。
• 有了 insert 支持 [] 实现就很简单了，具体参考下面代码实现。

pair<Iterator, bool> Insert(const T& data) {
    KeyOfT kot;
    Iterator it = Find(kot(data));
    if (it != End()) return make_pair(it, false);
    Hash hs;
    size_t hashi = hs(kot(data)) % _tables.size();
    if (_n == _tables.size()) {
        vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                size_t hashi = hs(kot(cur->_data)) % newtables.size();
                cur->_next = newtables[hashi];
                newtables[hashi] = cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newtables);
    }
    Node* newnode = new Node(data);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_n;
    return make_pair(Iterator(newnode, this), true);
}

2.4 my_lib::unordered_map 和 my_lib::unordered_set 代码实现

有了哈希表及其迭代器的封装后，我们在这基础上再封装一层来实现 unordered 系列容器。

// MyUnorderedSet.h
namespace my_lib {
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, const K, SetKeyOfT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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(); }
    pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
    iterator Find(const K& key) {  _ht.(key); }
    {  _ht.(key); }
:
    hash_bucket::HashTable<K,  K, SetKeyOfT, Hash> _ht;
};
{
    unordered_set<> s;
     a[] = { , , , , , , , , , , , ,  };
     ( e : a) { s.(e); }
     ( e : s) { cout << e << ; }
    cout << endl;
    unordered_set<>::iterator it = s.();
     (it != s.()) {
        cout << *it << ;
        ++it;
    }
    cout << endl;
}
}


 my_lib {
< ,  ,   = HashFunc<K>>
 unordered_map {
     MapKeyOfT {
         K& ()( pair<K, V>& kv) {  kv.first; }
    };
:
      hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash>::Iterator iterator;
      hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
    {  _ht.(); }
    {  _ht.(); }
    {  _ht.(); }
    {  _ht.(); }
    {  _ht.(kv); }
    V& []( K& key) {
        pair<iterator, > ret = _ht.((key, ()));
         ret.first->second;
    }
    {  _ht.(key); }
    {  _ht.(key); }
:
    hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash> _ht;
};
{
    unordered_map<string, string> dict;
    dict.({ ,  });
    dict.({ ,  });
    dict.({ ,  });
    dict[] = ;
    dict[] = ;
    dict[];
    unordered_map<string, string>::iterator it = dict.();
     (it != dict.()) {
        it->second += ;
        cout << it->first <<  << it->second << endl;
        ++it;
    }
    cout << endl;
}
}


< >   {
    {  ()key; }
};
<>  <string> {
    {
         hash = ;
         ( e : key) {
            hash *= ;
            hash += e;
        }
         hash;
    }
};
 hash_bucket {
< >   {
    T _data;
    HashNode<T>* _next;
    ( T& data) :_data(data), _next() {}
};
< ,  ,  ,  >  ;
< ,  ,  ,  ,  ,  >
  {
     HashNode<T> Node;
     HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;
    Node* _node;
     HashTable<K, T, KeyOfT, Hash>* _pht;
    (Node* node,  HashTable<K, T, KeyOfT, Hash>* pht) :_node(node), _pht(pht) {}
    Ref *() {  _node->_data; }
    Ptr ->() {  &_node->_data; }
     !=( Self& s) {  _node != s._node; }
    Self& ++() {
         (_node->_next) {
            _node = _node->_next;
        }  {
            KeyOfT kot;
            Hash hs;
             hashi = ((_node->_data)) % _pht->_tables.();
            ++hashi;
             (hashi < _pht->_tables.()) {
                 (_pht->_tables[hashi]) { ; }
                ++hashi;
            }
             (hashi == _pht->_tables.()) {
                _node = ;
            }  {
                _node = _pht->_tables[hashi];
            }
        }
         *;
    }
};
< ,  ,  ,  >
  {
    < ,  ,  ,  ,  ,  >
      ;
     HashNode<T> Node;
:
     HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
     HTIterator<K, T,  T*,  T&, KeyOfT, Hash> ConstIterator;
    {
         (_n == )  ();
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {  (cur, ); }
        }
         ();
    }
    {  (, ); }
    {
         (_n == )  ();
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {  (cur, ); }
        }
         ();
    }
    {  (, ); }
       __stl_next_prime(  n) {
           __stl_num_primes = ;
            __stl_prime_list[__stl_num_primes] = { 
            , , , , , , , , , , , , 
            , , , , , , , , 
            , , , , , , 
            ,  
        };
          * first = __stl_prime_list;
          * last = __stl_prime_list + __stl_num_primes;
          * pos = (first, last, n);
         pos == last ? *(last - ) : *pos;
    }
    () { _tables.(__stl_next_prime(_tables.()), ); }
    ~() {
         ( i = ; i < _tables.(); i++) {
            Node* cur = _tables[i];
             (cur) {
                Node* next = cur->_next;
                 cur;
                cur = next;
            }
            _tables[i] = ;
        }
    }
    {
        KeyOfT kot;
        Iterator it = ((data));
         (it != ())  (it, );
        Hash hs;
         hashi = ((data)) % _tables.();
         (_n == _tables.()) {
            ;
             ( i = ; i < _tables.(); i++) {
                Node* cur = _tables[i];
                 (cur) {
                    Node* next = cur->_next;
                     hashi = ((cur->_data)) % newtables.();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i] = ;
            }
            _tables.(newtables);
        }
        Node* newnode =  (data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
         ((newnode, ), );
    }
    {
        KeyOfT kot;
        Hash hs;
         hashi = (key) % _tables.();
        Node* cur = _tables[hashi];
         (cur) {
             ((cur->_data) == key) {  (cur, ); }
            cur = cur->_next;
        }
         ();
    }
    {
        KeyOfT kot;
        Hash hs;
         hashi = (key) % _tables.();
        Node* prev = ;
        Node* cur = _tables[hashi];
         (cur) {
             ((cur->_data) == key) {
                 (prev == ) { _tables[hashi] = cur->_next; }
                 { prev->_next = cur->_next; }
                 cur;
                --_n;
                 ;
            }
            prev = cur;
            cur = cur->_next;
        }
         ;
    }
:
    vector<Node*> _tables;
     _n = ;
};
}