模版——容器，迭代器

題：

試用多態實現線性表（隊列、串、堆棧），要求具備線性表的基本操作：插入、刪除、測長等。【美國著名軟件企業GS公司2007年11月面試題】

解析：

隊列、串、堆棧都可以實現push、pop、測長等操作。現在要求用多態去實現，就要建立一個線性表的共性模版，來實現以上的功能。

答案：程序源代碼與解釋如下

 // P101_example2.cpp : Defines the entry point for the console application.  
//  
 
#include "stdafx.h"  
#include <iostream>  
 
template <typename T> 
struct tcontainer 
{ 
    virtual void push(const T&) = 0;    //插入  
    virtual void pop() = 0; //刪除  
    virtual const T& begin() = 0;   //  
    virtual const T& end() = 0; //  
    virtual size_t size() = 0;  //返回長度  
}; 
 
template <typename T> 
struct tvector : public tcontainer<T> 
{ 
    static const size_t _step = 100;    //一次增加容量的大小  
private: 
    size_t _size;   //實際元素的個數  
    size_t _cap;    //已分配的容量  
    T* buf; //首地址  
public: 
    tvector() 
    { 
        _size = 0;  //初始化容器實際大小  
        _cap = _step;   //初始化容器容量的大小為_step  
        buf = 0;    //首地址需要動態分配內存  
        re_capacity(_cap);  //此時buf為空，即要設置buf初始值，配了100個元素的空間  
    } 
    ~tvector() 
    { 
        free(buf);  //釋放內存  
    } 
    void re_capacity(size_t s)  //調整容量  
    { 
        if(!buf)    //buf初始為空  
        { 
            buf = (T*)malloc(sizeof(T)*s); 
        } 
        else 
            buf = (T*)realloc(buf,sizeof(T)*s); //在buf基礎上調整容量  
    } 
    virtual void push(const T& v) 
    { 
        if(_size >= _cap)    //超過容量  
            re_capacity(_cap += _step); 
        buf[_size++] = v; 
    } 
    virtual void pop()  //刪除最後一個元素  
    { 
        if(_size) 
            _size--; 
    } 
    virtual const T& begin()    //返回第一個元素  
    { 
        return buf[0]; 
    } 
    virtual const T& end()  //返回最後一個元素  
    { 
        if(_size) 
            return buf[_size-1]; 
    } 
    virtual size_t size()   //返回容量的大小  
    { 
        return _size; 
    } 
    const T& operator[](size_t i)   //取第i個元素  
    { 
        if(i >= 0 && i < _size) 
            return buf[i]; 
    } 
}; 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    tvector<int> v; 
    for(int i = 0; i < 1000; ++i) 
    { 
        v.push(i); 
    } 
    for(int i = 0; i < 1000; ++i) 
    { 
        std::cout<<v[i]<<std::endl; 
    } 
    return 0; 
} 

// P101_example2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

template <typename T>
struct tcontainer
{
 virtual void push(const T&) = 0; //插入
 virtual void pop() = 0; //刪除
 virtual const T& begin() = 0; //
 virtual const T& end() = 0; //
 virtual size_t size() = 0; //返回長度
};

template <typename T>
struct tvector : public tcontainer<T>
{
 static const size_t _step = 100; //一次增加容量的大小
private:
 size_t _size; //實際元素的個數
 size_t _cap; //已分配的容量
 T* buf; //首地址
public:
 tvector()
 {
  _size = 0; //初始化容器實際大小
  _cap = _step; //初始化容器容量的大小為_step
  buf = 0; //首地址需要動態分配內存
  re_capacity(_cap); //此時buf為空，即要設置buf初始值，配了100個元素的空間
 }
 ~tvector()
 {
  free(buf); //釋放內存
 }
 void re_capacity(size_t s) //調整容量
 {
  if(!buf) //buf初始為空
  {
   buf = (T*)malloc(sizeof(T)*s);
  }
  else
   buf = (T*)realloc(buf,sizeof(T)*s); //在buf基礎上調整容量
 }
 virtual void push(const T& v)
 {
  if(_size >= _cap) //超過容量
   re_capacity(_cap += _step);
  buf[_size++] = v;
 }
 virtual void pop() //刪除最後一個元素
 {
  if(_size)
   _size--;
 }
 virtual const T& begin() //返回第一個元素
 {
  return buf[0];
 }
 virtual const T& end() //返回最後一個元素
 {
  if(_size)
   return buf[_size-1];
 }
 virtual size_t size() //返回容量的大小
 {
  return _size;
 }
 const T& operator[](size_t i) //取第i個元素
 {
  if(i >= 0 && i < _size)
   return buf[i];
 }
};
int _tmain(int argc, _TCHAR* argv[])
{
 tvector<int> v;
 for(int i = 0; i < 1000; ++i)
 {
  v.push(i);
 }
 for(int i = 0; i < 1000; ++i)
 {
  std::cout<<v[i]<<std::endl;
 }
 return 0;
}