/// Hashtable class, used to implement the hashed associative containers
/// hash_set, hash_map, hash_multiset, and hash_multimap.

///STL HashTable采用的是所谓的开链哈希法,依靠一个类似vector
  
   >来实现.
///先通过哈希函数确定所需处理元素应当在vector中的那个位置(可以一步找到),vector
///中的每个元素我们称之为一个桶,则这个过程即是寻找桶的过程,每个桶实际是一个
///list
   
    元素,若要处理的元素存在,则必然在这个桶之中,然后顺序遍历这个list即 ///可确定该元素是否存在或者所在位置.由于第一步的哈希使得桶中存放的元素一 ///般很少,因此遍历查询过程比较高效. template 
    
      struct _Hashtable_node { _Hashtable_node* _M_next; _Val _M_val; }; ///val:存储的值 ///key:对应的键 ///_HashFcn:所采用的hash函数类型 ///_ExtractKey:用于从存储对象值中抽出键对象的函数,当hash_table中 ///存储pair类型实现hash_map时最有用. ///_EqualKey:用于确定两个键值是否相等的函数 template 
     
       class hashtable; template 
      
        struct _Hashtable_iterator; template 
       
         struct _Hashtable_const_iterator; template 
        
          struct _Hashtable_iterator { typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> _Hashtable; typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> iterator; typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> const_iterator; typedef _Hashtable_node<_Val> _Node; typedef forward_iterator_tag iterator_category; typedef _Val value_type; typedef ptrdiff_t difference_type; typedef size_t size_type; typedef _Val& reference; typedef _Val* pointer; _Node* _M_cur; _Hashtable* _M_ht; _Hashtable_iterator(_Node* __n, _Hashtable* __tab) : _M_cur(__n), _M_ht(__tab) {} _Hashtable_iterator() {} reference operator*() const { return _M_cur->_M_val; } pointer operator->() const { return &(operator*()); } iterator& operator++(); iterator operator++(int); bool operator==(const iterator& __it) const { return _M_cur == __it._M_cur; } bool operator!=(const iterator& __it) const { return _M_cur != __it._M_cur; } }; template 
         
           struct _Hashtable_const_iterator { typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> _Hashtable; typedef _Hashtable_iterator<_Val,_Key,_HashFcn, _ExtractKey,_EqualKey,_Alloc> iterator; typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> const_iterator; typedef _Hashtable_node<_Val> _Node; typedef forward_iterator_tag iterator_category; typedef _Val value_type; typedef ptrdiff_t difference_type; typedef size_t size_type; typedef const _Val& reference; typedef const _Val* pointer; const _Node* _M_cur; const _Hashtable* _M_ht; _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) : _M_cur(__n), _M_ht(__tab) {} _Hashtable_const_iterator() {} _Hashtable_const_iterator(const iterator& __it) : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {} reference operator*() const { return _M_cur->_M_val; } pointer operator->() const { return &(operator*()); } const_iterator& operator++(); const_iterator operator++(int); bool operator==(const const_iterator& __it) const { return _M_cur == __it._M_cur; } bool operator!=(const const_iterator& __it) const { return _M_cur != __it._M_cur; } }; ///HashTable的vector长度是有讲究的,为了尽量减少冲突(过多的元素被散列 ///到同一个桶中),我们的桶个数一般应为质数个(由于我们是通过hash函数得到 ///的值与桶数做mod运算得到需处理元素所在的桶号).这里取53开始的后28个 ///质数,他们中的最大质数大于32位内存可存储的值. /// Note: assumes long is at least 32 bits. enum { __stl_num_primes = 28 }; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; ///给定一个值(实际即HashTable中所要存储的元素个数)得到大于等于 ///它的最小质数(实际即HashTable中Array的长度/桶的个数). inline unsign