昨天写完了音频的回放程序，在写音频捕捉程序时，突然有了一个想法，急于想知道它和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;
}
}
|
本类阅读TOP10