【C++】模拟实现vector
🦄个人主页:修修修也
🎏所属专栏:C++
⚙️操作环境:Visual Studio 2022
编辑
目录
🎏 实现vector的capacity()函数和size()函数
一.了解项目功能
声明:
该模拟实现仅适用于STL初学小白了解vector的简单实现,会结合一些STL源码作为参照,但是源码中涉及的空间配置器部分我们不做涉及!
在本篇博文中,将使用new/delete等方式来完成C++的动态内存的申请与释放.该方式相比于空间配置器效率有所降低,但是初学者较为友好的一种初步了解STL的一种方式.
在上篇博客中我们详细介绍了C++标准库vector对象集合,包含它的常用成员函数及其使用示例:
【C++】标准库类型vector 
https://blog.csdn.net/weixin_72357342/article/details/139740266?spm=1001.2014.3001.5501 而在本次项目中我们的目标是模拟实现一个vector对象集合类模板:
该对象集合包含三个成员变量,分别是:
• iterator类型成员变量_start,是指向vector开始位置的迭代器.
• iterator类型成员变量_finish,是指向vector最后一个有效元素的后一位置的迭代器.
• iterator类型成员变量_endofstorage,是指向vector最后一个有效容量的后一位置的迭代器.
可能大家会感到陌生,vector的成员变量不应该是一个T*的数据指针加上两个size_t的大小和容量的组合吗,为什么会是三个迭代器,这个我们具体会在"构造成员变量"部分细讲,这里只是介绍一下vector的组成.vector成员变量组成图示如下: 
编辑
模拟实现的成员函数有:
• 构造函数,拷贝构造函数,赋值运算符重载和析构函数
• size()函数
• capacity()函数
• reserve()函数
• resize()函数
• push_back()函数
• pop_back()函数
• insert()函数
• erase()函数
• swap()函数
• 运算符重载函数,包括: []
• 迭代器相关函数,包括:begin()函数,end()函数
注意,因为我们要实现的vector类并不只满足于只能存储一种固定类型的元素,我们在一个项目中,可能会创建几个存储不同类型元素的vector,如:
vector<int> vage; //存放学生年龄
vector<string> vname; //存放学生姓名
vector<double> vhigh; //存放学生身高
vector<Student> vstu; //存放自定义学生类
因此,我们需要将vector实现为一个类模板,这样才可以满足上面的需求,有关C++泛型编程模板相关知识还不是很了解的朋友可以先移步:
【C++】初阶模板 https://blog.csdn.net/weixin_72357342/article/details/137910913?spm=1001.2014.3001.5502
二.逐步实现项目功能模块及其逻辑详解
通过第一部分对项目功能的介绍，我们已经对vector的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第三部分。
🎏构建成员变量
我们先来看一下STL的源码中,vector是如何实现的:
首先来看一下成员变量部分:
//STL源码:vector成员变量部分
protected:
typedef simple_alloc<value_type, Alloc> data_allocator;//空间配置器,忽略
iterator start;
iterator finish;
iterator end_of_storage;
编辑
可以看到,源码中vector的实现的成员变量并不是我们想象中的:
protected:
T* v;
size_t size;
size_t capacity;
而是使用了三个迭代器来组成vector的成员变量,这样做的好处有:
1. 类型安全性：迭代器通常是类型安全的，能够提供编译时检查。使用迭代器可以避免因错误的指针操作而导致的潜在问题。
2. 抽象化：迭代器提供了一种更高级的抽象，能够隐蔽底层数据结构的实现细节，从而简化对容器的操作。用户只需关注迭代器的操作，无需关心内部数据结构的具体实现。
3. 统一接口：迭代器提供了一致的接口，使得对不同类型容器的操作变得更加统一和简洁。这种统一性使得算法和容器之间的互操作变得更加容易。
4. 灵活性：使用迭代器可以更好地支持不同类型的容器，例如支持随机访问、双向遍历等不同类型的迭代器。这样可以在设计和实现上增加灵活性。
5. 便于算法实现：许多 STL 算法都依赖于迭代器作为输入参数，使用迭代器可以直接与这些算法协同工作，而无需做额外的转换或访问层次。
6. 内存安全性：使用迭代器时，迭代器通常包含了对容器的引用或指针，可以更好地管理内存。如果容器被重分配或修改，迭代器可以通过类的成员函数来同步更新，而直接使用原始指针可能会引发悬挂指针问题。
7. 代码复用：迭代器的设计允许不同容器之间的代码复用，使得算法能与任何符合迭代器接口的容器一起工作，从而减小代码冗余。
因此,我们构建的成员变量部分代码如下:
//设置命名空间,防止与库中的vector冲突
namespace mfc
{
template<class T>
//因为我们使用vector中不只存储一种类型的数据,所以可以直接把它定义成模板
class vector
{
public:
typedef T* iterator; //定义一下vector的迭代器底层为T*(模板类型指针)
typedef const T* const_iterator;
//成员函数
private:
//成员变量
iterator _start;
iterator _finish;
iterator _endofstorage;
};
};
🎏实现vector构造函数
📌实现无参构造函数
vector的无参构造函数比较简单,我们利用初始化列表将所有的迭代器都指向nullptr即可,无参构造函数代码如下:
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
📌实现拷贝构造函数
vector的拷贝构造函数就是要根据传入的参数vector来重新拷贝构造一个新的vector,对于vector类型,我们不仅要防止vector本身浅拷贝,还要防止vector中的对象浅拷贝,对于这个问题我们会在后面reserve()函数中详细剖析,在这里简单来讲就是,我们不能通过浅拷贝的方式来拷贝vector中的对象的数据,而应该主动调用对象本身的赋值函数来完成其本身的深拷贝,代码如下:
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
_start = new T[v.capacity()];
//用memcpy,成员对象会浅拷贝
//memcpy(_start, v.begin(), sizeof(T) * v.size());
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
📌实现两种有参数的构造函数
n个val的构造函数
n个val的构造函数其实就是将一个空的vector,扩充数据到size为n的过程,所以我们可以考虑复用一下resize()函数,就可以达到构造vector的目的,代码如下:
//n个val的构造函数
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
但是注意,这里有一个小问题就是,我们下面就要写一个使用一个迭代区间去初始化的构造函数,它的两个参数类型都是模板类型:
vector(InputIterator first, InputIterator last)
这会导致如果有外部函数调用,是这样调用的:
vector<int> v1(10,1);
这会导致我们本来想调用n个val的构造函数,却不小心调用了迭代区间的构造函数,原因如下:
编辑
对于这个问题,解决方案是我们再补充一个以int为参数的n个val的构造函数,这样编译器在识别重载函数时就可以优先匹配这个重载函数了,补充的函数代码如下:
//n个val的构造函数
//为了应对vector<int> v(10,1)更匹配迭代区间构造参数的问题
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
迭代区间初始化的构造函数
因为我们在之前vector的介绍中有提到过,vector是可以不使用自己对象本身的迭代器初始化的,而是只要迭代器类型匹配就都可以用来初始化vector,因此我们选择将该函数写成模板函数,实现代码如下:
//用一个迭代器区间去初始化
//[first,last)
template<class InputIterator>
//写成模板,方便使用不是vector的迭代器也可以初始化vector
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);//将迭代器的内容逐一尾插进vector中
++first;
}
}
🎏实现vector析构函数
vector的析构函数逻辑和string类的很像,都是先释放之前动态开辟的空间,再将成员变量的迭代器指向空即可,vector析构函数代码如下:
~vector()
{
if (_start != nullptr)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
🎏实现vector的operator=运算符重载函数
我们在string类的模拟实现中曾经优化过一种的赋值重载函数,可以直接套用到vector中,它的思路是先使用v拷贝构造一个局部临时变量tmp,再将tmp的内容和this的内容做交换,这样交换后的this的内容就是我们想要得到的v赋值后的内容了,并且由于局部变量出了作用域自动销毁,因此我们也不需要再手动销毁交换后的tmp了,因为编译器会自动帮助我们处理掉,该思路图示如下:
编辑
编辑
编辑
编辑
上面的思路没有问题,但是我们可以再简化一下,可以直接用形参v来代替创建的局部变量tmp,还可以节省一次拷贝消耗的时间,综上,代码如下:
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
🎏实现vector的begin()函数和end()函数
因为我们实现的vector成员变量是由三个迭代器构成的,因此在编写vector的迭代器相关函数时就很简单,直接返回相应迭代器即可,代码如下:
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
🎏实现vector的capacity()函数和size()函数
vector的capacity()函数和size()函数实现起来非常简单,我们参照一下侯捷老师的源码剖析里的一张图就明白了: 
编辑
可以看到,vector的size其实就是finish - start;
而capacity其实就是endofstorage - start.
因此,vector的capacity()函数和size()函数实现代码如下:
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
🎏实现vector的operator[]重载函数
vector中的operator[]重载函数逻辑就是模仿数组的下标访问逻辑,在函数调用时,返回数组中该下标对应的对象即可,代码如下:
T& operator[](size_t pos)
{
//先检查pos的合法性
assert(pos < size());
//直接返回_start的pos位置的对象即可
return _start[pos];
}
注意,当const对象调用该函数时,我们要返回的就不能是正常的对象引用,而应该是const修饰的对象引用,所以重载一下const版本的operator[]函数代码如下:
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
🎏实现vector的push_back()函数
push_back()是尾插函数,对于顺序容器我们的尾插逻辑为:先查满,再扩容.代码如下:
void push_back(const T& x)
{
//查满扩容
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//插入数据
*_finish = x;
++_finish;
/*
后续有了insert(),这个push_back()的完整逻辑就可以不用了,可以直接复用insert
insert(end(), x);
*/
}
🎏实现vector的pop_back()函数
pop_back()函数的作用是尾删,对于顺序容器,我们尾删的逻辑是:先判断容器是否为空,再删除最后一个元素,代码如下:
void pop_back()
{
assert(_start != _finish);
_finish--;
/*
或者可以复用erase()函数
erase(end() - 1);
*/
}
🎏实现vector的swap()函数
swap()函数就是交换两个vector的成员变量,这里我们可以利用一下库里的swap()函数将两个vector的成员变量分别交换一下即可,代码如下:
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
🎏实现vector的reserve()函数
reserve()函数的作用是接收一个无符号整型值n,然后修改vector对象集合的容量大小为n.
在实现reserve()函数时,我们首先要判断n是否大于当前vector的容量,即判断这次reserve()函数的调用目的是"扩容"还是"缩容",因为调整容量的代价是需要重新开辟目标大小的空间并拷贝原本空间中的数据,会导致效率变低.相比于这个,未缩容导致的空间浪费几乎可以忽略,因此我们的实现策略是只在需要扩容时才调整容量大小,如果是缩容,则不做任何处理.
扩容实现逻辑如下:
1. 动态开辟目标容量的空间.
2. 拷贝原空间内容到新开辟的空间.
3. 释放原空间.
4. 修改_start迭代器,使其指向新开辟的空间.
5. 修改_finish迭代器,使其指向新空间的最后一个数据的下一个位置.
6. 修改_endofstorage迭代器,使其指向新空间容量末尾的下一个位置.
修改容量前后,vector在内存中的情况图示如下:
编辑
综上所述,reserve()函数实现代码如下(该实现包含两大陷阱错误):
void reserve(size_t n)
{
//检查n是否比当前的capacity大,如果小,则不处理
if (n > capacity())
{
T* tmp = new T[n];
if (_start != nullptr)
{
//copy data
memcpy(tmp, _start, sizeof(T) * size());
//delete old space
delete[] _start;
}
//更新三个迭代器指向的位置
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
}
}
上面的代码看似逻辑正确合理,没有什么问题,但是实际上有两个致命的错误:
📌错误1:
//更新三个迭代器指向的位置
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
这段代码的错误原因是假设我们是一个经过无参构造的vector,即此时
_start = _finish = _endofstorage = nullptr ;
然后代码运行到这里时,我们先令:
_start = tmp;
然后我们执行:
_finish = _start + size();
//size:函数实现如下
size_t size() const
{
return _finish - _start;
}
可以看到,因为执行这句代码时,_finish = nullptr,因此这句代码的后果将会导致:
_finish = _start + (nullptr - _start) ;
//即
_finish = _start -_start ;
//即
_finish = 0;
即会导致_finish被赋值为nullptr(无效指针),如果后续还有对_finish的访问操作的话,这将导致程序崩溃.
通过分析,我们清楚这里的问题就是size的计算时出现了问题,解决方法也很简单,我们只需要在还没改变_start的时候设置一个变量提前记录下size,然后在后面给_finish赋值时使用这个变量来代替size即可,综上,修改后的代码如下:
void reserve(size_t n)
{
//检查n是否比当前的capacity大,如果小,则不处理
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start != nullptr)
{
//copy data
memcpy(tmp, _start, sizeof(T) * size());
//delete old space
delete[] _start;
}
/*
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
经典错误,因为size = _finish - _start
而一开始的时候,_start = tmp ,_finish = 0
所以size = -tmp , 然后_finish = _start + (-tmp) = 0;
在这里,0 = nullptr
*/
//正确解决方案是在一开始就计算好size,然后记录下来,在这里使用
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
📌错误2:
我们在之前一起学习过深拷贝和浅拷贝对于类的影响:【C++】详解深浅拷贝的概念及其区别 https://blog.csdn.net/weixin_72357342/article/details/139046865?spm=1001.2014.3001.5501 通过分析知道使用浅拷贝对于有动态开辟空间的类是非常错误的行为,而vector显然满足这个条件,因此我们在前面实现拷贝构造函数和赋值重载函数时都对其使用了深拷贝.但是,显然vector更为特殊的一点是,vector内存放的对象可能也是需要深拷贝的类对象,如:
vector<string> vs;
既然如此,那么我们在拷贝数据时使用memcpy()来拷贝数据就会导致vector内存储的类浅拷贝,这同样会导致浅拷贝出现的诸多问题,因此,我们在这里并不能使用mempcy()来拷贝成员,而应该改为赋值,这样的好处是,vector的成员就可以通过赋值运算符重载去调用它自己的深拷贝逻辑,这样就可以避免成员浅拷贝的问题了,综上,修改后的代码如下:
void reserve(size_t n)
{
//检查n是否比当前的capacity大,如果小,则不处理
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start != nullptr)
{
//copy data
//当vector中存储的数据类型是不能浅拷贝的类型时,会出事
//vector确实没有浅拷贝,但是用memcpy拷贝的数据是浅拷贝的
//memcpy(tmp, _start, sizeof(T) * size());
//改为赋值,让成员去调它自己的赋值拷贝
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
//delete old space
delete[] _start;
}
/*
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
经典错误,因为size = _finish - _start
而一开始的时候,_start = tmp ,_finish = 0
所以size = -tmp , 然后_finish = _start + (-tmp) = 0;
在这里,0 = nullptr
*/
//正确解决方案是在一开始就计算好size,然后记录下来,在这里使用
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
🎏实现vector的insert()函数
insert()函数的作用是在vector的任意位置插入内容.insert()函数的算法逻辑为:
• 判断pos位置是否合理,不合理需要抛出异常
• 判断容量是否够用,如果不够需要扩容
• 挪动后面的数据
• 插入数据到挪出来的位置上
• _size变为_size+n
注意,对于vector的插入逻辑,有一个经典的错误就是迭代器失效问题,迭代器失效问题简单来讲,就是扩容后的_start等迭代器已经指向新空间,而pos还指向旧空间的某个位置:
编辑 在insert函数内部,迭代器失效问题的解决方法就是在扩容之前设置一个变量,提前记录一下pos相对于_start的相对位置,然后在容量调整后就可以借助这个变量准确更新pos的位置了.
但是对于insert外部的pos指针失效问题,是没有办法很好解决的,即传入insert的参数pos可能会因为扩容操作导致原本的pos迭代器失效,因此一般来说,我们创建了一个pos迭代器变量后,如果将其作为参数调用了insert函数,那么正常情况下,后续就不应该再使用这个迭代器了,因为很有可能该迭代器已经因为vector扩容而失效了.但是不排除有些情况下我们确实还需要使用前面的迭代器,对于这个问题STL源码中选择的解决方法是增加一个返回值,通过返回一个迭代器的方式来返回更新后的pos位置,如果后续用户还需要使用这个pos迭代器的话,就可以通过接收返回值的方式来获取更新后正确的迭代器.
综上,insert()函数的实现代码如下:
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
//查满扩容
if (_finish == _endofstorage)
{
//防止因为扩容后原来的_start空间释放导致pos失效,因此提前记录一下pos的相对位置
size_t lpos = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//扩容后更新pos
pos = _start + lpos;
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//insert data
*(pos) = x;
++_finish;
return pos;
}
🎏实现vector的erase()函数
erase()函数的实现逻辑是:要删除pos位置的元素,我们就将pos+1位置的元素挪动到pos位置上,再将pos+2位置的元素挪动到pos+1位置上,以此类推,直到end()-1位置(即最后一个有效数据)挪动到end()-2位置,这样就算是删除了pos位置的元素.在erase()函数元素时,同样会面临迭代器失效问题,因此我们同样通过返回值来解决这个问题,代码如下:
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
🎏实现vector的resize()函数
resize()函数的作用是调整vector的有效数据长度.它接收一个参数n,代表目标有效数据长度,分两种情况来处理:
• 当n<size时,就是缩短数据,我们只需要将_finish向前挪动即可.
• 当n>size时,就是填充数据,我们需要将另一个参数val填充到vector后,直到其长度达到n.
还有一点需要注意的是,填充数据的val是一个缺省参数,即用户可能在调用时并不给指定的参数,这时候我们填充的内容就要去调用vector对象类型的无参构造.
如果是自定义类型,还好说,一般都会有无参构造函数,但是对于内置类型:int,char,double等类型在我们的概念中似乎是没有构造函数的,基于此,C++对内置类型做了升级,使它们也拥有了构造函数.这点在Java中体现的尤为明显,但不是我们当下的重点,所以只是提及一下,避免有朋友对这个地方不理解.
综上,代码如下:
void resize(size_t n, const T& val = T())//C++对内置类型做了升级,它们也有构造函数,所以可以这样写
{
if (n < size)//缩短数据
{
_finish = _start + n;
}
else
{
//调整容量
reserve(n);
//填充数据
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
三.项目完整代码
因为模板定义和声明不能分离,所以我们将程序运行的代码分别在两个工程文件中编辑,完整代码如下:
🎏test.cpp文件
#include<iostream>
#include"vector.h"
using namespace std;
int main()
{
mfc::test_vector();
return 0;
}
🎏vector.h文件
#pragma once
#include<assert.h>
#include<string.h>
#include<iostream>
using namespace std;
namespace mfc
{
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;
}
//n个val的构造函数
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
//n个val的构造函数
//为了应对vector<int> v(10,1)更匹配迭代区间构造参数的问题
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
//用一个迭代器区间去初始化
//[first,last)
template<class InputIterator>
//写成模板,方便使用不是vector的迭代器也可以初始化vector
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
_start = new T[v.capacity()];
//用memcpy,成员会浅拷贝
//memcpy(_start, v.begin(), sizeof(T) * v.size());
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start != nullptr)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
void reserve(size_t n)
{
//检查n是否比当前的capacity大,如果小,则不处理
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start != nullptr)
{
//copy data
//当vector中存储的数据类型是不能浅拷贝的类型时,会出事
//vector确实没有浅拷贝,但是用memcpy拷贝的数据是浅拷贝的
//memcpy(tmp, _start, sizeof(T) * size());
//改为赋值,让成员去调它自己的赋值拷贝
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
//delete old space
delete[] _start;
}
/*
_start = tmp;
_finish = _start + size();
_endofstorage = _start + n;
经典错误,因为size = _finish - _start
而一开始的时候,_start = tmp ,_finish = 0
所以size = -tmp , 然后_finish = _start + (-tmp) = 0;
在这里,0 = nullptr
*/
//正确解决方案是在一开始就计算好size,然后记录下来,在这里使用
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void push_back(const T& x)
{
/*
有了insert(),这个push_back()的完整逻辑就可以不用了,直接复用insert
//查满扩容
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//插入数据
*_finish = x;
++_finish;
*/
insert(end(), x);
}
void pop_back()
{
assert(_start != _finish);
_finish--;
/*
或者可以复用erase()函数
erase(end() - 1);
*/
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
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 insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
//查满扩容
if (_finish == _endofstorage)
{
//防止因为扩容后原来的_start空间释放导致pos失效,因此提前记录一下pos的相对位置
size_t lpos = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//扩容后更新pos
pos = _start + lpos;
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//insert data
*(pos) = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
void resize(size_t n, const T& val = T())//C++对内置类型做了升级,它们也有构造函数,所以可以这样写
{
if (n < size)//缩短数据
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void print(const vector<int>& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.insert(v1.end(),5);
print(v1);
for (int i = 0; i < v1.size(); i++)
{
v1[i]++;
}
print(v1);
vector<int>::iterator p = v1.begin() + 3;
v1.insert(p, 99);
//外部insert后可能迭代器有失效风险
//失效原因主要是扩容导致_start和pos迭代器的相对位置改变
//而内部迭代器失效解决后并不能影响外部,故我们在使用的时候就要注意
//在insert后尽量不要再使用之前的形参迭代器.
//如果非要用,insert()的返回值是新的pos位置的迭代器
//那你在调用时就要注意接收这个返回值以便更新pos
vector<int>::iterator it = v1.end() - 1;
v1.erase(it);
print(v1); //打印 2 3 4 99 5
cout << *it << endl; //打印 6
//很明显it已经失效了,这个时候还使用it是一种非法的危险行为
//没有崩溃还能正常显示是因为实现的时候删除的元素不做处理,只是缩小范围.
vector<string> vs;
vs.push_back("111111");
vs.push_back("222222");
vs.push_back("333333");
vs.push_back("444444");
vs.push_back("555555");
}
}
结语
希望这篇vector的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
相关文章推荐
编辑
- 点赞
- 收藏
- 关注作者
评论（0）