关于STL中stack的实现的讨论

 template<class T>class mystack 
//测试用 
//没有考虑异常时的rollback语义 
//另： Elminster指出“使用 count 不是一个好主意。保存一个指向“下一个位置”的指针应该会效率更高，而且也更易读”；{ 
public: 
    typedef T               value_type; 
    typedef unsigned int      size_type; 
    mystack():_lenght(0),_count(0) {} 
    ~mystack() 
   { 
      if (_lenght!=0) 
      { 
         for (int i=0;i<_count;++i) 
         { 
            ((T*)(&_vData[i*sizeof(T)]))->T::~T(); 
         } 
      }
   } 
    bool empty() const    
      { return (0==_count); } 
    size_type size() const 
      { return _count; } 
    value_type& top() 
      { return*(T*)(&_vData[(_count-1)*sizeof(T)]); } 
    const value_type& top() const 
      { return*(T*)(&_vData[(_count-1)*sizeof(T)]); } 
    void push(const value_type& x) 
   { 
      if (_count>=_lenght) 
      { 
         _resize(); 
      } 
      new ((T*)(&_vData[_count*sizeof(T)])) T(x) ; 
      ++_count; 
   } 
    void pop() 
   { 
      --_count; 
      ((T*)(&_vData[_count*sizeof(T)]))->T::~T(); 
   } 
protected: 
   std::vector<unsigned char>   _vData; 
   size_type      _lenght; 
   size_type      _count; 
   void _resize() 
   { 
      if (0==_lenght) 
      { 
         _lenght=32; 
         _vData.resize(_lenght*sizeof(T)); 
      } 
      else 
      { 
         _lenght*=2; 
         std::vector<unsigned char> new_vData; 
         new_vData.resize(sizeof(T)*_lenght); 
         for (int i=0;i<_count;++i) 
         { 
            T& x=*(T*)(_vData.begin()+i*sizeof(T)); 
            new ((T*)(new_vData.begin()+i*sizeof(T))) T(x); 
            (&x)->T::~T(); 
         } 
         _vData.swap(new_vData); 
      } 
   } 
}; 

 
typedef int Test0_T;//简单 POD 类型 class Test1_T   //较复杂的类 { 
public: 
   char _c; 
   double _d; 
   int  _i; 
   char* _p; 
   Test1_T():_c(),_d(),_i(),_p(newchar[20]) 
      {} 
   Test1_T(const Test1_T& x) 
      :_c(),_d(),_i(),_p(newchar[20]) 
      { (*this).operator=(x);  } 
   ~Test1_T(){ delete[] _p; } 
   Test1_T&operator=(const Test1_T& x) 
   { 
      _c=x._c; _d=x._d; _i=x._i; 
      for (int i=0;i<20;++i) 
         _p[i]=x._p[i]; 
      return*this; 
   } 
}; 

__declspec( naked ) __int64 CPUCycleCounter()//获取当前CPU周期计数(CPU周期数){
 __asm
 {
  RDTSC    //0F 31  //eax,edx  ret
 }
}

template<class stackT>int testProc(stackT& s,int Count) 
{ 

   typename stackT::value_type vl=stackT::value_type(); 
   typename stackT::value_type vx; 

   __int64   t0=::CPUCycleCounter();//返回CPU启动以来运行的周期数 for (int c=0;c<100;++c) 
   { 
      int i; 
      for (i=0;i<Count;++i) 
         s.push(vl); 
      for (i=0;i<Count;++i) 
         vx=s.top(); 
      for (i=0;i<Count;++i) 
         s.pop(); 
   } 

   __int64   t1=::CPUCycleCounter(); 

   returnint((t1-t0)/100); 
} 

template<class stackT> 
CString TestStack(PCSTR lab,stackT& s) 
{ 
   int   t0=testProc(s,10); 
   int   t1=testProc(s,1000); 
   int   t2=testProc(s,100000); 

   CString str; 
   str.Format("%10d,%10d,%10d",t0,t1,t2); 
   str+=char(13);str+=char(10); 
   return lab+str; 
} 


void CSTACKTESTDlg::OnBUTTONTest() 
{ 
   // TODO: Add your control notification handler code here usingnamespace std; 
   typedef stack<Test0_T,deque<Test0_T>>   stack_deque_T0; 
   typedef stack<Test1_T,deque<Test1_T>>   stack_deque_T1; 
   typedef stack<Test0_T,vector<Test0_T>>   stack_vector_T0; 
   typedef stack<Test1_T,vector<Test1_T>>   stack_vector_T1; 
   typedef stack<Test0_T,list<Test0_T>>   stack_list_T0; 
   typedef stack<Test1_T,list<Test1_T>>   stack_list_T1; 
   typedef mystack<Test0_T>            mystack_T0; 
   typedef mystack<Test1_T>            mystack_T1; 

   CString str; 
   str+=TestStack("stack_deque_T0 : ",stack_deque_T0()); 
   str+=TestStack("stack_vector_T0: ",stack_vector_T0()); 
   str+=TestStack("stack_list_T0  : ",stack_list_T0()); 
   str+=TestStack("mystack_T0     : ",mystack_T0()); 
   str+=char(13);str+=char(10); 
   str+=TestStack("stack_deque_T1 : ",stack_deque_T1()); 
   str+=TestStack("stack_vector_T1: ",stack_vector_T1()); 
   str+=TestStack("stack_list_T1  : ",stack_list_T1()); 
   str+=TestStack("mystack_T1     : ",mystack_T1()); 

   this->m_str=str;//::MessageBox(0,str,"",0);    UpdateData(FALSE); 
}

  template<class T>class mystack 
{ 
public: 
   enum{ type_sizes=sizeof(T) }; 
    typedef T               value_type; 
    typedef unsigned int      size_type; 
    mystack():_begin(0),_end(0),_last(0) {} 
    ~mystack() 
   { 
      if (size()>0) 
      { 
         for (T* i=_begin;i<_end;++i) 
            i->T::~T(); 
      } 
      if (_begin!=0) delete[] (unsigned char*)_begin;
   } 
    bool empty() const    
      { return (0==size()); } 
    size_type size() const 
      { return (_end-_begin); } 
    value_type& top() 
      { return*(_end-1); } 
    const value_type& top() const 
      { return*(_end-1); } 
    void push(const value_type& x) 
   { 
      if (_end<_last) 
      { 
         new (_end) T(x) ; 
         ++_end; 
      } 
      else 
      { 
         _resize(); 
         new (_end) T(x); 
         ++_end; 
      } 
   } 
    void pop() 
   { 
      --_end; 
      _end->T::~T(); 
   } 
protected: 
   T*            _begin; 
   T*            _end; 
   T*            _last; 
   void _resize() 
   { 
      if (0==_begin) 
      { 
         const unsigned int lenght=32; 
         _begin=(T*)( new unsigned char[lenght*type_sizes]); 
         _end  =_begin; 
         _last =_begin+lenght; 
      } 
      else 
      { 
         unsigned int old_size=size(); 
         unsigned int lenght=(old_size<<1); 
         T* _pNewData=(T*)( new unsigned char[lenght*type_sizes]); 
 

         int i=0; 
         try 
         { 
            for (;i<(int)old_size;++i) 
               new (_pNewData + i) T(*(_begin+i)); 
         } 
         catch(...)//rollback语义          { 
            for (int r=0;r<i;++r) 
               (_pNewData + r)->T::~T(); 
            delete[] (unsigned char*)_pNewData; 
            throw; 
         } 

         for (int j=0;j<(int)old_size;++j) 
            (_begin+j)->T::~T(); 
         T* old_begin=_begin; 
         _begin=_pNewData; 
         _end  =_begin+old_size; 
         _last =_begin+lenght; 
         delete[] (unsigned char*)old_begin; 
      } 
   } 
};

class TAlloc//移植时 在不同的平台下需要改变的部分 { 
public: 
   staticvoid* reserve(unsigned int size)         //申请保留虚拟空间地址    { 
      return ::VirtualAlloc(0,size,MEM_RESERVE,PAGE_READWRITE); 
   } 
   staticbool commit(void* pbase,unsigned int offset,unsigned int size)   //提交物理空间    { 
      return0!=::VirtualAlloc(((BYTE*)pbase)+offset,size,MEM_COMMIT,PAGE_READWRITE); 
   } 
   staticbool free(void* pbase) //解除提交的物理空间，并释放申请的虚拟空间地址    { 
      return0!=::VirtualFree(pbase,0,MEM_RELEASE); 
   } 
}; 

 

template<class T>class ExStack 
{ 
public: 
   enum{ type_sizes=sizeof(T) };
    typedef T               value_type; 
    typedef unsigned int      size_type; 
    ExStack():_begin(0),_end(0),_last(0) {} 
    ~ExStack() 
   { 
      if (size()>0) 
      { 
         for (T* i=_begin;i<_end;++i) 
            i->T::~T(); 
      } 
      if (_begin!=0) TAlloc::free(_begin); 
   } 
    bool empty() const    
      { return (0==size()); } 
    size_type size() const 
      { return (_end-_begin); } 
    value_type& top() 
      { return*(_end-1); } 
    const value_type& top() const 
      { return*(_end-1); } 
    void push(const value_type& x) 
   { 
      if (_end<_last) 
      { 
         //std::_Construct(_end,x) ; new (_end) T(x) ; 
         ++_end; 
      } 
      else 
      { 
         _resize(); 
         //std::_Construct(_end,x); new (_end) T(x) ; 
         ++_end; 
      } 
   } 
    void pop() 
   { 
      //没有实现收回物理内存的语义--_end; 
      _end->T::~T(); 
   } 
protected: 
   T*            _begin; 
   T*            _end; 
   T*            _last; 
   void _resize() 
   { 
      if (0==_begin) 
      { 
         const unsigned int lenght=4*1024;//4KB 边界对齐          _begin=(T*)TAlloc::reserve(256*1024*1024);//预留地址空间 256 MB          TAlloc::commit((void*)_begin,0,lenght*type_sizes); 
         _end  =_begin; 
         _last =_begin+lenght; 
      } 
      else 
      { 
         unsigned int old_size=size(); 
         unsigned int lenght=(old_size<<1); 
         TAlloc::commit(_begin,old_size*type_sizes,(lenght-old_size) 

*type_sizes); 
         _last =_begin+lenght; 
      } 
   } 
};

int testProc(stackT& s,int Count)//注意测试条件变了很多!!! { 
 

   typename stackT::value_type vl=stackT::value_type(); 
   typename stackT::value_type vx; 

   __int64   t0=::CPUCycleCounter();//返回CPU启动以来运行的周期数 for (int c=0;c<100;++c) 
   { 
      stackT temps;//int i; 
      for (i=0;i<Count+1;++i)//+1          temps.push(vl); 
      for (i=0;i<Count;++i) 
         vx=temps.top(); 
      for (i=0;i<Count-1;++i)//-1          temps.pop(); 
      for (i=0;i<(Count>>1);++i)//!          temps.push(vl); 
   } 

   __int64   t1=::CPUCycleCounter(); 

   returnint((t1-t0)/100); 
}

//管理内存的list template<unsigned int byte_size>class Tdata_list//管理myfast_stack的内存 { 
   struct TNode//节点类型    { 
      TNode*         pPrev; 
      TNode*         pNext; 
      unsigned char   Data[byte_size];//数据空间    }; 
public: 
   Tdata_list():pNodeBegin(0),pNodeCur(0),_size(0){} 
   unsigned int size() const { return _size; } 
   void push()//配置空间    { 
      if (0==pNodeBegin) 
      { 
         pNodeBegin=new TNode; 
         pNodeBegin->pPrev=0; 
         pNodeBegin->pNext=0; 
         pNodeCur=pNodeBegin; 
      } 
      elseif (0!=pNodeCur->pNext)//还有一个空余的Node       { 
         pNodeCur=pNodeCur->pNext; 
      } 
      else 
      { 
         TNode* pNodeEnd=new TNode; 
         pNodeEnd->pPrev=pNodeCur; 
         pNodeEnd->pNext=0; 
         pNodeCur->pNext=pNodeEnd; 
         pNodeCur=pNodeEnd;    
      } 
      ++_size; 
   } 
   ~Tdata_list() 
   { 
      for (TNode* i=pNodeBegin;i!=0; ) 
      { 
         TNode* pNext=i->pNext; 
         delete i; 
         i=pNext; 
      } 
   } 
   unsigned char* top() 
   { 
         return pNodeCur->Data; 
   } 
   void pop() 
   { 
      TNode*& pTmp=pNodeCur->pNext; 
      if (pTmp!=0) 
      { 
         delete pTmp;//留一个空余Node,多余的释放          pTmp=0; 
      } 
      pNodeCur=pNodeCur->pPrev; 
      --_size; 
   } 
private: 
   TNode*   pNodeCur; 
   TNode*   pNodeBegin; 
   unsigned int _size;//用来追踪list的使用大小 }; 


//myfast_stack 
//注意它的实现并没有以降低stack的通用能力来提高性能 
//改进可能：1.提供专署的内存分配器，而不是默认的new/delete; (就可以和SGI中的stack对比测试了)template<class T,bool IsPOD=false>class myfast_stack 
{ 
public: 
   enum{ type_sizes=sizeof(T),//!          node_width=(1020/type_sizes)+1//使用这种策略,stack<T,list<T> >也没有存在必要了       }; 
    typedef T                           value_type; 
    typedef unsigned int                  size_type; 
   typedef Tdata_list<type_sizes*node_width>   Tbase_alloc; 

    myfast_stack():_node_begin(0),_node_cur(0),_node_last(0) {} 
    ~myfast_stack() 
   { 
      if ((!IsPOD)&&(_NodeList.size()>0)) 
      { 
         for (T* i=_node_begin;i<_node_cur;++i) 
            i->T::~T(); 
         int nsize=(int)_NodeList.size(); 
         for (int j=0;j<(nsize-1);++j) 
         { 
            _NodeList.pop(); 
            _node_cur=(T*)_NodeList.top(); 
            for (int i=0;i<node_width;++i) 
            { 
               _node_cur->T::~T(); 
               ++_node_cur; 
            } 
         } 
      } 
   } 
    bool empty() const    
      { return (0==size()); } 
    size_type size() const 
      { return (_node_last-_node_begin)+node_width*(min((int)_NodeList.size()-1,0)); } 
    value_type& top() 
      { return*(_node_cur-1); } 
    const value_type& top() const 
      { return*(_node_cur-1); } 
    void push(const value_type& x) 
   { 
      if (_node_cur==_node_last) 
      { 
         _ToNextNode(); 
      } 
      //std::_Construct(_node_cur,x); new (_node_cur) T(x) ; 
      ++_node_cur; 
   } 
    void pop() 
   { 
      if (_node_cur==_node_begin) 
      { 
         _ToPrevNode(); 
      } 
      --_node_cur; 
      _node_cur->T::~T(); 
   } 
protected: 
   T*            _node_begin; 
   T*            _node_cur; 
   T*            _node_last; 
   Tbase_alloc      _NodeList; 
   void _ToNextNode() 
   { 
      _NodeList.push();    
      _node_begin=(T*)(_NodeList.top()); 
      _node_last=_node_begin+node_width; 
      _node_cur=_node_begin; 
   } 
   void _ToPrevNode() 
   { 
      _NodeList.pop(); 
      _node_begin=(T*)(_NodeList.top()); 
      _node_last=_node_begin+node_width; 
      _node_cur=_node_last; 
   } 
};