文章目录

• 📕 vector 简介
• 📕 vector 模拟实现
• • 框架
  • 构造函数
  • ★ 拷贝构造、赋值重载 ★
  • resize() 、reserve()
  • _push_back() 、_pop_back()
  • ★ 迭代器使用、迭代器失效问题 ★
• 📕 源代码

📕 vector 简介

vector 是 C++ 的 STL 标准库中的一个容器，它主要使用的是泛型编程的思想，即使用模板。
vector 是表示可变大小数组的序列容器。它里面可以存储任意数据类型的数据，除了内置类型，还可以有自定义类型，它和数组明显的区别就是——vecctor的大小可以动态改变。当然了，不同平台下的增长方式不一样，如下图是VS 和 Linux 下的测试vector 标准库的增长方式。

📕 vector 模拟实现

框架

为了和 STL 标准库中的 vector 区分，自己实现的可以用命名空间包含起来，这里我取名为 simulate，是模拟的意思。
由于 vector 是一个容器，可以存放各种类型的数据，所以要使用模板。

namespace simulate
{templateclass vector{public:private:T* _start=nullptr;T* _finish=nullptr;T* _end_of_storage=nullptr;};
}

构造函数

如下，构造函数有多个函数重载。初始化列表可以使用缺省值代替（在申明的时候给成员变量缺省值）。

同时，这里也使用了模板，模板参数只能是迭代器区间（如果传其他的会出错），构造迭代器区间内的数据成为一个vector对象。

		// 直接用缺省值替代初始化列表vector(){}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){*(_start + i) = val;++_finish;  // 不要忘了++ _finish ，一开始忘记了，所以打印不出来}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){*(_start + i) = val;++_finish;  // 不要忘了++ _finish ，一开始忘记了，所以打印不出来}}// 写了模板，但是不加上上面的int参数重载，会报错，因为vector(10,5)会调用模板函数templatevector(InputIterator begin, InputIterator end){reserve(end - begin);while (begin != end){_push_back(*begin);++begin;}}

但是，为什么上面有两个构造函数的非常像，区别仅仅是第一个参数的类型呢？
如下，这是使用自己定义的vector，初始化后vector里面有10个5。

simulate::vector vv(10, 5);

如果没有第一个参数是 int 类型的构造函数，如下。如果是上面一行代码那样构造，传入的两个参数都被认为是 int 类型，而目前有两个参数的构造函数中，一个可以被认为是 （size_t ，int） ，另一个由于是模板，所以可以被认为是（int，int） ，编译器会选择后者。
但是实际上，后者由于不传入迭代器，而是实实在在的数据，就会造成错误，因为函数体内部有解引用。
所以要多一个函数重载，来重载这种情况，编译器会优先选择参数是（int，int）的，而不是使用模板。

★ 拷贝构造、赋值重载 ★

拷贝构造就涉及到深拷贝和浅拷贝的问题。
如果 vector 里面存放的数据是内置类型，根据拷贝构造方面的知识，深、浅拷贝都没有关系。
但是如果 vector 里面存放的是自定义类型，并且该类型涉及资源管理，那就必须要深拷贝。

如下图，vector 容器里面存放的是 string 类型的数据，根据对 string 类型的模拟实现，我们可以大概知道其实现原理。string 类有一个成员变量 _str 指向一串字符串。现在将 v 里面的数据拷贝到 vv 里面，如果是浅拷贝，那么就会如下图，导致 v[n] 和 vv[n] 里面的数据完全一样， _str，_size，_capcatiry ，那么 _str 指向同一块空间。在析构的时候，会造成重复析构，导致崩溃。

如下，深拷贝就不会出现上述问题，完全独立的空间。

那么如何实现深拷贝呢？vector是一个容器，由于使用泛型编程的思想，里面可以存放的数据类型各种各样，也许有的自定义类型，里面有多个指针分别指向不同的空间呢？我们如何知道每一次要深拷贝多少块空间呢？
所以，在这里做一个统一的标准显然是不现实的。也不能用memcpy，因为memcpy是直接把一个 vector 里面的数据拷贝到 另一个 vector，就会造成上图的浅拷贝问题。
其实，我们可以直接调用 赋值重载 ，这也是为什么这两个函数放在一起的原因。

试想一下，现在有 vector< stirng > v，里面存放了一定量的数据， vector vv(v) ，和上图一样的操作。只不过，拷贝构造内部使用的是 赋值重载 —— vv[0] = v[0] …… ，由于赋值符号两边都是string类型的数据，会调用 string 自己的赋值重载，string 内部实现的赋值重载当然是没有任何问题的！！！！其他的类型也是，内部实现的赋值重载是深拷贝，所以，这里就很好地解决了上述问题！

		vector(const vector& v){_start = new T[v.capacity()];for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];  // 会调用自己类型的赋值重载}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

但是，如果出现了 vector< vector< string > > v ；这样的情况呢？又要拷贝构造使得vector< vector< string > > vv(v) ；容器里面存放的是容器，由于拷贝构造内部是 vv[0] = v[0] …… 赋值符号两边都是 vector< string > 类型的数据，都是 vector 类型，所以会调用 vector 自己的赋值重载如下。
还是以上述的 vector< vector< string > > v 为例， vv[0] = v[0] ，调用 vector 类型的赋值重载，即调用下面的函数。v[0] 是 vector< string > 类型的数据，该类型的数据，就像上面的两张图片一样，内部存放了一个个 string 类型的数据，如下所示。所以 _start[i] 是 string 类型的数据的指针，_start[i] = val._start[i]; 会调用 string 类型的赋值重载，那当然是没有问题的。

		// 一个 vector 赋值给另一个 vectorvector operator=(const vector& val){_start = new T[val.capacity()];for (int i = 0; i < val.size(); i++){_start[i] = val._start[i];}_finish = _start + val.size();_end_of_storage = _start + val.capacity();return *this;}

以此类推，即使是更多层次的 vector 嵌套，也可以通过不断调用 vector 类里面的赋值重载，直到里面的类型不是 vector，而是其他的类型，而这些其他的类型是实现了深拷贝的赋值重载的，所以完全是行得通的。

resize() 、reserve()

这两个函数都和 string 类里面的两个函数类似，所以这里也不过多赘述。

		void resize(size_t n,T x=T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = x;_finish++;}}}void reserve(int n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start)  // 非空，复制数据，删除原空间。为空则不需要这样做{memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}

_push_back() 、_pop_back()

尾插其实也和 string 类差别不大，考虑扩容。
这里也可以再深入思考一下，锻炼思维。如果参数类型 T 是 vector< string > ，那么尾插会是一次成功的吗？当然是的， *_finishi 和 x 都是T类型的数据，也就是 vector< string > ，所以会调用 vector 自己的赋值重载；然后由于其内部数据是 string 类型的，所以vector 的赋值重载内部，又会进一步调用 string 类型的赋值重载，标准库里面的string类的赋值重载，自然是没有什么问题的。

		void _push_back(const T& x){if (_finish == _end_of_storage){int sz = capacity() == 0 ? 4 : 2 * capacity();reserve(sz);}*_finish = x;++_finish;}void _pop_back(){assert(!empty());--_finish;}

★ 迭代器使用、迭代器失效问题 ★

vector 的使用，非常需要注意的一点就是迭代器失效问题。如下代码是 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;}

如下，是使用迭代器设计 insert() 函数，由于是插入，所以要考虑扩容的问题，但是如果真的扩容了，那么原本传参的 pos 迭代器指向的位置，就可能是错误的了。因为扩容后，可能开辟一块新空间，那么指向旧空间某一处的 pos 迭代器，也就失去了意义，因为旧空间在 reserve 的过程中已经被释放了。

所以，要用一个变量来存储 pos 迭代器指向的位置 和 初始位置 的长度，这里用的是 len 。下面的就是普通的后移插入过程。

		iterator insert(iterator pos , const T& x){assert(pos >= _start);assert(pos < _finish);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(2 * capacity());pos = _start + len;  // 扩容之后，_start 改变了}iterator tmp = _finish - 1;while (tmp >= pos){*(tmp + 1) = *tmp;--tmp;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator tmp = pos + 1;while (tmp != _finish){*(tmp-1) = *tmp;tmp++;}--_finish;return pos;}

接下来就是迭代器失效的情况，这是在使用 vector 迭代器的时候会出现的问题。
现在有一个 vector< int > v; v里面存储着一些数据，要求删除所有偶数数据。

像下面一样去写（simulate 是我用来包含自己的 vector 的命名空间，防止和标准库中的冲突），就可以了吗？可以画图尝试理解，如下图。当删除一个数据的时候，由于删除这一动作本身就会使得后面的数据前移，然后又++，就导致直接跳过了一个数据。
而如果最后一个数据是偶数，那么会删除数据并跳过 v.end() ，导致 while() 的循环条件一直满足，从而陷入死循环。

这就是典型的迭代器失效问题，原本的迭代器，在经过 插入/删除 之后，导致迭代器不是指向原本的那个数据，后续使用就可能出错。

	simulate::vector::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}++it;}

所以，在删除数据之后，就不能再让迭代器++。如下代码，加上一个 else 就可以，这样子就可以使得删除之后不进入 else 的代码块。同时，it 也要接收 erase() 的返回值，其返回值也是 iterator ，指向被删除的后一个数据。

	while (it != v1.end()){if (*it % 2 == 0){it=v1.erase(it);}else ++it;}

📕 源代码

#pragma once
#include
#includenamespace simulate
{templateclass vector{public:typedef T* iterator;typedef const T* const_iterator;// 用缺省值替代初始化列表vector(){}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){*(_start + i) = val;++_finish;  // 不要忘了++ _finish ，一开始忘记了，所以打印不出来}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){*(_start + i) = val;++_finish;  }}// 写了模板，但是不加上上面的int参数重载，会报错，因为vector(10,5)会调用模板函数templatevector(InputIterator begin, InputIterator end){reserve(end - begin);while (begin != end){_push_back(*begin);++begin;}}vector(const vector& v){_start = new T[v.capacity()];for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}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 _end_of_storage - _start;}bool empty(){return _start == _finish;}T& operator[](size_t x){assert(x < size());return _start[x];}// 自己要写赋值重载，赋值重载和拷贝构造类似，一个 vector 复制给另一个 vectorvector operator=(const vector& val){_start = new T[val.capacity()];for (int i = 0; i < val.size(); i++){_start[i] = val._start[i];}_finish = _start + val.size();_end_of_storage = _start + val.capacity();return *this;}const T& operator[](size_t x)const{assert(x < size());return _start[x];}void resize(size_t n,T x=T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = x;_finish++;}}}void reserve(int n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start)  // 非空，复制数据，删除原空间。为空则不需要这样做{memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = tmp + sz;_end_of_storage = tmp + n;}}void _push_back(const T& x){if (_finish == _end_of_storage){int sz = capacity() == 0 ? 4 : 2 * capacity();reserve(sz);}*_finish = x;++_finish;}void _pop_back(){assert(!empty());--_finish;}// 用迭代器，可能会出现迭代器失效的情况iterator insert(iterator pos , const T& x){assert(pos >= _start);assert(pos < _finish);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(2 * capacity());pos = _start + len;  // 扩容之后，_start 改变了}iterator tmp = _finish - 1;while (tmp >= pos){*(tmp + 1) = *tmp;--tmp;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator tmp = pos + 1;while (tmp != _finish){*(tmp-1) = *tmp;tmp++;}--_finish;return pos;}~vector(){delete[] _start;_finish = _end_of_storage = nullptr;}private:T* _start=nullptr;T* _finish=nullptr;T* _end_of_storage=nullptr;};
}