迹忆客 专注技术分享

本文将演示如何在 C++ 中实现一个类似于 std::vector 的类。

使用 malloc 和 realloc 函数在 C++ 中实现自定义 vector 类

std::vector 容器被称为动态 C 样式数组，它连续存储其元素。尽管没有强制执行确切的实现，但规范要求容器的某些功能。也就是说，向量应该是一个有序的数据结构，并提供对其元素的随机访问。其他功能可以表示为作为接口公开的公共成员函数，其中一些我们将在以下示例中实现。请注意，实际的 std::vector 实现可能会非常广泛，因此我们只是展示了读者可能会添加更多功能的起点。

首先，我们需要定义一个 MyVector 类作为可以存储任何泛型类型的函数模板。然后我们可以包含核心数据成员，如指向元素数组的指针和整数对象，以相应地存储大小/容量。请记住，为了获得更好的性能，std::vector 可能会分配比存储元素更大的内存块。分配的内存大小称为向量的容量，我们将其存储在 cap 数据成员中。一旦构建了新的 MyVector 对象并将当前元素设置为零，我们将分配固定数量（20 个对象）。

请注意，我们使用了 malloc 函数，这在当代 C++ 中可能被认为是有害的，但如果谨慎使用，它会提供灵活性和良好的性能。此外，使用 malloc 分配的内存可以使用 realloc 函数进行扩展，我们将需要它来管理数组的大小调整。

总的来说，我们的类包含三个成员函数和 [] 运算符，它们构成了动态向量的基础。以下示例代码演示了 push_back、size 和 operator[] 函数实现。后两者非常直观且易于理解，而 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