揭开 C++ vector 底层面纱：从三指针模型到手写完整实现

C++ 标准库中的 vector 是一个动态数组容器，支持高效的元素访问、插入和删除。其底层实现通常采用“三指针模型”，这是一种简洁且高效的内存管理方式。在本教程中，我将逐步揭开 vector 的内部机制，从解释三指针模型开始，到手写一个完整的简化版 vector 实现。整个过程结构清晰，帮助您深入理解。

1. 三指针模型详解

vector 的核心是三个指针，它们共同管理动态数组的内存：

• start_：指向数组的起始位置（第一个元素）。
• finish_：指向数组的最后一个元素的下一个位置（即有效元素的结束点）。当前元素数量（size）可以通过 $size = \text{finish_} - \text{start_}$ 计算。
• end_of_storage_：指向分配内存的结束位置（即容量的结束点）。当前容量（capacity）可以通过 $capacity = \text{end_of_storage_} - \text{start_}$ 计算。

这三个指针确保了高效的内存管理：

• 当插入元素时（如 push_back），如果空间不足（$size \geq capacity$），需要重新分配更大的内存块（通常加倍容量），并复制原有元素。
• 这种模型避免了每次插入都重新分配的开销，时间复杂度平均为 $O(1)$。

2. 手写实现步骤

现在，我们手写一个简化版 Vector 类，模仿标准库的 vector。我们将逐步实现关键功能：

• 构造函数：初始化指针和内存。
• 析构函数：释放内存。
• push_back：添加元素，处理内存扩容。
• size 和 capacity：返回当前大小和容量。
• operator[]：支持下标访问。
• 内存管理：实现重新分配逻辑。

我们将使用 C++ 语言编写代码，确保代码简洁易读。实现基于三指针模型，并处理边界情况。

步骤 1: 定义 Vector 类和成员

首先，定义类结构，包括三个私有指针和一些辅助函数。

#include <cstddef>  // 用于 size_t
#include <algorithm> // 用于 std::copy

template <typename T>
class Vector {
private:
    T* start_;          // 指向数组起始位置
    T* finish_;         // 指向有效元素结束位置
    T* end_of_storage_; // 指向内存结束位置

public:
    // 构造函数
    Vector() : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) {}
    
    // 析构函数
    ~Vector() {
        delete[] start_;  // 释放整个内存块
    }

    // 其他函数将在后续实现
};

步骤 2: 实现基本访问函数

添加 size、capacity 和下标访问操作符。这些函数直接基于指针计算。

size_t size() const {
    return finish_ - start_;  // 元素数量
}

size_t capacity() const {
    return end_of_storage_ - start_;  // 当前容量
}

T& operator[](size_t index) {
    return start_[index];  // 下标访问，不检查边界（简化版）
}

步骤 3: 实现 push_back 和内存管理

push_back 是核心函数，需要处理内存扩容。当空间不足时，重新分配内存（容量加倍），并复制原有元素。

void push_back(const T& value) {
    if (finish_ == end_of_storage_) {  // 空间不足，需要扩容
        size_t new_capacity = (capacity() == 0) ? 1 : capacity() * 2;  // 新容量（初始为1或加倍）
        T* new_start = new T[new_capacity];  // 分配新内存
        
        // 复制原有元素到新内存
        for (size_t i = 0; i < size(); ++i) {
            new_start[i] = start_[i];
        }
        
        // 释放旧内存，更新指针
        delete[] start_;
        start_ = new_start;
        finish_ = start_ + size();  // finish_ 指向最后一个元素的下一个位置
        end_of_storage_ = start_ + new_capacity;
    }
    
    // 添加新元素
    *finish_ = value;
    ++finish_;  // 移动 finish_ 指针
}

步骤 4: 添加其他辅助函数（可选）

为了完整性，我们可以实现 reserve 和 clear 函数。

void reserve(size_t new_capacity) {
    if (new_capacity <= capacity()) return;  // 不需要扩容
    
    T* new_start = new T[new_capacity];
    for (size_t i = 0; i < size(); ++i) {
        new_start[i] = start_[i];
    }
    
    delete[] start_;
    start_ = new_start;
    finish_ = start_ + size();
    end_of_storage_ = start_ + new_capacity;
}

void clear() {
    finish_ = start_;  // 清空元素，但不释放内存
}

3. 完整 Vector 实现代码

以下是一个完整的简化版 Vector 类实现，基于上述步骤。代码包括注释以便理解。

#include <cstddef>
#include <algorithm>

template <typename T>
class Vector {
private:
    T* start_;
    T* finish_;
    T* end_of_storage_;

public:
    // 默认构造函数
    Vector() : start_(nullptr), finish_(nullptr), end_of_storage_(nullptr) {}
    
    // 带初始容量的构造函数
    explicit Vector(size_t capacity) {
        start_ = new T[capacity];
        finish_ = start_;
        end_of_storage_ = start_ + capacity;
    }
    
    // 析构函数
    ~Vector() {
        delete[] start_;
    }
    
    // 返回元素数量
    size_t size() const {
        return finish_ - start_;
    }
    
    // 返回当前容量
    size_t capacity() const {
        return end_of_storage_ - start_;
    }
    
    // 下标访问
    T& operator[](size_t index) {
        return start_[index];
    }
    
    // 添加元素
    void push_back(const T& value) {
        if (finish_ == end_of_storage_) {
            size_t new_capacity = (capacity() == 0) ? 1 : capacity() * 2;
            T* new_start = new T[new_capacity];
            for (size_t i = 0; i < size(); ++i) {
                new_start[i] = start_[i];
            }
            delete[] start_;
            start_ = new_start;
            finish_ = start_ + size();
            end_of_storage_ = start_ + new_capacity;
        }
        *finish_ = value;
        ++finish_;
    }
    
    // 预留容量
    void reserve(size_t new_capacity) {
        if (new_capacity <= capacity()) return;
        T* new_start = new T[new_capacity];
        for (size_t i = 0; i < size(); ++i) {
            new_start[i] = start_[i];
        }
        delete[] start_;
        start_ = new_start;
        finish_ = start_ + size();
        end_of_storage_ = start_ + new_capacity;
    }
    
    // 清空元素
    void clear() {
        finish_ = start_;
    }
};

4. 使用示例和注意事项

您可以使用这个 Vector 类如下：

#include <iostream>

int main() {
    Vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    std::cout << "First element: " << vec[0] << std::endl;
    return 0;
}

注意事项：

• 这个实现是简化版，省略了标准库中的一些高级特性（如迭代器、异常安全、移动语义等）。
• 在 push_back 中，内存扩容策略是加倍容量，这确保了平均 $O(1)$ 的插入时间。
• 实际使用中，应添加边界检查（例如在 operator[] 中）和拷贝控制（如拷贝构造函数、赋值操作符），以避免内存问题。

总结

通过三指针模型（start_, finish_, end_of_storage_），我们揭示了 vector 底层的高效内存管理机制。手写实现帮助您理解动态数组的核心逻辑：内存分配、扩容和元素操作。这个简化版 Vector 可作为学习基础，您可以根据需要扩展功能。如果您有更多问题，欢迎继续讨论！