模拟实现vector/迭代器失效问题
对于STL，我们不仅学会使用STL,还要了解其底层原理，这样一来，我们就能知道什么时候用string好，什么时候用vector，什么时候用list，哪种方法效率高等等。其次了解了STL的底层原理，也助于我们的C++功力大增！
先来看看vector类的成员变量：下图是从《STL源码剖析》书中截取的
vector类的成员变量有三个，分别是iterator start、iterator finish和iterator end_of_storage。我们可以用string类的成员变量来理解这三个变量：
string 类的成员变量有：T* a , size_t _size , size_t _capacity
start也就是a,finish也就是a+_size,end_of_storage也就是a+_capacity。
源码中的vector类：
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
//......
protected:
iterator start;
iterator finish;
iterator end_of_storage;
}开始模拟实现->
为了避免冲突，先创建一个命名空间，然后在命名空间里面创建vector类：
namespace my_vector
{
template<class T>
class vector {
public:
typedef T* iterator;//迭代器
typedef const T* const_iterator;//const迭代器
private:
iterator _start;
iterator _finish;
iterator end_of_storge;
};
}1.构造函数：
①无参构造，将成员变量全部置为空即可
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storge(nullptr)
{}②迭代器区间构造：
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storge(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}其它的接口就先实现，方便后续使用：
交换接口：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storge, v._end_of_storge);
}析构函数：
~vector()
{
delete[] _start;
_start = _finish = _end_of_storge = nullptr;
}清空数据：
void clear()
{
_finish = _start;
}③拷贝构造
传统写法：
先初始化，然后开空间，最后是将被拷贝对象的值弄到拷贝对象中。在范围for循环中，最好是引用。
vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storge(nullptr)
{
//先开辟空间
reserve(v.capacity);
for (auto& e : v)
{
push_back(e);
}
}现代写法：
vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storge(nullptr)
{
vector<T> tmp(v.begin, v.end);//用迭代器区间构造，找个打工人
swap(tmp);
}2.插入数据的相关函数接口：
①reserve()的模拟实现：
因为在插入数据时，不管是最初状态还是空间满的时候，都得扩容，所以就先实现reserve()。因为reserve是不会缩容的，缩容和扩容是需要代价的，而扩容是不可避免的，但是缩容就不必要了，采用空间换时间的策略。
在最初状态，_start是指向空指针的，因此在扩容的时候需要判断一下。
void reserve(size_t n)//不止是在插入数据的时候使用，也可以单独使用
{
if (n > capacity())//因为不缩容，所以判断一下，大的时候才处理
{
size_t oldSize = size();
T* tmp = new T[n];
if (_start)//判断一下_start是否为空，因为如果一开始的capacity是空的，然后赋值为4，但是此时的_start是nullptr，给不了数据
{
//不建议用memcpy，因为它是浅拷贝，如果T是string、vector等等，就会出错
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete _start;
}
_start = tmp;
_finish = tmp + oldSize;
_end_of_storge = _start + n;
}
}②size()和capacity():
实现size()和capacity()，方便操作，并且这也是需要实现的一部分。
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storge - _start;
}③push_back()：
因为_finish表示的是有效元素的个数，指向的是最后一个元素的下一个位置，因此不管是否需要扩容，尾插的位置必然是_finish指向的位置。
void push_back(const T& x)
{
if (_finish == _end_of_storge)//判断空间是否满了
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;//直接在_finish这个位置插入数据
++_finish;
}④insert接口/迭代器失效问题
void insert(iterator pos, const T& val)；
这部分很重要，因为涉及了迭代器失效问题！我们都知道，在插入数据前，我们需要进行一次判断，判断容器的容量是否满了，如果满了，则需要扩容，而问题也就发生在这里，扩容会导致迭代器失效的问题！（当然，迭代器失效的问题不仅仅会出现在这）
在扩容的时候，是重新开辟一块大的空间，然后释放原来的空间，看下图：
这样就导致了插入数据失败。解决问题呢，就是更新pos，让pos指向新空间的同一块位置：在扩容前记录一下pos距离_start的长度，在扩容后，让pos重新指向新空间的_start+len处。
//迭代器失效问题
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos < _finish);
if (_finish == _end_of_storge)
{
size_t len = pos - _start;//算出pos距离_start的长度
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
//待空间更新，就更新pos的位置，解决pos失效的问题
pos = _start + len;
}
iterator end = _finish - 1;
//挪动数据
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val
++_finish;
}当然，不扩容的话，就可能不会导致失效的问题了。其实迭代器失效，也就是野指针的问题。
解决迭代器哦失效，便是
3.实现迭代器
普通对象迭代器：
刚好，迭代器的begin刚好就是_start,end也刚好是_finish。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}const迭代器：
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}4.访问接口[]：
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}5.判空
当_finish等于_start的时候，说明此时容器是空的，没有空间，没有数据。
bool empty() const
{
return _finish == _start;
}6.resize()
对于resize(size_t n,T val = T())，是针对有效元素个数的。当n是大于容器当前的容量，则代表着是扩容+插入数据，当n小于容器的当前容量，大于当前有效元素个数，那么代表着不扩容，但是插入数据，当n小于当前容量，那么就是相当于删除数据。
那么插入的数据的话，缺省值是T()，即匿名对象，因为T有可能是string类型，是Date类型，是各种各样的类型，因此需要它的构造函数去初始化。
void resize(size_t n, T val = T())//T()是匿名对象，初始化resize的空间
{
if (n > capacity())//扩容
{
reserve(n);
}
if (n > size())//不扩容，但是插入数据
{
//从_finish开始填数据
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else//删除数据
{
_finish = _start + n;//相当于把有效元素的个数减少到n个
}
}7.删除数据的接口：
①pop_back();
void pop_back()
{
assert(empty());//如果容器已经空， 再次调用的话，直接报错
--_finish;
}②erase()接口以及其引起的迭代器失效
删除任意位置，即挪动要删除的数据的后面的位置，将他们往前挪即可。
void erase(iterator pos)
{
//pos的位置要合理
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--——finish;
}删除操作，会让pos迭代器会失效，但注意，在Linux下g++中不会报错，不会失效，因为g++采用的是模拟实现，它做不到识别失效问题，pj版能够识别，是因为它不是一个原生指针。但不管怎么样，一般来说统一认为它会失效！
而解决失效问题，可以将代码改成如下：
iterator erase(iterator pos)
{
//pos的位置要合理
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + ;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}删除后，更新pos位置即可。
8.find导致的迭代器失效问题
my_vector::vector<int>::iterator it = find(arr.begin(), arr.end(), 3);
if (it != arr.end())
{
arr.insert(it, 30);
}
//可能发生迭代器失效
(*it)++;如上代码，在insert之和，it会发生迭代器失效。其原因是：即使我们在insert后，pos位置更新，使得pos没有失效，但是对于reserve接口，传参是传值传参，pos的改变不会影响it，而it作为参数传到insert接口后，由于原本指向的空间已经释放了，it就变成了野指针，也就是迭代器失效了。当然了，如果没有发生扩容，就可能不会发生失效。
在C++官方库里面，insert也没有引用作参数，也是传值传参的。简单地解释一下就就是，有时候传进去的是一些具有常性的临时变量，不可传，比如insert(arr.begin(),1);，其中的arr.begin()就是临时变量。
9.赋值操作
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}腾讯云开发者
