文章目录
- 一.vector的基本结构
- 二.构造函数调用不明确
- 三.迭代器失效（其实是野指针问题）
- a.扩容导致的迭代器失效
- b.意义不同
- 四.深层次的深浅拷贝
- 五.整体代码实现
有了前面模拟实现string的经验，vector对大家来说也不会算很难。vector本质也就是一个空间可以动态变化的数组，所以这里就挑一些些容易踩坑的地方讲解一下，在最后会附上我的完整代码。
因为vector中没有使用size以及capacity而是使用了迭代器，在避免了整形转无符号整形的同时，也产生了如迭代器失效的新问题。此外因为vector本身是一个模板，也就是vector可以再嵌套一个vector，如果在扩容阶段会有一个深层次的深拷贝问题。
一.vector的基本结构
class vector {
public:
typedef T value_type;//可以看到这里所谓的value_type其实是T的重命名
typedef value_type* iterator;//迭代器
typedef const value_type* const_iterator;//const迭代器
protected:
iterator start;//这个是指向数组空间的首地址，相当于顺序表中的int*a
iterator finish;//这个相当于size
iterator end_of_storage;//相当于capacity
}
以上是我从sgi版本源代码中抽取出来的主要框架，在我们现阶段的学习中不建议去大量的阅读源代码，但可以从某些实现细节上以及它的整体框架去阅读。
这里附上sgi版本的stl30源码：
链接：https://pan.baidu.com/s/1lKls7ne0iiZJz6tsQEgufw
提取码：0325
下面再通过一张图来看一下整体结构
通过上图不难发现，我们可以通过end _ of _storag - start 得到vector的容量，通过finish - start得到vector的size
虽然我的模拟实现整体是跟着sgi版本的，但是在扩容的时候选择了扩二倍。
学习STL并不是为了造轮子，我们也很难造出比大佬们更好的轮子，之所以模拟实现STL是为了能更好的弄清STL中的一些小细节。
二.构造函数调用不明确
//使用n个val来构造
vector(size_t n, const T& val = T())//这里的size_t会导致调用不明确
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);//提前开好空间，减少后续扩容带来的损耗
for (size_t i = 0; i < n; i++)
{
push_back(val);//复用尾插
}
}
//用一段迭代器区间来构造this
template <class InputIterator>
vector(InputIterator first,InputIterator end)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != end)
{
push_back(*first);
first++;
}
}
这里说什么非法的间接寻址，这个报错属实恶心，原因如下：
在模板中提到过，编译器会自主选择最匹配的函数，在这个构造函数，我们本想调用一个构造函数（使用n个val构造），但是我们对n使用了size_t类型，而3和6都是int类型。
对于第一个构造函数来说，编译器需要将int类型强转为size_t，但是第二个构造函数是一个模板，可以直接将类型推演成int，直接就将两个类型都匹配上了不用强转。那么编译器选择最合适的当然会选择第二个模板参数的构造函数咯，但是第二个构造函数内部对first进行了解引用，这里传过去的first只是一个整形，所以就报错了。
解决办法就是多重载一个int类型的
三.迭代器失效（其实是野指针问题）
a.扩容导致的迭代器失效
void insert(iterator pos, const T& val)//这里给个返回值是为了解决迭代器失效,pos异地扩容的情况下也是会失效,所以内部处理需要更新pos位置
{
//如果size为零呢？对于这个问题，我们的迭代器就控制了第一次插入是不能用insert的,也就是说如果使用迭代器作为参数，则vector必须要有元素
if (size() == 0)
{
push_back(val);
}//其实不判断也行
else
{
assert(pos >= _start);
assert(pos < _finish);//分开写能更好的界定错误
if (_finish == _endofstorage)
{
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
//减完以后直接插入
*pos = val;
++_finish;
}
}
第五个值变成了随机值，是因为扩容可能是异地扩，一旦异地扩那么pos原本指向的那块空间就被释放了，pos也就变成了一个野指针因此无法在正确的位置插入我们想要的元素。
解决办法就是在如果要扩容（扩容有异地和原地，这里一律认为是异地扩），那么就更新pos的位置。
在扩容之前记住_start 和pos的相对位置，然后扩容之后再给 _start加上这个相对长度就可以在新空间中拿到正确的pos位置。
此外还要给一个返回值，因为我们将it传过去以后，it变成了野指针不能再使用了，如果我还要使用就也要更新，使用返回值来更新是一个好办法，更改代码如下：
iterator insert(iterator pos, const T& val)//这里给个返回值是为了解决迭代器失效,pos异地扩容的情况下也是会失效,所以内部处理需要更新pos位置
{
//如果size为零呢？对于这个问题，我们的迭代器就控制了第一次插入是不能用insert的,也就是说如果使用迭代器作为参数，则vector必须要有元素
if (size() == 0)
{
push_back(val);
}
else
{
assert(pos >= _start);
assert(pos < _finish);//分开写能更好的界定错误
if (_finish == _endofstorage)
{
int len = pos - _start;
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
//扩完容就要插入,防止异地扩解决失效，首先要更新pos
pos = _start + len;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
//减完以后直接插入
*pos = val;
++_finish;
}
return pos;
}
b.意义不同
除了在插入的时候有迭代器失效的问题以外，在删除元素的时候也会有迭代器失效的问题，相对于插入而言删除时的失效稍微难理解一些。下面我们来看这样一个现象：
void Test_vector3()
{
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
std:vector<int>::iterator it = find(v.begin(), v.end(), 3);
v.erase(it);
cout << *it << endl;
}
int main()
{
Test_vector3();
return 0;
}
调用库中的vector进行删除操作，删完以后再访问一下这个迭代器，看起来没什么问题，但是编译器报错了哦。
连读操作都报错了，那么写操作更不用说肯定是会报错的，这里报错是因为VS认为删除操作以后迭代器是失效的了的，它调用了一个函数去检查。如果将同样的代码放到g++中去测试，就会发现并不会报错。
如果去考虑最边界的情况，比如it迭代器是finish的前一个，这是删除以后这个迭代器确确实实是会失效的。
所以不论是为了程序的稳定性还是可移植性，都建议将erase以后的迭代器认为是失效的。
处理办法和insert类似，加一个返回值即可，库中也是给定了返回值的。
iterator erase(iterator pos)//这里有一个迭代器失效，并不是野指针类的，而是因为意义不同了，有时候也是真的会野指针
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos;
while (end < _finish)
{
*end = *(end + 1);
end++;
}
_finish--;
return pos;
}
四.深层次的深浅拷贝
引发这个问题的主要原因是因为我在实现扩容的时候采用的拷贝方式是使用memcpy函数进行拷贝的：
void reserve(size_t n)
{
//不缩容
if (n > capacity())
{
//新开辟一块空间，释放旧空间
T* tmp = new T[n];
int oldsize = size();
if (_start)
{
//之前的空间不是空，就拷贝
memcpy(tmp, _start, oldsize * sizeof(T));//这里有一个浅拷贝问题，memcpy是浅拷贝，不得行
}
_start = tmp;
_finish = tmp + oldsize;
_endofstorage = tmp + n;
}
}
众所周知memcpy的拷贝方式是按字节拷贝的，也就是浅拷贝，但是vector内部是一个模板，也就是说可能存在这样的情况：
vector<vector<int>>
如果vector的模板参数还是一个自定义类型的话，就很容易造成深层次的浅拷贝问题。
浅拷贝图解
最核心的地方在于，memcpy只是按字节拷贝，没有改变_start的指向。而delete又会调用析构函数，释放了 _start的空间，使其变成了野指针。
解决
void reserve(size_t n)
{
//不缩容
if (n > capacity())
{
//新开辟一块空间，释放旧空间
T* tmp = new T[n];
int oldsize = size();
if (_start)
{
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
//要开空间然后拷贝再更新指针指向
delete[]_start;
}
_start = tmp;
_finish = tmp + oldsize;
_endofstorage = tmp + n;
}
}
这里复用了赋值重载，赋值重载使用的是传值传参，形参是实参的一份临时拷贝，所以在传参的时候就已经开辟好了空间，并且在内部调用了swap函数，交换了_start的指向。
五.整体代码实现
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
//直接上手手搓一个
namespace wbm
{
template<class T>
class vector
{
public:
//vector采用迭代器，这里使用指针实现
typedef T* iterator;
typedef const T* const_iterator;
//首先上来手搓构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
//使用n个val来构造
vector(size_t n, const T& val = T())//这里采用的是匿名对象初始化T
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);//提前开好空间，减少后续扩容带来的损耗
for (size_t i = 0; i < n; i++)
{
push_back(val);//复用尾插
}
}
//用一段迭代器区间来构造this
template <class InputIterator>
vector(InputIterator first,InputIterator end)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != end)
{
push_back(*first);
first++;
}
}
//拷贝构造可以复用上面利用迭代器的构造
vector(vector& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());//创建一个临时对象，然后将临时对象用v的迭代器区间初始化
swap(tmp);
}
//析构
~vector()
{
//释放空间然后置空
delete[]_start;
_start = _finish = _endofstorage = nullptr;
}
//快速搓起来，先整迭代器和尾插， vector不提供头插函数因为效率太低，如果偶尔头插可以使用insert
//要插入元素就会涉及扩容的问题，所以要先实现扩容,要扩容就要判断容量，所以要给获取容量等函数
void reserve(size_t n)
{
//不缩容
if (n > capacity())
{
//新开辟一块空间，释放旧空间
T* tmp = new T[n];
int oldsize = size();
if (_start)
{
//之前的空间不是空，就拷贝
//memcpy(tmp, _start, oldsize * sizeof(T));//这里有一个浅拷贝问题，memcpy是浅拷贝，不得行
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
//要开空间然后拷贝再更新指针指向
delete[]_start;
}
_start = tmp;
_finish = tmp + oldsize;
_endofstorage = tmp + n;
}
}
void resize(size_t n,T val=T())//要有默认初始值,初始化后面的值,这里是生成一个匿名对象来初始化它
{
//在我看来改变size不一定要改变capacity，如果要更改的size大于capacity，那就必须扩容
if (n > capacity())
{
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
}
//改变size就是改变_finish
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
else
{
_finish = _start + n;
}
}
void push_back(const T& x)
{
//_finish指向的是末尾元素的下一个位置
//首先判断一下是否需要扩容那个
if (_finish == _endofstorage)
{
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(!empty());//是空还删毛
//尾删，直接挪动_finish
_finish--;
}
void clear()//不动空间
{
_finish = _start;
}
//iterator insert (iterator position, const value_type& val);
iterator insert(iterator pos, const T& val)//这里给个返回值是为了解决迭代器失效,pos异地扩容的情况下也是会失效,所以内部处理需要更新pos位置
{
//如果size为零呢？对于这个问题，我们的迭代器就控制了第一次插入是不能用insert的,也就是说如果使用迭代器作为参数，则vector必须要有元素
if (size() == 0)
{
push_back(val);
}
else
{
assert(pos >= _start);
assert(pos < _finish);//分开写能更好的界定错误
if (_finish == _endofstorage)
{
int len = pos - _start;
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
//扩完容就要插入,防止异地扩解决失效，首先要更新pos
pos = _start + len;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
//减完以后直接插入
*pos = val;
++_finish;
}
return pos;
}
//iterator erase (iterator position);//删除一个元素
//iterator erase(iterator first, iterator last);//删除一个区间内的元素
iterator erase(iterator pos)//这里有一个迭代器失效，并不是野指针类的，而是因为意义不同了，有时候也是真的会野指针
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos;
while (end < _finish)
{
*end = *(end + 1);
end++;
}
_finish--;
return pos;
}
//赋值重载,自己给自己赋值的情况太少，这里不做处理,但是库中有处理
vector<T>& operator=(vector<T>& x)
{
//赋值重载双方本来都有空间，这里用现代写法
swap(x);//默认this占据第一个参数
return *this;
}
//重载方括号
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
void swap(vector<T>&x)
{
std::swap(_start, x._start);
std::swap(_finish, x._finish);
std::swap(_endofstorage, x._endofstorage);
}
iterator begin()const
{
return _start;
}
iterator end()const
{
return _finish;
}
//尾插实现之前首先要提供容量等接口函数
size_t capacity()const
{
return _endofstorage - _start;
}
size_t size()const
{
return _finish - _start;
}
bool empty()const
{
return _finish == _start;
}
private:
iterator _start;//这个代表可更改大小的数组
iterator _finish;//这个类似于size
iterator _endofstorage;//capacity;
};
}
