利用内存chunk充当数据buffer的stack的一个简单实现

问题描述：

1.stack是计算机中最常用到的数据结构，它主要依据支持后进先出(LIFO)操作抽象而出的一种数据结构；

      2.本文尝试自己封装一个泛型的stack class，它支持常见的操作；

      3.这个类的底层的数据存储容器是以单链表串起来的内存块（memory chunk ）实现，这样做主要是为了性能的考量；

      4.有个小技巧预先分配一个内存块和这个链表没关联，当stack存储非常少量的东西时，都不用启用链表机制；

      5.最后我又封装一个底层容器为stl的stack class,这主要是为了性能比较的考虑；

      6.最后我分别比较了以下四种情形的性能：

 1）stack class (data container = memory chunk)

         2)  stack class ( data container =list )

         3)  stack class ( data container = vector )

         4)  st::stack

         结论是1最好，3是1的2倍，4比1差一些，2性能非常差；

程序代码：

#ifndef _ALSTACK_H_
#define _ALSTACK_H_

#include <list>
#include <vector>
#include <stack>
#include "windows.h"

/*
* The class encapsulate simple stack operation
* under interface, it‘s buffer is made of memory chunk
* compare with array and list in under buffer, it improve performance 
* 
*
*/
template<class T>
class AlStack
{
public:
	AlStack():m_totalCount(0), m_count(0)
	{
		m_dataBuffer = &m_initBuffer;
	}

	~AlStack()
	{
		Clear();
	}

	void Clear()
	{
		while( m_dataBuffer != &m_initBuffer )
		{
			Buffer* buf = m_dataBuffer;
			m_dataBuffer = m_dataBuffer->next;
			delete buf;			
		}
	}

	int Count()
	{
		return m_totalCount;
	}

	bool IsEmpty()
	{
		return m_totalCount == 0;
	}


	void Push( T& rhs )
	{
		*Push() = rhs;
	}


	T& At( int index )
	{
		assert( index >= 0 && index < m_count );
		return m_dataBuffer->buf[m_count - index - 1];
	}

	const T& At( int index ) const 
	{
		assert( index >= 0 && index < m_count );
		return m_dataBuffer->buf[m_count - index - 1];
	}


	T& Top()
	{
		assert( m_dataBuffer && m_count > 0 );
		return m_dataBuffer->buf[m_count - 1];
	}

	const T& Top() const
	{
		assert( m_dataBuffer && m_count );
		return m_dataBuffer->buf[m_count - 1];
	}

	void Pop( T& item )
	{
		item = Top();
		Pop();
	}

	void Pop()
	{
		m_totalCount--;
		if( --m_count == 0 )
		{
			if( m_dataBuffer != &m_initBuffer )
			{
				Buffer* buf = m_dataBuffer;
				m_dataBuffer = m_dataBuffer->next;

				delete buf;
				buf = 0;

				// reset the value of m_count
				m_count = KSlotCount;
			}
		}
	}


private:

	T* Push()
	{
		if( KSlotCount == m_count )
		{
			Buffer* buf = new Buffer;
			assert( buf );
			buf->next = m_dataBuffer;
			m_dataBuffer = buf;

			//reset the value of value in single buffer
			m_count = 0;
		}

		m_totalCount++;
		return &m_dataBuffer->buf[m_count++];
	}



private:
	enum 
	{
		KSlotCount = 64
	};

	int m_totalCount;
	int m_count;

	struct Buffer
	{
		T        buf[KSlotCount];
		Buffer*  next;

		Buffer():next(0)
		{
			memset( buf, 0x00, sizeof(buf) );
		}
	};

	Buffer     m_initBuffer;
	Buffer*    m_dataBuffer;
};


/*
* The stack implement it‘s operation by terms of stl container
* 
*/
template<class T, class V = std::list<T> >
class StackList
{
public:
	StackList():m_dataBuffer()
	{
	}

	~StackList()
	{
		Clear();
	}

	void Clear()
	{
		m_dataBuffer.clear();
	}

	int Count()
	{
		return m_dataBuffer.size();
	}

	bool IsEmpty()
	{
		return m_dataBuffer.size() == 0;
	}


	void Push( T& rhs )
	{
		m_dataBuffer.push_back(rhs);
	}




	T& Top()
	{
		assert( m_dataBuffer.size());
		return m_dataBuffer.back();
	}

	const T& Top() const
	{
		assert( m_dataBuffer.size());
		return m_dataBuffer.back();
	}

	void Pop( T& item )
	{
		item = m_dataBuffer.back();
		Pop();
	}

	void Pop()
	{
		m_dataBuffer.pop_back();
	}

private:
	V  m_dataBuffer;
};

/*
* Test interface
*
*/
template<class T>
void UnitTestPerformance( T& stackObj, int way )
{
	unsigned long start = GetTickCount();
	const int len = 640000;

	stackObj;
	for( int i = 0; i < len; i++ )
	{
		stackObj.Push( i );
	}


	for( int i = 0; i < len; i++ )
	{
		int res = stackObj.Top();
		stackObj.Pop();
		assert( res == len - i - 1 );
	}

	assert( stackObj.IsEmpty() == true );

	unsigned long interval = GetTickCount() - start;
	printf( "way %d consume time is %d \n", way, interval );

}


void StackPerformance( std::stack<int>& stackObj, int way )
{
	unsigned long start = GetTickCount();
	const int len = 640000;

	stackObj;
	for( int i = 0; i < len; i++ )
	{
		stackObj.push( i );
	}


	for( int i = 0; i < len; i++ )
	{
		int res = stackObj.top();
		stackObj.pop();
		assert( res == len - i - 1 );
	}


	unsigned long interval = GetTickCount() - start;
	printf( "way %d consume time is %d \n", way, interval );
}


/*
* Performance compare 
*
*/
void TestAlStack()
{
	AlStack<int> stackObj;
	UnitTestPerformance( stackObj, 1 );

	StackList<int> stackListObj;
	UnitTestPerformance( stackListObj, 2 );

	StackList<int, std::vector<int> > stackVecObj;
	UnitTestPerformance( stackVecObj, 3 );

	std::stack<int> stackStlObj;
	StackPerformance( stackStlObj, 4 );


}


#endif 

利用内存chunk充当数据buffer的stack的一个简单实现,布布扣,bubuko.com

利用内存chunk充当数据buffer的stack的一个简单实现

原文：http://blog.csdn.net/manthink2005/article/details/24517929