|
tmp, this); } ///所在桶中无键相同元素 _Node* __tmp = _M_new_node(__obj); __tmp->_M_next = __first; _M_buckets[__n] = __tmp; ++_M_num_elements; return iterator(__tmp, this); } template
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj) { ///首先调整hashtable,为了防止桶个数太少以至于冲突太多 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; } template
pair
::iterator, typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator> hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key) { typedef pair
_Pii; const size_type __n = _M_bkt_num_key(__key); for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next) if (_M_equals(_M_get_key(__first->_M_val), __key)) { ///找到一个键与__key相同的元素 ///继续从当前位置遍历该桶,若遇到一个与之不同的键即可得到所求 for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) if (!_M_equals(_M_get_key(__cur->_M_val), __key)) return _Pii(iterator(__first, this), iterator(__cur, this)); ///该桶中键与__key相同的元素为最后一波元素 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) if (_M_buckets[__m]) return _Pii(iterator(__first, this),iterator(_M_buckets[__m], this)); return _Pii(iterator(__first, this), end()); } return _Pii(end(), end()); } template
pair
::const_iterator, typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator> hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> ::equal_range(const key_type& __key) const { typedef pair
_Pii; const size_type __n = _M_bkt_num_key(__key); for (const _Node* __first = _M_buckets[__n] ; __first; __first = __first->_M_next) { if (_M_equals(_M_get_key(__first->_M_val), __key)) { for (const _Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) if (!_M_equals(_M_get_key(__cur->_M_val), __key)) return _Pii(const_iterator(__first, this), const_iterator(__cur, this)); for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) if (_M_buckets[__m]) return _Pii(const_iterator(__first, this), const_iterator(_M_buckets[__m], this)); return _Pii(const_iterator(__first, this), end()); } } return _Pii(end(), end()); } template
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
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it) { ///同样找到对应桶后和单链表删除操作相同 _Node* __p = __it._M_cur; if (__p) { const size_type __n = _M_bkt_num(__p->_M_val); _Node* __cur = _M_buckets[__n]; if (__cur == __p) { _M_buckets[__n] = __cur->_M_next; _M_delete_node(__cur); --_M_num_elements; } else { _Node* __next = __cur->_M_next; while (__next) { if (__next == __p) { __cur->_M_next = __next->_M_next; _M_delete_node(__next); --_M_num_elements; break; } else { __cur = __next; __next = __cur->_M_next; } } } } } template
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> ::erase(iterator __first, iterator __last) { size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size(); size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size(); if (__first._M_cur == __last._M_cur) return; else if (__f_bucket == __l_buc |