C++ vector底层模拟实现与迭代器失效深度剖析(最新推荐)

C++ vector底层模拟实现与迭代器失效深度剖析(最新推荐)需要先看清适用场景和关键步骤，避免只记结论却忽略实际限制。

一、vector的定义

1. 构造函数与析构函数

在 vector 的模拟实现中，构造函数、析构函数、拷贝构造函数和赋值运算符重载共同构成了对象的生命周期管理核心。下面我们将这些内容整合到一个逻辑连贯的章节中，并提供统一的代码风格。

1.1 成员变量声明

首先定义 vector 类的三个核心指针成员变量，它们分别表示动态数组的起始位置、最后一个元素的下一个位置以及存储空间末尾的下一个位置：

template<class T>class vector{public:    // 迭代器类型定义    typedef T* iterator;    typedef const T* const_iterator;private:    // 成员变量    T* _start = nullptr;          // 指向数组起始位置    T* _finish = nullptr;         // 指向最后一个元素的下一个位置    T* _end_of_storage = nullptr; // 指向存储空间末尾的下一个位置    // 辅助函数声明    size_t size() const { return _finish - _start; }    size_t capacity() const { return _end_of_storage - _start; }    void reserve(size_t n);    void push_back(const T& x);public:    // 构造函数、析构函数等将在下面实现};

1.2 构造函数

vector 提供了多种构造函数来满足不同的初始化需求：

// 1. 无参构造函数（默认构造函数）vector()    : _start(nullptr)    , _finish(nullptr)    , _end_of_storage(nullptr){    // 预留初始空间以提高后续插入效率    reserve(4);}// 2. 带参构造函数：构造包含 n 个 val 元素的 vectorvector(size_t n, const T& val = T())    : _start(nullptr)    , _finish(nullptr)    , _end_of_storage(nullptr){    reserve(n);    for (size_t i = 0; i < n; i++)    {        push_back(val);    }}// 3. 拷贝构造函数（深拷贝）vector(const vector<T>& v)    : _start(nullptr)    , _finish(nullptr)    , _end_of_storage(nullptr){    // 先分配与被拷贝对象相同容量的空间    reserve(v.capacity());    // 深拷贝元素    T* dest = _start;    const T* src = v._start;    while (src != v._finish)    {        *dest = *src;  // 调用 T 的赋值运算符        ++dest;        ++src;    }    _finish = _start + v.size();}// 4. 迭代器范围构造函数（模板）template<class InputIterator>vector(InputIterator first, InputIterator last)    : _start(nullptr)    , _finish(nullptr)    , _end_of_storage(nullptr){    // 计算元素数量    size_t count = 0;    InputIterator it = first;    while (it != last)    {        ++count;        ++it;    }    // 分配空间    reserve(count);    // 拷贝元素    it = first;    while (it != last)    {        push_back(*it);        ++it;    }}

构造函数详解：

1. 无参构造函数：初始化成员变量为 nullptr，并预留 4 个元素的初始空间以提高效率。
2. 带参构造函数：构造包含 n 个 val 元素的 vector，使用 reserve 预分配空间，然后通过 push_back 添加元素。
3. 拷贝构造函数：实现深拷贝，先分配与被拷贝对象相同容量的空间，然后逐个拷贝元素。
4. 迭代器范围构造函数：支持从任意迭代器范围构造 vector，这是 STL vector 的标准接口之一。

1.3 析构函数

析构函数负责释放动态分配的内存，并将所有指针置为 nullptr 以避免悬空指针：

// 析构函数~vector(){    if (_start)    {        delete[] _start;        _start = _finish = _end_of_storage = nullptr;    }}

1.4 赋值运算符重载

赋值运算符重载（operator=）是拷贝构造函数的重要补充，它允许已存在的 vector 对象被另一个 vector 对象赋值。现代 C++ 中常用拷贝交换（copy-and-swap）惯用法实现：

// 赋值运算符重载（现代 C++ 写法）vector<T>& operator=(vector<T> v)  // 注意：这里按值传递，会调用拷贝构造函数{    // 交换当前对象和临时对象 v 的资源    swap(v);    return *this;}// 交换两个 vector 的辅助函数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. 参数按值传递：参数 v 是按值传递的，这会调用拷贝构造函数创建一个临时副本，实现了深拷贝。
2. 交换资源：通过 swap 函数交换当前对象和临时副本的资源，当前对象获得新数据，临时副本获得旧数据。
3. 自动清理：函数结束时，临时副本（包含旧数据）被销毁，自动调用析构函数释放内存。
4. 异常安全：这种实现是强异常安全的，即使在拷贝过程中发生异常，当前对象的状态也不会被破坏。

传统写法（对比参考）：

// 赋值运算符重载（传统写法）vector<T>& operator=(const vector<T>& v){    if (this != &v)  // 防止自赋值    {        // 释放原有资源        delete[] _start;        // 分配新空间        _start = new T[v.capacity()];        // 拷贝元素        T* dest = _start;        const T* src = v._start;        while (src != v._finish)        {            *dest = *src;            ++dest;            ++src;        }        _finish = _start + v.size();        _end_of_storage = _start + v.capacity();    }    return *this;}

1.5 注意事项

1. 深拷贝与浅拷贝：拷贝构造函数和赋值运算符必须实现深拷贝，避免多个对象共享同一块内存导致双重释放问题。
2. 自赋值处理：在传统写法中需要检查 this != &v 防止自赋值，而现代写法通过按值传递自动处理了自赋值。
3. 异常安全：现代写法（拷贝交换）提供了强异常安全保证，是推荐的做法。
4. 资源管理：构造函数中需要正确处理内存分配和元素初始化，析构函数中需要确保资源被正确释放。
5. 默认参数要求：带参构造函数中的默认参数 val = T() 要求类型 T 有默认构造函数。
6. 模板构造函数：迭代器范围构造函数是模板函数，可以接受任意类型的输入迭代器，提供了极大的灵活性。

通过将构造函数、析构函数、拷贝构造函数和赋值运算符重载整合在一起，我们可以更清晰地理解 vector 对象的完整生命周期管理机制。这些特殊成员函数共同确保了 vector 在复制、赋值和销毁时的正确行为。

二、vector迭代器失效问题

迭代器失效是使用vector时最容易遇到的问题之一，特别是在进行插入和删除操作时。理解迭代器失效的原因和避免方法对于编写安全的C++代码至关重要。

1. 什么是迭代器失效？

迭代器失效指的是：当容器（如vector）的内部结构发生变化时，之前获取的迭代器可能不再指向有效的元素，或者指向了错误的元素。继续使用这些失效的迭代器会导致未定义行为（程序崩溃、数据错误等）。

2. vector中导致迭代器失效的操作

2.1 插入操作（insert、push_back）

当vector需要扩容时，所有迭代器、指针和引用都会失效：

vector<int> v = {1, 2, 3};auto it = v.begin() + 1;  // 指向元素2v.push_back(4);  // 如果导致扩容，it失效！// 此时使用 *it 是未定义行为

即使不扩容，在pos位置插入元素也会使从pos开始的所有迭代器失效。

2.2 删除操作（erase、pop_back）

删除元素会使被删除元素及其之后所有元素的迭代器失效：

vector<int> v = {1, 2, 3, 4};auto it = v.begin() + 2;  // 指向元素3v.erase(v.begin() + 1);  // 删除元素2// it现在指向什么？可能是元素4，也可能是无效位置

2.3 扩容操作（reserve、resize导致扩容）

任何导致vector重新分配内存的操作都会使所有迭代器失效：

vector<int> v = {1, 2, 3};auto it = v.begin();v.reserve(100);  // 重新分配内存，it失效！

3. 如何避免迭代器失效？

3.1 更新迭代器

许多STL操作会返回新的有效迭代器：

vector<int> v = {1, 2, 3, 4, 5};// 删除所有偶数元素（正确做法）for (auto it = v.begin(); it != v.end(); ) {    if (*it % 2 == 0) {        it = v.erase(it);  // erase返回被删除元素之后的位置    } else {        ++it;    }}

3.2 使用索引而非迭代器

如果需要保持位置信息，可以使用索引：

vector<int> v = {1, 2, 3, 4};size_t pos = 2;  // 记录索引而不是迭代器v.insert(v.begin() + 1, 99);  // 插入元素// pos仍然有效，指向元素3（现在在索引3的位置）

3.3 在模拟实现中的处理

回顾我们模拟实现的insert函数：

void insert(iterator pos, const T& x) {    // 扩容    if (_finish == _end_of_storage) {        // 关键：先保存相对位置        size_t len = pos - _start;    // 保存偏移量        reserve(capacity() == 0 ? 4 : capacity() * 2);        pos = _start + len;           // 重新计算pos    }    // ... 后续插入逻辑}

这里通过保存和恢复相对偏移量，避免了因扩容导致的pos迭代器失效。

4. 实战示例：删除特定元素

删除vector中所有等于特定值的元素：

// 方法1：使用erase-remove惯用法（推荐）vector<int> v = {1, 2, 3, 2, 4, 2, 5};v.erase(remove(v.begin(), v.end(), 2), v.end());// 方法2：手动循环（需要正确处理迭代器）vector<int> v2 = {1, 2, 3, 2, 4, 2, 5};for (auto it = v2.begin(); it != v2.end(); ) {    if (*it == 2) {        it = v2.erase(it);  // 重要：更新迭代器    } else {        ++it;    }}

5. 总结

1. 插入操作：可能导致扩容，使所有迭代器失效；不扩容时，插入点及之后的迭代器失效
2. 删除操作：被删除元素及之后元素的迭代器失效
3. 扩容操作：所有迭代器、指针、引用都失效
4. 最佳实践：
   1. 使用erase的返回值更新迭代器
   2. 考虑使用索引而不是迭代器来跟踪位置
   3. 使用erase-remove惯用法进行批量删除
   4. 在模拟实现中，扩容前保存偏移量，扩容后重新计算

理解迭代器失效机制是编写健壮C++代码的基础，特别是在使用vector这类动态容器时。

三、vector空间的增长问题

size 获取数据个数

capacity 获取容量大小

empty 判断是否为空

resize 改变vector的size

reserve 改变vector的capacity

注意：reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。一般情况下reserve不会缩容。

size    获取数据个数capacity  获取容量大小empty     判断是否为空resize    改变vector的sizereserve   改变vector的capacityint main(){    vector<int> v;    v.size();    v.capacity();    v.resize();    v.reserve();    v.empty();    return 0;}

四、vector的增删查改

push_back 尾插

pop_back 尾删

find 查找（这个是算法问题，不属于vector的接口）

insert 在pos位置之前插入

erase 从pos位置开始删除

swap 交换两个vector的数据空间

operator[] 像数组一样可以访问

五、vector的模拟实现

我们在这里就不用库里面的接口了，比较简单，我们这里直接进行vector的模拟实现，既然是模拟实现，那么这里我们需要自己命名一个命名空间，在这个命名空间里面进行实现。

1.vector的底层：一段连续的动态数组

template<class T>class vector{public:    typedef T* iterator;private:    T* _start = nullptr;    T* _finish = nullptr;    T* _end_of_storage = nullptr;};

这里的vector虽然是顺序表，但是我们不写size,capacity,和地址,我们在这里统一以指针的形式写

在模拟实现这些接口之前，先把vector常用的接口直接写出来

// 数据个数size_t size() const{    return _finish - _start;}// 数据的容量size_t capacity() const{    return _end_of_storage - _start;}// 空间是否为空bool empty(){    return _start == _finish;}// 访问数据T& operator[](size_t i){    assert(i < size());    return _start[i];}

2.vector的扩容

❌错误的写法

void reserve(size_t n){    // 扩容    if (n > capacity())    {        T* tmp = new T[n];        memcpy(tmp, _start, sizeof(T) * size());        delete[] _start;        _start = tmp;        _finish = _start + size();        _end_of_storage = _start + n;    }}

这里最致命的操作是：这里当我们把新开辟的地址赋值给旧的地址之后，我们再赋值finish的时候，这里的size()已经发生改变了，本来的size()里面应该是_finish-_start；但是当我们把tmp赋值给_start之后，这里的_start就发生了改变，所以这里会报错。

✔正确做法

void reserve(size_t n){    // 扩容    if (n > capacity())    {        size_t old_size = size();  // 先把旧的size()先保存一下        T* tmp = new T[n];        memcpy(tmp, _start, sizeof(T) * size());        delete[] _start;        _start = tmp;        _finish = _start + old_size;  // 这里用旧的        _end_of_storage = _start + n;    }}

3.vector的尾插

void push_back(const T& x){    // 插入数据之前，先判断空间是否足够，不够的话进行扩容，这里进行判断一下    if (_start == _end_of_storage)    {        // 这里我们用三目操作符进行判断扩容，避免capacity==0        reserve(capacity() == 0 ? 4 : 2 * capacity());    }    *_finish = x;    _finish++;}

4.vector的尾删

void pop_back(){    assert(!empty());    _finish--;}

5.vector的insert插入

void insert(iterator pos, const T& x){    // 扩容    if (_finish == _end_of_storage)    {        // 这里我们先算出在pos位置在扩容前的相对位置，避免pos指针变成野指针        size_t len = pos - _start;        reserve(capacity() == 0 ? 4 : capacity() * 2);        pos = _start + len;    }    iterator end = _finish - 1;    while (end >= pos)    {        *(end + 1) = *end;        --end;    }    *pos = x;    ++_finish;}

6.vector的erase的删除

void erase(iterator pos){    assert(pos >= _start);    assert(pos < _finish);    iterator it = pos + 1;    while (it != end())    {        *(it - 1) = *it;        ++it;    }    --_finish;}