11-自己實作一個 vector 類別

11-1 規劃我們的 Vec 類別
11-2 實作 Vec 的細節
11-3 測試 Vec 類別
11-4 重載 [] 運算子
11-5 讓 Vec 可以儲存 int 以外的資料型別

11-1 規劃我們的 Vec 類別

一、Vec 類別需要什麼？

在這個章節裡，我們嘗試自己建立一個簡單版的 vector，一個叫做 Vec 的類別。

我們至少需要以下三項屬性：

data: 指向一塊儲存資料的記憶體空間
size: 記錄目前 Vec 裡的元素數量
capacity: 記錄目前 Vec 裡己向作業系統要求配置的空間大小

接下來考慮需要對外公開的成員函數。

Vec(): 建構函數
~Vec(): 解構函數
size(): 回傳目前 Vec 裡有幾個元素
capacity(): 回傳目前 Vec 配置的記憶體大小最多可放幾個元素
push_back(val): 將 val 附加在 Vec 的尾端
pop_back(): 將 Vec 尾端的元素移除

現在我們可以先完成這個類別的原型宣告如下:

[vec.h]

class Vec {
private:
    int *m_data;
    int m_size;
    int m_capacity;
public:
    Vec();
    ~Vec();
    int size();
    int capacity();
    void push_back(int val);
    void pop_back();
};

在成員函數的部分，我們使用 m_ 開頭的名稱，一方面用來提醒自己這是個 data member。一方面也是因為 data member 和 member function 不能用相同的名稱，我們不能有一個叫做 size 的 data member，同時又有一個叫做 size 的 member function。

11-2 實作 Vec 的細節

一、建構與解構函數

在建構函數中，我們要初始化 Vec 的 data member。因為剛建立好的 Vec 會是一個空的容器，所以一開始 m_size 和 m_capacity 都是 0。而 m_data 則先賦予它 nullptr 值，表示目前沒有指向任何記憶體。

Vec::Vec()
{
    m_data = nullptr;
    m_size = 0;
    m_capacity = 0;
}

在解構函數部分，我們先檢查是不有向作業系統要求配置記憶體，若有的話 m_data 將不會是 nullptr，而是會指向那塊記憶體。我們要釋放配置的記憶，把它還給作業系統。

Vec::~Vec()
{
    if(m_data!=nullptr)
    {
        delete [] m_data;
    }
}

二、size 和 capacity

Vec 的 size 和 capacity 會隨著 push_back 放入愈來愈多的元素而成長，這兩個 data member 不應該被使用者修改，所以我們只提供兩個相應的成員函數用來回傳其值。

int Vec::size()
{
    return m_size;
}

int Vec::capacity()
{
    return m_capacity;
}

三、push_back

在 Vec 空間需要成長時，我們採用一個簡單的策略 - 每次成長為之前的 2倍大。

要留意的是，由於一開始 capacity 是 0，乘以 2 之後還是 0，所以要特別處理這個狀況，在第一次 push_back 時，capacity 要成長為 1。

在成長的部分，流程如下。

配置一塊原來 2 倍大的記憶體空間
把舊資料搬到新空間
釋放舊空間記憶體，還給作業系統
將 m_data 指向新的這塊記憶體

void Vec::push_back(int val)
{
    // 如果空間不夠用
    if(m_size==m_capacity)
    {
        // 每次成長為原來的 2 倍大小
        int new_capacity = m_capacity*2;

        if(new_capacity==0)
            new_capacity = 1;

        // 配置一塊新的空間
        int *new_data = new int[new_capacity];
        // 把資料搬到新的空間
        for(int i=0; i<m_size; i++)
        {
            new_data[i] = m_data[i];
        }
        // 釋放舊的空間，改用新空間
        if(m_data!=nullptr)
            delete [] m_data;

        m_data = new_data;
        m_capacity = new_capacity;
    }

    m_data[m_size] = val;
    m_size++;
}

四、pop_back()

pop_back 部分很簡單，只要把 size - 1 即可，不必清除那塊記憶體。下次 push_back 時，新資料就會蓋掉它。

void Vec::pop_back()
{
    m_size--;
}

11-3 測試 Vec 類別

目前我們的 Vec 類別如下：

[vec.h]

#ifndef VEC_H_INCLUDED
#define VEC_H_INCLUDED

class Vec {
private:
    int *m_data;
    int m_size;
    int m_capacity;
public:
    Vec();
    ~Vec();
    int size();
    int capacity();
    void push_back(int val);
    void pop_back();
};

Vec::Vec()
{
    m_data = nullptr;
    m_size = 0;
    m_capacity = 0;
}

Vec::~Vec()
{
    if(m_data!=nullptr)
    {
        delete [] m_data;
    }
}

int Vec::size()
{
    return m_size;
}

int Vec::capacity()
{
    return m_capacity;
}

void Vec::push_back(int val)
{
    // 如果空間不夠用
    if(m_size==m_capacity)
    {
        // 每次成長為原來的 2 倍大小
        int new_capacity = m_capacity*2;

        if(new_capacity==0)
            new_capacity = 1;

        // 配置一塊新的空間
        int *new_data = new int[new_capacity];
        // 把資料搬到新的空間
        for(int i=0; i<m_size; i++)
        {
            new_data[i] = m_data[i];
        }
        // 釋放舊的空間，改用新空間
        if(m_data!=nullptr)
            delete [] m_data;

        m_data = new_data;
        m_capacity = new_capacity;
    }

    m_data[m_size] = val;
    m_size++;
}

void Vec::pop_back()
{
    m_size--;
}

#endif // VEC_H_INCLUDED

在主程式中引入其標頭檔來使用看看。

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

using namespace std;

int main()
{
    Vec a;

    a.push_back(1);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(3);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(5);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(7);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(9);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;

    return 0;
}

注意看 capacity 和 size 的變化。

Cap:1 Size:1 Cap:2 Size:2 Cap:4 Size:3 Cap:4 Size:4 Cap:8 Size:5

11-4 重載 [] 運算子

現在我們還缺一個重要的功能，那就是存取 Vec 裡的值。

試著執行這段程式看看。

[main.cpp]

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

using namespace std;

int main()
{
    Vec a;

    a.push_back(1);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(3);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(5);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(7);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(9);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;

    for(int i=0; i<a.size(); i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

我們會得到這個錯誤訊息。

error: no match for 'operator[]' (operand types are 'Vec' and 'int')|

因為在第 23 行中的cout << a[i]，編譯器不知道 Vec [] 要怎麼處理。

[]是一個運算子，每種資料型別的 [] 運算可能有所不同，我們必須自己實作 Vec 的 [] 運算子運算。

在 Vec 宣告的尾端加入這行重載 [] 運算子的成員函數。

    ...
    void pop_back();
    int& operator[] (int index); // <== 加入這行
};

在函數實作部分加入。

int& Vec::operator[] (int index)
{
    return m_data[index];
}

這段程式碼是在做什麼呢? 我們把它拆解成四個部分來看。

int&（回傳型態）：注意那個 & 符號，它代表「參照」（Reference）。意思是它不只傳回那個數字的值，而是直接把那塊記憶體的「真身」給你。這樣你才能寫出像 a[0] = 10; 這樣的程式碼，直接修改裡面的數值。
Vec::（所屬類別）：這代表這個功能是屬於 Vec 這個類別。
operator[]（函數名稱）：這是 C++ 的特殊關鍵字。組合起來就是告訴編譯器：「我要重新定義中括號 [] 的功能」。
(int index)（參數）：中括號裡面填的數字（索引值）。例如 a[3]，這個 index 就是 3。

現在可以執行這段程式來驗證了。

[main.cpp]

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

using namespace std;

int main()
{
    Vec a;

    a.push_back(1);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(3);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(5);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(7);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;
    a.push_back(9);
    cout << "Cap:" << a.capacity() << " Size:" << a.size() << endl;

    for(int i=0; i<a.size(); i++)
    {
        cout << a[i] << " ";  // 1 3 5 7 9
        a[i] = a[i]*2; // 把值修改為 2 倍
    }
    cout << endl;

    for(int i=0; i<a.size(); i++)
    {
        cout << a[i] << " ";  // 2 6 10 14 18
    }
    cout << endl;

    return 0;
}

Cap:1 Size:1 Cap:2 Size:2 Cap:4 Size:3 Cap:4 Size:4 Cap:8 Size:5 1 3 5 7 9 2 6 10 14 18

11-5 讓 Vec 可以儲存 int 以外的資料型別

目前我們 Vec 雖然可以動態成長，但是只能存放 int 型別的資料，這讓它變得很沒用。

明明只有型別不同，難道我們要寫一個 Vec_int 給 int 用，寫一個 Vec_double 給 double 用，......。

在這裡我們要使用一個新東西 樣版(template)，class 是用來產生物件的 [模版]，而 template 則是用來產生 class 的 [模版]。

你可以這樣想，在宣告時寫 Vec<int> 這時 template 就會幫我們生成一個可以儲存 int 的 class，宣告時寫 Vec<double> 這時 template 就會幫我們生成一個可以儲存 double 的 class。

在程式碼中插入 template<typename T> 表示接下來這個類別、函數裡，看到 T 時，把它替代成指定的型別。

例如：

template<typename T>
class Vec {
private:
  T* m_data;
  int m_size;
  int m_capacity;
};

想像在主程式中，我們宣告一個 Vec<double> a;，會自動產生一個像這樣的 Vec class。

class Vec<double> {
private:
  double* m_data;
  int m_size;
  int m_capacity;
};

如此一來，我們就可以讓 Vec 裡儲存各種型別的元素，甚至是我們自己設計的型別。

修改後的 [vec.h]

#ifndef VEC_H_INCLUDED
#define VEC_H_INCLUDED

template<typename T>
class Vec {
private:
    T *m_data;
    int m_size;
    int m_capacity;
public:
    Vec();
    ~Vec();
    int size();
    int capacity();
    void push_back(T val);
    void pop_back();
    T& operator[] (int index);
};

template<typename T>
Vec<T>::Vec()
{
    m_data = nullptr;
    m_size = 0;
    m_capacity = 0;
}

template<typename T>
Vec<T>::~Vec()
{
    if(m_data!=nullptr)
    {
        delete [] m_data;
    }
}

template<typename T>
int Vec<T>::size()
{
    return m_size;
}

template<typename T>
int Vec<T>::capacity()
{
    return m_capacity;
}

template<typename T>
void Vec<T>::push_back(T val)
{
    // 如果空間不夠用
    if(m_size==m_capacity)
    {
        // 每次成長為原來的 2 倍大小
        int new_capacity = m_capacity*2;

        if(new_capacity==0)
            new_capacity = 1;

        // 配置一塊新的空間
        T *new_data = new T[new_capacity];
        // 把資料搬到新的空間
        for(int i=0; i<m_size; i++)
        {
            new_data[i] = m_data[i];
        }
        // 釋放舊的空間，改用新空間
        if(m_data!=nullptr)
            delete [] m_data;

        m_data = new_data;
        m_capacity = new_capacity;
    }

    m_data[m_size] = val;
    m_size++;
}

template<typename T>
void Vec<T>::pop_back()
{
    m_size--;
}

template<typename T>
T& Vec<T>::operator[] (int index)
{
    return m_data[index];
}

#endif // VEC_H_INCLUDED