C++ 中的向量實現

Jinku Hu 2022年1月13日 2021年10月2日
C++ 中的向量實現

本文將演示如何在 C++ 中實現一個類似於 std::vector 的類。

使用 mallocrealloc 函式在 C++ 中實現自定義 vector

std::vector 容器被稱為動態 C 樣式陣列,它連續儲存其元素。儘管沒有強制執行確切的實現,但規範要求容器的某些功能。也就是說,向量應該是一個有序的資料結構,並提供對其元素的隨機訪問。其他功能可以表示為作為介面公開的公共成員函式,其中一些我們將在以下示例中實現。請注意,實際的 std::vector 實現可能會非常廣泛,因此我們只是展示了讀者可能會新增更多功能的起點。

首先,我們需要定義一個 MyVector 類作為可以儲存任何泛型型別的函式模板。然後我們可以包含核心資料成員,如指向元素陣列的指標和整數物件,以相應地儲存大小/容量。請記住,為了獲得更好的效能,std::vector 可能會分配比儲存元素更大的記憶體塊。分配的記憶體大小稱為向量的容量,我們將其儲存在 cap 資料成員中。一旦構建了新的 MyVector 物件並將當前元素設定為零,我們將分配固定數量(20 個物件)。

請注意,我們使用了 malloc 函式,這在當代 C++ 中可能被認為是有害的,但如果謹慎使用,它會提供靈活性和良好的效能。此外,使用 malloc 分配的記憶體可以使用 realloc 函式進行擴充套件,我們將需要它來管理陣列的大小調整。

總的來說,我們的類包含三個成員函式和 [] 運算子,它們構成了動態向量的基礎。以下示例程式碼演示了 push_backsizeoperator[] 函式實現。後兩者非常直觀且易於理解,而 push_back 可能需要一些解釋。

請注意,當元素數量超過容量時,我們只需要在構造物件後分配新的記憶體區域。因此,對於 push_back 函式中的每個場景,我們需要兩個單獨的路徑,其中一個將呼叫 realloc 函式來擴充套件當前記憶體塊。realloc 接受兩個引數:指向前一個記憶體區域的指標和新區域的大小(以位元組為單位)。如果呼叫成功,則返回一個有效指標,與前一個指標相同或一個新指標,具體取決於在同一塊中是否可以找到足夠的記憶體。否則,返回 NULL 指標以表示請求失敗。

#include <iostream>
#include <string>

using std::cout; using std::cin;
using std::endl; using std::string;

template<typename T>
class MyVector {
public:
    MyVector() {
        cap = alloc;
        vector = (T*)malloc(sizeof(T) * alloc);
        elem_num = 0;
    };

    void push_back(const T &data);
    void pop_back();

    [[nodiscard]] bool empty() const;
    [[nodiscard]] size_t size() const;
    [[nodiscard]] size_t capacity() const;
    T &operator[](size_t pos);

    ~MyVector();
private:
    T *vector = nullptr;
    size_t cap;
    size_t elem_num;
    const int alloc = 20;
};

template<typename T>
MyVector<T>::~MyVector() {
    free(vector);
}

template<typename T>
void MyVector<T>::push_back(const T &data) {
    if (elem_num < cap) {
        *(vector + elem_num) = data;
        elem_num++;
    } else {
        vector = (T*)realloc(vector, sizeof(T) * cap * 2);
        cap *= 2;

        if (vector) {
            *(vector + elem_num) = data;
            elem_num++;
        }
    }
}

template<typename T>
void MyVector<T>::pop_back() {
    if (empty())
        return;
    elem_num--;
}

template<typename T>
T &MyVector<T>::operator[](size_t pos) {
    if (pos >= 0 &&  pos <= elems)
        return *(this->arr + pos);
    throw std::out_of_range("Out of bounds element access");
}

template<typename T>
size_t MyVector<T>::capacity() const {
    return cap;
}

template<typename T>
bool MyVector<T>::empty() const {
    return elem_num == 0;
}

template<typename T>
size_t MyVector<T>::size() const {
    return elem_num;
}

struct MyClass {
    int num;
    double num2;
};

int main() {
    MyVector<MyClass> m1;

    m1.push_back({1, 1.1});
    m1.push_back({1, 1.2});
    m1.push_back({1, 1.3});
    m1.push_back({1, 1.4});

    for (size_t i = 0; i < m1.size(); ++i) {
        cout << m1[i].num << ", " << m1[i].num2 << endl;
    }

    cout << "/ ------------------- /" << endl;
    m1.pop_back();
    m1.pop_back();

    for (size_t i = 0; i < m1.size(); ++i) {
        cout << m1[i].num << ", " << m1[i].num2 << endl;
    }

    return EXIT_SUCCESS;
}

輸出:

1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2

為了測試 MyVector 類,我們在 main 函式中包含了一些驅動程式程式碼,並定義了 MyClass 自定義物件以儲存為元素。最後,我們新增了 pop_back 函式,用於刪除向量後面的元素。pop_back 函式不需要釋放或刪除元素內容。它可以在每次呼叫時將 elem_num 成員減一,下一次 push_back 呼叫將重寫丟棄的元素位置。一旦物件超出範圍,釋放記憶體塊也很重要。因此,我們需要在類的解構函式中包含對 free 函式的呼叫。

#include <iostream>
#include <string>

using std::cout; using std::cin;
using std::endl; using std::string;

template<typename T>
class MyVector {
public:
    MyVector() {
        arr = new T[default_capacity];
        cap = default_capacity;
        elems = 0;
    };

    void push_back(const T &data);
    void pop_back();

    [[nodiscard]] bool empty() const;
    [[nodiscard]] size_t size() const;
    [[nodiscard]] size_t capacity() const;
    T &operator[](size_t pos);

    ~MyVector();
private:
    T *arr = nullptr;
    size_t cap;
    size_t elems;
    const int default_capacity = 20;
};

template<typename T>
MyVector<T>::~MyVector() {
    delete [] arr;
}

template<typename T>
void MyVector<T>::push_back(const T &data) {
    if (elems < cap) {
        *(arr + elems) = data;
        elems++;
    } else {
        auto tmp_arr = new T[cap * 2];
        cap *= 2;
        for (int i = 0; i < elems; i++) {
            tmp_arr[i] = arr[i];
        }
        delete [] arr;
        arr = tmp_arr;

        *(arr + elems) = data;
        elems++;
    }
}

template<typename T>
T &MyVector<T>::operator[](size_t pos) {
    if (pos >= 0 &&  pos <= elems)
        return *(this->arr + pos);
    throw std::out_of_range("Out of bounds element access");
}

template<typename T>
size_t MyVector<T>::size() const {
    return elems;
}

template<typename T>
size_t MyVector<T>::capacity() const {
    return cap;
}

template<typename T>
void MyVector<T>::pop_back() {
    if (empty())
        return;
    elems--;
}

template<typename T>
bool MyVector<T>::empty() const {
    return elems == 0;
}

struct MyClass {
    string name;
    double num;
};

int main() {
    MyVector<MyClass> m1;

    m1.push_back({"one", 1.1});
    m1.push_back({"two", 1.2});
    m1.push_back({"three", 1.3});
    m1.push_back({"four", 1.4});

    for (size_t i = 0; i < m1.size(); ++i) {
        cout << m1[i].name << ", " << m1[i].num << endl;
    }

    cout << "/ ------------------- /" << endl;
    m1.pop_back();
    m1.pop_back();

    for (size_t i = 0; i < m1.size(); ++i) {
        cout << m1[i].name << ", " << m1[i].num << endl;
    }

    return EXIT_SUCCESS;
}

輸出:

one, 1.1
two, 1.2
three, 1.3
four, 1.4
/ ------------------- /
one, 1.1
two, 1.2
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相關文章 - C++ Vector