編寫自己的vector類（完整實作push_back、pop_back、erase、insert、clear、empty）————定義抽象資料類 第十一章心得

目錄

• ​​1 設計類​​
• ​​2 實作Vec類​​

• ​​2.1 類的類型​​
• ​​2.2 資料成員​​
• ​​2.3 記憶體配置設定​​

• ​​2.3.1 如何配置設定記憶體（預配置設定記憶體）​​
• ​​2.3.2 使用庫函數實作記憶體配置設定​​

• ​​2.3.2.1 思想​​
• ​​2.3.2.2 實作​​

• ​​2.3.2.2.1 庫函數準備​​
• ​​2.3.2.2.2 類不變式​​

• ​​2.4 成員函數​​

• ​​2.4.1 構造函數​​
• ​​2.4.2 析構函數(destructor)​​
• ​​2.4.3 複制構造函數(destructor)​​
• ​​2.4.5 重載運算符函數​​
• ​​2.4.5.1 索引運算符函數​​
• ​​2.4.5.2 指派運算符​​
• ​​2.4.6 push_back成員函數​​
• ​​2.4.6 clear成員函數​​
• ​​2.4.7 erase成員函數​​
• ​​2.4.8 pop_back成員函數​​
• ​​2.4.9 empty成員函數​​
• ​​2.4.10 insert函數​​
• ​​2.4.11 assign函數：​​
• ​​2.4.12 print_vec成員函數(類中沒有，重寫了輸出流)​​

• ​​3 完整版示例​​

1 設計類

開始設計類時，通常要首先确定要在什麼類中提供什麼樣的接口。精确确定接口的一種方式是研究一下類的使用者将用我們所編寫的類寫什麼程式。

由于我們要設計與标準庫的向量相同的功能。是以我們可以以向量類的使用作為模仿對象。

比如向量可以動态增加元素、索引通路元素、資料成員可以存儲不同的内建類型等。

2 實作Vec類

2.1 類的類型

因為類中要存儲幾種不同的資料成員，是以我們使用模版類來實作。

template <class T> class Vec{
  public:
    //接口
  private:
  //實作
}      

2.2 資料成員

由于類中要實作begin、end和size等函數的功能，是以需要首先儲存元素的首位址、元素後面的位址以及元素的個數。

這三個資料知道任意兩個就能推出第三個。為了友善後面記憶體管理的指針使用，這裡選擇了隻保留數組的首位址和末元素後面的位址指針，然後計算出數組的大小。

這裡進一步完善Vec類：

template <class T> class Vec{
  public:
    //接口
  private:
  T* data;
  T* limit;
}      

在使用T類型時，編譯器會使用使用者在生成Vec時提供的參數代替T。該類型隻有在一個Vec的定義執行個體化時菜戶被确定。

2.3 記憶體配置設定

2.3.1 如何配置設定記憶體（預配置設定記憶體）

現向一個Vec類添加一個元素，由于vec類對象中的元素增加了一個（這裡記憶體大小是固定，每次隻能容納下目前的元素），是以需要為對象重新配置設定新的記憶體，然後将原記憶體中的元素複制到目前新的記憶體中，然後構造一個指向新末端元素的後面一個疊代器。

如果頻繁增加元素，那麼開銷将會非常大。

是以将采用一種經典的方法，為程式配置設定比實際更多的記憶體，隻有在使用完所有預配置設定的記憶體時，才可以申請更多的記憶體。

即，隻要向類對象要求配置設定更多的記憶體時，我們都為類對象配置設定目前使用的空間的兩倍的記憶體空間。

例如，我們建立一個包含10個元素的Vec類對象，然後向類對象中添加元素（調用push_back函數），這個函數将會配置設定20個元素的記憶體空間。它會将現存的10個元素複制到新配置設定的記憶體的前一半空間，并為接下來的第一個元素空間進行初始化。

這樣的預配置設定需要我們增加元素指針。

原來的“末指針”指向新配置設定記憶體空間的末尾後面元素；

另一個新的“末指針”指向構造元素的末元素後面的那個元素（也就是新配置設定記憶體後的通路的第一個元素）。

具體如下圖所示，原來的“末指針”（limit），新的“末指針”（avail）。

這裡進一步完善Vec類：

template <class T> class Vec{
  public:
    //接口
  private:
  T* data;
  T* avail;//新增
  T* limit;
}      

2.3.2 使用庫函數實作記憶體配置設定

2.3.2.1 思想

我們可能希望用newT[n]為Vec配置設定空間，其中n為要配置設定記憶體的數目。但是，new T[n]不僅配置設定記憶體空間，還會運作T的構造函數來為每個元素進行預設初始化。

如果打算使用new T[n]，就必須滿足：隻有在T具有預設的構造函數時才能建立一個Vec<T>。

而這有悖于為使用者提供盡可能大的彈性的初衷。

由于标準的向量vector類中，沒有這樣的限制，是以我們編寫的類也希望沒有這樣的限制。這就要用到庫函數提供的記憶體配置設定類。

另外，如果我們要使用自己提供的資料進行初始化Vec類對象的元素，實際上它會進行兩次初始化：

• 1 一次是new自己進行的，使用T:T()構造函數為一個類型為T的數組中的每個元素進行初始化；
• 2 另一次是将使用者提供的數值賦給Vec類型對象的元素時。

但是如果我們使用前面的預配置設定的方法（配置設定我們實際需要的兩倍的空間），沒有必要對這些額外的元素（多配置設定的空間裡的元素）進行初始化。這些空間隻有我們新增加元素（使用push_back函數）時，才會被使用。

不用new，總結起來就是兩點：

• 1 為使用者提供盡可能大的彈性的初衷；
• 2 當使用預配置設定記憶體，沒必要對多配置設定空間裡的元素進行初始化。

2.3.2.2 實作

2.3.2.2.1 庫函數準備

由于關于記憶體的性質太複雜多變，沒有必要将特性固定在語言中，是以我們使用C++專門設計以支援靈活記憶體管理的一些類來管理記憶體。

例如計算機中有非常多種類的記憶體。一台計算機可能有幾種不同速度的記憶體在使用。計算機上的記憶體可能是具有特殊用途的，像圖形緩沖記憶體或共享記憶體等，有些記憶體可能在斷電後仍然保持記憶的，由于使用者可能想要配置設定和管理其中任何一種記憶體，是以最好将如何配置設定和管理的工作留給庫函數。

标準庫并不需要支援所有的記憶體，相反它提供了一種功能來管理記憶體，還有一個同一的記憶體管理接口。

在<memory>頭檔案中，提供了一個名為allocator<T>的類，它可以配置設定一塊預備用于存儲T類型對象但是尚未被初始化的記憶體快，并傳回一個指向這塊記憶體塊中的頭元素的指針。

這樣的指針非常危險，由于指針的類型表明它們指向類型對象，但是這些記憶體塊中并沒有存儲實際的對象。

allocator的模版函數如下：

template<class T> class allocator{
public:
  T* allocate(size_t);//配置設定未初始化記憶體塊
  void deallocate(T*, size_t);//釋放未初始化記憶體塊
  void construct(T*, const T&);//未初始化記憶體塊構造單個對象
  void destory(T*);//删除參數所指的對象
  //...
}      

其中：<cstddef>頭檔案中的size_t類型（無符号整型）表示數組的大小，size_t類型的大小可以裝在任何對象。

這裡我們僅研究與建立Vec類有關的成員函數以及非成員函數。

• 1 allocate成員函數:用于配置設定一塊被指定了類型但卻未被初始化的記憶體塊，它足以存儲相應類型對象的元素。

• 它被稱為被指定了類型的記憶體塊，因為它被用于存儲類型為T的值，并且可以通過使用一個T*類型的指針來得到它的位址。但是，它未初始化，這個記憶體塊中沒有構造任何實際的對象。

• 2 deallocate成員函數：用于釋放未被初始化的記憶體，它的兩個參數分别為：allocate函數已配置設定的指針；另一個是指出該記憶體大小中配置設定了多少元素。
• 3 construct成員函數：在尚未被初始化的記憶體塊區域中構造單個對象。它的兩個參數分别是：一個是allocate函數已配置設定的記憶體指針；另一個是用于複制到該記憶體塊的值。
• 4 destory成員函數：删除它的參數所指的類型T的對象。

與allocator類有關的非成員函數：

//一個區間的值複制到另一個區間
template<class In, calss For> For uninitalized_copy(In, In, For);
//用值來填充一個區間
template<class For, class T>
void uninitialized_fill(For, For, const T&);      

其中：In是一個輸入疊代器類型，For是一個前向疊代器類型（順序讀寫通路疊代器類型）。因為構造新對象不隻是為它配置設定記憶體，是以For必須是前向疊代器類型，而不是輸出疊代器類型。

這兩個函數用于在allocate所配置設定的記憶體塊中構造并初始化新的對象。

uninitalized_copy函數：類似與标準庫的中copy函數，用于将前兩個參數指針所指向的記憶體塊區間中的值複制到第三個參數指針所指向的目标記憶體塊中。

uninitialized_fill函數：根據需要構造其第三個參數盡可能多的副本，以填充前兩個參數提供的記憶體塊。

2.3.2.2.2 類不變式

為了建立一個有些的Vec類型對象，我們必須始終滿足以下4個條件：

• 1 如果對象存在元素，data指向對象數組的首元素，否則為零；
• 2;
• 3 在區間内的元素被初始化；
• 4 在區間内的元素不會初始化。

這四個條件叫做類不變式(class invariant)。一旦建立了一個類對象，總要建立起類不變式條件。

如果滿足了4個條件，隻要3個成員函數不改變這4個條件，那麼這個規律就永遠成立。

類的所有公有成員都不能打破這一不變式。

2.4 成員函數

2.4.1 構造函數

預設構造函數：

template<class T>
void Vec<T>::create(){
  data = avail = limit = 0;
}      

Vec(){ create();}      

帶參構造函數：

帶兩個參數：長度、初值

template<calss T>
void Vec<T>::create(size_type n, const T& val){
 data = alloc.allocate(n);
 limit = avail = data + n;
 uninitialized_fill(data, limit, val);
}      

explict Vec(size_type n, const T& t = T()){
create(n, t);
}      

複制構造函數：

帶兩個參數：頭指針、尾指針

template<class T>
void Vec<T>::create(const_iterator i, const_iterator j){
  data = alloc.allocate(j -i);
  limit = avail = uninitialized_copy(i, j, data);
}      

Vec(const Vec& v){
  create(v.begin(), v.end());
}      

帶參構造函數：

帶兩個疊代器參數的

template<class T> class Vec{
public:
    //帶兩個疊代器參數的構造函數
    template <class In> Vec(In b, In e){create(b, e);}
private:
        template <class In> void create(In, In);
}      

定義：

template <class T>
template <class In>
void Vec<T>::create(In b, In e) {
    data = alloc.allocate(e - b);
    limit = avail = std::uninitialized_copy(b, e, data);
}      

2.4.2 析構函數(destructor)

一個在局域範圍裡被建立的對象在它的生存範圍以外，就會被自動删除；而動态配置設定的記憶體的對象，則隻有在我們使用delete函數删除它時才會被删除。

對于Vec類我們在構造函數中為其配置設定了記憶體，是以必須要在析構函數中釋放記憶體。

如果使用預設析構函數，會僅删除對象的指針，而删除一個指針不會釋放指針對象占用的記憶體空間，最終結果導緻記憶體洩露。

template<class T> 
void Vec<T>::uncreate(){
  if(data){//以相反的順序，删除構造函數生成的元素
    iterator it = avail;
    while(it != data){
      alloc.destory(--t);
    }
    alloc.deallocate(data, limit - data);
  }
  //重置指針以表明Vec類型對象為空
  data = limit = avail = 0;
}      

~Vec(){uncreate();}      

2.4.3 複制構造函數(destructor)

當類中有指針成員時，如果複制指針的值，則被複制的對象和複制後的對象都指向記憶體中的同一個資料。這樣會導緻任何對象的資料元素的改動都會影響另一個對象的值。

解決的辦法，就是通過值傳遞将對象作為參數傳遞過去，這樣在複制對象中的操作不會影響原本對象中的值。

是以有複制構造函數：

template<class T> class Vec{
public: 
  Vec(const Vec& c){create(v.begin(), v.end());}
}      

2.4.5 重載運算符函數

2.4.5.1 索引運算符函數

索引運算符在數組中定位正确的元素位置并傳回該元素的一個引用。通過傳回的引用，可以修改Vec類型對象中所存儲的資料。

傳回類型為引用而不是值是為了避免容器中的對象非常大時，對它進行複制，那樣不但會造成時間上的浪費，更會影響運作速度。

//讀寫
T& operator[](size_type i){return data[i];}//必須是成員函數
//隻讀
const T& operator[](size_type i) const {return data[i];}      

2.4.5.2 指派運算符

進行指派時要進行自我指派判斷，如果不是自我指派，才删除原對象并釋放記憶體，然後複制新對象。

如果去掉這個判斷，會造成将左操作數對象的元素删除并釋放其占用的記憶體的同時，由于左右操作數指向同一對象，導緻右操作數同時被删除。但還要将右操作對象複制，這将會帶來災難。

常用this判斷，this關鍵詞隻在成員函數内部才有效，代表指向函數操作的對象的指針。例如在Vec::operator=函數裡，this的類型為Vec*。對于二進制操作來說，如指派操作，this總是指向左操作數。

在指派操作中，我們傳回一個指向 表達式做操作數對象的一個引用調用，該對象的生存周期大于指派操作，保證了函數傳回的時候不被删除。

繼續完善Vec類：

template<class T > class Vec{
public:
//在模版檔案的範圍内，C++允許我們忽略器具體類型名稱。
  Vec& operator=(const Vec&);//必須是成員函數
}      

//實作
//一旦前面指定了我們定義一個Vec類型的成員函數，後面就不需要重複使用這個定語了。
template<class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs){
  if(&rhs != this){//進行字元指派判斷
    uncreate();//删除運算符左測的數組
    create(rhs.begin(), rhs.end());//從右側元素複制到左側
  }
  returnn *this;
}      

2.4.6 push_back成員函數

如果目前對象的記憶體不夠插入新的元素，那麼就需要重新配置設定足夠的記憶體，以便使其至少再多存儲一倍的元素。

下面的grow函數，就是實作這樣的功能。

template<class T> void Vec<<T>::grow(){
//擴充對象大小，并為對象配置設定實際使用的兩倍大小的空間
  size_type new_size = max(2*(limit - data),ptrdiff_t(1));
  //配置設定新的記憶體空間并将已存在的對象元素内容複制到新記憶體中
  iterator new_data = alloc.allocate(new_size);
  iterator new_avail = uninitialized_copy(data,avail,new_date)
  //傳回原來的記憶體空間
  uncreate();
  //重置指針，使其指向新配置設定的記憶體空間
  data = new_data;
  avail = new_avail;
  limit = data + new_size;
}      

在新配置設定完記憶體空間後，就是插入元素。

template<class T>
void Vec<T>::unchecked_append(const T& val){
  alloc.construct(avail++, val);
}      

于是push_back函數就可以寫成：

template<class T>
class Vec{
public:
  void push_back(const T& t){
    if(avail = = limit)
      grow();
    unchecked_append(t);
  }
}      

由于grow函數會産生一個avail指針指向一個尚未被初始化的記憶體空間，但是我們在調用grow函數後，馬上調用unchecked_append函數，這樣avail指針就指向了一個有效值。

2.4.6 clear成員函數

倒着删除類對象中的值,

template <class T>
void Vec<T>::destory() {
    iterator it = avail;
    while(it != data){
        alloc.destroy(--it);
    }
    avail = data;
}      

繼續完善Vec類：

template<class T>
class Vec{
public:
     void clear(){
        destory();
    }
private:
    void destory();
}      

2.4.7 erase成員函數

删除單個元素：（判斷對象非空以及删除位置有效）

首先删除對象中的元素，然後把該位置後一個的元素值複制到目前未初始化元素的位置，後一個元素值清空，然後這樣依次複制直到目前位置等于avail為止，最後重置avail指針。

template <class T>
typename Vec<T>::iterator Vec<T>::destory(Vec::iterator pos) {
     if(data && pos < avail && pos >= data){
        alloc.destroy(pos);
        iterator it = pos +1;
        while(it != avail){
            alloc.construct(pos++, *it++);
            alloc.destroy(pos);
        }
        avail = pos;
    }
    return avail;
}      

删除多個元素：（判斷對象非空以及删除區間有效）

首先删除區間内對象中的元素，然後把區間後的元素依次移動到被删除的區間（每次移動後，都删除區間後面對應位置的元素的值）。

template <class T>
typename Vec<T>::iterator Vec<T>::destory(Vec<T>::iterator b, Vec<T>::iterator e) {
    if(data && b < e && e < avail && b >= data){
        iterator it = b;
        while(it != e){
            alloc.destroy(it++);
        }
        while(e != avail){
            alloc.construct(b++, *e);
            alloc.destroy(e++);
        }
        avail = b;
    }
    return avail;
}      

繼續完善Vec類：

template<class T>
class Vec{
    public:
        void erase(iterator pos){
            destory(pos);
    }
    void erase(iterator b , iterator e){
        destory(b, e);
    }
    private:
         iterator destory(iterator);
         iterator destory(iterator, iterator);
}      

2.4.8 pop_back成員函數

把最後一個進入向量的元素删除：

template <class T>
void Vec<T>::pop() {
    if(data){
        alloc.destroy(--avail);
    }
}      

繼續完善Vec類：

template<class T>
class Vec{
public:
    void pop_back(){
        pop();
    }
private:
        void pop();     
}      

2.4.9 empty成員函數

為空時傳回fasle。

template<class T>
class Vec{
public:
 bool empty() const{return !data;}
 }      

2.4.10 insert函數

難點在于重新配置設定記憶體後，data、avail、limit的值都會改變，因為重新配置設定了一塊新的記憶體，是以位址也是新的。結局方法就是記錄插入的位置到起始點的距離，這樣無論位址怎麼改變，隻要起始位址加上距離就可以計算出插入點在新記憶體的位址。

在疊代器的位置插入單個元素

template <class T>
void Vec<T>::add(std::ptrdiff_t dis, const T& val){
    if(dis < avail - data){
        iterator e = avail;
        iterator b = avail -1;
        while(e != data + dis){
            alloc.construct(e--, *b--);
            alloc.destroy(b);
        }
        alloc.construct(data + dis, val);
        ++avail;
    }
}      

繼續完善Vec類：

template<class T>
class Vec{
public:
    void insert(iterator it,const T& t){
        std::ptrdiff_t dis = it - data;
        if(avail == limit) grow();
        add(dis, t);
    }
private:
        void add(std::ptrdiff_t,const T&);
}      

插入區間内的元素

template <class T>
void Vec<T>::add(std::ptrdiff_t start,Vec<T>::const_iterator b, Vec<T>::const_iterator e) {
    iterator pos = data + size_type(start);
    if(size_type(start)> size()) throw std::domain_error("");

    Vec<T>temp;
    iterator insert_pos = pos;
    for ( ; insert_pos != avail; ++insert_pos) {//原插入位置的後面部分暫存
        temp.push_back(*insert_pos);
    }

    for (const_iterator it = b; it != e; ++it) {//覆寫插入元素
        *insert_pos++ = *it;
    }

    for (const_iterator it = temp.begin(); it != temp.end(); ++it) {//把願插入位置後面的部分重新插入
        *insert_pos++ = *it;
    }
    //更新avail
    avail = insert_pos;


//    std::copy(pos, avail, temp);
//    std::copy(temp.begin(),temp.end(),std::copy(b, e, pos));

}      

繼續完善Vec類：

template<class T>
class Vec{
public:
       template <class In>
    void insert(iterator out, In b, In e){
        std::ptrdiff_t start = out - data;//插入位置
        std::ptrdiff_t dis = e - b;
        if(dis > 0){//插入區間合法
            const size_type new_length = size() + size_type (dis);
            size_type container = limit - data;//容器所有的長度包括未初始化
            while(new_length >= container){
                grow();
                container = limit - data;
            }
            add(start,  b, e);
        }
    }
private:
        void add(std::ptrdiff_t, const_iterator, const_iterator);
}      

2.4.11 assign函數：

複制一個疊代器中的内容到向量

template <class T>
template <class In>
void Vec<T>::assign(In b, In e) {
    uncreate();
    create(b, e);
}      

聲明：

template<class T> class Vec{
public:
    template <class In>
    void assign(In, In);
    }      

2.4.12 print_vec成員函數(類中沒有，重寫了輸出流)

把向量中的元素讀到輸出流中。

template<class T>
ostream& Vec<T>::print_vec(std::ostream &os) {
    if(avail - data > 0){
        const_iterator iter = data;
        os << *iter++;
        while(iter != avail){
            os << " " << *iter++;
        }
        os << std::endl;
    }
    return os;
}      

繼續完善Vec類：

template<class T>
class Vec{
public:
      std::ostream& print_vec(std::ostream&); 
}      

3 完整版示例

#ifndef Vec_H
#define Vec_H

#include 
#include 
#include 
#include 

template<class T> class Vec{
public:
    typedef T* iterator;
    typedef const T* const_iterator;//疊代器
    typedef size_t size_type;//容器長度
    typedef T value_type;//值類型
    typedef std::ptrdiff_t difference_type;//疊代器相減後的結果
    typedef T& reference;//
    typedef const T& const_reference;

    //構造函數
    Vec(){create();}
    //可以顯示的給val值，也可以使用T的預設構造函數來生成這個值
    explicit Vec(std::size_t n, const T& val = T()){create(n, val);}
    //複制構造函數
    Vec(const Vec& v) { create(v.begin(), v.end());}
    //帶兩個疊代器參數的構造函數
    template <class In> Vec(In b, In e){create(b, e);}
    //指派運算符
    Vec& operator=(const Vec&);//允許忽略具體類型的名稱（是以沒有顯示聲明傳回類型名稱）
    //析構函數
    ~Vec(){ uncreate();}

    //索引（傳回引用，是為了避免容器的對象非常大時對它進行複制）
    T& operator[](size_type i) { return data[i];}//讀寫
    const T& operator[](size_type i) const { return data[i];}//隻讀
    //動态增加數組
    void push_back(const T& t){
        if(avail == limit){
            grow();
        }
        unchecked_append(t);
    }
    //清空
    void clear(){
        destory();
    }
    //删除
    void erase(iterator pos){
        destory(pos);
    }
    void erase(iterator b , iterator e){
        destory(b, e);
    }
    //出元素
    void pop_back(){
        pop();
    }
    //列印數組
    std::ostream& print_vec(std::ostream&);
    //判斷空
    bool empty() const{return !data;}

    //添加元素：
    void insert(iterator it,const T& t){
        std::ptrdiff_t dis = it - data;
        if(avail == limit) grow();
        add(dis, t);
    }
    template <class In>
    void insert(iterator out, In b, In e){
        std::ptrdiff_t start = out - data;//插入位置
        std::ptrdiff_t dis = e - b;
        if(dis > 0){//插入區間合法
            const size_type new_length = size() + size_type (dis);
            size_type container = limit - data;
            while(new_length >= container){
                grow();
                container = limit - data;
            }
            add(start,  b, e);
        }
    }
    template <class In>
    void assign(In, In);

    //容器有元素的長度
    size_type size() const { return avail - data;}

    //傳回疊代器類型
    iterator begin(){ return data;}//讀寫
    const_iterator begin() const { return data;}//隻讀

    iterator end() { return avail;}
    const_iterator end() const { return avail;}

private:
    iterator data;//指針指向Vec的第一個元素
    iterator avail;//指針指向構造元素後面的一個元素
    iterator limit;//指針指向最後一個可獲得元素後面的一個元素
    //記憶體配置設定工具
    std::allocator<T> alloc;//控制記憶體塊配置設定的對象
    //為底層的數組配置設定空間并對它進行初始化
    void create();
    void create(size_type, const T&);
    void create(const_iterator, const_iterator);
    template <class In> void create(In, In);
    //删除數組中的元素并釋放其占有的記憶體
    void uncreate();

    //支援push_back函數
    void grow();
    void unchecked_append(const T&);

    //支援clear函數
    void destory();

    //支援erase函數
    iterator destory(iterator);
    iterator destory(iterator, iterator);

    //支援pop_back
    void pop();

    //支援insert
    void add(std::ptrdiff_t,const T&);
    void add(std::ptrdiff_t, const_iterator, const_iterator);

};
//指派運算符
template<class T> Vec<T>& Vec<T>::operator=(const Vec& rhs){
    if(&rhs != this){//this：指向操作數對象的指針
        //删除運算符左側的數組
        uncreate();
        //從右側複制元素到左側
        create(rhs.begin(), rhs.end());
    }
    //傳回一個指向表達式做操作數對象的一個引用調用
    //該對象生存周期大于指派操作
    //保證了函數傳回的時候不被删除
    return *this;//傳回指向的對象
}
//預設構造
template<class T> void Vec<T>::create() {
    data = avail = limit = 0;
}
//帶一個參數大小和給初值
template<class T> void Vec<T>::create(size_type n, const T& val){
    data = alloc.allocate(n);
    limit = avail = data + n;
    std::uninitialized_fill(data, limit, val);
}
//帶參數大小
template<class T> void Vec<T>::create(const_iterator i, const_iterator j){
    data = alloc.allocate(j - i);
    limit = avail = std::uninitialized_copy(i, j, data);
}

template <class T>
template <class In>
void Vec<T>::create(In b, In e) {
    data = alloc.allocate(e - b);
    limit = avail = std::uninitialized_copy(b, e, data);
}

//删除對象，釋放占用的記憶體
template<class T> void Vec<T>::uncreate(){
    //alloc.deallocate函數需要一個非零指針作為參數
    //既是它不準備釋放任何記憶體
    if(data){
        //以相反順序構造函數生成的元素
        iterator it = avail;
        while(it != data){//删除對象
            alloc.destroy(--it);
        }
        //傳回占用的所有記憶體空間
        alloc.deallocate(data, limit - data);//删除未初始化記憶體
    }
    //重置指針以表明Vec類型對象為空
    data = limit = avail = 0;
}

//push_back函數的成員函數
template<class T> void Vec<T>::grow(){
    size_type new_size;
        //擴充對象大小時，為對象配置設定實際使用的兩倍大小的記憶體空間
        //Vec為空的時候，選擇一個元素進行配置設定
        new_size = std::max(2 * (limit - data), std::ptrdiff_t(1));


    //配置設定新的記憶體空間并将已存在的對象元素内容複制搭配新記憶體中
    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);

    //傳回原來的記憶體空間
    uncreate();

    //重置指針，使其指向新配置設定的記憶體空間
    data = new_data;
    avail = new_avail;
    limit = data + new_size;
}

//假設avail指向一片新配置設定的但尚未初始化的記憶體空間
template<class T> void Vec<T>::unchecked_append(const T& val){
    alloc.construct(avail++, val);
}

template <class T>
void Vec<T>::destory() {
    iterator it = avail;
    while(it != data){
        alloc.destroy(--it);
    }
    avail = data;
}

template <class T>
typename Vec<T>::iterator Vec<T>::destory(Vec::iterator pos) {
    if(data && pos < avail && pos >= data){
        alloc.destroy(pos);
        iterator it = pos +1;
        while(it != avail){
            alloc.construct(pos++, *it++);
            alloc.destroy(pos);
        }
        avail = pos;
    }
    return avail;
}


template <class T>
typename Vec<T>::iterator Vec<T>::destory(Vec<T>::iterator b, Vec<T>::iterator e) {
    if(data && b < e && e < avail && b >= data){
        iterator it = b;
        while(it != e){
            alloc.destroy(it++);
        }
        while(e != avail){
            alloc.construct(b++, *e);
            alloc.destroy(e++);
        }
        avail = b;
    }
    return avail;
}

template<class T>
std::ostream& Vec<T>::print_vec(std::ostream &os) {
    if(avail - data > 0){
        const_iterator iter = data;
        os << *iter++;
        while(iter != avail){
            os << " " << *iter++;
        }
        os << std::endl;
    }
    return os;
}

template <class T>
void Vec<T>::pop() {
    if(data){
        alloc.destroy(--avail);
    }
}

template <class T>
void Vec<T>::add(std::ptrdiff_t dis, const T& val){
    if(dis < avail - data){
        iterator e = avail;
        iterator b = avail -1;
        while(e != data + dis){
            alloc.construct(e--, *b--);
            alloc.destroy(b);
        }
        alloc.construct(data + dis, val);
        ++avail;
    }
}

template <class T>
void Vec<T>::add(std::ptrdiff_t start,Vec<T>::const_iterator b, Vec<T>::const_iterator e) {
    iterator pos = data + size_type(start);
    if(size_type(start)> size()) throw std::domain_error("");

    Vec<T>temp;
    iterator insert_pos = pos;
    for ( ; insert_pos != avail; ++insert_pos) {//原插入位置的後面部分暫存
        temp.push_back(*insert_pos);
    }

    for (const_iterator it = b; it != e; ++it) {//覆寫插入元素
        *insert_pos++ = *it;
    }

    for (const_iterator it = temp.begin(); it != temp.end(); ++it) {//把願插入位置後面的部分重新插入
        *insert_pos++ = *it;
    }
    //更新avail
    avail = insert_pos;


//    std::copy(pos, avail, temp);
//    std::copy(temp.begin(),temp.end(),std::copy(b, e, pos));

}


template <class T>
template <class In>
void Vec<T>::assign(In b, In e) {
    uncreate();
    create(b, e);
}
#endif      

#include 
#include "Vec.h"
#include 
using std::vector;
using std::cin; using std::cout;
using std::endl;


int main(int argc, char const *argv[]){
    //測構造函數
    Vec<int> v;//預設構造
    Vec<int> v2(4);//帶一個大小參數
    Vec<int> v3(4,6);//帶一個大小參數和初值

    //cout << v3.size() << endl;
//    for (Vec::size_type j = 0; j != v3.size(); ++j) {//測索引
//        cout << v3[j] <<" ";
//    }

//測複制構造函數
//    v.push_back(3);//測push_back
//    v.push_back(1);
//    v.push_back(10);
//    v.push_back(7);
    //隐式複制操作
//    int d = max_Vec(v);//将vi作為參數傳遞給max_Vac函數
//    cout << d;
//    Vec v4 = sort_Vec(v);//将sort_Vec函數的傳回值賦給v4 //初始化
//    for (Vec::size_type j = 0; j != v4.size(); ++j) {
//        cout << v4[j] <<" ";
//    }
    //顯示複制
//    Vec v5 = v3;
//    for (Vec::size_type j = 0; j != v5.size(); ++j) {
//        cout << v5[j] <<" ";
//    }
    //指派
//    Vec v4 = v;//初始化
//    v3 = v4;//指派操作，已存在的值擦去，以新值代替
//    for (Vec::size_type j = 0; j != v3.size(); ++j) {
//        cout << v3[j] <<" ";
//    }
    //測删除、清空
//    v.push_back(1);//測push_back
//    v.push_back(2);
//    v.push_back(3);
//    v.push_back(4);
    v.erase(v.begin());
//    v.erase(v.begin(), v.begin()+3);
    v.pop_back();
    v.clear();
//    v.print_vec(cout);
//    for (Vec::const_iterator it = v.begin(); it != v.end(); ++it) {
//        cout << *it <<" ";
//    }
    //測empty
//    if(!v.empty()){
//        cout << "Yes"<
//    }else{
//        cout << "No"<
//    }
//    if(!v3.empty()){
//        cout << "Yes"<
//    }else{
//        cout << "No" <
//    }
    //測試insert單個
//    v3.insert(v3.begin()+ 5, 10);
//    v3.print_vec(cout);
 //測insert區間
    v3.insert(v3.begin()+ 3, 10);
    Vec<int> v4(100,66);
    v3.insert(v3.begin()+1, v4.begin(), v4.end());
    v3.print_vec(cout);

    return  0;
}