【C++】——Vector的模拟实现

                                           博主主页：Yan. yan.
                                              C语言专栏
                                            数据结构专栏
                                         力扣牛客经典题目专栏
                                                     C++专栏

一、Vector的成员变量

  我们以类模板的方式来实现Vector的实现。

template<class T>

  类型名称也重新进行修改

typedef T* iterator;
typedef const T* const_iterator;

根据库的实现方式，成员函数如下：

private:iterator _start;iterator _finish;iterator _end_of_storage;

二、默认成员函数

1、构造函数

构造函数可分为3种：

• 无参构造
• 构造n个val对象
• 根据迭代区间构造
  对于无参的构造，我们只需要初始化成员函数即可。
  
  
  无参构造

//无参构造函数
vector()//:_start(nullptr)//,_finish(nullptr)//,_end_of_storage(nullptr)
{}

构造n个val对象

//构造n个对象
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//1.开空间reserve(n);//2.将空间填充为val对象for (size_t i = 0; i < capacity(); i++){_start[i] = val;}//也可以复用resize//resize(n, val);
}

注意：这里在构造时必须初始化，如果不初始化，在调用reserve函数开空间时会出现访问野指针的问题。也可以调用resize函数进行拷贝构造n个对象。

使用迭代区间进行构造
同理，如果不初始化，会出现扩容后访问野指针的情况。

template<class Inputiterator>
vector(Inputiterator first, Inputiterator last)
{while (first != last){push_back(*first);++first;}
}

2、拷贝构造函数

vector(const vector<T>& v)
//这里必须初始化，否则扩容时会访问不属于自己的空间
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
//如果私有成员给了缺省值，就不用再再次初始化了
{
reserve(v.capacity());
//memcpy(_start, v._start, sizeof(T) * v.size());
//这里使用memcpy的错误跟扩容的错误一样，不再赘述
for (size_t i = 0; i < v.size(); i++) // 如果是string类，会调用string的赋值重载，赋值重载调用string的拷贝构造，完成深拷贝
{_start[i] = v._start[i];
}_finish = _start + v.size();
}

拷贝构造需要注意的几个问题：

• 拷贝构造同构造函数一样，如果不初始化，在开空间时会出现访问野指针的情况。
• 拷贝构造必须进行深拷贝，否则如果vector的对象是自定义类型，比如string，会出现两次释放同一块空间的问题。

3、析构函数

释放_start指向的空间，然后全部置为空即可。

~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage;}
}

三、增删查改工作

说明size()和capapcity()

size的大小为_finish - _start
capacity的大小为_end_of_storage - _start

1、reserve()

该函数的作用是：扩容。

void reserve (size_type n);

• 思路：
• 如果要扩容的大小n小于capacity，则不会缩容。
• 否则执行扩容。
• 先申请一块n大小的空间
• 拷贝原空间的数据到新空间，并释放原空间
• 将新空间的数据交给_start管理。

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n]; size_t sz = size();if (_start){for (size_t i = 0; i < sz, i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

2、 resize（）

该函数的功能是：重新改变vector容器的大小，让其到达n。新的空间默认初始化为val。

• 思路：
• 如果n小于size，则让_finish指向_start + n位置。
• 如果n大于等于size，先调用reserve函数进行扩容，再将新的空间填充为val。

void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{//扩容到n,如果n<capacity()，则啥事不做，否则，扩容到nreserve(n);//将多的空间全部设置成缺省值while (_finish != _start + n){*_finish = val;++_finish;}}}

3、insert()

该函数的作用是：在pos位置插入模板对象val。

• 思路：
• 插入元素前先检查容量
• 如果容量满了,则调用reserve函数执行扩容操作
• 然后从pos位置开始将其之后的元素全部都往后挪。
• 再在pos位置插入val。

void insert(iterator pos, const T& val)
{
assert(pos <= _finish);
//插入前先检查扩容
if (_finish == _end_of_storage)
{size_t oldpos = pos - _start;//记录相对位置size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + oldpos;
}//记录旧的size，防止出现迭代器失效问题。//将pos之后的位置往后挪，再插入
iterator end = _finish - 1; // reserve之后，_finish也跟着更新了。
while (end >= pos)
{*(end + 1) = *end;--end;
}*pos = val;
_finish += 1;
}

4、erase（）

该函数的功能是：删除pos位置的值。

iterator erase(iterator pos)
{assert(pos < _finish);iterator end = pos;while (end != _finish){*end = *(end + 1);++end;}--_finish;return pos;
}

有一个需要注意的点：当我们删除元素后，pos迭代器就会失效，因为空间已经释放，这时候不能使用pos迭代器。
解决方法：返回删除位置的下一个元素的位置，即pos位置。
然而，在只剩下一个待删除元素或者删除最后一个位置的元素时，不能再使用pos迭代器。

四、[]重载和迭代器

1、begin迭代器

返回_start地址即可。

iterator begin()
{return _start;
}const_iterator begin() const
{return _start;
}

2、end迭代器

返回_finish地址即可。

iterator end()
{return _finish;
}const_iterator end() const
{return _finish;
}

3、[]运算符重载

只需给定pos下标即可。
在此之前需要判断pos位置不能超过整个顺序表的size大小。

T& operator[]( size_t pos)
{assert(pos < size());return *(_start + pos);
}//不可修改的
const T& operator[]( size_t pos) const
{assert(pos < size());return *(_start + pos);
}