C++ 编写自己的 `std::vector`：从零实现标准库容器

好的，各位老铁，今天咱们要搞点刺激的，手撸一个 C++ 的 std::vector。别害怕，不是让你重新发明轮子，而是让你彻底理解这个轮子是怎么转的。搞明白之后，以后再用 vector，心里就有底了，bug 来了也不慌。

第一章：开局一张图，内容全靠编…咳咳，是设计！

在开始写代码之前，咱得先想清楚 vector 到底是个啥。它就是一个动态数组，能自动扩容，用起来方便。核心功能无非就这几个：

存储元素: 肯定要有个地方放数据，就像你家里的冰箱。
动态扩容: 容量不够了，就得自动变大，就像你家的冰箱可以无限扩容（如果真能这样就好了）。
随机访问: 像数组一样，可以通过下标快速访问元素。
增删元素: 在末尾添加和删除元素是基本操作。
获取大小和容量: 知道里面有多少东西，冰箱还有多少空间。

用人话说，vector 就是一个可变长的数组，它在内存中是一块连续的空间。

第二章：搭积木，从最简单的开始

咱们先创建一个 MyVector 类，把基本框架搭起来。

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

template <typename T>
class MyVector {
private:
    T* data;       // 指向存储元素的数组
    size_t size;     // 当前元素个数
    size_t capacity; // 当前容量

public:
    // 构造函数
    MyVector();
    MyVector(size_t initialCapacity);

    // 析构函数
    ~MyVector();

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

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

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

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

    // 元素访问
    T& operator[](size_t index);
    const T& operator[](size_t index) const;
    T& at(size_t index);
    const T& at(size_t index) const;
    T* begin();
    const T* begin() const;
    T* end();
    const T* end() const;

    // 容量相关
    size_t getSize() const;
    size_t getCapacity() const;
    bool isEmpty() const;
    void reserve(size_t newCapacity); // 预留空间
    void resize(size_t newSize);      // 改变大小

    // 修改器
    void push_back(const T& value); // 尾部添加元素
    void pop_back();               // 尾部删除元素
    void insert(size_t index, const T& value); // 在指定位置插入元素
    void erase(size_t index);                  // 删除指定位置的元素
    void clear();                             // 清空所有元素

    // 辅助函数
    void printVector();
};

// 构造函数
template <typename T>
MyVector<T>::MyVector() : data(nullptr), size(0), capacity(0) {}

template <typename T>
MyVector<T>::MyVector(size_t initialCapacity) : size(0), capacity(initialCapacity) {
    data = new T[capacity];
}

// 析构函数
template <typename T>
MyVector<T>::~MyVector() {
    delete[] data;
}

// 获取大小
template <typename T>
size_t MyVector<T>::getSize() const {
    return size;
}

// 获取容量
template <typename T>
size_t MyVector<T>::getCapacity() const {
    return capacity;
}

// 是否为空
template <typename T>
bool MyVector<T>::isEmpty() const {
    return size == 0;
}

// 打印vector
template <typename T>
void MyVector<T>::printVector() {
    std::cout << "Vector: ";
    for (size_t i = 0; i < size; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "Size: " << size << ", Capacity: " << capacity << std::endl;
}

这段代码定义了一个 MyVector 类，带有一些基本的成员变量（data, size, capacity）和构造函数、析构函数、以及获取大小和容量的函数。现在，这个 MyVector 就像一个空的房子，啥也没有，但地基已经打好了。

第三章：核心功能：增删改查

接下来，咱们来实现 vector 最核心的功能：增删改查。

push_back()：尾部添加元素

template <typename T>
void MyVector<T>::push_back(const T& value) {
    if (size == capacity) {
        // 容量不够了，需要扩容
        size_t newCapacity = capacity == 0 ? 1 : capacity * 2; // 如果容量为0，则初始化为1，否则翻倍
        reserve(newCapacity);
    }
    data[size] = value;
    ++size;
}

push_back() 的逻辑很简单：

先检查容量够不够，不够就扩容。
把新元素放到数组末尾。
size 加 1。

pop_back()：尾部删除元素

template <typename T>
void MyVector<T>::pop_back() {
    if (size > 0) {
        --size;
        // 注意：这里不需要真正删除元素，只需要减小 size 即可
    }
}

pop_back() 更简单：

检查 size 是否大于 0，否则啥也不干。
size 减 1。

注意，这里并没有真正删除元素，只是逻辑上删除了。因为 size 变小了，所以访问不到原来的元素了。

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>
T& MyVector<T>::at(size_t index) {
    if (index >= size) {
        throw std::out_of_range("Index out of range");
    }
    return data[index];
}

template <typename T>
const T& MyVector<T>::at(size_t index) const {
    if (index >= size) {
        throw std::out_of_range("Index out of range");
    }
    return data[index];
}

下标访问直接返回数组中对应位置的元素。 at 函数会进行边界检查，如果越界会抛出异常，比[]更安全。

insert()：在指定位置插入元素

template <typename T>
void MyVector<T>::insert(size_t index, const T& value) {
    if (index > size) {
        throw std::out_of_range("Index out of range");
    }

    if (size == capacity) {
        size_t newCapacity = capacity == 0 ? 1 : capacity * 2;
        reserve(newCapacity);
    }

    // 将 index 及其后面的元素都向后移动一位
    for (size_t i = size; i > index; --i) {
        data[i] = data[i - 1];
    }

    data[index] = value;
    ++size;
}

insert() 的逻辑稍微复杂一点：

先检查索引是否越界。
如果容量不够，先扩容。
把 index 及之后的元素都向后移动一位。
把新元素放到 index 位置。
size 加 1。

erase()：删除指定位置的元素

template <typename T>
void MyVector<T>::erase(size_t index) {
    if (index >= size) {
        throw std::out_of_range("Index out of range");
    }

    // 将 index 之后的元素都向前移动一位
    for (size_t i = index; i < size - 1; ++i) {
        data[i] = data[i + 1];
    }

    --size;
}

erase() 的逻辑：

先检查索引是否越界。
把 index 之后的元素都向前移动一位。
size 减 1。

clear()：清空所有元素

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

clear() 的逻辑很简单，就是把 size 设置为 0。

第四章：扩容：保证能装

扩容是 vector 的关键特性。当 size 等于 capacity 时，就需要分配更大的内存空间。

template <typename T>
void MyVector<T>::reserve(size_t newCapacity) {
    if (newCapacity <= capacity) {
        return; // 如果新的容量小于等于当前容量，则什么也不做
    }

    T* newData = new T[newCapacity]; // 分配新的内存空间

    // 将原来的数据拷贝到新的内存空间
    if (data != nullptr) {
        std::copy(data, data + size, newData);
        delete[] data; // 释放原来的内存空间
    }

    data = newData;       // 更新 data 指针
    capacity = newCapacity; // 更新 capacity
}

reserve() 的逻辑：

如果 newCapacity 小于等于 capacity，啥也不干。
分配一块大小为 newCapacity 的新内存。
把原来的数据拷贝到新内存。
释放原来的内存。
更新 data 和 capacity。

这个函数是保证 vector 能装下更多东西的关键。

第五章：构造、拷贝、赋值、移动，一个都不能少

C++ 的类，特别是涉及到动态内存分配的类，必须正确处理构造、拷贝、赋值和析构。否则，很容易出现内存泄漏或者悬挂指针。

拷贝构造函数

template <typename T>
MyVector<T>::MyVector(const MyVector& other) : size(other.size), capacity(other.capacity) {
    data = new T[capacity];
    std::copy(other.data, other.data + size, data);
}

拷贝构造函数用于创建一个新的 MyVector，它是现有 MyVector 的副本。

拷贝赋值运算符

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

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

    // 分配新的内存
    size = other.size;
    capacity = other.capacity;
    data = new T[capacity];

    // 拷贝数据
    std::copy(other.data, other.data + size, data);

    return *this;
}

拷贝赋值运算符用于将一个 MyVector 的内容赋值给另一个 MyVector。

移动构造函数

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;
}

移动构造函数用于创建一个新的 MyVector，它“偷”走了现有 MyVector 的资源，而不是进行拷贝。

移动赋值运算符

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

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

    // “偷”走 other 的资源
    data = other.data;
    size = other.size;
    capacity = other.capacity;

    // 将 other 置为空
    other.data = nullptr;
    other.size = 0;
    other.capacity = 0;

    return *this;
}

移动赋值运算符用于将一个 MyVector 的资源移动给另一个 MyVector。

移动构造和移动赋值运算符通过转移资源所有权，避免了不必要的拷贝，提高了效率。

第六章：迭代器：遍历容器的利器

template <typename T>
T* MyVector<T>::begin() {
    return data;
}

template <typename T>
const T* MyVector<T>::begin() const {
    return data;
}

template <typename T>
T* MyVector<T>::end() {
    return data + size;
}

template <typename T>
const T* MyVector<T>::end() const {
    return data + size;
}

begin() 返回指向第一个元素的指针，end() 返回指向最后一个元素之后位置的指针。通过这两个函数，就可以用迭代器遍历 MyVector 了。

第七章：测试：骡子是马拉出来溜溜

光说不练假把式，咱们写个测试程序来验证一下 MyVector 的功能。

int main() {
    MyVector<int> vec;

    // 添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    std::cout << "Size: " << vec.getSize() << ", Capacity: " << vec.getCapacity() << std::endl;
    vec.printVector();

    // 访问元素
    std::cout << "Element at index 1: " << vec[1] << std::endl;

    // 删除元素
    vec.pop_back();
    std::cout << "Size: " << vec.getSize() << ", Capacity: " << vec.getCapacity() << std::endl;
    vec.printVector();

    // 插入元素
    vec.insert(1, 25);
    std::cout << "Size: " << vec.getSize() << ", Capacity: " << vec.getCapacity() << std::endl;
    vec.printVector();

    // 删除元素
    vec.erase(0);
    std::cout << "Size: " << vec.getSize() << ", Capacity: " << vec.getCapacity() << std::endl;
    vec.printVector();

    // 清空 vector
    vec.clear();
    std::cout << "Size: " << vec.getSize() << ", Capacity: " << vec.getCapacity() << std::endl;
    vec.printVector();

    // 使用 reserve 预留空间
    MyVector<int> vec2;
    vec2.reserve(10);
    std::cout << "Size: " << vec2.getSize() << ", Capacity: " << vec2.getCapacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        vec2.push_back(i * 10);
    }

    vec2.printVector();

    // 测试 at 函数
    try {
        std::cout << "Element at index 5: " << vec2.at(5) << std::endl;
        std::cout << "Element at index 15: " << vec2.at(15) << std::endl; // 抛出异常
    } catch (const std::out_of_range& e) {
        std::cerr << "Exception: " << e.what() << std::endl;
    }

    // 使用迭代器
    std::cout << "Vector elements using iterator: ";
    for (int* it = vec2.begin(); it != vec2.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

这个测试程序演示了 MyVector 的基本用法，包括添加、删除、访问、插入、清空元素等。运行这个程序，如果输出结果符合预期，说明 MyVector 的基本功能是正常的。

第八章：总结：手撸的快乐

通过手撸 std::vector，咱们深入了解了动态数组的实现原理，掌握了 C++ 内存管理、拷贝构造、赋值运算符、移动语义等重要概念。

当然，这个 MyVector 只是一个简化版本，和 std::vector 相比，还缺少很多功能，比如：

异常安全保证
更高效的内存管理
更多成员函数（如 assign, emplace_back 等）

但是，通过这个过程，你已经对 std::vector 的内部实现有了更深刻的理解。以后再用 std::vector，就不再是只会调库的菜鸟了，而是能洞悉其原理的大佬！

记住，编程的乐趣在于探索和创造。手撸代码，能让你更深入地理解技术，提升编程能力。下次你想实现一个数据结构或者算法，不妨也尝试手撸一遍，你会发现其中的乐趣。

好了，今天的分享就到这里，希望对大家有所帮助！咱们下期再见！

发表回复 取消回复

发表回复取消回复