C++ 自定义 `std::vector`：深入理解其内存管理与扩容策略

好的，各位观众老爷，欢迎来到“C++ 自定义 Vector：从入门到入土”讲座现场！今天咱们不聊虚的，直接撸起袖子，手搓一个自己的 std::vector，顺便把内存管理和扩容策略这俩磨人的小妖精给扒个精光。

第一部分：为啥要自虐？（自定义 Vector 的意义）

可能有人要问了：“std::vector 这么好用，为啥要自己造轮子？吃饱了撑的？” 问得好！理由嘛，当然不是为了证明你比标准库的开发者更聪明（虽然某些时候… 咳咳），而是为了：

深入理解底层机制： 真正理解 vector 背后的内存管理、动态扩容等机制，让你以后在面对各种奇葩 Bug 的时候，不再两眼一抹黑。
定制化需求： std::vector 虽然强大，但毕竟是通用的。某些特殊场景下，你可能需要更精细的控制，比如优化内存占用、避免不必要的拷贝等。
面试装 X 必备： 面试官最喜欢问的就是 “你了解 vector 的实现吗？如果让你自己实现一个，你会怎么做？” 到时候你就可以微微一笑，亮出你的自定义 Vector，让面试官眼前一亮。

第二部分：磨刀霍霍向 Vector（基本结构与成员变量）

咱们先来定义一个简单的 MyVector 类，看看需要哪些基本成员变量：

#include <iostream>
#include <algorithm> // 为了用到 std::copy

template <typename T>
class MyVector {
private:
    T* data;       // 指向动态分配的内存块
    size_t size;      // 当前已存储的元素个数
    size_t capacity;  // 当前分配的内存块大小（能容纳的元素个数）

public:
    // 构造函数、析构函数、成员函数等等...
};

data: 这个指针指向我们用来存储元素的内存块。这块内存是在堆上动态分配的，所以我们可以根据需要调整它的大小。
size: 表示 vector 中实际存储了多少个元素。它告诉我们有效数据的范围。
capacity: 表示 vector 当前分配的内存块能容纳多少个元素。当 size 达到 capacity 时，就需要进行扩容。

第三部分：生死轮回（构造函数与析构函数）

构造函数负责初始化 MyVector，析构函数负责释放内存，避免内存泄漏。

public:
    // 默认构造函数
    MyVector() : data(nullptr), size(0), capacity(0) {
        std::cout << "Default constructor called.n";
    }

    // 带初始大小的构造函数
    MyVector(size_t initialSize) : size(initialSize), capacity(initialSize) {
        data = new T[initialSize];
        std::cout << "Constructor with initial size called.n";
    }

    // 拷贝构造函数
    MyVector(const MyVector& other) : size(other.size), capacity(other.capacity) {
        data = new T[other.capacity];
        std::copy(other.data, other.data + other.size, data);
        std::cout << "Copy constructor called.n";
    }

    // 移动构造函数
    MyVector(MyVector&& other) : data(other.data), size(other.size), capacity(other.capacity) {
        other.data = nullptr;
        other.size = 0;
        other.capacity = 0;
        std::cout << "Move constructor called.n";
    }

    // 析构函数
    ~MyVector() {
        delete[] data;
        std::cout << "Destructor called.n";
    }

默认构造函数： 初始化 data 为 nullptr，size 和 capacity 为 0。
带初始大小的构造函数： 分配一块大小为 initialSize 的内存，并将 size 和 capacity 都设置为 initialSize。
拷贝构造函数： 创建一个新的 MyVector，并将 other 中的数据拷贝到新的 MyVector 中。注意，这里要进行深拷贝，也就是分配新的内存，而不是简单地复制指针。
移动构造函数： 将 other 中的数据的所有权转移到新的 MyVector 中，避免不必要的拷贝。将 other.data 设置为 nullptr，防止 other 析构时释放内存。
析构函数： 释放 data 指向的内存，防止内存泄漏。

第四部分：增删改查（核心成员函数）

接下来，咱们来实现一些常用的成员函数，让 MyVector 具备基本的功能。

public:
    // 添加元素到末尾
    void push_back(const T& value) {
        if (size == capacity) {
            reserve(capacity == 0 ? 1 : capacity * 2);  // 扩容
        }
        data[size] = value;
        ++size;
    }

    // 弹出末尾元素
    void pop_back() {
        if (size > 0) {
            --size;
        }
    }

    // 获取元素个数
    size_t getSize() const {
        return size;
    }

    // 获取容量
    size_t getCapacity() const {
        return capacity;
    }

    // 重载 [] 运算符，访问元素
    T& operator[](size_t index) {
        if (index >= size) {
            throw std::out_of_range("Index out of bounds.");
        }
        return data[index];
    }

    const T& operator[](size_t index) const {
        if (index >= size) {
            throw std::out_of_range("Index out of bounds.");
        }
        return data[index];
    }

    // 预留空间，避免频繁扩容
    void reserve(size_t newCapacity) {
        if (newCapacity <= capacity) {
            return; // No need to reserve less space
        }

        T* newData = new T[newCapacity];
        if (data) {
            std::copy(data, data + size, newData);
            delete[] data;
        }
        data = newData;
        capacity = newCapacity;
    }

    // 调整大小，可以增加或减少元素
    void resize(size_t newSize) {
        if (newSize > capacity) {
            reserve(newSize);
        }
        size = newSize;
    }

    // 赋值运算符
    MyVector& operator=(const MyVector& other) {
        if (this == &other) {
            return *this;
        }

        if (capacity < other.size) {
            reserve(other.size);
        }

        size = other.size;
        std::copy(other.data, other.data + size, data);

        return *this;
    }

    // 移动赋值运算符
    MyVector& operator=(MyVector&& other) {
        if (this == &other) {
            return *this;
        }

        delete[] data;

        data = other.data;
        size = other.size;
        capacity = other.capacity;

        other.data = nullptr;
        other.size = 0;
        other.capacity = 0;

        return *this;
    }

    // 清空vector
    void clear() {
        size = 0;
    }
};

push_back(const T& value)： 在 vector 的末尾添加一个元素。如果 size 等于 capacity，则需要先进行扩容。这里使用了 reserve() 函数来扩容，后面会详细讲解。
pop_back()： 移除 vector 的末尾元素。
getSize()： 返回 vector 中元素的个数。
getCapacity()： 返回 vector 的容量。
operator[]： 重载 [] 运算符，允许使用下标访问 vector 中的元素。需要进行越界检查，避免访问非法内存。
reserve(size_t newCapacity)： 预留空间，避免频繁扩容。如果 newCapacity 大于当前的 capacity，则分配一块大小为 newCapacity 的新内存，将原来的数据拷贝到新内存中，并释放原来的内存。
resize(size_t newSize)： 调整大小，可以增加或减少元素。如果 newSize 大于当前的 capacity，则先调用 reserve() 进行扩容。
operator= (拷贝赋值运算符)： 将一个 MyVector 赋值给另一个 MyVector。需要考虑自赋值的情况，并进行深拷贝。
operator= (移动赋值运算符)： 将一个 MyVector 的资源移动到另一个 MyVector。
clear()： 清空 Vector，将 size 设置为 0，但 capacity 不变。

第五部分：内存管理与扩容策略（重头戏）

内存管理是 vector 的核心，而扩容策略直接影响 vector 的性能。

内存分配：

vector 使用动态内存分配，也就是在堆上分配内存。这使得 vector 可以根据需要调整大小。我们使用 new T[size] 来分配内存，使用 delete[] data 来释放内存。
扩容策略：

当 size 达到 capacity 时，vector 需要进行扩容。常见的扩容策略有：
- 每次扩容增加固定大小： 例如，每次增加 10 个元素的大小。这种策略简单，但可能导致频繁扩容，尤其是在 vector 增长很快的情况下。
- 每次扩容增加一倍： 也就是 capacity = capacity * 2。这种策略可以减少扩容的次数，但可能会浪费一些内存。 std::vector 通常采用这种策略。
- 其他策略： 例如，每次扩容增加 1.5 倍。
我们的 push_back 函数中使用了每次扩容增加一倍的策略：
```
    if (size == capacity) {
        reserve(capacity == 0 ? 1 : capacity * 2);  // 扩容
    }
```
reserve() 函数负责实际的扩容操作：
```
    void reserve(size_t newCapacity) {
        if (newCapacity <= capacity) {
            return; // No need to reserve less space
        }

        T* newData = new T[newCapacity];
        if (data) {
            std::copy(data, data + size, newData);
            delete[] data;
        }
        data = newData;
        capacity = newCapacity;
    }
```
- 首先，分配一块大小为 newCapacity 的新内存。
- 然后，将原来的数据拷贝到新内存中。
- 接着，释放原来的内存。
- 最后，更新 data 和 capacity。
为什么扩容时要拷贝元素？

因为 vector 中的元素是连续存储的。当我们扩容时，需要分配一块更大的连续内存块，并将原来的元素拷贝到新的内存块中，以保持元素的连续性。

第六部分：实战演练（代码示例）

来，咱们写个 main 函数，测试一下咱们的 MyVector：

int main() {
    MyVector<int> vec;

    std::cout << "Initial size: " << vec.getSize() << ", capacity: " << vec.getCapacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
        std::cout << "Size: " << vec.getSize() << ", capacity: " << vec.getCapacity() << std::endl;
    }

    for (size_t i = 0; i < vec.getSize(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;

    vec.pop_back();
    std::cout << "After pop_back, size: " << vec.getSize() << ", capacity: " << vec.getCapacity() << std::endl;

    vec.resize(5);
    std::cout << "After resize(5), size: " << vec.getSize() << ", capacity: " << vec.getCapacity() << std::endl;

    MyVector<int> vec2 = vec; // Copy constructor
    std::cout << "vec2 size: " << vec2.getSize() << ", capacity: " << vec2.getCapacity() << std::endl;

    MyVector<int> vec3 = std::move(vec); // Move constructor
    std::cout << "vec3 size: " << vec3.getSize() << ", capacity: " << vec3.getCapacity() << std::endl;
    std::cout << "vec size: " << vec.getSize() << ", capacity: " << vec.getCapacity() << std::endl;

    return 0;
}

运行结果（大概）：

Default constructor called.
Initial size: 0, capacity: 0
Size: 1, capacity: 1
Size: 2, capacity: 2
Size: 3, capacity: 4
Size: 4, capacity: 4
Size: 5, capacity: 8
Size: 6, capacity: 8
Size: 7, capacity: 8
Size: 8, capacity: 8
Size: 9, capacity: 16
Size: 10, capacity: 16
0 1 2 3 4 5 6 7 8 9
After pop_back, size: 9, capacity: 16
After resize(5), size: 5, capacity: 16
Copy constructor called.
vec2 size: 5, capacity: 16
Move constructor called.
vec3 size: 5, capacity: 16
vec size: 0, capacity: 0
Destructor called.
Destructor called.
Destructor called.

可以看到，MyVector 能够正常工作，并且扩容策略也符合我们的预期。

第七部分：更上一层楼（优化与改进）

咱们的 MyVector 已经基本可用了，但还有很多可以优化和改进的地方：

使用 Allocator： std::vector 使用 Allocator 来进行内存分配。通过使用 Allocator，我们可以自定义内存分配策略，例如使用内存池来提高性能。
异常安全： 在拷贝构造函数和赋值运算符中，需要保证异常安全。也就是说，如果拷贝过程中发生异常，vector 的状态应该保持一致。
迭代器： 实现迭代器，使得可以使用 std::algorithm 中的算法来操作 MyVector。
emplace_back： 实现 emplace_back 函数，避免不必要的拷贝。
缩小容量： 实现 shrink_to_fit 函数，释放多余的内存。
其他优化： 例如，使用移动语义来优化拷贝操作。

第八部分：总结与展望

今天咱们一起手搓了一个简单的 MyVector，深入理解了 vector 的内存管理和扩容策略。虽然咱们的 MyVector 还比较简陋，但它已经具备了 std::vector 的核心功能。

希望通过这次讲座，大家能够对 vector 的底层实现有更深入的了解，并在实际开发中更好地使用 vector。

记住，编程的乐趣在于不断学习和探索！感谢各位的观看，咱们下期再见！

发表回复 取消回复

发表回复取消回复