比Deque速度快5倍的DequeEx！

昨天写完了音频的回放程序，在写音频捕捉程序时，突然有了一个想法，急于想知道它和Deque来比，哪一个速度更快，于是暂停了音频捕捉程序，写了一个DequeEx，经测试，它在进行前插入、后插入、前读取、后读取、随机访问时的时间均为常数n，比Deque的速度快了5倍。但它在进行中间插入和删除时的速度肯定要慢于Deque，因此我没有增加中间插入和删除的方法。有兴趣的朋友可以测试一下。

其程序代码如下：其中MSGDEQUE定义如下，因为这个已经在DLL中定义了，因此，在测试时，请自己将下面三行代码添加在DequeEx.h文件中：

#include <deque>

using namespace std;

typedef deque<DWORD> MSGDEQUE;

DequeEx.h文件如下：

// DequeEx.h: interface for the DequeEx class.

//

//////////////////////////////////////////////////////////////////////

#if !defined(AFX_DEQUEEX_H__57392FC5_5F59_4B58_B506_2D7B6FB7331C__INCLUDED_)

#define AFX_DEQUEEX_H__57392FC5_5F59_4B58_B506_2D7B6FB7331C__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

enum

{

//设定主要操作的模式。

PUSH_BACK, //主要操作为从后插入。

PUSH_FRONT, //主要操作为从前插入。

PUSH_MIDDLE, //主要操作为从中间插入。

};

//DequeEx是对Dqueue的扩展，它在进行前插、后插、前读取、后读取、随机访问时的速度均为常数n。

//在进行上述操作时的速度，比Dqueue快5倍。

class AFX_EXT_CLASS DequeEx : public CObject

{

public:

void clear(); //清空列表，并释放缓存。

int size(); //得到当前列表中的元素的个数。

bool empty(); //列表是否为空。

DWORD pop_back(); //从列表的尾弹出一个元素。

DWORD pop_front(); //从列表的头弹出一个元素。

void push_front(DWORD value); //将元素放入列表的最前面。

void push_back(DWORD value); //将元素放入列表的最后面。

void SetElementsNoPerBufferAdd(WORD wElementsNoPerAdd); //设置每次缓冲区增加时所增加的元素个数。

void SetFrequentlyAddElementMode(int nMode,WORD wOffset=0); //设置列表频繁进行操作时的方式。

DWORD operator [](int nIndex); //以索引方式直接访问列表中的元素。

//列表在初始化，缺省认为是在列表的两头都进行插入和删除操作。

//如果只想在列表的一边进行插入操作，应该调用SetFrequentlyAddElementMode()方法，

//设定相应的模式，将提高插入元素时的速度。

//如果列表有可能进行保存很多的元素，则应该调用SetElementsNoPerBufferAdd()方法，

//增大每次缓冲区增加的大小，可以明显提高速度。

DequeEx(WORD wElementsNoPerAdd=20, int nMode=PUSH_MIDDLE, WORD wOffset=10);

~DequeEx();

private:

void InitData();

void CheckBuffer();

char* m_pBuffHead; //缓冲区的头指针。

DWORD m_dwBuffSize; //缓冲区的尺寸。

char* m_pBuffTail; //缓冲区的尾指针。

char* m_pHead; //有效数据的始点。

char* m_pTail; //有效数据的尾指针。

WORD m_wElementsNoPerAdd; //每次增加的元素个数。

DWORD m_dwBuffSizePerAdd/*=m_wElementsNoPerAdd*4*/; //每次增加的缓冲区的大小。

DWORD m_dwOffset; //每次改变缓冲区大小时，在m_szEnter前预留的字节个数。

};

#endif // !defined(AFX_DEQUEEX_H__57392FC5_5F59_4B58_B506_2D7B6FB7331C__INCLUDED_)

DequeEx.cpp文件如下：

// DequeEx.cpp: implementation of the DequeEx class.

//

//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "DequeEx.h"

#ifdef _DEBUG

#undef THIS_FILE

static char THIS_FILE[]=__FILE__;

#define new DEBUG_NEW

#endif

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

DequeEx::DequeEx(WORD wElementsNoPerAdd/*=20*/, int nMode/*=PUSH_MIDDLE*/, WORD wOffset/*=10*/)

{

this->InitData();

this->SetElementsNoPerBufferAdd(wElementsNoPerAdd);

this->SetFrequentlyAddElementMode(nMode,wOffset);

}

DequeEx::~DequeEx()

{

}

void DequeEx::SetElementsNoPerBufferAdd(WORD wElementsNoPerAdd)

{

this->m_wElementsNoPerAdd=wElementsNoPerAdd;

this->m_dwBuffSizePerAdd=this->m_wElementsNoPerAdd*4;

}

void DequeEx::SetFrequentlyAddElementMode(int nMode,WORD wOffset/*=0*/)

{

switch(nMode)

{

//根据操作模式，设定偏移。

case PUSH_BACK:

this->m_dwOffset=0;

break;

case PUSH_FRONT:

this->m_dwOffset=this->m_wElementsNoPerAdd*4;

break;

default:

//缺省时为PUSH_MIDDLE:

if(wOffset>this->m_wElementsNoPerAdd || wOffset==0)

wOffset=this->m_wElementsNoPerAdd/2;

this->m_dwOffset=wOffset*4;

break;

}

}

void DequeEx::CheckBuffer()

{

if(this->m_pHead==NULL)

{

//如果缓冲区为空。

this->m_pBuffHead=new char[this->m_dwBuffSizePerAdd];

this->m_pBuffTail=this->m_pBuffHead+this->m_dwBuffSizePerAdd;

this->m_pHead=this->m_pBuffHead+this->m_dwOffset;

this->m_pTail=this->m_pHead;

this->m_dwBuffSize=this->m_dwBuffSizePerAdd;

}

else

{

//如果数据区已经到了缓冲区的尾。

DWORD dwLen=this->m_pTail-this->m_pHead; //数据的实际长度。

if(dwLen==0)

{

//如果数据区的长度为。

this->m_pHead=this->m_pBuffHead+this->m_dwOffset;

this->m_pTail=this->m_pHead;

}

else if((dwLen+this->m_dwOffset)>=this->m_dwBuffSize)

{

//如果数据区的头与缓冲区头之间的尺寸小于等于设定的偏移尺寸，则增加缓冲。

this->m_dwBuffSize+=this->m_dwBuffSizePerAdd;

char* sz=new char[this->m_dwBuffSize];

memcpy(sz+this->m_dwOffset,this->m_pHead,dwLen);

delete []this->m_pBuffHead;

this->m_pBuffHead=sz;

this->m_pBuffTail=sz+this->m_dwBuffSize;

this->m_pHead=sz+this->m_dwOffset;

this->m_pTail=this->m_pHead+dwLen;

}

else

{

//如果数据区的头与缓冲区头之间的尺寸大于设定的偏移尺寸，则将数据移动到距缓冲区头的偏移尺寸处。

memcpy(this->m_pBuffHead+this->m_dwOffset,this->m_pHead,dwLen);

this->m_pHead=this->m_pBuffHead+this->m_dwOffset;

this->m_pTail=this->m_pHead+dwLen;

}

}

}

void DequeEx::push_back(DWORD value)

{

if((this->m_pTail+4)>this->m_pBuffTail)

this->CheckBuffer();

this->m_pTail[0]=(BYTE)value;

this->m_pTail[1]=(BYTE)(value>>8);

this->m_pTail[2]=(BYTE)(value>>16);

this->m_pTail[3]=(BYTE)(value>>24);

this->m_pTail+=4;

}

void DequeEx::push_front(DWORD value)

{

char* psz=this->m_pHead-4;

if(psz<this->m_pBuffHead || psz>this->m_pBuffTail)

{

this->CheckBuffer();

psz=this->m_pHead-4;

}

psz[0]=(BYTE)value;

psz[1]=(BYTE)(value>>8);

psz[2]=(BYTE)(value>>16);

psz[3]=(BYTE)(value>>24);

this->m_pHead-=4;

}

DWORD DequeEx::pop_front()

{

if(this->m_pHead>=this->m_pTail)

return 0;

DWORD dw=MAKELONG(MAKEWORD(this->m_pHead[0],this->m_pHead[1]),

MAKEWORD(this->m_pHead[2],this->m_pHead[3]));

this->m_pHead+=4;

return dw;

}

DWORD DequeEx::pop_back()

{

if(this->m_pTail<=this->m_pHead)

return 0;

this->m_pTail-=4;

DWORD dw=MAKELONG(MAKEWORD(this->m_pTail[0],this->m_pTail[1]),

MAKEWORD(this->m_pTail[2],this->m_pTail[3]));

return dw;

}

bool DequeEx::empty()

{

return this->m_pTail==this->m_pHead;

}

int DequeEx::size()

{

return (this->m_pTail-this->m_pHead)/4;

}

DWORD DequeEx::operator [](int nIndex)

{

char* psz=this->m_pHead+nIndex*4;

if(psz<this->m_pTail)

return MAKELONG(MAKEWORD(psz[0],psz[1]),MAKEWORD(psz[2],psz[3]));

return 0;

}

void DequeEx::clear()

{

delete []this->m_pBuffHead;

this->InitData();

}

void DequeEx::InitData()

{

this->m_pBuffHead=NULL;

this->m_pBuffTail=NULL;

this->m_pHead=NULL;

this->m_pTail=NULL;

this->m_dwBuffSize=0;

}

测试程序如下：

{

if(true)

{

//DequeEx测试随机访问。

DequeEx queue;

DWORD dw=23456789;

WORD w=65000;

// WORD ws=10000;

// queue.SetElementsNoPerBufferAdd(ws);

queue.SetFrequentlyAddElementMode(PUSH_MIDDLE,10);

SYSTEMTIME time,time2;

::GetSystemTime(&time);

for(int i=0;i<100;i++)

queue.push_front(dw);

for(int j=0;j<w;j++)

{

for(i=0;i<100;i++)

dw=queue[i];

}

::GetSystemTime(&time2);

int sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

int msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

DWORD t=sec*1000+msec;

//Deque后插入数据，前读取数据测试。

MSGDEQUE md;

::GetSystemTime(&time);

for(i=0;i<100;i++)

md.push_front(dw);

for(j=0;j<w;j++)

{

for(i=0;i<100;i++)

dw=md[i];

}

::GetSystemTime(&time2);

sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

t=sec*1000+msec;

msec=t;

}

if(!true)

{

//DequeEx前插入数据，后读数据测试。

DequeEx queue;

DWORD dw=23456789;

WORD w=65000;

// WORD ws=10;

// queue.SetElementsNoPerBufferAdd(ws);

queue.SetFrequentlyAddElementMode(PUSH_MIDDLE,10);

SYSTEMTIME time,time2;

::GetSystemTime(&time);

for(int j=0;j<w;j++)

{

for(int i=0;i<78;i++)

queue.push_front(dw);

queue.push_front(12345678);

queue.push_front(456);

for(i=0;i<30;i++)

dw=queue.pop_back();

for(i=0;i<20;i++)

queue.push_front(dw);

for(i=0;i<70;i++)

dw=queue.pop_back();

}

::GetSystemTime(&time2);

int sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

int msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

DWORD t=sec*1000+msec;

//Deque后插入数据，前读取数据测试。

MSGDEQUE md;

::GetSystemTime(&time);

for(j=0;j<w;j++)

{

for(int i=0;i<80;i++)

md.push_front(dw);

dw=md[0];

for(i=0;i<30;i++)

md.pop_back();

for(i=0;i<20;i++)

md.push_front(dw);

for(i=0;i<70;i++)

md.pop_back();

}

::GetSystemTime(&time2);

sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

t=sec*1000+msec;

msec=t;

}

if(!true)

{

//DequeEx后插入数据，前读数据测试。

DequeEx queue;

DWORD dw=23456789;

WORD w=65000;

WORD ws=10;

queue.SetElementsNoPerBufferAdd(ws);

SYSTEMTIME time,time2;

::GetSystemTime(&time);

for(int j=0;j<w;j++)

{

for(int i=0;i<80;i++)

queue.push_back(dw);

for(i=0;i<30;i++)

dw=queue.pop_front();

for(i=0;i<20;i++)

queue.push_back(dw);

for(i=0;i<70;i++)

dw=queue.pop_front();

}

::GetSystemTime(&time2);

int sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

int msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

DWORD t=sec*1000+msec;

//Deque后插入数据，前读取数据测试。

MSGDEQUE md;

::GetSystemTime(&time);

for(j=0;j<w;j++)

{

for(int i=0;i<80;i++)

md.push_back(dw);

for(i=0;i<30;i++)

md.pop_front();

for(i=0;i<20;i++)

md.push_back(dw);

for(i=0;i<70;i++)

md.pop_front();

}

::GetSystemTime(&time2);

sec=time2.wSecond-time.wSecond;

if(sec<0)

{

sec=time2.wSecond+60-time.wSecond;

}

msec=time2.wMilliseconds-time.wMilliseconds;

if(msec<0)

{

sec--;

msec=time2.wMilliseconds+1000-time.wMilliseconds;

}

t=sec*1000+msec;

msec=t;

}

}

• ·EJB设计模式(第二版)之EJB Comman
• ·如何更好的获取自己需要的知识？
• ·谨慎使用ATL X2X字符串转换宏
• ·使用PHP4中的 IntegratedTemp
• ·《赤壁》学习笔记(一)
• ·封装了P2P连接与传输过程的DLL最新版--支
• ·封装了P2P连接与数据传输过程的DLL(一)
• ·C++一种有意思的构造析构函数调用现象
• ·利用对手论证法证明中位数问题的比较次数下界
• ·n进制补码,格雷码