如何将模拟实现的vector改写为长尾？

本文共计3322个文字，预计阅读时间需要14分钟。

首先，要知道vector是什么 + vector是什么 + 1.vector表示表示可变大小数组的序列容器。就像数组一样，vector也使用连续存储空间来存储元素。也就是说，可以使用下标对vector的元素进行访问。

首先要知道vector是什么

vector是什么

1.vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

vector的实现

要实现一个容器第一步肯定还是确定vector的成员变量，并且因为vector和我们知道的普通数组不一样的就是，普通的数组内部只能储存整型的数据，但是vector你传入什么类型那么它就会实例化成能储存你传入类型的容器。由此实现vector需要使用到模板。

下面是vector的模拟实现基本代码：

template<class T> class vector { private: T* start; T* end; T* endofstorage; };

至于为什么vector的成员变量是三个指针。

下面我来解释这三个指针的用途：这三个指针指向的是同一片连续空间的不同位置。其中从start指向的是空间的开始，而end指向的是这个空间储存的有效数据的下一位。而endofstorage指向的是这篇空间的末尾。

无参默认构造和析构函数

下面是vector的无参的默认构造函数

vector()//首先实现一个无参的默认构造函数 :start(nullptr) ,end(nullptr) ,endofstorage(nullptr) {} ~vector() { delete[] _start;//释放空间 _start = _end = _endofstorage = nullptr; }//析构函数

然后下面我们来实现拷贝构造但是在实现拷贝构造之前肯定要让vector存在开辟空间的函数

reserve函数

//下面是和string一样的基本信息获取函数,连续的空间指针相减得到的就是两个指针之间的元素个数 size_t size() { return _end - _start } size_t capacity() { return _endofstorage - _start; } void reserve(size_t n) { //第一步需要判断是否需要扩容，而连续的空间指针相减得到的就是两个指针之间的元素个数 size_t __capacity = capacity();//获取当前的容量 size_t __size = size();//获取当前的有效数据长度 if (n > __capacity)//需要扩容 { T* tmp = new T[n];//首先创建一个n个大小的新空间 if (_start)//如果原空间中存在信息，而非空 { memcpy(tmp, _start, sizeof(T)*__size);//将原空间数据拷贝到新空间 } _start = tmp;//将新空间赋值过去 _end = _start + __size; _endofstorage = _start + n;//在这里就可以体现出我们提前将原空间有效数据记录下来的好处了 //如果在这里你没有记录原空间的有效数据个数，而是采用函数计算，但是不要忘了现在的_start指向了一片新空间 //而end指向的任然是老空间就会出现错误 //所以这里需要记录老空间的有效数据个数 delete[] _start;//删除原空间内存 } }

在完成了reserve函数之后，我们就可以去完成push_back函数往vector中插入数据了。

push_back和[]函数

void push_back(const T& x)//尾插入一个数据 { if (_end == _endofstorage)//判断空间是否足够 { reserve(capacity() == 0 ? 4 : 2 * capacity());//这里的双目表达式，在capacity本省便为0的时候会创建4个大小的 //空间，不然就按照空间两倍的大小扩容 } *_end = x;//之后让*_end指向的那个空间填入x _end++;//再让_end++ }

下面我们再来完成[]函数，之后来检测一下是否有错误存在。

T& operator[](size_t n) { assert(n < size());//首先判断是否超出有效数据范围。 return *(_start + n);//然后返回这个数据即可 }//并且我们现在重载的这个操作符既能读也能写 T operator[](size_t n) const { assert(n < size_t n); return *(_start + n); }//这个函数则是只有读的功能

下面是测试和运行截图（测试代码就不写了，可以在下图查看）

正向迭代器的模拟

既然已经完成了基本的输入输出，下面我们就来完成迭代器的模拟实现。因为vector的空间也是连续的所以使用原生指针即可。

typedef T* iterator; typedef const T* const_iterator;//const迭代器是可以改变指针的指向，但是不能通过指针去修改值 iterator begin() { return _start; } iterator end() { return _end; } const_iterator begin() const { return _start; } const_iterator end() const { return _end; }

最后是测试和运行截图：

反向迭代器的模拟

和正向迭代器不一样，反向迭代器就不能使用原生指针了，因为反向迭代器的加加，反而需要我们去让指针减减，而反向迭代器的减减又需要我们去加加指针。

所以我们需要自己在写一个类用于反向迭代器的模拟（模板）。

如下：

template<class T, class ref,class ptr> struct Reserve_iterator { typedef Reserve_iterator<T, ref, ptr> self; T* _stu;//这个便是反向迭代器的成员变量是一个T* 的指针 //然后下面我们来模拟一个指针能做的++，--，*，->,!=,== Reserve_iterator(T* tmp = nullptr) :_stu(tmp) {} self operator++()//前置++ { _stu--;//将T*的指针减减，就是反向迭代器的加加 return *this; } self operator--()//前置-- { _stu++; return *this; }//和上一个一样 self operator++(int)//后置++这里的int就只是表明这是一个后置++而已 { self tmp(*this); _stu--; return tmp; } self operator--(int) { self tmp(*this); _stu++; return tmp; } //下面要重载*和-> //这两个函数也是为什么要传入三个模板参数的原因 //对于反向迭代器而言const版本和非const版本唯一的不同也就是，const版本的迭代器不能通过指针去修改值 //那么对于const迭代器的*我们就可以返回const T&，非const迭代器就直接返回T&即可 //所以我们设置了三个模板参数 ptr operator*() { return (*_stu); } ref operator->() { return _stu; } bool operator!=(const self& b) { return _stu != b._stu; } bool operator==(const self& b) { return _stu == b._stu; } };

但是只完成这一个类也无法完成反向迭代器，最后还需要再vector的类中加入rbegin和rend函数

如下：

typedef Reserve_iterator<T, T*, T&> reserve_iterator; typedef Reserve_iterator<T, const T*, const T&> const_reserve_iterator; reserve_iterator rbegin()//返回反向迭代器的开头 { return (_end - 1);//因为_end指向的是有效数据的下一位 } reserve_iterator rend()//反向迭代器的结束 { return _start - 1;//这里的_start也需要减一，因为循环结束的条件是it和rend相等如果方向迭代器的rend返回的是开头元素的指针 //那么当it和rend相等的时候不会进入循环，也就会导致原本开头的元素会被漏掉 } const_reserve_iterator rbegin() const { return (_end - 1); } const_reserve_iterator rend() const { return _start - 1; }

那么为什么反向迭代器要三个模板参数呢？究其原因是为了区分const反向迭代器和非const反向迭代器

const 反向迭代器和非const的不同就在于两个函数，一个是*一个是->, 对于const迭代器而言。返回的 是const T& 而非const迭代器返回的是T& ，对于->函数const迭代器返回的是const T*。非const迭代器返回的是 T*。

所以我们将这几个不同的返回值作为模板参数，让我们只用写一个结构体就能实例化出，const反向迭代器和非const反向迭代器。

下面是测试和运行截图：

复制拷贝函数和赋值=函数

下面我们来完成vector的复制拷贝函数以及=函数。

vector(vector<T>& b) { //我们需要拷贝b的内容，首先就需要拥有和b一样大的空间 reserve(b.capacity());//创建空间 for (int i = 0; i < b.size(); i++) { push_back(b[i]);//再将b里面的数据尾插入*this中完成拷贝。 } } void swap(vector<T>& b) { std::swap(_start, b._start); std::swap(_end, b._end); std::swap(_endofstorage, b._endofstorage); } vector<T>& operator=(vector<T> b) { //这里的=我就使用了新式的写法，将要拷贝的vector在传参的时候，就将其拷贝完成， //然后让b和*this交换，即能把原空间释放（离开这个函数后b就会被销毁），也能完成*This的赋值 swap(b); return *this; }

下面是测试截图：

resize函数

和string的resize函数一样，resize也需要考虑三种情况。

void resize(size_t n, T tmp = T()) { if (n < size())//当n小于有效数据个数的时候需要我们删除元素 { _end = _start + n; } else//需要我们增加数据，并且可能会伴有扩容 { reserve(n);//如果n小于容量那么这个函数什么也不会做 for (int i = size(); i < n; i++) { *(first + i) = tmp;//从最后一个元素开始往后赋值 } } }

那么在这里我来解释一下，为什么tmp的全缺省使用的是T（）而不是0，因为我们完成的vector是一个模板，它不是专门储存整型的容器，而是一个既能储存内置类型也能储存自定义类型的容器。所以这里的全缺省填的是匿名对象，让其能去调用这个T的构造函数，而在c++11之后内置类型也支持了默认构造。所以这里天的是一个匿名对象。

下面是测试实例：

使用迭代器的构造函数

在库里面还有一种构造函数的方法，就是使用迭代器区间去初始化，并且这个迭代器是支持所有容器的迭代器的（使用模板）。

template <class InputIterator> vector(InputIterator start,InputIterator,end) { while (start != end) { push_back(*start);//将迭代器指向的元素尾插到*this中 start++; } }

下面是测试实例

insert函数

和string的insert函数不同 它是插入到一个迭代器的前面。返回的也是插入数据的那个迭代器。

首先第一个是在某个迭代器前面插入一个数据：

iterator insert(iterator pos, const T& x = T()) { //第一步还是要判断要插入的位置是否超出了有效数据的长度 assert(pos >= _start); assert(pos <= _end); //下面需要判断空间是否需要扩容 if (_end == _endofstorage) { //记录pos是在哪一个位置的迭代器，因为扩容后 //pos指向的那个空间就会被释放 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len;//再次让pos指向它应该在的位置 } //然后连续的空间需要插入还是使用从后向前的移动方法 iterator tmp = _end; while (tmp >= pos) { *(tmp + 1) = *(tmp); tmp--; } *pos = x; _end++; return pos; }//这个是插入一个数据

下一个是在某个迭代器的前面插入n个数据

iterator insert(iterator pos, size_t n, const T& x = T()) { assert(pos >= _start); assert(pos <= _end); //第一步创建一个临时的足够大的空间 size_t len = pos - _start;//求出在pos前面存在多少数据 T* tmp = new T[size() + n];//创建一个足够大的空间 size_t tmpi = 0; for (; tmpi < len; tmpi++) { tmp[tmpi] = *(_start + tmpi); }//将pos前面的数据放到tmp中去 while (n--) { tmp[tmpi++] = x; }//将n个数据放到tmp中去 //最后将pos后的数据放到tmp中去 for (int i = len; i < size(); i++) { tmp[tmpi++] = *(_start + i); } delete[] _start;//释放原空间储存 _start = tmp; _end = _start + tmpi; _endofstorage = _start + n + size(); return pos; }//在pos前面插入n个数据

因为使用迭代器完成插入一段数据如果是使用移动的方式，那么在插入数据时比较复杂，所以这里我才已经的是先创建一个足够大的空间，然后将pos前面的数据放到这个新数组中去，然后插入数据，最后将pos后面的数据再放到这个新创建的数组中去。由此完成。

还有一个方法就是移动数据

iterator insert(iterator pos, size_t n, const T& x = T()) { size_t add = pos - _start;//首先找到pos在vector的哪一个位置 size_t len = size();//记录原本的空间大小 reserve(len + n+1);//扩容需要多扩容一个空间，否则在移动之后会导致 //_size指向超出容量的空间导致析构出错，析构出错的原因也就是 //_szie指向了超出容量的那一个空间，最后导致错误 pos = _start + add;//重新找到pos for (int i = _end - _start; i >= add; i--)//移动数据 { *(_start + i + n) = *(_start + i); } size_t times = n; while (times--) { *(_start + add) = x; add++; } _end = _start + len + n; return pos; }

需要注意的是如果使用这种方法俺么

下面是测试和运行截图：

erase函数

首先erase函数有两个版本，一个删除迭代器此时指向的那一个元素，还有一个是删除一段迭代去区间。

首先来完成删除迭代器指向的那一个元素。

//删除pos位置的元素 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _end); size_t len = pos - _start; for (int i = len; i < size(); i++) { *(_start + i) = *(_start + i + 1); }//从后往前移动数据 _end--; return _start + len;//最后返回删除数据后的那个迭代器 }//删除一个元素

删除一段迭代器区间的数据：

iterator erase(iterator first,iterator last) { assert(first >= _start); assert(first < _end); assert(last >= first); assert(last <= _end); if (last == _end)//删除从first开始往后的能删的所有元素 { _end = first;//直接让_end等于_first即可 return _; } else { //将last往后的元素从后往前移动即可 for (int i = last - _start; i <size(); i++) { *first = *(_start + i); first++; } _end = first; return _start; } }

测试即运行截图：

在完成了这两个函数之后，push_back和pop_back等函数就可以复用这两个函数完成了。我这里就不写了。

希望这篇博客对你能有所帮助，如果发现了任何错误，欢迎指出。我一定改正。