C++ vector模拟实现
- 一.我们要实现的大致框架
- 1.STL库中是如何实现的呢?
- 1.迭代器
- 2.成员变量
- 3.vector的特性
- 4.vector的成员变量大致情况
- 2.我们要实现的大致框架
- 3.前言
- 二.具体实现
- 1.迭代器,begin,end
- 2.无参构造,析构,简单函数
- 3.push_back
- 4.reserve
- 1.reserve的第一大坑点:野指针问题
- 1.reserve的第二大坑点:浅拷贝问题
- 3.正确版本
- 5.resize
- 6.insert
- 1.insert内部的迭代器失效问题
- 2.insert外部的迭代器失效问题
- 7.erase
- 1.erase的实现
- 2.erase外部的迭代器失效问题
- 8.push_back和pop_back对于insert和erase的复用
- 1.push_back
- 2.pop_back
- 9.含参构造
- 10.迭代器区间构造
- 11.拷贝构造
- 1.传统写法
- 2.现代写法
- 12.赋值运算符重载
- 1.传统写法
- 2.现代写法
- 三.完整代码
首先我们先明确一点:
对于vector而言,最难的点是
1.它如何进行设计与封装的
2.迭代器失效问题
3.memcpy,memmove导致的浅拷贝问题
而不是顺序表的基础操作
一.我们要实现的大致框架
1.STL库中是如何实现的呢?
1.迭代器
vector中的迭代器其实就是指针
因为vector的底层物理空间是连续的(vector其实就是数据结构中的顺序表)
2.成员变量
也就是说STL库中的vector容器维护的是3个指针:start finish end_of_storage
关于这三个指针大家一定要牢记它们的作用,因为下面全是对这三个指针的操作
3.vector的特性
注意:vector作为STL库中的容器,是采用泛型编程和面向对象的思想来设计的
vector的元素不仅仅可以是内置类型,也可以是自定义类型,其他容器类型
其实是因为vector采用了类模板的技术,因此vector可以存放所有类型的数据
例如
vector<string>
vector<vector<xxx>>
vector<int>
vector<list>
等等等等....
4.vector的成员变量大致情况
其实vector中成员变量大致情况就是这样的
也就是说接下来我们所有的操作都是通过操作
_start _finish _endOfStorage这三个指针来完成的
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
namespace wzs
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}
2.我们要实现的大致框架
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
namespace wzs
{
template<class T>
class vector
{
public:
///
// 构造,拷贝构造,赋值运算符重载,析构
vector();
vector(int n, const T& value = T());
template<class InputIterator>
//迭代器区间构造
vector(InputIterator first, InputIterator last);
//拷贝构造函数传统写法
vector(const vector<T>& v);
//拷贝构造函数现代写法
vector(const vector<T>& v);
//赋值运算符重载传统写法
vector<T>& operator=(const vector<T>& v);
//赋值运算符重载现代写法
vector<T>& operator=(vector<T> v);
~vector();
/
// 迭代器相关
// vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
//
// 容量相关
size_t size() const;
size_t capacity() const;
void reserve(size_t n);
void resize(size_t n, const T& value = T());
bool empty() const;
///
// 元素访问
//operator[]运算符重载
T& operator[](size_t pos);
const T& operator[](size_t pos)const;
//返回第一个数据的引用
T& front();
const T& front()const;
//返回最后一个有效数据的引用
T& back();
const T& back()const;
/
// vector的修改操作
void push_back(const T& x);
void pop_back();
void swap(vector<T>& v);
//返回插入的元素的位置
iterator insert(iterator pos, const T& x);
//返回被删除的位置的下一个位置
iterator erase(iterator pos);
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}
3.前言
为了更好地演示整个实现过程,
首先我们先实现
1.迭代器
2.无参构造函数,析构函数和其他一些很简单的函数
3.push_back
4.reserve
5.resize
6.insert
7.erase 然后是push_back和pop_back的复用
8.含参构造函数
9.迭代器区间构造函数
10.拷贝构造函数和赋值运算符重载
期间
在介绍reserve的时候我们会介绍本文的第一个重点:
memcpy/memmove导致的浅拷贝问题
在介绍insert和erase的时候我们会介绍本文的第二个重点:
迭代器失效问题
二.具体实现
1.迭代器,begin,end
刚才说明了vector的迭代器其实就是指针类型,因此我们就可以这么来定义
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;
}
对于vector来说,iterator很简单,就是原生指针
2.无参构造,析构,简单函数
无参构造:
vector()
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{}
析构:
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
// 容量相关的简单函数
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
bool empty() const
{
return _finish == _start;
}
// 元素访问的简单函数
T& operator[](size_t pos)
{
return _start[pos];
}
const T& operator[](size_t pos)const
{
return _start[pos];
}
T& front()
{
return *_start;
}
const T& front()const
{
return *_start;
}
T& back()
{
return *(_finish - 1);
}
const T& back()const
{
return *(_finish - 1);
}
注意:
front是第一个有效数据的引用
back是最后一个有效数据的引用
operator[]是下标访问运算符重载,跟数组的下标访问是一样的用法
3.push_back
下面我们就来实现push_back
void push_back(const T& x)
{
//扩容
if (size() == capacity())
{
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//尾插
*_finish = x;
++_finish;
}
先扩容,后尾插
4.reserve
相信上面的那些函数对大家来说没有什么挑战
下面我们就来看一下reserve的实现过程中的坑点吧
reserve函数:扩容函数
1.reserve的第一大坑点:野指针问题
void reserve(size_t n);
如果n<=capacity:那么就不会进行任何操作(在这里我们不考虑缩容的情况,reserve是否可以缩容取决于编译器的具体实现)
只有当n>capacity时才会扩容
大家看一下这份代码有问题吗?
void reserve(size_t n)
{
if (n > capacity())
{
//1.申请新空间
T* tmp = new T[n];
//2.将原有数据拷贝到新空间当中
memmove(tmp, _start, sizeof(T) * size());
//3.释放原有空间
delete _start;
//4.指向新空间
_start = tmp;
_finish = _start + size();
_endOfStorage = _start + capacity();
}
}
其实是有问题的,_finish和_endOfStorage会成为野指针
原因如下:
给大家调试来看一下:
可以看出,扩容结束之后,_finish和_endOfStorage仍然还是指向旧空间的对应位置
那么应该怎么办呢?
其实我们可以把旧空间的size保存下来
记为oldSize,这样只需要
_finish = _start + oldSize; 即可将_finish也指向新空间的相应位置
而_endOfStorage呢?
因为新空间的容量是n
所以
_endOfStorage = _start + n; 即可将_endOfStorage也指向新空间的相应位置
因此下面的代码才是"正确"的
void reserve(size_t n)
{
if (n > capacity())
{
//1.保存原有空间的size
int oldSize = size();
//2.开辟新空间
T* tmp = new T[n];
//3.将原有空间的数据拷贝到新空间当中
memmove(tmp, _start, sizeof(T) * oldSize);
//4.释放旧空间
delete _start;
//5.指向新空间
_start = tmp;
_finish = _start + oldSize;
_endOfStorage = _start + n;
}
}
分为5步:
1.保存原有空间的size
2.开辟新空间
3.将原有空间的数据拷贝到新空间当中
4.释放旧空间
5.指向新空间
下面我们来调试看一下:
1.reserve的第二大坑点:浅拷贝问题
刚才那个代码其实也是不正确的
不过他不正确的原因是因为memmove的底层实现其实是浅拷贝
是以字节为单位进行拷贝的
因为刚才我们这个vector里面存放的数据类型是int这种内置类型
而对于内置类型来说是不会受到浅拷贝的影响的
不过对于开辟在堆上的自定义类型来说就会受到浅拷贝的影响导致出现同一内存空间多次释放的错误
比方说此时vector里面存放的是string类型
第二次扩容之前是没有任何问题的
不过当他发生了扩容之后
崩了,断言报错
为什么呢?
而且:
delete的时候会先调string的析构函数把string都析构(string的空间在string的析构函数当中释放)了,然后才会释放_start这个旧空间
3.正确版本
因为我们实现的在堆上开辟了空间的自定义类型都是有赋值运算符重载的,而我们实现的赋值运算符重载都是深拷贝
因此我们可以这样修改
void reserve(size_t n)
{
if (n > capacity())
{
//提前保存偏移量oldSize
int oldSize = size();
//1.申请新空间
T* tmp = new T[n];
//2.将原有空间中的数据拷贝到新空间当中
for (int i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
//内置类型直接赋值即可,自定义类型会调用其赋值运算符重载,实现深拷贝
}
//3.释放原有空间
delete[] _start;
//4.将_start,_finish,_endOfStorage都指向到新空间
_start = tmp;
_finish = _start + oldSize;
_endOfStorage = _start + n;
}
}
此时就没有任何问题了
5.resize
resize:调整有效数据的个数
void resize(size_t n, const T& value = T())
作用是:
1.n<size:只保留该对象的前n个数据,其余数据全都删除
2.size<=n<=capacity:尾插value,直到该对象的size==n
同含参构造,value是缺省参数,默认值是T()
3.n>capacity:扩容+尾插数据
就是在进行尾插之前因为容量不够而需要扩容
扩容结束之后继续尾插
void resize(size_t n, const T& value = T())
{
//1.n<size:删除数据
if (n < size())
{
//将_finish移动到_start向后偏移n个单位的位置
//我们知道:[_start,_finish)才是有效数据
//因此就是只让前n个数据作为有效数据
_finish = _start + n;
}
//2.size<=n<=capacity: 尾插数据
else if (n <= capacity())
{
while (size() < n)
{
push_back(value);
}
}
//3.n>capacity:扩容+尾插数据
else
{
reserve(n);
while (size() < n)
{
push_back(value);
}
}
}
注意:
n<size时:
我们知道:[_start,_finish)才是有效数据
因此_finish = _start + n;就是只让前n个数据作为有效数据
6.insert
1.insert内部的迭代器失效问题
大家看一下这个代码有没有问题?
iterator insert(iterator pos, const T& x)
{
//检查pos的合法性
assert(pos >= _start && pos <= _finish);
//需要扩容的话扩容
if (size() == capacity())
{
//扩容
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//开始insert
//把[pos,_finish)的数据往后挪
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
--end;
}
//插入数据
*pos = x;
//更新size
++_finish;
return pos;
}
此时崩了,为什么呢?
我们来调试看一下:
我们可以看出:是因为扩容之后pos这个迭代器没有指向新空间
因此就会发生各种任何意想不到的错误
下面给大家画了一张图来帮助大家理解
经过前面reserve的野指针问题的启发,我们就能够很好地解决这个问题:
//发生扩容之后pos迭代器会失效,因此需要在扩容之前先保存偏移量,并在扩容之后重新调整pos迭代器的位置
iterator insert(iterator pos, const T& x)
{
//检查pos的合法性
assert(pos >= _start && pos <= _finish);
//需要扩容
if (size() == capacity())
{
//先保存pos的偏移量
int gap = pos - _start;
//扩容
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//调整pos的位置
pos = _start + gap;
}
//开始insert
//把[pos,_finish)的数据往后挪
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
--end;
}
//插入数据
*pos = x;
//更新size
++_finish;
return pos;
}
此时就能成功运行了
2.insert外部的迭代器失效问题
大家可能会有一些疑惑:为什么insert要有返回值呢?
而且为什么返回值类型是iterator呢?
因为
所以设计STL库的大佬就规定:vector里面的insert需要返回插入的数据的迭代器
因此我们可以通过接收返回值的方式来让it这个迭代器"续命"
7.erase
1.erase的实现
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
//保存pos
iterator tmp = pos;
//把[pos+1,_finish)的数据往前挪一格
while (pos < _finish - 1)
{
*pos = *(pos + 1);
++pos;
}
//调整size
--_finish;
return tmp;
}
2.erase外部的迭代器失效问题
大家可能会有疑惑:为什么erase也会有迭代器失效问题呢?
别急,我们通过一个例子来验证一下:
比方说:一个数组当中删除所有的偶数
结果是1 2 3 5,没删干净啊?
为什么呢?
也是迭代器失效导致的
刚才还是好的情况,如果最后一个元素是偶数的话
就会因为越界访问而报错
为什么呢?
跟刚才一样
那么怎么办呢?
erase返回被删除的元素的下一个位置
因此我们可以这样做:
因此,对于insert和erase来说:
我们认为insert和erase的迭代器都会失效,不能再访问了,结果是未定义的(也取决于编译器的具体实现)
如果想要继续使用 请接收返回值
8.push_back和pop_back对于insert和erase的复用
1.push_back
复用前:
void push_back(const T& x)
{
//空间不够的话要扩容
if (size() == capacity())
{
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//尾插数据
*_finish = x;
++_finish;
}
复用后:
void push_back(const T& x)
{
insert(end(), x);
}
2.pop_back
复用前:
void pop_back()
{
assert(!empty());
--_finish;
}
复用后:
void pop_back()
{
erase(_finish - 1);
}
9.含参构造
vector支持这样来构造:vector<int> v(10,99):意思是构造v这个对象时向里面写入10个99
vector<int> v(10):意思是构造v这个对象时向里面写入10个0(int的默认值是0)
//用n个value来构造该对象
vector(int n, const T& value = T())
//1.先初始化为nullptr
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
//2.预扩容:扩容为n个大小,将capacity扩容为n
reserve(n);
//3.尾插这n个数据(value)
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
注意:
1.这是一个半缺省构造函数,value的默认值是T()
2.这里的T()是匿名对象(是调用T这个类型的默认构造函数生成的)
在模板这个语法出现之后C++支持了内置类型的默认构造函数
int a();//默认用0来构造a
int a(10);//就是用10来构造a
同理:double默认用0.0构造 int*默认用nullptr来构造 等等等等....
其实整个步骤就是:
1.先初始化为nullptr
2.预扩容:扩容为n个大小,将capacity扩容为n
3.尾插这n个数据(value)
10.迭代器区间构造
template<class InputIterator>
//迭代器区间构造
//用[first,last)这个区间内的数据来构造该对象
vector(InputIterator first, InputIterator last)
//1.初始化为nullptr
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
//2.尾插
while (first != last)
{
push_back(*first);
first++;
}
}
注意:
1.如果依然使用iterator做迭代器来构造,会导致初始化的迭代器区间[first,last)只能是vector的迭代器
因此需要重新声明迭代器,让迭代器区间[first,last)可以是任意容器的迭代器
2.然后后面依然是初始化和尾插的操作
11.拷贝构造
1.传统写法
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
reserve(v.capacity());
for (auto& e:v)
{
push_back(e);
}
}
我们可以直接预扩容,然后尾插即可
2.现代写法
//现代写法:复用构造函数+swap即可
vector(const vector<T>& v)
//1.初始化为nullptr
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
//2.利用迭代器区间构造来构造一个临时变量tmp
vector<T> tmp(v.begin(), v.end());
//3.交换this和tmp
swap(tmp);
}
注意:swap之后原有的this会通过tmp这个形参析构,因此需要先将:_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) 初始化为空指针然后再swap
否则会因为delete时释放野指针指向的空间导致出错
12.赋值运算符重载
1.传统写法
vector<T>& operator=(const vector<T>& v)
{
//防止自己给自己赋值
if (this != &v)
{
//1.开辟新空间
T* tmp = new T[v.capacity()];
//2.将数据拷贝到新空间当中
for (int i = 0; i < v.size(); i++)
{
tmp[i] = v._start[i];
}
//3.释放原有空间
delete[] _start;
//4.指向新空间
_start = tmp;
_finish = _start + v.size();
_endOfStorage = _start + v.capacity();
}
return *this;
}
2.现代写法
//赋值运算符重载现代写法
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//只需要交换this和v的三个指针即可
void swap(vector<T>& v)
{
//调用标准库中的swap函数
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
我们知道:传值传参时:自定义类型会调用其拷贝构造函数形成形参
形参是实参的一份临时拷贝,因此我们可以让这个形参跟我们的this交换
这样的话就可以一举两得:
1.我们的this就成功被赋值为我们想要的值了
2.this指向的旧空间在交换后被形参v所指向,出了这个作用域之后,形参v会调用其析构函数释放掉this指向的旧空间
因此只需要传值传参+swap交换就可以完成开辟新空间+拷贝数据+释放原有空间+指向新空间这4个步骤了
不过大家请注意:这里一定要传值传参
如果传引用:那么就是swap了,而不是赋值了
三.完整代码
#include <iostream>
using namespace std;
#include <string>
#include <assert.h>
namespace wzs
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
///
// 构造和销毁
vector()
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{}
vector(size_t n, const T& value = T())
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
reserve(n);
while (n--)
{
push_back(value);
}
}
vector(int n, const T& value = T())
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(n);
while (n--)
{
push_back(value);
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
reserve(v.capacity());
for (auto& e:v)
{
push_back(e);
}
}
vector<T>& operator=(const vector<T>& v)
{
//防止自己给自己赋值
if (this != &v)
{
//1.开辟新空间
T* tmp = new T[v.capacity()];
//2.将数据拷贝到新空间当中
for (int i = 0; i < v.size(); i++)
{
tmp[i] = v._start[i];
}
//3.释放原有空间
delete[] _start;
//4.指向新空间
_start = tmp;
_finish = _start + v.size();
_endOfStorage = _start + v.capacity();
}
return *this;
}
//现代写法
//vector<T>& operator=(vector<T> v)
//{
// swap(v);
// return *this;
//}
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
/
// 迭代器相关
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//
// 容量相关
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
bool empty() const
{
return _finish == _start;
}
//错误版本1
//void reserve(size_t n)
//{
// if (n > capacity())
// {
// //1.申请新空间
// T* tmp = new T[n];
// //2.将原有数据拷贝到新空间当中
// memmove(tmp, _start, sizeof(T) * size());
// //3.释放原有空间
// delete _start;
// //4.指向新空间
// _start = tmp;
// _finish = _start + size();
// _endOfStorage = _start + capacity();
// }
//}
//错误版本2
//void reserve(size_t n)
//{
// if (n > capacity())
// {
// //1.保存原有空间的size
// int oldSize = size();
// //2.开辟新空间
// T* tmp = new T[n];
// //3.将原有空间的数据拷贝到新空间当中
// memmove(tmp, _start, sizeof(T) * oldSize);
// //4.释放旧空间
// delete _start;
// //5.指向新空间
// _start = tmp;
// _finish = _start + oldSize;
// _endOfStorage = _start + n;
// }
//}
void reserve(size_t n)
{
if (n > capacity())
{
//提前保存偏移量oldSize
int oldSize = size();
//1.申请新空间
T* tmp = new T[n];
//2.将原有空间中的数据拷贝到新空间当中
for (int i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
//内置类型直接赋值即可,自定义类型会调用其赋值运算符重载,实现深拷贝
}
//3.释放原有空间
delete[] _start;
//4.将_start,_finish,_endOfStorage都指向到新空间
_start = tmp;
_finish = _start + oldSize;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
//1.n<size:删除数据
if (n < size())
{
_finish = _start + n;
}
//2.n>size:插入数据直到size==n为止
else
{
//先扩容
reserve(n);
//尾插数据
while (size() < n)
{
push_back(value);
}
}
}
///
// 元素访问
T& operator[](size_t pos)
{
return _start[pos];
}
const T& operator[](size_t pos)const
{
return _start[pos];
}
T& front()
{
return *_start;
}
const T& front()const
{
return *_start;
}
T& back()
{
return *(_finish - 1);
}
const T& back()const
{
return *(_finish - 1);
}
/
// vector的修改操作
//void push_back(const T& x)
//{
// //空间不够的话要扩容
// if (size() == capacity())
// {
// int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
// }
// //尾插数据
// *_finish = x;
// ++_finish;
//}
//复用insert
void push_back(const T& x)
{
insert(end(), x);
}
/*void pop_back()
{
assert(!empty());
--_finish;
}*/
//复用erase
void pop_back()
{
erase(_finish - 1);
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
//错误版本:pos迭代器会失效
//iterator insert(iterator pos, const T& x)
//{
// //检查pos的合法性
// assert(pos >= _start && pos <= _finish);
// //需要扩容的话扩容
// if (size() == capacity())
// {
// //扩容
// int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
// }
// //开始insert
// //把[pos,_finish)的数据往后挪
// iterator end = _finish;
// while (end > pos)
// {
// *end = *(end - 1);
// --end;
// }
// //插入数据
// *pos = x;
// //更新size
// ++_finish;
// return pos;
//}
//发生扩容之后pos迭代器会失效,因此需要在扩容之前先保存偏移量,并在扩容之后重新调整pos迭代器的位置
iterator insert(iterator pos, const T& x)
{
//检查pos的合法性
assert(pos >= _start && pos <= _finish);
//需要扩容
if (size() == capacity())
{
//先保存pos的偏移量
int gap = pos - _start;
//扩容
int newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//调整pos的位置
pos = _start + gap;
}
//开始insert
//把[pos,_finish)的数据往后挪
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
--end;
}
//插入数据
*pos = x;
//更新size
++_finish;
return pos;
}
// 返回删除数据的下一个数据
// 方便解决:一边遍历一边删除的迭代器失效问题
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
//保存pos
iterator tmp = pos;
//把[pos+1,_finish)的数据往前挪一格
while (pos < _finish - 1)
{
*pos = *(pos + 1);
++pos;
}
//调整size
--_finish;
return tmp;
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}
以上就是C++ vector模拟实现的全部内容,希望能对大家有所帮助!
