当前位置：首页 > news >正文

【C++】vector(下)：vector类的模拟实现（含迭代器失效问题）

news 来源：原创 2025/8/25 5:57:12

文章目录

前言
一、vector类的常用接口的模拟实现
- 1.头文件（my vector.h）整体框架
- 2.模拟实现vector类对象的常见构造
- 3.模拟实现vector iterator
- 4.模拟实现vector类对象的容量操作
- 5.模拟实现vector类对象的访问
- 6.模拟实现vector类对象的修改操作
二、vector 迭代器失效问题

前言

vector类的常用接口的模拟实现以及 vector 迭代器失效问题。配套博客: 【C++】vector(上)：vector的常用接口介绍

一、vector类的常用接口的模拟实现

1.头文件（my vector.h）整体框架

#include <algorithm>
#include <assert.h>
namespace zh
{template<class T>class vector{public:// Vector的迭代器可以直接用指针封装typedef T* iterator;typedef const T* const_iterator;// construct and destroy //vector();vector(int n, const T& value = T());template<class InputIterator>vector(InputIterator first, InputIterator last);vector(const vector<T>& v);vector<T>& operator= (vector<T> v); // 赋值运算符重载~vector(); // 析构函数// iterator //iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;// capacity //size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& value = T());// access //T& operator[](size_t pos);const T& operator[](size_t pos)const;// modify //void push_back(const T& x);void pop_back();iterator insert(iterator pos, const T& x);iterator erase(iterator pos);void swap(vector<T>& v);private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部};
}

2.模拟实现vector类对象的常见构造

template<class T>
class vector
{
public:vector() // 默认构造函数{}vector(int n, const T& value = T()) // 构造并初始化n个val{_start = new T[n];_finish = _end_storage = _start + n;while (n--){_start[n] = value;}}template<class InputIterator>vector(InputIterator first, InputIterator last) // 使用迭代器进行初始化构造{auto it = first;while (it != last){push_back(*it++);}}vector(const vector<T>& v) // 拷贝构造{if (v._start != nullptr){_start = new T[v.capacity()];_finish = _start + v.size();_end_storage = _start + v.capacity();auto it1 = begin();auto it2 = v.begin();while (it2 != v.end()){*it1++ = *it2++;}}}vector<T>& operator= (vector<T> v) // 赋值运算符重载{swap(v);return *this;}~vector() // 析构函数{if (_start != nullptr){delete[] _start;_start = _finish = _end_storage = nullptr;}}
private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部
};

3.模拟实现vector iterator

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}
private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部
};

4.模拟实现vector类对象的容量操作

template<class T>
class vector
{
public:size_t size() const{return _finish - _start;}size_t capacity() const{return _end_storage - _start;}void reserve(size_t n){if (n > capacity()){iterator tmp = new T[n];auto it = _start;int i = 0;while (it != _finish){tmp[i++] = *it;it++;}delete[] _start;_start = tmp;_finish = tmp + i;_end_storage = tmp + n;}}void resize(size_t n, const T& value = T()){if (n <= size()){_finish -= size() - n;}else{if (n > capacity()){size_t newcap = 2 * capacity();if (n > newcap)newcap = n;reserve(newcap);}size_t i = size();_finish += n - size();while (i < size()){_start[i++] = value;}}}
private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部
};

5.模拟实现vector类对象的访问

template<class T>
class vector
{
public:T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部
};

6.模拟实现vector类对象的修改操作

template<class T>
class vector
{
public:void push_back(const T& x) // 在末尾插入一个元素{if (size() == capacity()){size_t n = capacity() == 0 ? 4 : 2 * capacity();reserve(n);}_start[size()] = x;_finish++;}void pop_back() // 删除末尾元素{assert(size() > 0);_finish--;}iterator insert(iterator pos, const T& x) // 在迭代器 pos 位置插入元素 x{assert(pos >= _start && pos <= _finish);if (size() == capacity()){size_t newcap = capacity() == 0 ? 4 : 2 * capacity();size_t n = pos - _start;reserve(newcap);pos = _start + n;}auto it = _finish;while (pos < it){*it = *(it - 1);it--;}*pos = x;_finish++;return pos;}iterator erase(iterator pos) // 删除迭代器 pos 指向的元素{assert(pos >= _start && pos < _finish);auto it = pos;while (it < _finish - 1){*it = *(it + 1);it++;}_finish--;return pos;}void swap(vector<T>& v) // 交换两个vector对象的内容{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_storage, v._end_storage);}
private:iterator _start = nullptr; // 指向有效数据的开始iterator _finish = nullptr; // 指向有效数据的尾部iterator _end_storage = nullptr; // 指向存储容量的尾部
};

二、vector 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就可以使用原生态指针T* 。因此迭代器失效，实际是指 vector 进行某些修改操作后，原有的迭代器（或指针、引用）指向的内存地址可能变得无效，继续使用这些迭代器会导致未定义行为（如程序崩溃、数据错误）。比如：迭代器底层对应指针所指向的空间被销毁了（扩容等行为导致底层空间改变），而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

会引起其底层空间改变的操作（插入、赋值和修改容量），都有可能会导致迭代器失效，比如：resize、push_back、insert、assign 和 reserve等。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v{ 1,2,3,4,5,6 }; // 由调试结果（下图）可知:size == capacity = 6auto it = v.begin();// 头插一个元素，因为size == capacity，所以该操作会引起扩容v.insert(v.begin(), 0);// resize的作用是增加有效元素个数,操作期间可能会引起扩容// v.resize(50, 8);// reserve的作用是扩充容量但不改变有效元素个数，操作期间可能会引起扩容// v.reserve(50);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.push_back(8);// 给vector重新赋值，可能会引起扩容// v.assign(50, 8);while (it != v.end()){cout << *it << " ";++it;} cout << endl;return 0;
}

在这里插入图片描述

出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。
如下：

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v{ 1,2,3,4,5,6 };auto it = v.begin();// insert的返回值：若插入单个元素，返回值指向新插入的该元素;//                若插入多个元素或区间，则指向第一个新插入的元素。it = v.insert(v.begin(), 0);// 即使插入导致内存重新分配，返回的迭代器仍有效（直接指向新内存位置）。while (it != v.end()){cout << *it << " ";++it;} cout << endl;return 0;
}

在这里插入图片描述

指定位置元素的删除操作（erase）

示例一（erase删除元素后，被删除位置之后的迭代器失效（元素前移））：

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v = { 10, 20, 30, 40 };auto it = v.begin(); // 指向10auto it1 = v.begin() + 1;  // 指向20auto it2 = v.begin() + 2;  // 指向30v.erase(it1);  // 删除20，vector变为{10,30,40}cout << *it2; // 删除元素后，被删除位置之后的迭代器失效（元素前移）return 0;
}

在这里插入图片描述

示例二（删除元素后，被删除位置的迭代器也失效（元素前移））：

int main()
{vector<int> v = { 10, 20, 30, 40 };auto it = v.begin(); // 指向10auto it1 = v.begin() + 1;  // 指向20auto it2 = v.begin() + 2;  // 指向30v.erase(it1);  // 删除20，vector变为{10,30,40}cout << *it1; // 删除元素后，被删除位置的迭代器也失效（元素前移）return 0;
}

在这里插入图片描述
解决方式：在以上操作完成之后，如果想要继续通过迭代器it1操作vector中的元素，只需给it1重新赋值即可，如下：

int main()
{vector<int> v = { 10, 20, 30, 40 };auto it = v.begin(); // 指向10auto it1 = v.begin() + 1;  // 指向20auto it2 = v.begin() + 2;  // 指向30// erase的返回值是指向被删除元素之后第一个有效元素的迭代器// 删除元素后，被删元素及其之后的所有迭代器都会失效，但返回值是新的有效迭代器it1 = v.erase(it1);  // 删除20，vector变为{10,30,40}cout << *it1;return 0;
}

在这里插入图片描述

示例三（删除元素后，被删除位置之前的迭代器能正常使用）：

int main()
{vector<int> v = { 10, 20, 30, 40 };auto it = v.begin(); // 指向10auto it1 = v.begin() + 1;  // 指向20auto it2 = v.begin() + 2;  // 指向30v.erase(it1);  // 删除20，vector变为{10,30,40}cout << *it; // 删除元素后，被删除位置之前的迭代器能正常使用return 0;
}

在这里插入图片描述

一、导致迭代器失效的典型场景总结

插入元素(push_back, insert和resize等)

当插入导致vector容量不足时，会重新分配内存，所有迭代器、指针、引用都会失效。
即使容量足够，插入位置及其之后的迭代器也会失效（元素被后移）。

扩充容量(reserve等) 和重新赋值(assign等)

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

删除元素(erase, pop_back等)

被删除元素及其之后的所有迭代器、指针、引用会失效（元素前移）
被删除元素之前的迭代器、指针、引用仍然保持有效

二、如何减少迭代器失效？

插入/删除后更新迭代器
erase和insert会返回新的有效迭代器：
vector<int> v{ 1,2,3,4,5,6 }; 	
auto it = v.begin(); 	
it = v.insert(v.begin(), 0); // 使用返回的新迭代器 	
it = v.erase(it); // 使用返回的新迭代器  
预留足够容量
使用reserve()预先分配足够内存，减少重新分配次数：
std::vector<int> v;    
v.reserve(100);  // 预分配足够内存空间   
避免保存旧迭代器
修改操作后，不要继续使用旧的迭代器、指针或引用。

总结表格

操作类型	失效范围	解决方案
插入导致扩容	所有迭代器	重新获取所有迭代器
插入未扩容	插入位置及其之后的迭代器	更新插入位置后的迭代器
用`reserve`扩容和用`assign`重新赋值	所有迭代器	重新获取所有迭代器
删除元素	被删位置及其之后的迭代器	使用`erase`返回的新迭代器

文章目录

前言

一、vector类的常用接口的模拟实现

1.头文件（my vector.h）整体框架

2.模拟实现vector类对象的常见构造

3.模拟实现vector iterator

4.模拟实现vector类对象的容量操作

5.模拟实现vector类对象的访问

6.模拟实现vector类对象的修改操作

二、vector 迭代器失效问题

相关文章：