目录
一、前言
二、源码引入
三、vector的模拟实现
✨实现框架
✨前情提要
✨Member functions —— 成员函数
⚡构造函数
⭐无参构造
⭐迭代器区间构造
⭐n个值构造
⚡拷贝构造
⚡运算符赋值重载
⚡析构函数
✨Element access —— 元素访问
⚡operator[ ]
⚡Iterator —— 迭代器
✨Capacity —— 容量
⚡size和capacity
⚡reserve
⚡ resize
✨Modifiers —— 修改器
⚡push_back
⚡pop_back
⚡insert (重点：迭代器失效)
⭐迭代器失效---扩容导致野指针
⭐迭代器指向的位置意义改变
⚡erase(重点：迭代器失效)
四、vector 类的模拟实现整体代码
🥝 vector.h
🍇vector.cpp
五、共勉
一、前言
在经过漫长的类和对象与 STL 学习之后，对于 STL中的 vector类 有了一个基本的认识，如果还有不太了解 vector 类的老铁，可以看看这篇文章：vector详细解析
本模块呢，我将会带大家一起从 0~1去模拟实现一个STL库中的 vector类，当然模拟实现的都是一些常用的接口，以便于让大家更好的巩固之前学习过的 缺省参数、封装、类中的6大默认成员函数等，代码量大概在 600行左右。
二、源码引入
首先，带大家看一下，vector的源码是如何去实现的，再根据我们自己的理解来实现。
- 以下我所介绍的都是基于【SGI】版本的STL，对源码有兴趣的同学可以去看看 侯捷老师的《STL源码剖析》
- 然后呢我们就去调出【vector】的一些核心源码，这里我们主要关注的就是这个使用原生指针
value_type*所定义出来的迭代器iterator - 然后我们又看到了保护成员：
[start]、[finish]、[end_of_stroage]。看到它们你是否有想起我们在 模拟string 的时候写到过的[a]、[size]、[capacity]；没错，它们就存在着一定的对应关系
- 但是呢，只看上面这些成员变量还不够，我们要将其带入到具体的场景中，例如下面有两个接口分别为【尾插】和【扩容】，对于
push_back()封装得没有那么厉害，读者结合下面的图应该就能看得懂，分别就是 未满追加的逻辑和已满扩容的逻辑
- 那对于
reserve()来说，就是一个扩容的逻辑，【allocate_and_copy】是开辟和拷贝空间，那【deallocate】就是释放空间。在扩完容之后不要忘了去对三个成员变量做更新，这一块的模拟实现我在下面马上就会讲到
💬 对于上面的这些源码呢，读者可以在学习了STL一段时间后，配合侯捷老师的《STL源码剖析》再去展开阅读，因为考虑到读者的基础，就不在继续深入讲解了~
三、vector的模拟实现
然后我们就来模拟实现一下【vector】中的各种接口
✨实现框架
✨前情提要
- 首先第一点，为了不和库中的vector类发生冲突，我们可以包上一个名称为xas_vector的命名空间，此时因为作用域的不同，就不会产生冲突了，如果这一块有点忘记的同学可以再去看看 namespace命名空间
- 其他部分可以看到迭代器我定义的就是原生指针类型，然后将
[_start]、[_finish]、[_end_of_storage]也定义为了三个迭代器类型，并且采用提前声明的形式将它们都初始化为nullptr，这样当我们后面在写 构造函数和析构函数 的时候就不需要再去做初始化了
#pragma once
#include <iostream>
#include <assert.h>
using std::ostream;
using std::istream;
using std::cout;
using std::cin;
using std::endl;
// 为了不和 std库 中的 vector类 发生冲突，创建我们自己的作用域xas_vector
namespace xas_vector
{
template<class T>//通过模板能够实现不同类型的数据存储
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
/*
各类函数功能实现
*/
private:
iterator _start = nullptr; //指向容器中的起始位置
iterator _finish = nullptr; //指向容器中最后一个有效数据的下一个位置
iterator _end_of_storage = nullptr; //指向容器中现有容量的位置
};
}
- 接下去呢，就在vector.h中进行声明，在test.cpp中进行定义和测试即可。其中需要包含一下这个头文件，此时我们才可以在自己实现的类中去调用一些库函数
✨Member functions —— 成员函数
⚡构造函数
好，首先第一个我们要来讲的就是【构造函数】
⭐无参构造
- 对于vector的无参构造，我们只需要将三个成员变量置为空指针即可。
//构造函数 --- 无参构造
vector()
//初始化成员列表
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}⭐迭代器区间构造
当我们想要以某个对象的区间来进行初始化时，就需要用到模板了。它既可以是类模板，也可以是函数模板。如果对模板还是不是很熟悉，可以看看这篇文章：C++模板
例如：
用一个常量字符串来构造vector
const char* p = "hello";
vector<char>v(p, p + 2);用一个数组来构造vector
int a[5] = { 1,2,3,4,5 };
vector<int>v1(a, a + sizeof(a) / sizeof(a[0]));用一个string类来构造vector
string s1("hello");
vector<char>v2(s1.begin(), s1.end());//构造函数 --- 迭代器区间构造
template <class InputIterator>//既是一个类模板的成员函数，又可以是一个函数模板
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);//尾插
++first;
}
}💬 马上我们就来测试一下
// 构造函数
void test6()
{
// 无参构造
xas_vector::vector<int> v;
xas_vector::print_vector(v);
cout << endl;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
// 迭代器区间构造
xas_vector::vector<int> v2(v.begin(), v.end());
xas_vector::print_vector(v2);
cout << endl;
std::string s("abcdef");
xas_vector::vector<char> v3(s.begin(), s.end());
xas_vector::print_vector(v3);
cout << endl;
int a[] = { 1,2,3,4 };
xas_vector::vector<int> v4(a, a + 4);
xas_vector::print_vector(v4);
cout << endl;
}
⭐n个值构造
此外，vector还支持构造这样一种容器，该容器当中含有n个值为val的数据。对于该构造函数，我们可以先使用resize()函数进行复用将容器容量先设置为n，并进行初始化。
// 有参构造
vector(size_t n, const T& val = T())
{
resize(n, val);
}
- 注意：在设计带参构造函数时，需要使用 匿名对象 作为缺省值（ const T& val = T()）,因为 T类型不确定，在设置缺省值时，只能使用 匿名对象 的方式，如果大家对匿名对象还不太了解，可以去看看这篇文章：匿名对象详解
匿名对象生命周期只有一行，但在被const修饰后，其生命周期会延长- 内置类型 也能创建匿名对象，比如
int()、char()是合法可用的
💬 马上我们就来测试一下
// 构造函数
void test6()
{
// n 个值构造
xas_vector::vector<int> v5(5, 0)；
}-
我们可以看到出现了报错，说的是“非法的间接寻址”
- 这里对迭代器
first去进行解引用目的就是为了获取这个位置上的数据， 在之前的指针有所提到 只有指针和迭代器可以解引用，基本数据类型不能解引用
💬 但是有同学一定会疑惑说：为什么这里不会去匹配有参构造，而是去匹配的迭代器区间构造呢？
1️⃣：在讲 C++模板 的时候，我们有说到过模版参数会去进行自动类型推导，从而匹配最合适函数模版。因为我们在这里所传入的【10】和【1】都是int类型，但是呢有参构造的第一个形参类型为size_t，并不是最匹配的
2️⃣： 而迭代器区间初始化其参数类型都是模版参数，所以在匹配的时候它是最优先进行匹配的
那我们该如何去进行预防呢？
- 很简单，我们可以利用在 C++函数重载 中所学习的参数类型不同去另写一个有参构造的重载形式
vector(size_t n, const T& val = T())
{
resize(n, val);
}
vector(int n, const T& val = T())
{
resize(n, val);
}
- 我们可以看出这里就没有歧义了
⚡拷贝构造
讲完构造函数了，我们来看看拷贝构造
- 首先读者要明确为什么要写拷贝构造，这个我们通过调试来看一下就知道了：很明显可以看到这里只是做了一个浅拷贝，而不是去做了深拷贝
- 所以我们要自己去实现一个深拷贝，逻辑很简单，就不赘述， 如果还有不太懂拷贝构造的老铁的可以去看看这篇文章：拷贝构造详解
// 拷贝构造
vector(vector<int>& v)
{
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
memcpy(tmp, v._start, sizeof(T) * v.size());//将容器v当中的数据一个个拷贝过来
_finish = _start + v.size(); //容器有效数据的尾
_end_of_storage = _start + v.capacity(); //整个容器的尾
}
- 但是看到上面这个
memcpy()，你是否会有一种警惕的心理呢，因为我们上面讲到过 vector 对象中存放的是 string数组，在拷贝的过程中会产生浅拷贝的问题，那就不可以去使用这个memcpy()，具体问题间下图
- 注意： 将容器当中的数据一个个拷贝过来时不能使用memcpy函数，当vector存储的数据是内置类型或无需进行深拷贝的自定义类型时，使用memcpy函数是没什么问题的，但当vector存储的数据是需要进行深拷贝的自定义类型时，使用memcpy函数的弊端就体现出来了。例如，当vector存储的数据是string类的时候。
- 并且vector当中存储的每一个string都指向自己所存储的字符串。
- 如果此时我们使用的是memcpy函数进行拷贝构造的话，那么拷贝构造出来的vector当中存储的每个string的成员变量的值，将与被拷贝的vector当中存储的每个string的成员变量的值相同，即两个vector当中的每个对应的string成员都指向同一个字符串空间。
- 这显然不是我们得到的结果，那么所给代码是如何解决这个问题的呢？
- 代码中看似是使用普通的“=”将容器当中的数据一个个拷贝过来，实际上是调用了所存元素的赋值运算符重载函数，而string类的赋值运算符重载函数就是深拷贝，所以拷贝结果是这样的：
//拷贝构造
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_endofstorage = _start + v.capacity(); //整个容器的尾
}
总结一下： 如果vector当中存储的元素类型是内置类型（int）或浅拷贝的自定义类型（Date），使用memcpy函数进行进行拷贝构造是没问题的，但如果vector当中存储的元素类型是深拷贝的自定义类型（string），则使用memcpy函数将不能达到我们想要的效果。
⚡运算符赋值重载
vector的赋值运算符重载当然也涉及深拷贝问题，我们这里也提供两种深拷贝的写法：
传统写法：
- 首先判断是否是给自己赋值，若是给自己赋值则无需进行操作。若不是给自己赋值，则先开辟一块和容器v大小相同的空间，然后将容器v当中的数据一个个拷贝过来，最后更新_finish和_end_of_storage的值即可。
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //释放原来的空间
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_end_of_storage = _start + v.capacity(); //整个容器的尾
}
return *this; //支持连续赋值
}注意： 这里和拷贝构造函数的传统写法类似，也不能使用memcpy函数进行拷贝。
现代写法：
- 赋值运算符重载的现代写法非常精辟，首先在右值传参时并没有使用引用传参，因为这样可以间接调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。
//现代写法
// v1 = v3
// v1是v3 的拷贝， 注意这里不能用& 这样v3就变成v1了，而我们的目的是让 v1 = v3
vector<T>& operator=(vector<T> v) //编译器接收右值的时候自动调用其拷贝构造函数
{
swap(v); //交换这两个对象
return *this; //支持连续赋值
}
⚡析构函数
对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针即可。
//析构函数
~vector()
{
if (_start) //避免对空指针进行释放
{
delete[] _start; //释放容器存储数据的空间
_start = nullptr; //_start置空
_finish = nullptr; //_finish置空
_end_of_storage = nullptr; //_endofstorage置空
}
}
✨Element access —— 元素访问
基本的成员函数我们已经讲完了，string对象也构造出来了，接下去我们来访问一下对象里面的内容吧
⚡operator[ ]
- 对于元素访问的话我们最常用的就是
下标 + []的形式，这里给出两种，一个是const版本和非const版本
//访问容器相关函数
T& operator[](size_t pos)
{
assert(pos < size());
// 返回应用的时数组的下标
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
// 返回应用的时数组的下标
return _start[pos];
}}
⚡Iterator —— 迭代器
那经过上面的学习我们可以知道，要去遍历访问一个vector对象的时候，除了【下标 + []】的形式，我们还可以使用迭代器的形式去做一个遍历
- 而对于迭代器而言我们也是要去实现两种，一个是非const的，一个则是const的
- vector类中的迭代器实际上就是字符指针，只是给字符指针起了一个别名叫iterator而已。
typedef T* iterator; // 迭代器某种意义上就是指针
typedef const T* const_iterator;- vector的begin直接返回容器的_start，end返回容器的_finish。
//begin
iterator begin()
{
return _start; //返回容器的起始位置
}
//end
iterator end()
{
return _finish; //返回有效数据下一个的地址
}- const版本：
//const版本迭代器
const_iterator begin()const
{
return _start;
}
//end
const_iterator end()const
{
return _finish;
}- 常量的打印
void print_vector(const vector<T>& v)
{
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
}💬 马上我们就来测试一下
// 测试遍历方式
void test1()
{
xas_vector::vector<int> v;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
v.Push_back(4);
v.Push_back(4);
cout << "------------迭代器打印-----------" << endl;
// 1.迭代器
xas_vector::vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
cout << "------------范围for打印-----------" << endl;
// 2.有迭代器就支持 范围for
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
cout << "------------下标[]打印-----------" << endl;
// 3. []
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
cout << "------------const打印-----------" << endl;
print_vector(v);
}
✨Capacity —— 容量
- 然后我们来讲讲容量相关的接口，首先的话就是【size】和【capacity】这两个接口
⚡size和capacity
- 因为指针相减的结果就是这两个指针之间对应类型的数据个数，所以获取size只需_finish-_start。获取capacity只需_end_of_stoage-_start。
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
⚡reserve
-
reserve增容：
1.当 n > capacity 时，将capacity扩大到n；
2.当 n < capacity 时，不进行任何操作；
看着逻辑很清晰，但是呢下面的代码存在着非常多的漏洞
void reserve(size_t n)
{
if (n > capacity())//判断是否需要扩容
{
//扩容
T* tmp = new T[n]; //开辟n个空间
if (_start)
{
//数据拷贝，也不能去使用memcpy函数
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start; //释放旧空间
}
_start = tmp; //指向新空间
_finish = _start + size();
_end_of_storage = _start + n;
}
}- 我们这里再写一个
push_back的接口（后面讲），让代码先跑起来
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
_finish++;
}
💬 马上我们就来测试一下
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
- 但是呢在运行起来后却发现程序出现了崩溃，这是为什么呢？
- 按下【F5】以调试的方式运行起来就可以发现有地方出现了 空指针异常
- 进一步，我们通过【调试窗口】再来看看，很明显得就看到这个
_finish的值为【0x00000000】
- 其实真正的问题还是出在【reserve】这个扩容的逻辑中，随着我们一步一步地去看，可以看到
_start和_end_of_storage这两个都没什么问题，但是_finish就是没有什么变化，所以呢我们可以锁定到下面这句话
_finish = _start + size();
- 此时就需要去看看这个【size】了，之前我们使用的是_finish - _start来计算的 size()，在执行这句话时_start已经发生了改变，因为我们去开出了一块新的空间，但是这时_finish的值还是一开始的【nullptr】，那么这个 size() 最后计算出来的大小即为 -_start，此时再和_start去做一个结合的话即为 0
💬 所以，上述就是为什么这个_finish的值为【0x00000000】原因，那我们要如何去修改呢？
- 我们可以在每次没开始扩容之前我们都可以去事先保存一下这个 size()，后面的更新顺序就不需要发生变动了，在加的时候加上
sz即可
void reserve(size_t n)
{
if (n > capacity())//判断是否需要扩容
{
//扩容
size_t sz = size(); //提前算好增容前的数据个数
T* tmp = new T[n]; //开辟n个空间
if (_start)
{
//数据拷贝，也不能去使用memcpy函数
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start; //释放旧空间
}
_start = tmp; //指向新空间
_finish = _start + sz;
_end_of_storage = _start + n;
}
}⚡ resize
接下去的话我们再来看看【resize】这个接口该如何去实现
还是一样分为三类来进行讨论：
- 一个是
n < _finish的情况； - 第二个是
n > _finish && n <= _end_of_storage的情况； - 第三个是
n >_end_of_storage的情况；
对于后两种情况我们可以做一个合并，使用上面【reserve】去做一个容量的检查
- 我们来看一下具体的代码，首先是第一种，直接让
_finish = _start + n即可；如果是另一种情况的话，就先使用【reserve】去检查一下是否需要扩容，然后再去通过循环追加对应的数据即可
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
// 先使用reserve()去检查一下是否需要扩容
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
简单地来测试一下
✨Modifiers —— 修改器
接下去的话我们来讲讲有关修改操作的一些接口
⚡push_back
- 首先第一个的话就是push_back，这个我在上面讲【reserve】的时候给出过，现在仔细地再来讲一讲：首先的话我们要考虑的就是扩容的逻辑，上面我们有讲到在VS下是呈现 1.5倍 的增长趋势，但是在g++下呈现的则是 2倍 的扩容逻辑，这里的扩容的话我们就交给【reserve】来实现
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
_finish++;
}
⚡pop_back
在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。
void pop_back(const T& x)
{
assert(_finish > _start);
--_finish;
}⚡insert (重点：迭代器失效)
然后的话我们来实现一下【insert】这个接口
void insert(iterator pos, const T& x)
这一块的话我们已经讲过很多遍了，要在某一个位置插入数据的话就需要先去挪动部分的数据，这里我们从后往前挪，防止造成覆盖的情况，当数据挪动完毕后，再在pos这个位置插入指定的数据即可
- 在一进入函数的时候大家可以去做一个断言的操作，不过很多同学可能会好奇这边的
pos >= _start，为什么可以位于首部
assert(pos >= _start && pos <= _finish);
- 不过呢，既然是插入数据的话就一定会存在容量不足的情况，此时就需要一个扩容逻辑，这里我们直接用上面在
push_back()接口中所写的即可
// 1.首先考虑扩容逻辑
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
以下是整体的代码
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
// 1.首先考虑扩容逻辑
if (_finish == _end_of_storage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
// 2.挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
⭐迭代器失效---扩容导致野指针
- 好，在写完【insert】接口后，我们再来做一个测试。可以发现程序崩溃了
马上，我们通过调试来观察一下
- 此时我们已经往【v】中插入了4个数据，马上使用
insert(v.begin(),0)去做一个头插，那么一进到函数中我们就可以知道这个当前对象的_start和pos所处的迭代器位置是相同的，也就是同一段空间的地址
- 那此时我们知道容器中的空间已经满了，所以会去走一个扩容的逻辑，此时可以看到当前对象this的
_start已经发生了改变
- 可以看到，在扩完容之后，当前对象的
_start和待插入位置的pos已经发生了变化，那么在此时我们再去挪动数据进行插入的时候就会出现问题了
💬 我们可以通过下面的图示来看看到底这个扩完容之后是怎样的
- 可以看到
_start确实发生了一个变化，但是呢pos还是指向原来的那个地方。那读者可以自己去想象一下子在遍历挪动数据的时候究竟何时才是个头呢？
🔰 以上所出现的这个问题就被称作是 【迭代器失效的问题】---- 扩容导致野指针
那我们要如何去解决呢？
- 首先大家要明白的一个点是出错的根本原因在于：
_start的位置改变了但是pos的位置没有发生改变。 - 所以我们所要做的一个点就是：让
pos的位置随着_start的变动而一起变动，这样就不会出现问题了。以下我们需要改进的代码部分，在进行扩容之前，我们可以先去计算一下从【_start】到【pos】的位置有多远； - 然后呢我们在执行完扩容的逻辑之后，就要去更新一下这个【pos】迭代器的位置所在，就使用刚才计算出来的这段距离即可
//在pos位置插入数据
void insert(iterator pos, const T& x)
{
if (_finish == _end_of_storage) //判断是否需要增容
{
size_t len = pos - _start; //记录pos与_start之间的间隔
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //将容量扩大为原来的两倍
reserve(newcapacity); //增容
pos = _start + len; //通过len找到pos在增容后的容器当中的位置
}
//将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入
iterator end = _finish;
while (end >= pos + 1)
{
*end = *(end - 1);
end--;
}
*pos = x; //将数据插入到pos位置
_finish++; //数据个数增加一个，_finish后移
}
⭐迭代器指向的位置意义改变
- 但是呢就上面这样还不够，我们只解决了内部迭代器失效的问题，而外部迭代器失效的问题并没有很好地解决。
- 外部迭代器，那是什么东西？ 我们来看下这段代码
vector<int> v1;
v1.Push_back(1);
v1.Push_back(2);
v1.Push_back(3);
v1.Push_back(4);
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;
vector<int>::iterator it = v1.begin();
it = v1.insert(it, 0);
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;
cout << *it << endl;- 可以看到，在使用完这个这个迭代器之后再去访问就出现了问题
👉 所以，对于迭代器这一块我们在使用的时候一定要慎重，在使用完之后不要去轻易地修改它
🔰 以上所出现的这个问题就被称作是 【迭代器失效的问题】---- 位置意义改变
- 如何执意要进行修改的话也不是没有办法，我们只需要在【insert】之后去接受一下当前所操作的这个迭代器的位置即可，记住这个位置，下次在访问的时候也就不会出问题
//insert
iterator insert(iterator pos, const T& x)
{
//检测参数合法性
assert(pos >= _start && pos <= _finish);
//检测是否需要扩容
/*扩容以后pos就失效了，需要更新一下*/
if (_finish == _end_of_stoage)
{
size_t n = pos - _start;//计算pos和start的相对距离
size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapcacity);
pos = _start + n;//防止迭代器失效，要让pos始终指向与_start间距n的位置
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *(end);
end--;
}
//把值插进去
*pos = x;
_finish++;
return pos;
}
⚡erase(重点：迭代器失效)
- 对于【erase】来说，我们也是需要先去挪动数据的，但是在这里呢我们需要从前往后挪，也是防止造成覆盖的情况
//删除pos位置的数据
iterator erase(iterator pos)
{
assert(!empty()); //容器为空则断言
//将pos位置之后的数据统一向前挪动一位，以覆盖pos位置的数据
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
_finish--; //数据个数减少一个，_finish前移
return pos;
}
立马来测试一下：
四、vector 类的模拟实现整体代码
🥝 vector.h
#pragma once
#include <iostream>
#include <string>
#include <assert.h>
using std::ostream;
using std::istream;
using std::cin;
using std::cout;
using std::endl;
//为了避免和库里的vector产生冲突，在自己的命名空间内实现vector
namespace xas_vector
{
//通过模板能够实现不同类型的数据存储
template<class T>
// 创建一个 vecto 类
class vector
{
public:
typedef T* iterator; // 迭代器某种意义上就是指针
typedef const T* const_iterator;
//默认成员函数
vector(); // 构造函数 --- 无参构造
template<class InputIterator> // 有参构造
vector(InputIterator first, InputIterator last); // 有参构造
vector(size_t n, const T& value = T()); //n个值构造
vector(int n, const T& value = T());
~vector(); // 析构函数
vector<T>& operator=(vector<T> v); // 赋值运算符重载
vector(const vector<T>& v); // 拷贝构造
//容量和大小相关函数
size_t size() const; // 空间的有效个数
size_t capacity() const; // 空间的容量大小
void reserve(size_t n); // 扩容函数
// T 如果是string类，就可能调用string类的默认构造
// T 如果是 int 也是有默认构造的 C++对其进行了升级
// 总结：在C++中内置类型也有构造函数哦
void resize(size_t n, const T& val = T()); // 改变有效字符数
// 迭代器相关函数
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//修改容器内容相关函数
void Push_back(const T& x); // 尾插
void Pop_back(); // 尾删
iterator insert(iterator pos, const T& x);// 在pos位置之前插入
iterator erase(iterator pos); // 删除pos位置的值
void swap(vector<T>& v); // 交换
//访问容器相关函数
T& operator[](size_t pos);
const T& operator[](size_t pos)const;
private:
iterator _start; // 指向容器中的起始位置
iterator _finish; // 指向容器中最后一个有效数据的下一个位置
iterator _end_of_storage; // 指向容器中现有容量的位置
};
// 打印函数
template<class T>
void print_vector(const vector<T>& v)
{
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
}
} 🍇vector.cpp
#include "vector.h"
template<class T>
xas_vector::vector<T>::vector() // 构造函数 --- 无参构造
// 初始化成员列表
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
template<class T>
template<class InputIterator>
xas_vector::vector<T>::vector(InputIterator first, InputIterator last)
{
while (first != last)
{
Push_back(*first);
++first;
}
}
template<class T>
xas_vector::vector<T>::vector(int n, const T& value)
{
resize(n, value);
}
template<class T>
xas_vector::vector<T>::vector(size_t n, const T& value)
{
resize(n, value);
}
template<class T>
xas_vector::vector<T>::vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
//memcpy(_start, v._start, sizeof(T) * v.size());
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效数据的尾
_end_of_storage = _start + v.capacity(); //整个容器的尾
}
// v1 = v3
// v1是v3 的拷贝， 注意这里不能用& 这样v3就变成v1了，而我们的目的是让 v1 = v3
template<class T>
xas_vector::vector<T>& xas_vector::vector<T>::operator=(vector<T> v) //赋值运算符重载
{
swap(v); //交换这两个对象
return *this;
}
// 迭代器相关函数
// typename 来声明 iterator 是一个类型名
template<class T>
typename xas_vector::vector<T>::iterator xas_vector::vector<T>::begin()
{
return _start;
}
template<class T>
typename xas_vector::vector<T>::iterator xas_vector::vector<T>::end()
{
return _finish;
}
template<class T>
typename xas_vector::vector<T>::const_iterator xas_vector::vector<T>::begin() const
{
return _start;
}
template<class T>
typename xas_vector::vector<T>::const_iterator xas_vector::vector<T>::end() const
{
return _finish;
}
template<class T>
xas_vector::vector<T>::~vector() // 析构函数
{
//防止对空指针进行释放
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
template<class T>
size_t xas_vector::vector<T>::size() const // 空间的有效个数
{
return _finish - _start;
}
template<class T>
size_t xas_vector::vector<T>::capacity() const // 空间的容量大小
{
return _end_of_storage - _start;
}
template<class T>
void xas_vector::vector<T>::reserve(size_t n) // 扩容函数
{
// 在之前保存 size
size_t sz = size();
if (n > capacity())
{
T* temp = new T[n]; // 开一块新空间
// 如果有效个数不为0 需要将有效数据拷贝到新开辟的空间中
if (_start)
{
// 进行数据拷贝
//memcpy(temp, _start, sizeof(T) * sz);
for (size_t i = 0; i < size(); i++)
{
temp[i] = _start[i];
}
// 销毁之前的空间
delete[] _start;
}
_start = temp; // 指向新的空间
_finish = _start + sz; // 指向有效个数的下一个位置
_end_of_storage = _start + n;
}
}
template<class T>
// T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
void xas_vector::vector<T>::resize(size_t n, const T& val)
{
// 缩容 相应的数据会减少，只需要调整一下_finish的位置
if (n < size())
{
_finish = _start + n;
}
// 判断是新增数据还是扩容
else
{
// 先使用reserve()去检查一下是否需要扩容
reserve(n);
// 新增数据
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
template<class T>
void xas_vector::vector<T>::Push_back(const T& x) // 尾插
{
// 判断是否需要扩容
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
template<class T>
void xas_vector::vector<T>::Pop_back() // 尾删
{
asseert(size() > 0);
_finish--;
}
template<class T>
typename xas_vector::vector<T>::iterator xas_vector::vector<T>::insert(iterator pos, const T& x) // 在pos位置之前插入x
{
// 1.最多是尾插,最小是头插
assert(pos <= _finish);
assert(pos >= _start);
// 2.既然是插入，那肯定需要判断是否需要扩容
// 扩容以后pos就会失效，需要更新一下
if (_finish == _end_of_storage)
{
// 首先保存一下从_start到pos的距离
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
// 再扩完容之后更新一下pos, 解决迭代器失效问题
pos = _start + len;
}
// 3.挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
// 4.填入数据
*pos = x;
_finish++;
return pos;
}
template<class T>
typename xas_vector::vector<T>::iterator xas_vector::vector<T>::erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
// 从pos + 1的位置开始往前覆盖，即可完成删除pos位置的值
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
//传pos位置的迭代器，防止迭代器失效
return pos;
}
//访问容器相关函数
template<class T>
T& xas_vector::vector<T>::operator[](size_t pos)
{
assert(pos < size());
// 返回应用的时数组的下标
return _start[pos];
}
template<class T>
const T& xas_vector::vector<T>::operator[](size_t pos)const
{
assert(pos < size());
// 返回应用的时数组的下标
return _start[pos];
}
template<class T>
void xas_vector::vector<T>::swap(vector<T>& v) //交换
{
//交换容器当中的各个成员变量
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// 测试插入问题 size() 与 capacity() 的问题
// 测试遍历方式
void test1()
{
xas_vector::vector<int> v;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
v.Push_back(4);
v.Push_back(4);
cout << "------------迭代器打印-----------" << endl;
// 1.迭代器
xas_vector::vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
cout << "------------范围for打印-----------" << endl;
// 2.有迭代器就支持 范围for
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
cout << "------------下标[]打印-----------" << endl;
// 3. []
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
cout << "------------const打印-----------" << endl;
print_vector(v);
}
// 测试resize()问题
// 测试 拷贝构造
void test3()
{
cout << "------------测试resize():-----------" << endl;
xas_vector::vector<int> v;
v.resize(10);
for (auto ch : v)
{
cout << ch << " ";
}
cout << endl;
/*cout << "------------测试拷贝构造-----------" << endl;
xas_vector::vector<std::string> v;
v.Push_back("1111");
v.Push_back("2222");
v.Push_back("3333");
v.Push_back("4444");
v.Push_back("5555");
v.Push_back("6666");
xas_vector::vector<std::string> v1(v);
xas_vector::print_vector(v1);*/
/*cout << "------------测试赋值重载-----------" << endl;
xas_vector::vector<int> v1;
xas_vector::print_vector(v1);
xas_vector::vector<int> v3;
v3.Push_back(1);
v3.Push_back(2);
v3.Push_back(3);
v3.Push_back(4);
v3.Push_back(5);
v1 = v3;
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;*/
}
// 测试插入问题
void test2()
{
xas_vector::vector<int> v1;
v1.Push_back(1);
v1.Push_back(2);
v1.Push_back(3);
v1.Push_back(4);
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;
xas_vector::vector<int>::iterator it = v1.begin();
v1.insert(it, 0);
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;
cout << *it << endl;
/*xas_vector::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.insert(it, 20);
it++;
}
it++;
}
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;*/
}
// 测试删除问题
void test4()
{
//删除所有的偶数
xas_vector::vector<int> v;
v.Push_back(1);
v.Push_back(2);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
v.Push_back(5);
v.Push_back(6);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
it++;
}
}
for (auto e : v)
{
cout << e << " ";
}
/*v1.erase(v1.begin() + 3);
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;*/
/*cout << v1.size() << " : " << v1.capacity() << endl;
vector<int>::iterator it;
it = std::find(v1.begin(), v1.end(), 6);
if (it != v1.end())
{
it = v1.erase(it);
}
cout << *it << endl;
*it = 10;
cout << *it << endl << endl;
cout << v1.size() << " : " << v1.capacity() << endl;
for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;*/
}
// vector<string> 测试
void test5()
{
xas_vector::vector<std::string> v;
v.Push_back("11111");
v.Push_back("22222");
v.Push_back("33333");
v.Push_back("44444");
v.Push_back("55555");
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
// 构造函数
void test6()
{
// 无参构造
xas_vector::vector<int> v;
xas_vector::print_vector(v);
cout << endl;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
// 迭代器区间构造
xas_vector::vector<int> v2(v.begin(), v.end());
xas_vector::print_vector(v2);
cout << endl;
std::string s("abcdef");
xas_vector::vector<char> v3(s.begin(), s.end());
xas_vector::print_vector(v3);
cout << endl;
int a[] = { 1,2,3,4 };
xas_vector::vector<int> v4(a, a + 4);
xas_vector::print_vector(v4);
cout << endl;
// n 个值构造
xas_vector::vector<int> v5(5, 0);
xas_vector::print_vector(v5);
}
// 测试reserve
void test7()
{
xas_vector::vector<int> v;
v.Push_back(1);
v.Push_back(2);
v.Push_back(3);
v.Push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test4();
return 0;
}五、共勉
以下就是我对 vector类的模拟实现 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 C++vector迭代器失效 的理解，请持续关注我哦！！！
