xhash

C语言库函数的原型,有用的拿去

		return (_Max_bucket_size);
		}

	void max_load_factor(float _Newmax)
		{	// set new load factor
		if (_Newmax != _Newmax	// may detect a NaN
			|| _Newmax < 0)
			_STD _Xout_of_range("invalid hash load factor");

		_Max_bucket_size = _Newmax;
		}

	void rehash(size_type _Buckets)
		{	// rebuild table with at least _Buckets buckets
		size_type _Maxsize = _Vec.max_size() / 4;
		size_type _Newsize = _Min_buckets;

		for (; _Newsize < _Buckets && _Newsize < _Maxsize; )
			_Newsize *= 2;	// double until big enough
		if (_Newsize < _Buckets)
			_STD _Xout_of_range("invalid hash bucket count");
		for (float _Size = (float)size();
			max_load_factor() < _Size / _Newsize && _Newsize < _Maxsize; )
			_Newsize *= 2;	// double until load factor okay

		_Init(_Newsize);
		_Reinsert(end());
		}
// ADDED WITH TR1 -- END

	_Pairib insert(const value_type& _Val)
		{	// try to insert node with value _Val
		_List.push_front(_Val);
		return (_Insert(_Val, begin()));
		}

	iterator insert(const_iterator, const value_type& _Val)
		{	// try to insert node with value _Val, ignore hint
		return (insert(_Val).first);
		}

	template<class _Iter>
		void insert(_Iter _First, _Iter _Last)
		{	// insert [_First, _Last) at front, then put in place
		iterator _Oldlast = begin();
		_List.insert(begin(), _First, _Last);
		if (max_load_factor() < load_factor())
			rehash(bucket_count());
		else
			_Reinsert(_Oldlast);
		}

	iterator erase(const_iterator _Plist)
		{	// erase element at _Plist
		size_type _Bucket = _Hashval(this->_Kfn(*_Plist));

		_Erase_bucket(_List._Make_iter(_Plist), _Bucket);
		return (_List.erase(_Plist));
		}

	iterator erase(const_iterator _First, const_iterator _Last)
		{	// erase [_First, _Last)
		_DEBUG_RANGE(_First, _Last);
		if (_First == begin() && _Last == end())
			{	// erase all
			clear();
			return (begin());
			}
		else
			{	// partial erase, one at a time
			while (_First != _Last)
				erase(_First++);
			return (_List._Make_iter(_First));
			}
		}

	size_type erase(const key_type& _Keyval)
		{	// erase and count all that match _Keyval
		_Pairii _Where = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Where.first, _Where.second, _Num);
		erase(_Where.first, _Where.second);
		return (_Num);
		}

	void erase(const key_type *_First,
		const key_type *_Last)
		{	// erase all that match array of keys [_First, _Last)
		_DEBUG_RANGE(_First, _Last);
		for (; _First != _Last; ++_First)
			erase(*_First);
		}

	void clear()
		{	// erase all
		_List.clear();
		_Init();
		}

	iterator find(const key_type& _Keyval)
		{	// find an element in mutable hash table that matches _Keyval
		return (lower_bound(_Keyval));
		}

	const_iterator find(const key_type& _Keyval) const
		{	// find an element in nonmutable hash table that matches _Keyval
		return (lower_bound(_Keyval));
		}

	size_type count(const key_type& _Keyval) const
		{	// count all elements that match _Keyval
		_Paircc _Ans = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Ans.first, _Ans.second, _Num);
		return (_Num);
		}

	iterator lower_bound(const key_type& _Keyval)
		{	// find leftmost not less than _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (iterator _Where = _Begin(_Bucket);
			_Where != _End(_Bucket); ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				return (this->comp(_Keyval,
					this->_Kfn(*_Where)) ? end() : _Where);
		return (end());
		}

	const_iterator lower_bound(const key_type& _Keyval) const
		{	// find leftmost not less than _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (const_iterator _Where = _Begin(_Bucket);
			_Where != _End(_Bucket); ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				return (this->comp(_Keyval,
					this->_Kfn(*_Where)) ? end() : _Where);
		return (end());
		}

	iterator upper_bound(const key_type& _Keyval)
		{	// find leftmost not greater than _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (iterator _Where = _End(_Bucket);
			_Where != _Begin(_Bucket); )
			if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
				return (this->comp(this->_Kfn(*_Where),
					_Keyval) ? end() : (iterator)++_Where);
		return (end());
		}

	const_iterator upper_bound(const key_type& _Keyval) const
		{	// find leftmost not greater than _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (const_iterator _Where = _End(_Bucket);
			_Where != _Begin(_Bucket); )
			if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
				return (this->comp(this->_Kfn(*_Where),
					_Keyval) ? end() : (const_iterator)++_Where);
		return (end());
		}

	_Pairii equal_range(const key_type& _Keyval)
		{	// find range equivalent to _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (iterator _Where = _Begin(_Bucket);
			_Where != _End(_Bucket); ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				{	// found _First, look for end of range
				iterator _First = _Where;
				for (; _Where != _End(_Bucket); ++_Where)
					if (this->comp(_Keyval, this->_Kfn(*_Where)))
						break;
				if (_First == _Where)
					break;
				return (_Pairii(_First, _Where));
				}
		return (_Pairii(end(), end()));
		}

	_Paircc equal_range(const key_type& _Keyval) const
		{	// find range equivalent to _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		for (const_iterator _Where = _Begin(_Bucket);
			_Where != _End(_Bucket); ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				{	// found _First, look for end of range
				const_iterator _First = _Where;
				for (; _Where != _End(_Bucket); ++_Where)
					if (this->comp(_Keyval, this->_Kfn(*_Where)))
						break;
				if (_First == _Where)
					break;
				return (_Paircc(_First, _Where));
				}
		return (_Paircc(end(), end()));
		}

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		if (this != &_Right)
			{	// different, worth swapping
			_Swap_adl(this->comp, _Right.comp);
			this->_List.swap(_Right._List);
			this->_Vec.swap(_Right._Vec);
			_STD swap(this->_Mask, _Right._Mask);
			_STD swap(this->_Maxidx, _Right._Maxidx);
			_STD swap(this->_Max_bucket_size, _Right._Max_bucket_size);
			}
		}

protected:
	iterator& _Vec_lo(size_type _Bucket)
		{	// return reference to begin() for _Bucket
		return (_Vec[2 * _Bucket]);
		}

	const iterator& _Vec_lo(size_type _Bucket) const
		{	// return reference to begin() for _Bucket
		return (_Vec[2 * _Bucket]);
		}

	iterator& _Vec_hi(size_type _Bucket)
		{	// return reference to end()-1 for _Bucket
		return (_Vec[2 * _Bucket + 1]);
		}

	const iterator& _Vec_hi(size_type _Bucket) const
		{	// return reference to end()-1 for _Bucket
		return (_Vec[2 * _Bucket + 1]);
		}

	iterator _Begin(size_type _Bucket)
		{	// return begin iterator for bucket _Bucket
		return (_Vec_lo(_Bucket));
		}

	const_iterator _Begin(size_type _Bucket) const
		{	// return begin iterator for bucket _Bucket
		return (_Vec_lo(_Bucket));
		}

	iterator _End(size_type _Bucket)
		{	// return end iterator for bucket _Bucket
		if (_Vec_lo(_Bucket) == end())
			return (end());
		else
			{	// point past last element
			iterator _Ans = _Vec_hi(_Bucket);
			return (++_Ans);
			}
		}

	const_iterator _End(size_type _Bucket) const
		{	// return end iterator for bucket _Bucket
		if (_Vec_lo(_Bucket) == end())
			return (_List._Make_iter(end()));
		else
			{	// point past last element
			iterator _Ans = _Vec_hi(_Bucket);
			return (++_Ans);
			}
		}

	void _Erase_bucket(iterator _Plist, size_type _Bucket)
		{	// fix iterators before erasing _Plist before _Where
		if (_Vec_hi(_Bucket) == _Plist)
			if (_Vec_lo(_Bucket) == _Plist)
				{	// make bucket empty
				_Vec_lo(_Bucket) = end();
				_Vec_hi(_Bucket) = end();
				}
			else
				_Vec_hi(_Bucket) = --_Plist;	// move end back one element
		else if (_Vec_lo(_Bucket) == _Plist)
			_Vec_lo(_Bucket) = ++_Plist;	// move beginning up one element
		}

	void _Insert_bucket(iterator _Plist, iterator _Where,
		size_type _Bucket)
		{	// fix iterators after inserting _Plist before _Where
		if (_Vec_lo(_Bucket) == end())
			{	// make bucket non-empty
			_Vec_lo(_Bucket) = _Plist;
			_Vec_hi(_Bucket) = _Plist;
			}
		else if (_Vec_lo(_Bucket) == _Where)
			_Vec_lo(_Bucket) = _Plist;	// move beginning back one element
		else if (++_Vec_hi(_Bucket) != _Plist)	// move end up one element
			--_Vec_hi(_Bucket);	// or not
		}

	void _Copy(const _Myt& _Right)
		{	// copy entire hash table
		_Mask = _Right._Mask;
		_Maxidx = _Right._Maxidx;
		_Max_bucket_size = _Right._Max_bucket_size;
		_List.clear();

		_TRY_BEGIN
		_List.insert(end(), _Right.begin(), _Right.end());
		this->comp = _Right.comp;
		_CATCH_ALL
		_List.clear();	// list or compare copy failed, bail out
		_RERAISE;
		_CATCH_END

		_Vec.assign(_Right._Vec.size(), end());
		_Reinsert(end());
		}

	void _Grow()
		{	// grow hash table by one bucket
		if (_Vec.size() / 2 <= _Maxidx)
			{	// table full, double its size
			_Mask = _Vec.size() - 1;
			_Vec.insert(_Vec.end(), _Vec.size(), end());
			}
		else if (_Mask < _Maxidx)
			_Mask = (_Mask << 1) + 1;

		size_type _Bucket = _Maxidx - (_Mask >> 1) - 1;
		for (iterator _Plist = _Begin(_Bucket);
			_Plist != _End(_Bucket); )
			{	// split old bucket
			size_type _Newbucket =
				this->comp(this->_Kfn(*_Plist)) & _Mask;
			if (_Newbucket == _Bucket)
				++_Plist;	// leave element in old bucket

 #if _ITERATOR_DEBUG_LEVEL == 2
			else if (_Newbucket != _Maxidx)
				_DEBUG_ERROR("bad hash function");
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

			else
				{	// move element to new bucket
				iterator _Where = _Plist;

				++_Where;
				_Erase_bucket(_Plist, _Bucket);
				_List._Splice_same(end(), _List, _Plist, _Where, 0);
				_Insert_bucket(_Plist, end(), _Newbucket);
				_Plist = _Where;
				}
			}
		++_Maxidx;	// open new bucket for hash lookup
		}

	size_type _Hashval(const key_type& _Keyval) const
		{	// return hash value, masked and wrapped to current table size
		size_type _Num = this->comp(_Keyval) & _Mask;
		if (_Maxidx <= _Num)
			_Num -= (_Mask >> 1) + 1;
		return (_Num);
		}

	void _Init(size_type _Buckets = _Min_buckets)
		{	// initialize hash table with _Buckets buckets, leave list alone
		_Vec.assign(2 * _Buckets, end());
		_Mask = _Buckets - 1;
		_Maxidx = _Buckets;
		}

	_Pairib _Insert(const value_type& _Val, iterator _Plist)
		{	// try to insert existing node with value _Val
		size_type _Bucket = _Hashval(this->_Kfn(_Val));
		iterator _Where = _End(_Bucket);

		for (; _Where != _Begin(_Bucket); )
			if (this->comp(this->_Kfn(_Val), this->_Kfn(*--_Where)))
				;	// still too high in bucket list
			else if (_Multi
				|| this->comp(this->_Kfn(*_Where), this->_Kfn(_Val)))
				{	// found insertion point, back up to it
				++_Where;
				break;
				}
			else
				{	// discard new list element and return existing
				_List.erase(_Plist);
				return (_Pairib(_Where, false));
				}

		iterator _Next = _Plist;
		if (_Where != ++_Next)
			_List._Splice_same(_Where, _List,
				_Plist, _Next, 1);	// move element into place

		_Insert_bucket(_Plist, _Where, _Bucket);
		_Check_size();
		return (_Pairib(_Plist, true));	// return iterator for new element
		}

	void _Check_size()
		{	// grow table as needed
		if (max_load_factor() < load_factor())

 #if _HAS_INCREMENTAL_HASH
			_Grow();	// too dense, need to grow hash table

 #else /* _HAS_INCREMENTAL_HASH */
			{	// rehash to bigger table
			size_type _Maxsize = _Vec.max_size() / 2;
			size_type _Newsize = bucket_count();

			for (int _Idx = 0; _Idx < 3 && _Newsize < _Maxsize; ++_Idx)
				_Newsize *= 2;	// multiply safely by 8
			_Init(_Newsize);
			_Reinsert(end());
			}
 #endif /* _HAS_INCREMENTAL_HASH */
		}

	void _Reinsert(iterator _Last)
		{	// insert elements in [begin(), _Last)
		if (begin() != _Last)
			for (--_Last; ; )
				{	// reinsert elements in [begin(), _Last]
				iterator _First = begin();
				bool _Done = _First == _Last;
				_Insert(*_First, _First);
				if (_Done)
					break;
				}
		}

	_Mylist _List;	// list of elements, must initialize before _Vec
	_Myvec _Vec;	// vector of list iterators, begin() then end()-1
	size_type _Mask;	// the key mask
	size_type _Maxidx;	// current maximum key value
	float _Max_bucket_size;	// current maximum bucket size
	};

		// _Hash TEMPLATE OPERATORS
template<class _Ty> inline
	bool operator==(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test for hash table equality
	return (_Left.size() == _Right.size()
		&& equal(_Left.begin(), _Left.end(), _Right.begin()));
	}

template<class _Ty> inline
	bool operator!=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test for hash table inequality
	return (!(_Left == _Right));
	}

template<class _Ty> inline
	bool operator<(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left < _Right for hash tables
	return (lexicographical_compare(_Left.begin(), _Left.end(),
		_Right.begin(), _Right.end()));
	}

template<class _Ty> inline
	bool operator>(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left > _Right for hash tables
	return (_Right < _Left);
	}

template<class _Ty> inline
	bool operator<=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left <= _Right for hash tables
	return (!(_Right < _Left));
	}

template<class _Ty> inline
	bool operator>=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left >= _Right for hash tables
	return (!(_Left < _Right));
	}
_STD_END

 #pragma warning(pop)
 #pragma pack(pop)

#endif /* RC_INVOKED */
#endif /* _XHASH_ */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.20:0009 */