C++ 从零开始实现一个简化版 `std::vector`：深入内存管理

哈喽，各位好！今天我们来一起手撸一个简化版的 std::vector，重点放在内存管理上，保证让你彻底理解 C++ 里面的动态数组是怎么回事儿。

啥是 std::vector？

简单来说，std::vector 就是一个可以自动增长的数组。你不用一开始就确定它的大小，可以随时往里面添加元素，它会自动帮你分配和释放内存。这玩意儿在 C++ 里简直是神器，用得不要太频繁。

为啥要自己实现？

直接用 std::vector 不香吗？香！但是，想要真正理解它的工作原理，特别是内存管理那一块，最好的办法就是自己动手实现一个简化版。这样你才能知道 std::vector 背后都做了些什么，以后遇到内存相关的问题也能更快地定位。

我们简化版的目标

• 动态增长： 可以像 std::vector 一样，动态地添加元素。
• 基本操作： 实现 push_back（添加元素到末尾）、size（获取元素个数）、capacity（获取容量）、operator[]（下标访问）等基本操作。
• 内存管理： 重点关注内存的分配、释放和重新分配。
• 异常安全： 尽量保证在出现异常时，不会导致内存泄漏或者数据损坏。

开始撸代码！

首先，我们创建一个 MyVector 类，并定义一些成员变量：

#include <iostream>
#include <algorithm> // For std::copy

template <typename T>
class MyVector {
private:
    T* data;       // 指向动态分配的内存
    size_t size_;    // 当前元素个数
    size_t capacity_; // 当前容量

public:
    // 构造函数
    MyVector();
    MyVector(size_t initial_capacity); //构造函数指定初始容量

    // 析构函数
    ~MyVector();

    // 拷贝构造函数
    MyVector(const MyVector& other);

    // 拷贝赋值运算符
    MyVector& operator=(const MyVector& other);

    // 移动构造函数
    MyVector(MyVector&& other) noexcept;

    // 移动赋值运算符
    MyVector& operator=(MyVector&& other) noexcept;

    // 添加元素到末尾
    void push_back(const T& value);

    // 获取元素个数
    size_t size() const;

    // 获取容量
    size_t capacity() const;

    // 下标访问
    T& operator[](size_t index);
    const T& operator[](size_t index) const;

    // 删除末尾元素
    void pop_back();

    // 扩容函数
    void reserve(size_t new_capacity);

    // 清空所有元素
    void clear();

    // 删除指定位置的元素
    void erase(size_t index);

    // 插入元素到指定位置
    void insert(size_t index, const T& value);

private:
    // 内部扩容函数（方便复用）
    void grow();
};

• data: 指向我们动态分配的内存，用来存储元素。
• size_: 记录当前已经存储了多少个元素。
• capacity_: 记录当前分配的内存可以容纳多少个元素。

构造函数

template <typename T>
MyVector<T>::MyVector() : data(nullptr), size_(0), capacity_(0) {}

template <typename T>
MyVector<T>::MyVector(size_t initial_capacity) : size_(0), capacity_(initial_capacity) {
    data = new T[initial_capacity];
}

• 默认构造函数：初始化 data 为 nullptr，size_ 和 capacity_ 都为 0。
• 带初始容量的构造函数：根据指定的 initial_capacity 分配内存。

析构函数

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

• delete[] data: 释放之前分配的内存。一定要用 delete[]，因为我们用 new[] 分配的。

push_back：添加元素

这是 std::vector 最常用的操作之一。

template <typename T>
void MyVector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        grow(); // 扩容
    }
    data[size_] = value;
    size_++;
}

• 先检查 size_ 是否等于 capacity_，如果相等，说明当前内存已经满了，需要扩容。
• data[size_] = value: 将新元素放到数组的末尾。
• size_++: 更新元素个数。

grow：扩容

这是内存管理的核心部分。

template <typename T>
void MyVector<T>::grow() {
    // 如果当前容量为0，则初始容量设为1，否则翻倍
    size_t new_capacity = (capacity_ == 0) ? 1 : capacity_ * 2;

    // 分配新的内存
    T* new_data = new T[new_capacity];

    // 将原来的数据复制到新的内存
    for (size_t i = 0; i < size_; ++i) {
        new_data[i] = data[i];
    }

    // 释放原来的内存
    delete[] data;

    // 更新 data 和 capacity_
    data = new_data;
    capacity_ = new_capacity;
}

• 计算新的容量：通常是当前容量的两倍。
• new T[new_capacity]: 分配新的内存。
• 将原来的数据复制到新的内存：这里可以用 std::copy 优化一下，更高效。
• delete[] data: 释放原来的内存。
• 更新 data 和 capacity_。

size 和 capacity

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

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

这两个函数很简单，直接返回对应的成员变量。

operator[]：下标访问

template <typename T>
T& MyVector<T>::operator[](size_t index) {
    return data[index];
}

template <typename T>
const T& MyVector<T>::operator[](size_t index) const {
    return data[index];
}

• 提供两种版本：一个用于可修改的访问，一个用于只读访问。

拷贝构造函数，拷贝赋值运算符，移动构造函数，移动赋值运算符

这四个函数对于保证类的正确性和避免内存泄漏至关重要，尤其是在涉及动态内存管理时。

template <typename T>
MyVector<T>::MyVector(const MyVector& other) : size_(other.size_), capacity_(other.capacity_) {
    data = new T[capacity_];
    for (size_t i = 0; i < size_; ++i) {
        data[i] = other.data[i];
    }
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(const MyVector& other) {
    if (this == &other) {
        return *this; // 防止自赋值
    }

    // 如果容量不同，则需要重新分配内存
    if (capacity_ != other.capacity_) {
        delete[] data;
        capacity_ = other.capacity_;
        data = new T[capacity_];
    }

    size_ = other.size_;
    for (size_t i = 0; i < size_; ++i) {
        data[i] = other.data[i];
    }
    return *this;
}

template <typename T>
MyVector<T>::MyVector(MyVector&& other) noexcept : data(other.data), size_(other.size_), capacity_(other.capacity_) {
    other.data = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector&& other) noexcept {
    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;
}

• 拷贝构造函数 (Copy Constructor):

  • 作用：创建一个新对象作为现有对象的副本。
  • 实现：分配新的内存空间，并将现有对象的数据复制到新对象中。
  • 为什么需要深拷贝：避免多个对象指向同一块内存，当一个对象销毁时释放了内存，其他对象仍然尝试访问该内存，导致悬挂指针和未定义行为。

• 拷贝赋值运算符 (Copy Assignment Operator):

  • 作用：将现有对象的数据复制到另一个现有对象中。
  • 实现：
    1. 自赋值检查：首先检查是否是自赋值（this == &other），如果是，则直接返回 *this，避免不必要的操作。
    2. 释放旧内存：释放当前对象已有的内存，因为要被新数据覆盖。
    3. 分配新内存：分配与源对象相同大小的内存。
    4. 数据复制：将源对象的数据复制到当前对象的新内存中。
    5. *返回 `this`**：返回当前对象的引用，支持链式赋值。
  • 为什么需要深拷贝：与拷贝构造函数类似，避免多个对象指向同一块内存，导致问题。
  • 注意:如果容量不同，需要重新分配内存，容量相同时，只需要覆盖现有数据即可。

• 移动构造函数 (Move Constructor):

  • 作用：将现有对象的所有权（资源，如动态分配的内存）转移到新对象，而不是复制数据。
  • 实现：
    1. 直接转移：直接将源对象的指针（如 data）赋给新对象，而不是分配新的内存并复制数据。
    2. 置空源对象：将源对象的指针置为 nullptr，防止源对象在其析构函数中释放已被转移的资源。
    3. noexcept：声明为 noexcept，表示这个操作不会抛出异常，这对于某些优化（如 std::vector 的 resize）很重要。
  • 优点：避免了昂贵的内存分配和数据复制操作，提高了性能。
  • 适用场景：源对象是一个临时对象（右值），例如函数返回值或通过 std::move 显式转换的对象。

• 移动赋值运算符 (Move Assignment Operator):

  • 作用：将现有对象的所有权（资源）转移到另一个现有对象。
  • 实现：
    1. 自赋值检查：首先检查是否是自赋值（this == &other），如果是，则直接返回 *this，避免不必要的操作。
    2. 释放旧内存：释放当前对象已有的内存，因为要被新资源覆盖。
    3. 资源转移：将源对象的指针（如 data）赋给当前对象。
    4. 置空源对象：将源对象的指针置为 nullptr，防止源对象在其析构函数中释放已被转移的资源。
    5. *返回 `this`**：返回当前对象的引用，支持链式赋值。
  • 优点：与移动构造函数类似，避免了昂贵的内存分配和数据复制操作，提高了性能。
  • 适用场景：源对象是一个临时对象（右值），例如函数返回值或通过 std::move 显式转换的对象。

其他操作

template <typename T>
void MyVector<T>::pop_back() {
    if (size_ > 0) {
        size_--;
    }
}

template <typename T>
void MyVector<T>::reserve(size_t new_capacity) {
    if (new_capacity > capacity_) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size_; ++i) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity_ = new_capacity;
    }
}

template <typename T>
void MyVector<T>::clear() {
    size_ = 0;
}

template <typename T>
void MyVector<T>::erase(size_t index) {
    if (index >= size_) {
        return; // 或者抛出异常
    }
    for (size_t i = index; i < size_ - 1; ++i) {
        data[i] = data[i + 1];
    }
    size_--;
}

template <typename T>
void MyVector<T>::insert(size_t index, const T& value) {
    if (index > size_) {
        return; // 或者抛出异常
    }

    if (size_ == capacity_) {
        grow();
    }

    for (size_t i = size_; i > index; --i) {
        data[i] = data[i - 1];
    }
    data[index] = value;
    size_++;
}

这些操作和 std::vector 的功能类似，就不一一解释了。

完整代码示例

#include <iostream>
#include <algorithm> // For std::copy

template <typename T>
class MyVector {
private:
    T* data;       // 指向动态分配的内存
    size_t size_;    // 当前元素个数
    size_t capacity_; // 当前容量

public:
    // 构造函数
    MyVector();
    MyVector(size_t initial_capacity); //构造函数指定初始容量

    // 析构函数
    ~MyVector();

    // 拷贝构造函数
    MyVector(const MyVector& other);

    // 拷贝赋值运算符
    MyVector& operator=(const MyVector& other);

    // 移动构造函数
    MyVector(MyVector&& other) noexcept;

    // 移动赋值运算符
    MyVector& operator=(MyVector&& other) noexcept;

    // 添加元素到末尾
    void push_back(const T& value);

    // 获取元素个数
    size_t size() const;

    // 获取容量
    size_t capacity() const;

    // 下标访问
    T& operator[](size_t index);
    const T& operator[](size_t index) const;

    // 删除末尾元素
    void pop_back();

    // 扩容函数
    void reserve(size_t new_capacity);

    // 清空所有元素
    void clear();

    // 删除指定位置的元素
    void erase(size_t index);

    // 插入元素到指定位置
    void insert(size_t index, const T& value);

private:
    // 内部扩容函数（方便复用）
    void grow();
};

template <typename T>
MyVector<T>::MyVector() : data(nullptr), size_(0), capacity_(0) {}

template <typename T>
MyVector<T>::MyVector(size_t initial_capacity) : size_(0), capacity_(initial_capacity) {
    data = new T[initial_capacity];
}

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

template <typename T>
MyVector<T>::MyVector(const MyVector& other) : size_(other.size_), capacity_(other.capacity_) {
    data = new T[capacity_];
    for (size_t i = 0; i < size_; ++i) {
        data[i] = other.data[i];
    }
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(const MyVector& other) {
    if (this == &other) {
        return *this; // 防止自赋值
    }

    // 如果容量不同，则需要重新分配内存
    if (capacity_ != other.capacity_) {
        delete[] data;
        capacity_ = other.capacity_;
        data = new T[capacity_];
    }

    size_ = other.size_;
    for (size_t i = 0; i < size_; ++i) {
        data[i] = other.data[i];
    }
    return *this;
}

template <typename T>
MyVector<T>::MyVector(MyVector&& other) noexcept : data(other.data), size_(other.size_), capacity_(other.capacity_) {
    other.data = nullptr;
    other.size_ = 0;
    other.capacity_ = 0;
}

template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector&& other) noexcept {
    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;
}

template <typename T>
void MyVector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        grow(); // 扩容
    }
    data[size_] = value;
    size_++;
}

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

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

template <typename T>
T& MyVector<T>::operator[](size_t index) {
    return data[index];
}

template <typename T>
const T& MyVector<T>::operator[](size_t index) const {
    return data[index];
}

template <typename T>
void MyVector<T>::pop_back() {
    if (size_ > 0) {
        size_--;
    }
}

template <typename T>
void MyVector<T>::reserve(size_t new_capacity) {
    if (new_capacity > capacity_) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size_; ++i) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity_ = new_capacity;
    }
}

template <typename T>
void MyVector<T>::clear() {
    size_ = 0;
}

template <typename T>
void MyVector<T>::erase(size_t index) {
    if (index >= size_) {
        return; // 或者抛出异常
    }
    for (size_t i = index; i < size_ - 1; ++i) {
        data[i] = data[i + 1];
    }
    size_--;
}

template <typename T>
void MyVector<T>::insert(size_t index, const T& value) {
    if (index > size_) {
        return; // 或者抛出异常
    }

    if (size_ == capacity_) {
        grow();
    }

    for (size_t i = size_; i > index; --i) {
        data[i] = data[i - 1];
    }
    data[index] = value;
    size_++;
}

template <typename T>
void MyVector<T>::grow() {
    // 如果当前容量为0，则初始容量设为1，否则翻倍
    size_t new_capacity = (capacity_ == 0) ? 1 : capacity_ * 2;

    // 分配新的内存
    T* new_data = new T[new_capacity];

    // 将原来的数据复制到新的内存
    for (size_t i = 0; i < size_; ++i) {
        new_data[i] = data[i];
    }

    // 释放原来的内存
    delete[] data;

    // 更新 data 和 capacity_
    data = new_data;
    capacity_ = new_capacity;
}

int main() {
    MyVector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

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

    vec.erase(1);

    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;

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

    MyVector<int> vec2 = vec; //copy constructor
    vec2.push_back(40);

    std::cout << "Size of vec2: " << vec2.size() << std::endl;
    std::cout << "Capacity of vec2: " << vec2.capacity() << std::endl;

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

    return 0;
}

总结

我们实现了一个简化版的 std::vector，重点关注了内存管理。通过这个过程，你应该对以下几点有了更深入的理解：

• 动态数组的内存分配和释放。
• 扩容的原理和实现。
• 拷贝构造函数，拷贝赋值运算符，移动构造函数，移动赋值运算符的重要性。

后续改进

• 异常安全： 完善异常处理，确保在出现异常时，不会导致内存泄漏或者数据损坏。
• 更高效的扩容策略： 可以尝试不同的扩容策略，比如每次增加固定大小的容量，或者使用更复杂的增长模型。
• 使用 std::allocator： 可以使用 std::allocator 来管理内存，提供更灵活的内存分配方式。
• 迭代器： 实现迭代器，可以更方便地遍历 MyVector 中的元素。

希望这次手撸 std::vector 的旅程对你有所帮助！掌握了这些基础知识，以后再遇到更复杂的 C++ 问题，也能更加得心应手。