|
_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 { ///通过hash_fun得到的值在和桶个数做mod运算得到 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; try { construct(&__n->_M_val, __obj); return __n; }catch(...){ _M_put_node(__n); } } void _M_delete_node(_Node* __n) { destroy(&__n->_M_val); _M_put_node(__n); } void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); void _M_erase_bucket(const size_type __n, _Node* __last); void _M_copy_from(const hashtable& __ht); }; template
_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; if (!_M_cur) { ///当前迭代器所指元素为当前桶中的最后一个元素 ///得到当前桶序号 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); ///从下一个桶开始查找非空桶,查找的的第一个非空桶的第一个元素 ///即为所求 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) _M_cur = _M_ht->_M_buckets[__bucket]; } return *this; } template
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; } template
_Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() { const _Node* __old = _M_cur; _M_cur = _M_cur->_M_next; if (!_M_cur) { size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) _M_cur = _M_ht->_M_buckets[__bucket]; } return *this; } template
inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) { const_iterator __tmp = *this; ++*this; return __tmp; } ///判断两个HashTable是否相等 template
bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) { typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node; ///(1)桶个数必须相等 if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) return false; ///(2)每个相同桶序号的相同位置的元素必须相等 for (int __n = 0; __n < __ht1._M_buckets.size(); ++__n) { _Node* __cur1 = __ht1._M_buckets[__n]; _Node* __cur2 = __ht2._M_buckets[__n]; for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val; __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) {} if (__cur1 || __cur2) return false; } return true; } template
pair
::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(__cur, this), false); ///需要插入 _Node* __tmp = _M_new_node(__obj); ///构建对应值的插入结点 ///插入应在桶头部 __tmp->_M_next = __first; _M_buckets[__n] = __tmp; ++_M_num_elements; return pair
(iterator(__tmp, this), true); } template
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]; 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(__ |