ket) ///删除区间位于同一个桶内 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); else { ///区间内的每个桶分别作合适的删除 _M_erase_bucket(__f_bucket, __first._M_cur, 0); for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) _M_erase_bucket(__n, 0); if (__l_bucket != _M_buckets.size()) _M_erase_bucket(__l_bucket, __last._M_cur); } } template
inline void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first, const_iterator __last) { erase(iterator(const_cast<_Node*>(__first._M_cur), const_cast
(__first._M_ht)), iterator(const_cast<_Node*>(__last._M_cur), const_cast
(__last._M_ht))); } template
inline void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it) { erase(iterator(const_cast<_Node*>(__it._M_cur), const_cast
(__it._M_ht))); } ///对hashtable的重新调整,为了避免桶个数太少以至于冲突太多.这是整个 ///hashtable中最关键也最复杂的一个成员函数. template
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()); ///重新分配合适大小的vector
try { ///按序号遍历每个桶 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) { ///得到桶中第一个元素 _Node* __first = _M_buckets[__bucket]; ///依次将该桶中的元素插入到新hashtable中对应的桶中,直到该桶为空 while (__first) { ///或得该元素在新的hashtable内应在的桶序号 size_type __new_bucket = _M_bkt_num(__first->_M_val, __n); ///将该元素从旧的位置摘下,插入新的hashtable应在的桶内 _M_buckets[__bucket] = __first->_M_next; __first->_M_next = __tmp[__new_bucket]; __tmp[__new_bucket] = __first; ///将first指向旧桶中的第一个元素 __first = _M_buckets[__bucket]; } } ///将得到的新hashtable和原有hashtable替换 _M_buckets.swap(__tmp); } catch(...) { ///如果操作失败,需要依次删除所有新hashtable内的元素, ///以防内存泄露 for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) { while (__tmp[__bucket]) { _Node* __next = __tmp[__bucket]->_M_next; _M_delete_node(__tmp[__bucket]); __tmp[__bucket] = __next; } } throw; } } } } ///删除序号为__n的桶内[first,last)区间内的元素 template
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) { _Node* __cur = _M_buckets[__n]; ///从头结点开始删除,需要特殊处理 if (__cur == __first) _M_erase_bucket(__n, __last); else { _Node* __next; ///找到需要删除的起点 for (__next = __cur->_M_next; __next != __first; __cur = __next, __next = __cur->_M_next) ; ///类似单链表删除 while (__next != __last) { __cur->_M_next = __next->_M_next; _M_delete_node(__next); __next = __cur->_M_next; --_M_num_elements; } } } ///删除序号为__n的桶内自头结点至__last的元素,不包括__last template
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> ::_M_erase_bucket(const size_type __n, _Node* __last) { _Node* __cur = _M_buckets[__n]; while (__cur != __last) { _Node* __next = __cur->_M_next; _M_delete_node(__cur); __cur = __next; _M_buckets[__n] = __cur; ///记着调整_M_buckets[__n]的指向 --_M_num_elements; } } template
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear() { ///挨个清空单链表,并将桶清空 for (size_type __i = 0; __i < _M_buckets.size(); ++__i) { _Node* __cur = _M_buckets[__i]; while (__cur != 0) { _Node* __next = __cur->_M_next; _M_delete_node(__cur); __cur = __next; } _M_buckets[__i] = 0; } _M_num_elements = 0; } template
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> ::_M_copy_from(const hashtable& __ht) { ///挨个复制单链表 _M_buckets.clear(); _M_buckets.reserve(__ht._M_buckets.size()); _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); try { for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { const _Node* __cur = __ht._M_buckets[__i]; if (__cur) { _Node* __copy = _M_new_node(__cur->_M_val); _M_buckets[__i] = __copy; for (_Node* __next = __cur->_M_next; __next; __cur = __next, __next = __cur->_M_next) { __copy->_M_next = _M_new_node(__next->_M_val); __copy = __copy->_M_next; } } } _M_num_elements = __ht._M_num_elements; }catch(...){ clear(); throw; } }
|