必須要注意的C++動態內存資源管理(六)vector的簡單實現

myVector分析 我們知道，vector類將其元素存放在連續的內存中。為了獲得可接受的性能，vetor預先分配足夠大的內存來保存可能需要的更多元素。vector的每個添加元素的成員函數會檢查是否有空間容納更多的元素。如果有，成員函數會在下一個可用位置構造一個對象。如果沒有可用空間，vector就會重新分配空間；它獲得新的空間，將已有元素移動到新空間中，釋放舊空間，並添加新元素。 既然是動態開辟的內存，於是我們在myVector中使用動態數組來存儲，而每次插入元素的時候需要先判斷開辟的內存是否已滿，如果滿了需要重新分配內存。
下面給出最初版本的代碼：

//myVector.h
#include 
template
class myVector
{
public:
    typedef myVector _Myt;
    myVector() :
        elements(nullptr), first_free(nullptr), cap(nullptr){}    // allocator成員進行默認初始化
    myVector(const _Myt&);
    _Myt& operator=(const _Myt&);
    ~myVector();
    T& operator[](size_t i){ return *(elements + i); }
    void push_back(const T&);                                      // 添加元素
    size_t size()const{ return first_free - elements; }
    size_t capacity()const{ return cap - elements; }
    T *begin()const{ return elements; }
    T *end()const{ return first_free; }
private:
    void chk_n()                           //被添加元素函數使用
    {
        if (size() == capacity())reallocate();
    }
    std::pair n_copy
        (const T*, const T*);          //被拷貝構造，賦值運算符，析構函數使用
    void free();                       //銷毀元素並釋放內存
    void reallocate();                 //獲得更多內存並拷貝已有元素

    T *elements;
    T *first_free;
    T *cap;
};

template
myVector::myVector(const _Myt& v)
{
    //調用alloc_n_copy 分配空間以容納與s中一樣多的元素
    auto newdata = n_copy(v.begin(), v.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
}
template
myVector::~myVector()
{
    free();
}
template
myVector& myVector::operator=(const _Myt& rhs)
{
    //調用alloc_n_copy分配內存,大小與rhs一樣.
    auto data = n_copy(rhs.begin(), rhs.end());

    free();

    elements = data.first;
    first_free = cap = data.second;

    return *this;
}
template
std::pair myVector::
n_copy(const T *b, const T *e)
{
    auto data = new T[e - b];
    for (auto i = b; i < e; i++)
        data[i-b] = *i;

    return{ data, data + (e - b) };
}
template
void myVector::push_back(const T& s)
{
    chk_n();                               //確保已有新空間
    *(first_free++) = s;
}

template
void myVector::free()
{
    delete[] elements;
}

template
void myVector::reallocate()
{
    //我們將分配當前大小兩倍的內存空間
    auto newcapacity = size() ? 2 * size() : 1;

    //分配新內存
    auto newdata = new T[newcapacity];
    auto dest = newdata;
    auto elem = elements;

    //將數據從舊地址移動到新地址
    for (size_t i = 0; i != size(); ++i)
        *(dest++) = *(elem++);
    free();  //一旦更新完就要釋放舊內存

    elements = newdata;
    first_free = dest;

    cap = elements + newcapacity;
}

恩，以上代碼實現了vector的部分功能，實現了vector內存的動態分配。不過，我們可以發現以上代碼還是有幾個可以優化的地方： 1.在分配內存的時候，new將內存分配和對象構造組合在了一起。但是在vector分配內存的時候，事實上有許多內存我們可能並用不上；而如果對於這些內存進行構造對象，可能就會帶來不必要的開銷。 2.在內存重新分配的時候，我們涉及到了舊數據的轉移；不對，這裡應該說是拷貝。雖然的確應該是轉移，然而我們實現是通過拷貝。在c++11的時候提供了移動構造語義。它可以對於即將銷毀(保證重新賦值前不再使用)的對象進行移動。這樣對於某些支持移動語義的對象。移動比拷貝就可以帶來更小的開銷。 恩，要進行以上的優化我們要先介紹：allocator類，移動語義。

 

十七.allocator類介紹

new有一些靈活性的局限，一方面表現在它將內存分配和對象構造組合在一起。類似的，delete將對象析構和內存釋放組合在一起。我們分配單個對象時，通常我們希望將內存和對象初始化放在一起。因為在這樣的情況下，我們幾乎已經知道了對象應當是什麼值。
當分配一大塊內存時，我們通常計劃在這塊內存上按需構造對象。在這種情況下，我們就應該希望將內存分配和對象構造分離。這意味著我們可以分配大塊內存，然而只有我們真正需要的時候才執行對象創建操作(同時付出一定開銷)。
標准庫allocator類定義在頭文件memory中，它幫助我們將內存分配和對象構造分離開來。

 

函數 介紹 allocator a 定義了一個名為a的allocator對象，它可以為類型為T的對象分配內存。 a.allocate(n) 分配一段原始的，未構造的內存，保存n個類型為T的對象。 a.deallocate(p,n) 釋放從T*指針p開始的內存，這塊內存保存了n個類型為T的對象；p必須是一個先前由allocate返回的指針，且n必須是p創建時指定的大小。在調用deallocate之前，用戶必須對每個在這塊內存創建的內存調用destroy。 a.construct(p,args) p必須是一個類型為T*的指針，指向一塊原始內存；args被傳遞給類型為T的構造函數，用來在p指向的內存上構造一個對象。 a.destroy(p) p為T*類型指針，此算法對p指向的對象執行析構函數。 下面是一段簡單的代碼，介紹了如何使用allocator進行內存分配，對象構造，對象釋放，內存回收。

int main()
{
    allocator  alloc;          //這個對象可以用來分配 string 類型的內存。
    string* p = alloc.allocate(5);     //使用alloc對象分配5個string對象大的連續內存並將頭指針給p。

    //allocate分配的內存在沒有構造之前是不能使用的！！
    alloc.construct(p,"hello world");   //使用"hello world"構造string

    cout << *p << endl;       //輸出剛才構造的string，輸出hello world

    alloc.destroy(p);         //銷毀剛才構造的對象

    alloc.deallocate(p,5);    //釋放內存
    return 0;
}

不僅這樣，標准庫還提供了一些算法讓我們使用的時候更加方便： |函數|介紹| |—|—-| |uninitialized_copy(b,e,b2)|從迭代器b和e指出的輸入范圍中拷貝元素到迭代器b2指定的未構造的原始內存中。b2指向的內存必須足夠大，能容納輸入序列中元素的拷貝。 |uninitialized_copy_n(b,n,b2)|從迭代器b指向的元素開始，拷貝n個元素到b2開始的內存中。 |uninitialized_fill(b,e,t)|在迭代器b,e指定的原始內存范圍中創建對象，對象的值均為t的拷貝。 |uninitialized_fill_n(b,n,t)|從迭代器b指向的內存地址開始創建n個對象。b必須指向足夠大的未構造原始內存，能夠容納給定數量的對象。 值得注意的是，所有通過allocate分配的內存都必須通過deallocate去回收，而所有構造的對象都必須通過destroy去釋放。所以這些拷貝算法都必須要求原始內存，如果內存上有對象，請先使用destroy釋放！！

 

十八.移動語義介紹

很多情況下都會發生對象拷貝，然而在其中某些情況下，對象拷貝後就會立即被銷毀。在這些情況下，移動而非拷貝對象會大幅度提升性能。還有的情況諸如IO類或者unique_ptr這些類都包含不能共享的資源，因此這些類的對象也不能拷貝只能移動。 為了支持移動操作，在新標准中引入了一種新的引用類型 —— 右值引用。右值引用有個重要的性質：只能綁定到一個即將要銷毀的對象上。因此我們可以自由地將一個右值引用的資源”移動”到另一個對象中。下面給出一些例子來表示哪些是右值：

int i = 42;                 
int &r = i;                   //正確：r引用i
int &&rr = i;                 //錯誤：不能將一個右值引用綁定到左值上
int &r2 = i * 42;             //錯誤：i * 42 是個右值
const int & r3 = i * 432;     //正確：我們可以把一個const引用綁定到右值上
int &&rr2 = i * 42;           //正確：右值引用綁定右值

考察左值和右值的區別：左值有持久的狀態，而右值要麼是字面常量，要麼是在表達式求值過程中或者是函數返回的時候創建的臨時變量。
因為變量是左值，所以我們不能將一個右值引用綁定到一個變量上，即使這個變量是一個右值引用類型也不行。所以為了解決這個問題，標准庫提供了一個move函數，它可以用來獲得綁定到左值上的右值引用。此函數定義在頭文件utility中。
我們可以銷毀一個移後源對象，也可以賦予新值，但不能在賦新值之前使用移後源對象的值。
根據以上所說，如果類也支持移動拷貝和移動賦值，那麼也能在某些時候的初始化(賦值)的時候提高性能。如果要想讓類支持移動語義，我們需要為其定義移動構造函數和移動賦值運算符。這兩個函數的參數都是一個右值引用。就如同上面的代碼，對於vector的移動我們只需要拷貝三個指針參數，而不是拷貝三個指針參數指向的值。

 

template
myVector::myVector(_Myt&& v):elements(v.elements),first_free(v.first_free),cap(v.cap){
    v.elements = v.first_free = v.cap = nullptr;
}

值得注意的是，我們要保證移後源對象必須是可析構狀態，而且如果移動構造(賦值)函數不拋出異常的話必須要標記為noexcept(primer p474)。 對於移動賦值運算符我們要保證能正確處理自我賦值：

template
myVector& myVector::operator=(_Myt&& rhs)
{
    if (this != &rhs)
    {
        free();
        elements = rhs.elements;
        first_free = rhs.first_free;
        cap = rhs.cap;
        //將rhs置為可析構狀態
        rhs.elements = rhs.first_free = rhs.cap = nullptr;
    }
}

當然，和其他構造函數一樣，如果我們沒有定義移動構造函數的時候，編譯器會給我們提供默認的移動構造函數。不過，前提是該類沒有定義任何版本的拷貝控制函數以及每個非staitc成員變量都可以移動。編譯器就會默認為它合成移動構造函數和移動賦值運算符。

 

十九.優化過後的Vector

我們使用 allocate 和移動語義對以上的vector進行優化：

#pragma once

#include 

template
class myVector
{
public:
    typedef myVector _Myt;
    myVector() :
        elements(nullptr), first_free(nullptr), cap(nullptr){}    // allocator成員進行默認初始化
    myVector(const _Myt&);
    myVector(_Myt&&);
    _Myt& operator=(const _Myt&);
    _Myt& operator=(_Myt&&);
    ~myVector();
    T& operator[](size_t i){ return *(elements + i); }
    void push_back(const T&);                                      // 添加元素
    size_t size()const{ return first_free - elements; }
    size_t capacity()const{ return cap - elements; }
    T *begin()const{ return elements; }
    T *end()const{ return first_free; }
private:
    static std::allocator alloc;
    void chk_n_alloc()                           //被添加元素函數使用
    {
        if (size() == capacity())reallocate();
    }
    std::pair alloc_n_copy
        (const T*, const T*);          //被拷貝構造，賦值運算符，析構函數使用
    void free();                       //銷毀元素並釋放內存
    void reallocate();                 //獲得更多內存並拷貝已有元素

    T *elements;
    T *first_free;
    T *cap;
};

template
std::allocator myVector::alloc;

template
myVector::myVector(const _Myt& v)
{
    //調用alloc_n_copy 分配空間以容納與s中一樣多的元素
    auto newdata = alloc_n_copy(v.begin(), v.end());
    elements = newdata.first;
    first_free = cap = newdata.second;
}
template
myVector::myVector(_Myt&& v):elements(v.elements),first_free(v.first_free),cap(v.cap){
    v.elements = v.first_free = v.cap = nullptr;
}

template
myVector::~myVector()
{
    free();
}
template
myVector& myVector::operator=(const _Myt& rhs)
{
    //調用alloc_n_copy分配內存,大小與rhs一樣.
    auto data = alloc_n_copy(rhs.begin(), rhs.end());

    free();

    elements = data.first;
    first_free = cap = data.second;

    return *this;
}
template
myVector& myVector::operator=(_Myt&& rhs)
{
    if (this != &rhs)
    {
        free();
        elements = rhs.elements;
        first_free = rhs.first_free;
        cap = rhs.cap;
        //將rhs置為可析構狀態
        rhs.elements = rhs.first_free = rhs.cap = nullptr;
    }
}

template
std::pair myVector::
alloc_n_copy(const T *b, const T *e)
{
    auto data = alloc.allocate(e - b);

    //初始化並返回一個pair,該pair由data和uninitialized_copy組成
    return{ data, uninitialized_copy(b, e, data) };
}
template
void myVector::push_back(const T& s)
{
    chk_n_alloc();              //確保已有新空間
    alloc.construct(first_free++, s);
}

template
void myVector::free()
{
    //不能傳遞給deallocate一個空指針，如果elements為NULL,那麼函數什麼都不做
    if (elements)
    {
        //逆序銷毀所有元素
        for (auto p = first_free; p != elements;/* 空 */)
            alloc.destroy(--p);
        alloc.deallocate(elements, cap - elements);
    }
}

template
void myVector::reallocate()
{
    //我們將分配當前大小兩倍的內存空間
    auto newcapacity = size() ? 2 * size() : 1;

    //分配新內存
    auto newdata = alloc.allocate(newcapacity);

    //將數據從舊地址移動到新地址
    auto dest = newdata;
    auto elem = elements;

    for (size_t i = 0; i != size(); ++i)
        alloc.construct(dest++, std::move(*elem++));
    free();  //一旦更新完就要釋放舊內存

    elements = newdata;
    first_free = dest;

    cap = elements + newcapacity;
}

盡管，以上的代碼vector只實現了vector很少的一部分功能，而且可能實現方式也有不足的地方。不過，在這裡只是想體現動態內存的使用。所以，以上的代碼還是可以作為c++動態內存管理的的示例的。 基本上c++動態內存管理的就介紹到這裡了。