dtable.h

用于快速插入删除和查找的快表文件,速度极快

#pragma once
#include <stack>
#include <vector>

template<class _TValue, UINT32 _InitSize = 65536, UINT32 _StepSize = 4>
class dtable
{
protected:
	typedef struct tagElem
	{
		bool _IsUsing;
		_TValue _Value;
	} ELEM;
	typedef std::stack<UINT32>	INDEXSTACK;
	typedef std::vector<ELEM> VALUEVECTOR;

	INDEXSTACK _Stack;
	VALUEVECTOR _Values;
	UINT32 _Size;
	UINT32 _MaxIndex;
protected:
	void _realloc(UINT32 newsize)
	{
		for (UINT32 i = newsize; i != _Size;)
			_Stack.push(--i);
		_Values.resize(newsize);
		_Size = newsize;
	}
public:
	dtable() : _Size(0), _MaxIndex(0)
	{
		_realloc(_InitSize);
	}
	_TValue& request(UINT32* pOutIndex)
	{
		if (_Stack.empty())
			_realloc(_Size * _StepSize);
		UINT32 i = _Stack.top();
		*pOutIndex = i;
		_Values[i]._IsUsing = true;
		return _Values[i]._Value;
	}
	void reclaim(UINT32 index)
	{
		_Stack.push(index);
		ATLASSERT(_Values[index]._IsUsing);
		_Values[index]._IsUsing = false;
	}
	_TValue& operator [](UINT32 index)
	{
		ATLASSERT(_Values[index]._IsUsing);
		if (index > _MaxIndex)
			_MaxIndex= index; 
		return _Values[index]._Value;
	}
	UINT32 max_index()
	{
		return _MaxIndex;
	}
	UINT32 count()
	{
		return _Size - _Stack.size();
	}
	bool is_using(UINT32 index)
	{
		return _Values[index]._IsUsing;
	}
	void swap(dtable<_TValue, _InitSize, _StepSize>& dest)
	{
		dtable<_TValue, _InitSize, _StepSize> temp;
		_Stack.swap(dest._Stack);
		_Values.swap(dest._Values);
		UINT32 temp = _Size;
		_Size = dest._Size;
		dest._Size = temp;

		temp = _MaxIndex;
		_MaxIndex =dest._MaxIndex;
		dest._MaxIndex = temp;
	}
};