Vector的模拟实现与迭代器失效问题
一.Vector的介绍与使用
vector的英文解释是向量的意思，向量是序列容器，表示大小可以变化的数组。就像数组一样是连续存储的可以通过指针偏移来访问元素。但与数组不同的是它的大小可以动态变化，其存储由容器自动处理。在存储数据时容器可能会分配一些额外的空间来适应可能的增长，因此实际的容器可能大于包含其元素严格需要的存储空间。
二.Vector的实现
接下来我会通过vector的基本功能用法，迭代器的模拟，以及构造析构方面进行模拟实现。
首先搭好架子，创建一个类模板T，将T的指针定义为iterator后续用来模拟实现迭代器，_start表示指向首位的指针，_finish表示指向有效元素末尾的指针，_end_of_storage表示容器最大存储量。
namespace bicup
{
template<class T>//类型模板
class vector //类型
{
public:
typedef T* iterator;//类型指针
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}1.构造析构函数
1.构造与析构
下面书写一下构造函数和析构函数，当然这里的构造函数我们先写一部分，后面根据需要来进行补充修改。
namespace bicup { template<class T> class vector { public: typedef T* iterator; vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) {} ~vector() { if (_start) { delete[] _start; _start = _finish = _end_of_storage = nullptr; } } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }需要注意这里的构造在 ：下要用（）而不能用 = 直接初始化 ，析构时需要判断vector内是否有数据。
2.拷贝函数
下面是拷贝构造
namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 typedef const T* const_iterator; vector(const vector<T>& v) { reserve(v.size()); for (auto& e : v) { push_back(e); } } /* void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector<T>& operator=(const vector<T>& v) { swap(v); return *this; }*/ vector<T>& operator=(const vector<T>& v) { if (this != &v) { delete[] _start; _start = _finish = _end_of_storage = nullptr; reserve(v.size()); for (auto& e : v) { push_back(e); } } return *this; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; }这里有两种表示方法，v2（v1）或者v2 = v1，此处没有太多的难点。
2.功能函数模拟
下面来实现尾插，首先对vector进行判断，是否有空间插入数据，若没有则需要进行扩容。在扩容这部分操作我们需要用到reserve以及vector空间大小capacity和实际大小size，我们在下面依次实现。为了节省空间以及更加清楚的展示，每个板块只放上核心代码部分，当然在最后我会将所有代码一次性放上。
1.reverse与push_back
#pragma once namespace bicup { template<class T> class vector { public: size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; memcpy(tmp, _start, sizeof(T) * oldsize); delete[] _start; _start = tmp; _finish = _start + oldsize; _end_of_storage = _start + n; } } void push_back(const T&x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } *_finish = x; _finish++; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }reverse部分中，需要判断扩容是否大于capacity， 若小于capacity则不会改变容量，若大于capacity我们不能在原有的空间上进行添加数据。我们需要重新的开辟一块新的空间，new出n个单位的空间，通过memcpy将原有的数据转移到新开辟的空间上，回收原有的内存空间。将tmp首元素地址给_start，更新_finish和_end_of_storage。
当然这块并不是最终的代码，下面我们再来看一个例子
int main() { bicup::vector<string> v1; v1.push_back("1111111111111111"); v1.push_back("111111111111111111"); v1.push_back("1111111111111111111"); v1.push_back("111111111111111111"); v1.push_back("11111111111111111111"); for (const auto& e : v1) { cout << e << " "; } cout << endl; return 0; }当我们运行这串代码后发现
这是什么原因导致的呢？
这里使用了一个memcpy，它属于浅拷贝，它通过首元素的地址对整个string进行拷贝，所以当vector扩容之后tmp会与_start指向同一个位置，最后会被delete[ ] 析构掉。所以看到的就是乱码。
那我们该怎么调整呢？
很简单，不使用memcpy就可以了
namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 typedef const T* const_iterator; void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; //memcpy(tmp, _start, sizeof(T) * oldsize); for (size_t i = 0; i < oldsize; i++) { tmp[i] = _start[i]; } delete[] _start; _start = tmp; _finish = _start + oldsize; _end_of_storage = _start + n; } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; }
2. [ ] 运算符重载
接下来测试一下push_back，我们希望像数组一样用 [ ] 的方式来表示下标元素，这就需要用到运算符重载。
#pragma once #include <string> #include <assert.h> namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 T& operator[](size_t i) { assert(i < size()); return _start[i];//等于*(_start + i) } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }这里的本质就是以指针_start为起始点+i个单位之后解引用得到的数据。 可以用_start [ i ] 来简便书写。
测试代码：
int main() { bicup::vector<int> vv; vv.push_back(2); vv.push_back(3); vv.push_back(5); for (const auto &e : vv) { cout << e << " "; } cout << endl; for (size_t i = 0; i < vv.size(); i++) { cout << vv[i] << " "; } cout << endl; return 0; }
3.迭代器模拟
当我们需要测试const类型的vector时，原先的下标以及迭代器就用不了了，需要重新进行函数重载。
例如下面的测试代码：
void func(const bicup::vector<int>& v) { for (size_t i = 1; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; bicup::vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } }当然上述的代码是跑不起来的，原因是const进行了函数的权限缩小，但是我们还没有进行函数重载。这里需要注意，我们不能直接在 bicup::vector<int>::iterator it = v.begin() 前面加const，因为这里加的const就是修饰迭代器本身不能达到我们的目的，我们需要const来修饰的是vector里的数据。所以请看
namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 typedef const T* const_iterator; iterator begin() { return _start; } const_iterator begin() const { return _start; } iterator end() { return _finish; } const_iterator end() const { return _finish; } T& operator[](size_t i) { assert(i < size()); return _start[i];//等于*(_start + i) } const T& operator[](size_t i) const { assert(i < size()); return _start[i];//等于*(_start + i) } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }我们需要在typedef处添加const修饰，随之而来的我们需要重载一份const的函数begin() end() 以及 [ ] 。
下面是更正后的写法：
void func(const bicup::vector<int>& v) { for (size_t i = 1; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; bicup::vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } }
三.迭代器失效问题
1.野指针
接下来是本篇的重点部分，关于迭代器失效的问题。我们先来看一串代码。
namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 typedef const T* const_iterator; void insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos < _finish); if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } iterator it = _finish - 1; while (it >= pos) { *(it + 1) = *it; it--; } *pos = x; _finish++; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }我们来看insert这部分逻辑，空间不够扩容，移动数据，插入数据，更新_finish 好像没有什么问题。事实也是如此，当我们用5个数据测试时并没有找出问题，但当我们用4个数据测试时，程序就崩溃了。原因是vector内只有4个数据时要插入数据，那么就会涉及到扩容，扩容的时候需要将数据移动到另一块空间上。但是此时vector内的 _start 仍然指向原空间首位，所以需要我们对其进行更新。
正确写法：
#pragma once #include <string> #include <assert.h> namespace bicup { template<class T>//类型模板 class vector //类型 { public: typedef T* iterator;//类型指针 typedef const T* const_iterator; void insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos < _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); _start = len; } iterator it = _finish - 1; while (it >= pos) { *(it + 1) = *it; it--; } *pos = x; _finish++; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
2.编译器强制检查
当然迭代器失效的情况不止这一种，下面我们来继续探讨。
int main() { bicup::vector<int> vv; vv.push_back(2); vv.push_back(3); vv.push_back(5); vv.push_back(4); int i; cin >> i; auto it = vv.begin() + i; vv.insert(it, 2); cout << *it << " "; return 0; }当我们创建一个变量 it 来传参时，函数的形参会改变但是实参并没有进行更新，所以 it 无法找到扩容之后的pos位置。有的同学可能会疑惑，那不能在函数参数上添加 & 吗？当然这也是不行的，虽然添加之后 it 会进行更新，但参数一旦添加常量之后（it + 1）就无法运行通过了。所以，规定了只要使用了insert函数，迭代器就会失效（不使用）。
接下来我们看下一个经典的迭代器失效。
int main() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //删除偶数 auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { v.erase(it); } it++; } }这个操作是对偶数项进行删除，但是当我们在vs下编译时确没有结果显示。
这是由于编译器的设定 ，在vs下当编译器当程序erase之后，认为迭代器失效会将其标记，一旦访问就会报错。
总结，迭代器的失效主要是由两种原因导致，一个是野指针另一个是强制检查标记。虽然不同编译器对于erase和insert的迭代器处理不同，但我们默认使用了erase和insert后迭代器失效。
四.完整代码
#pragma once
#include <string>
#include <assert.h>
namespace bicup
{
template<class T>//类型模板
class vector //类型
{
public:
typedef T* iterator;//类型指针
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];//等于*(_start + i)
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];//等于*(_start + i)
}
vector()
{}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
_finish++;
}
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldsize = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * oldsize);
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
void push_back(const T&x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(_finish > _start);
_finish--;
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos < _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
_start = len;
}
iterator it = _finish - 1;
while (it >= pos)
{
*(it + 1) = *it;
it--;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
/* void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(const vector<T>& v)
{
swap(v);
return *this;
}*/
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}五.结语
创作不易，希望大家多多支持！！！