C++ STL Vector 模拟实现与核心原理解析

2.2 核心三指针模型

这是 vector 实现中最精妙的设计之一：

// 内存布局示意图
_start ---------->|0|1|2|3|...||||---有效数据区---|---未用空间---|
_finish -----------^^
_end_of_storage -------------------^

// 计算方法
size() = _finish - _start   // 有效元素个数
capacity() = _end_of_storage - _start // 总容量

设计优点：

• 计算 size 和 capacity 只需指针相减，O(1) 时间复杂度
• 清晰地划分了已用空间和未用空间的边界
• 方便判断是否需要扩容（_finish == _end_of_storage）

🔧 三、构造函数实现详解

3.1 默认构造函数（现代 C++ 风格）

vector() = default; // C++11 强制生成默认构造

与传统写法的对比：

// 传统写法
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

// 现代写法（推荐）
vector() = default; // 结合成员变量初始化

3.2 拷贝构造函数（深拷贝实现）

vector(const vector<T>& v) {
    reserve(v.size()); // 第一步：预分配足够空间
    for (auto& e : v) { // 第二步：深拷贝每个元素
        push_back(e);
    }
}

3.3 迭代器范围构造函数（泛型设计）

template <class InputIterator>
vector(InputIterator first, InputIterator last) {
    while (first != last) { // 关键：使用!=而不是<
        push_back(*first); // 解引用获取元素值
        ++first;
    }
}

设计亮点：

• 使用 != 而不是 <：list 等容器的迭代器不支持 < 操作
• 模板参数 InputIterator：可以接受 vector、list、set 等任何容器的迭代器

3.4 数量 + 值构造函数

vector(size_t n, const T& val = T()) {
    reserve(n); // 预分配空间
    for (size_t i = 0; i < n; i++) {
        push_back(val); // 插入 n 个 val
    }
}

注意：这里使用 size_t 而不是 int，避免与迭代器构造函数产生歧义。

💾 四、内存管理：深拷贝的艺术

4.1 错误的浅拷贝示例

// 错误实现：使用 memcpy
void reserve(size_t n) {
    if (n > capacity()) {
        size_t old_size = size();
        T* tmp = new T[n];
        memcpy(tmp, _start, old_size * sizeof(T)); // 问题所在！
        delete[] _start;
        _start = tmp;
        // ...
    }
}

问题分析： 当 T 是 string、vector 等包含动态内存的类时：

1. memcpy 只复制了 string 对象的指针，没有复制字符串内容
2. 两个 string 对象指向同一块内存
3. 析构时会双重释放，导致程序崩溃

4.2 正确的深拷贝实现

void reserve(size_t n) {
    if (n > capacity()) {
        size_t old_size = size();
        T* tmp = new T[n]; // 分配新空间

        // 关键：循环深拷贝
        for (size_t i = 0; i < old_size; i++) {
            tmp[i] = _start[i]; // 调用 T::operator=，进行深拷贝
        }

        delete[] _start; // 释放旧空间（调用每个元素的析构函数）

        // 更新指针
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = tmp + n;
    }
}

工作原理：

• tmp[i] = _start[i] 实际调用 T::operator=(const T&)
• 对于 int/double 等内置类型：直接值拷贝
• 对于 string 等自定义类型：调用其拷贝赋值运算符，进行深拷贝

🎯 五、迭代器失效：C++ 程序员的噩梦

5.1 insert 操作中的迭代器失效

iterator insert(iterator pos, const T& x) {
    // 1. 参数检查
    assert(pos >= _start && pos <= _finish);

    // 2. 处理可能的扩容（迭代器失效场景）
    if (_finish == _end_of_storage) {
        // 关键：保存相对偏移量
        size_t len = pos - _start; // 计算 pos 相对于_start 的位置
        // 扩容操作（会改变_start 的指向）
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        // 重新计算 pos 在新空间的位置
        pos = _start + len; // 修正迭代器
    }

    // 3. 移动元素
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end; // 向后移动
        --end;
    }

    // 4. 插入元素
    *pos = x;
    ++_finish;
    return pos; // 返回新的有效迭代器
}

5.2 erase 操作的迭代器安全写法

// 错误写法：迭代器失效后继续使用
for (auto it = v.begin(); it != v.end(); ++it) {
    if (condition(*it)) {
        v.erase(it); // it 失效后，下一轮++it 是未定义行为！
    }
}

// 正确写法：接收 erase 的返回值
auto it = v.begin();
while (it != v.end()) {
    if (condition(*it)) {
        it = v.erase(it); // erase 返回下一个有效迭代器
    } else {
        ++it; // 只有不删除时才手动递增
    }
}

5.3 迭代器失效总结表

🚀 六、现代 C++ 技巧：拷贝交换惯用法

6.1 传统的拷贝赋值实现

// 传统写法：需要检查自赋值
vector<T>& operator=(const vector<T>& v) {
    if (this != &v) { // 1. 检查自赋值
        delete[] _start; // 2. 释放旧空间
        // 3. 分配新空间并深拷贝
        _start = new T[v.capacity()];
        // ... 拷贝逻辑
        // 4. 更新指针
        _finish = _start + v.size();
        _end_of_storage = _start + v.capacity();
    }
    return *this;
}

缺点：

• 代码冗余（与拷贝构造函数重复）
• 需要检查自赋值
• 异常不安全

6.2 现代写法：拷贝交换惯用法

// 现代写法：优雅且安全
vector<T>& operator=(vector<T> v) { // 关键：传值，调用拷贝构造
    swap(v); // 交换资源
    return *this; // v 是局部变量，离开作用域自动析构
}

void swap(vector<T>& v) {
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

优点分析：

1. 异常安全：拷贝发生在参数传递时，如果 new 失败，原对象不受影响
2. 自赋值安全：传值创建了临时对象，自动处理自赋值情况
3. 代码复用：复用了拷贝构造函数和析构函数的逻辑
4. 自动清理：临时对象 v 在函数结束时自动析构，释放旧资源

🔄 七、扩容策略与性能优化

7.1 扩容策略实现

void push_back(const T& x) {
    // 检查是否需要扩容
    if (_finish == _end_of_storage) {
        // 成倍扩容策略
        size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(new_capacity);
    }
    // 插入元素
    *_finish = x;
    ++_finish;
}

7.2 扩容策略对比

STL 选择×2 的原因：

• 均摊时间复杂度为 O(1)
• 实现简单高效
• 在时间效率和空间效率间取得平衡

7.3 预分配优化

// 使用前预分配，避免多次扩容
vector<int> v;
v.reserve(1000); // 一次性分配足够空间
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // 避免多次扩容拷贝
}

📝 八、完整代码实现要点总结

8.1 必须实现的函数

1. 基本构造析构：默认构造、拷贝构造、析构
2. 迭代器支持：begin、end 及其 const 版本
3. 容量操作：size、capacity、reserve、resize
4. 元素访问：operator[]、at（可选）
5. 修改操作：push_back、pop_back、insert、erase
6. 赋值操作：operator=、swap

8.2 易错点提醒

1. 深拷贝问题：绝对不能使用 memcpy
2. 迭代器失效：insert/erase 后迭代器失效
3. 自赋值处理：operator= 要处理 a = a 的情况
4. 异常安全：new 失败时要保证资源不泄漏
5. 类型兼容：模板代码要兼容各种类型 T

8.3 扩展功能建议

// 1. 移动语义支持（C++11）
vector(vector&& v) noexcept;
vector& operator=(vector&& v) noexcept;
void push_back(T&& x);

// 2. 列表初始化（C++11）
vector(std::initializer_list<T> il);

// 3. 原位构造（C++11）
template <class... Args>
void emplace_back(Args&&... args);

// 4. 数据访问（C++11）
T* data() noexcept;
const T* data() const noexcept;

🎓 九、面试常见问题

Q1：vector 的底层实现原理是什么？

答：vector 使用动态数组实现，通过三个指针（start、finish、end_of_storage）管理内存，支持随机访问和动态扩容。

Q2：vector 的扩容机制是怎样的？

答：当 size == capacity 时，vector 会重新分配一块更大的内存（通常是原来的 2 倍），将旧元素拷贝到新空间，然后释放旧空间。

Q3：什么是迭代器失效？vector 哪些操作会导致失效？

答：迭代器失效指迭代器指向的元素位置变得无效。vector 的 insert、erase、push_back（扩容时）、reserve 等操作都可能导致迭代器失效。

Q4：vector 的深拷贝和浅拷贝有什么区别？

答：浅拷贝只复制指针，深拷贝复制指针指向的内容。vector 必须实现深拷贝，否则多个 vector 对象会共享同一块内存，导致双重释放等问题。

Q5：vector 的 insert 和 erase 操作时间复杂度是多少？

答：在尾部操作是 O(1)，在中间或头部操作是 O(n)，因为需要移动后续元素。

📊 十、性能测试与对比

🔚 十一、结语

通过手写 vector 的实现，我们不仅学会了如何实现一个动态数组容器，更重要的是：

1. 深入理解了 C++ 的内存管理机制
2. 掌握了模板编程和泛型设计思想
3. 认识了异常安全和资源管理的重要性
4. 理解了 STL 容器的设计哲学

vector 的实现是 C++ 学习的重要里程碑，它融合了 C++ 的多个核心特性：模板、异常、RAII、迭代器等。希望这篇文章能帮助你深入理解 vector，并在实际编程中更加得心应手地使用它。