比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;
 }
}

本文地址：http://com.8s8s.com/it/it2422.htm