STL笔记之hashtable

template <class _Val> struct _Hashtable_node {   _Hashtable_node* _M_next;   _Val _M_val; };

struct _Hashtable_iterator {   typedef _Hashtable_node<_Val> _Node;     typedef forward_iterator_tag iterator_category;     _Node* _M_cur;   _Hashtable* _M_ht;     iterator& operator++();   iterator operator++(int); };

template <class _Val, class _Key, class _HF, class _ExK, class _EqK,           class _All> _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() {   // 从当前的节点开始进行遍历操作   const _Node* __old = _M_cur;   // 取得下一个节点的指针   _M_cur = _M_cur->_M_next;   // 如果为空，表明当前的bucket已经没有节点了，需要指向下一个存在节点的bucket   if (!_M_cur) {     // 取得当前的bucket索引值     size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);     // 寻找下一个存在节点的bucket     while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())       _M_cur = _M_ht->_M_buckets[__bucket];   }   return *this; }   // operator++(int)基于operator++()实现 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,           class _All> inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) {   iterator __tmp = *this;   ++*this;   return __tmp; }

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 };   inline unsigned long __stl_next_prime(unsigned long __n) {   const unsigned long* __first = __stl_prime_list;   const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;   const unsigned long* pos = lower_bound(__first, __last, __n);   return pos == __last ? *(__last - 1) : *pos; }   size_type max_bucket_count() const {   return __stl_prime_list[(int)__stl_num_primes - 1]; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360

template <class _Val, class _Key, class _HashFcn,           class _ExtractKey, class _EqualKey, class _Alloc> class hashtable { public:   typedef _Key key_type;   typedef _Val value_type;   typedef _HashFcn hasher;   typedef _EqualKey key_equal;     hasher hash_funct() const { return _M_hash; }   key_equal key_eq() const { return _M_equals; }   private:   // hash table 节点   typedef _Hashtable_node<_Val> _Node;   private:   hasher                _M_hash;   key_equal             _M_equals;   _ExtractKey           _M_get_key;   // bucket vector : hash数组本身使用vector进行管理   vector<_Node*,_Alloc> _M_buckets;   size_type             _M_num_elements;   public:   hashtable(size_type __n,             const _HashFcn&    __hf,             const _EqualKey&   __eql,             const _ExtractKey& __ext,             const allocator_type& __a = allocator_type())     : __HASH_ALLOC_INIT(__a)       _M_hash(__hf),       _M_equals(__eql),       _M_get_key(__ext),       _M_buckets(__a),       _M_num_elements(0)   {     // 调用_M_initialize_buckets进行初始化操作     _M_initialize_buckets(__n);   }     hashtable(size_type __n,             const _HashFcn&    __hf,             const _EqualKey&   __eql,             const allocator_type& __a = allocator_type())     : __HASH_ALLOC_INIT(__a)       _M_hash(__hf),       _M_equals(__eql),       _M_get_key(_ExtractKey()),       _M_buckets(__a),       _M_num_elements(0)   {     _M_initialize_buckets(__n);   }     hashtable(const hashtable& __ht)     : __HASH_ALLOC_INIT(__ht.get_allocator())       _M_hash(__ht._M_hash),       _M_equals(__ht._M_equals),       _M_get_key(__ht._M_get_key),       _M_buckets(__ht.get_allocator()),       _M_num_elements(0)   {     _M_copy_from(__ht);   }     ~hashtable() { clear(); }     size_type size() const { return _M_num_elements; }   size_type max_size() const { return size_type(-1); }   bool empty() const { return size() == 0; }     // begin() 返回第一个有效的节点，不存在则返回end()   iterator begin()   {     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)       if (_M_buckets[__n])         return iterator(_M_buckets[__n], this);     return end();   }     iterator end() { return iterator(0, this); }   public:     size_type bucket_count() const { return _M_buckets.size(); }     // 返回hash数组中指定bucket下标上冲突链表的长度   size_type elems_in_bucket(size_type __bucket) const   {     size_type __result = 0;     for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)       __result += 1;     return __result;   }     // 插入操作   pair<iterator, bool> insert_unique(const value_type& __obj)   {     resize(_M_num_elements + 1);     return insert_unique_noresize(__obj);   }     iterator insert_equal(const value_type& __obj)   {     resize(_M_num_elements + 1);     return insert_equal_noresize(__obj);   }     pair<iterator, bool> insert_unique_noresize(const value_type& __obj);   iterator insert_equal_noresize(const value_type& __obj);     // 查找指定的key   iterator find(const key_type& __key)   {     // 计算key得到的下标     size_type __n = _M_bkt_num_key(__key);     // 遍历冲突链表     _Node* __first;     for ( __first = _M_buckets[__n];           __first && !_M_equals(_M_get_key(__first->_M_val), __key);           __first = __first->_M_next)       {}     return iterator(__first, this);   }     // 计算具有指定key的节点的个数   size_type count(const key_type& __key) const   {     const size_type __n = _M_bkt_num_key(__key);     size_type __result = 0;       for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next)       if (_M_equals(_M_get_key(__cur->_M_val), __key))         ++__result;     return __result;   }   private:   // 计算hash表格的大小(取素数表中的合适的素数)   size_type _M_next_size(size_type __n) const     { return __stl_next_prime(__n); }     // 初始化hash数组   void _M_initialize_buckets(size_type __n)   {     const size_type __n_buckets = _M_next_size(__n);     _M_buckets.reserve(__n_buckets);     _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);     _M_num_elements = 0;  // 实际节点个数   }     // 计算下标的几组函数   size_type _M_bkt_num_key(const key_type& __key) const   {     return _M_bkt_num_key(__key, _M_buckets.size());   }     size_type _M_bkt_num(const value_type& __obj) const   {     return _M_bkt_num_key(_M_get_key(__obj));   }     size_type _M_bkt_num_key(const key_type& __key, size_t __n) const   {     return _M_hash(__key) % __n;   }     size_type _M_bkt_num(const value_type& __obj, size_t __n) const   {     return _M_bkt_num_key(_M_get_key(__obj), __n);   }     // 内存管理：分配新节点   _Node* _M_new_node(const value_type& __obj)   {     _Node* __n = _M_get_node();     __n->_M_next = 0;     __STL_TRY {       construct(&__n->_M_val, __obj);       return __n;     }     __STL_UNWIND(_M_put_node(__n));   }     // 内存管理：节点回收   void _M_delete_node(_Node* __n)   {     destroy(&__n->_M_val);     _M_put_node(__n);   } };   // 插入操作，不允许重复 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool> hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>   ::insert_unique_noresize(const value_type& __obj) {   const size_type __n = _M_bkt_num(__obj);   _Node* __first = _M_buckets[__n];     // 如果已经存在则直接返回   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))       return pair<iterator, bool>(iterator(__cur, this), false);     // 插入新节点   _Node* __tmp = _M_new_node(__obj);   __tmp->_M_next = __first;   _M_buckets[__n] = __tmp;   ++_M_num_elements;   return pair<iterator, bool>(iterator(__tmp, this), true); }   // 插入操作，允许重复 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>   ::insert_equal_noresize(const value_type& __obj) {   const size_type __n = _M_bkt_num(__obj);   _Node* __first = _M_buckets[__n];     // 如果发现同样的key的节点存在，则插入到这个节点之后   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {       _Node* __tmp = _M_new_node(__obj);       __tmp->_M_next = __cur->_M_next;       __cur->_M_next = __tmp;       ++_M_num_elements;       return iterator(__tmp, this);     }     // 否则插入到链表头部   _Node* __tmp = _M_new_node(__obj);   __tmp->_M_next = __first;   _M_buckets[__n] = __tmp;   ++_M_num_elements;   return iterator(__tmp, this); }   // 查找或者插入：找到则直接返回，否则进行插入操作 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj) {   resize(_M_num_elements + 1);     size_type __n = _M_bkt_num(__obj);   _Node* __first = _M_buckets[__n];     for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))       return __cur->_M_val;     _Node* __tmp = _M_new_node(__obj);   __tmp->_M_next = __first;   _M_buckets[__n] = __tmp;   ++_M_num_elements;   return __tmp->_M_val; }   // 删除指定key的节点 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key) {   const size_type __n = _M_bkt_num_key(__key);   _Node* __first = _M_buckets[__n];   size_type __erased = 0;     if (__first) {     _Node* __cur = __first;     _Node* __next = __cur->_M_next;     while (__next) {       if (_M_equals(_M_get_key(__next->_M_val), __key)) {         __cur->_M_next = __next->_M_next;         _M_delete_node(__next);         __next = __cur->_M_next;         ++__erased;         --_M_num_elements;       }       else {         __cur = __next;         __next = __cur->_M_next;       }     }     if (_M_equals(_M_get_key(__first->_M_val), __key)) {       _M_buckets[__n] = __first->_M_next;       _M_delete_node(__first);       ++__erased;       --_M_num_elements;     }   }   return __erased; }   // 重新调整表格大小 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>   ::resize(size_type __num_elements_hint) {   const size_type __old_n = _M_buckets.size();   // 超过原来表格的大小时才进行调整   if (__num_elements_hint > __old_n) {     // 新的表格大小     const size_type __n = _M_next_size(__num_elements_hint);     // 在边界情况下可能无法调整(没有更大的素数了)     if (__n > __old_n) {       vector<_Node*, _All> __tmp(__n, (_Node*)(0),                                  _M_buckets.get_allocator());       __STL_TRY {         // 填充新的表格         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {           _Node* __first = _M_buckets[__bucket];           while (__first) {             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);             _M_buckets[__bucket] = __first->_M_next;             __first->_M_next = __tmp[__new_bucket];             __tmp[__new_bucket] = __first;             __first = _M_buckets[__bucket];           }         }         // 通过swap交换         _M_buckets.swap(__tmp);