vector模拟实现

vector就是一个动态的顺序表，可以存放任何元素，其中使用三个指针（start，finish，end_of_storage）进行实现，本文将实现5个模块中常用的的接口。

 此图大致为vector的结构。

首先声明迭代器以及维护的指针：

typedef T* Itreator;
private:
		Itreator start;
		Itreator finish;
		Itreator end_of_storage;

一、构造和析构

本文实现四种构造方法；

（1）无参构造：对三个指针进行初始化： 

Vector()
 :start(nullptr)
 , finish(nullptr)
 , end_of_storage(nullptr)
{}

（2）使用n个data构造对象：首先申请空间存储n个元素，然后在对指针进行位置进行修改。

Vector(int n, const T& data=T())
		{
			start = new T[n];
			for (int i = 0; i < n; i++) {
				start[i] = data;
			}

			finish = start + n;
			end_of_storage = finish;
		}

（3）使用迭代器进行区间构造：同样先申请空间，对指针进行解引用进行赋值，然后维护指针

Vector(Itreator first, Itreator last)
		{
			start = new T[last - first];
			finish = start;
			auto it = first;
			while (it != last) {
				*finish++ = *it++;
			}
			end_of_storage = finish;
		}

（4）拷贝构造：这个主要防止浅拷贝的问题。

Vector(const Vector& v)
		{
			start = new T[v.capacity()];
			for (int i = 0; i < v.size(); i++) {
				start[i] = v[i];
			}
			finish = start + v.size();
			end_of_storage = start+v.capacity();
		}

（5）析构函数：防止对一块空间进行重复回收，所以首先进行判断是否为空。

~Vector()
		{
			if (start) {
				delete[] start;
				start = finish = end_of_storage = nullptr;
			}
		}

二、容量操作

(1)size()，vector中存储有效元素的个数

int size() const{
			return finish - start;
		}

(2)capacity()，vector的容量

int capacity() const{
			return end_of_storage - start;
		}

(3)empty()：判断是否为空

bool empty() {
			if (start == finish) {
				return true;
			}
			return false;
		}

(4)reserve(int newcapacity)：首先要知道vector扩容规律（缩小空间忽略，扩大空间进行操作）修改vector的容量，重新申请空间，将原来空间的元存储到新空间中，然后回收原来start的空间，将新申请的空间赋值给start，并且修改空间容量。

void reserve(int newcapacity) {
			int oldcapacity = capacity();
			int sz = size();
			if (newcapacity > oldcapacity) {

				T* temp = new T[newcapacity];

				for (int i = 0; i < sz; i++) {
					temp[i] = start[i];
					
				}

				delete[] start;
				
				start = temp;
				finish = start + sz;
				
				end_of_storage = start + newcapacity;
				
				
			}
		}

(5)resize(n,data)，改变有效元素个数，首先判断是否需要修改空间容量，则是否进行扩容操作，然后对指针进行解引用赋值。

void resize(int newsize,const T& data=T()) {
			if (newsize < size()) {
				finish = start+newsize;
				return;
			}
			if (capacity() < newsize) {
				reserve(capacity() * 2+3);
			}
			
			auto it = finish;
			
			finish = start + newsize;

			while (it != finish) {
				*it = data;
				it++;
			}
			
		}

三、元素访问

（1）operator[](index)：可以理解为重载运算符。

		T& operator[](int index) const
		{
			return start[index];
		}

(2)at(index)：访问序号为index的元素

		T& at(int index) const
		{
			return start[index-1];
		}

四、迭代器

		Itreator begin(){
			return start;
		}
		Itreator end() {
			return finish;
		}
		Itreator rbegin() {
			return finish;
		}
		Itreator rend() {
			return start;
		}

五、修改

（1）push_back(data)，尾插，插入完成后维护指针

void push_back(const T& data) {
			if (finish == end_of_storage) {
				reserve(capacity() * 2 + 1);
			}
			*finish = data;
			finish++;
		}
		
		

(2)pop_back()：尾删，删除完成后维护指针

void pop_back() {
			finish--;
		}

(3)erase(pos)：删除指定位置元素。

void erase(int pos) {
			if (pos > size()) {
				cout << "error" << endl;
			}
			for (int i = pos - 1; i < size(); i++) {
				start[i] = start[i + 1];
			}
			finish--;
		}

六、源程序：

#include
using namespace std;
namespace my {
	template
	class Vector {
	public:
		typedef T* Itreator;
		Vector()
			:start(nullptr)
			, finish(nullptr)
			, end_of_storage(nullptr)
		{
		}
		Vector(int n, const T& data=T())
		{
			start = new T[n];
			for (int i = 0; i < n; i++) {
				start[i] = data;
			}

			finish = start + n;
			end_of_storage = finish;
		}
		Vector(Itreator first, Itreator last)
		{
			start = new T[last - first];
			finish = start;
			auto it = first;
			while (it != last) {
				*finish++ = *it++;
			}
			end_of_storage = finish;
		}
		Vector(const Vector& v)
		{
			start = new T[v.capacity()];
			for (int i = 0; i < v.size(); i++) {
				start[i] = v[i];
			}
			finish = start + v.size();
			end_of_storage = start+v.capacity();
		}
		int size() const{
			return finish - start;
		}
		int capacity() const{
			return end_of_storage - start;
		}
		Itreator begin(){
			return start;
		}
		Itreator end() {
			return finish;
		}
		Itreator rbegin() {
			return finish;
		}
		Itreator rend() {
			return start;
		}
		T& at(int index) const
		{
			return start[index-1];
		}
		T& operator[](int index) const
		{
			return start[index];
		}
		bool empty() {
			if (start == finish) {
				return true;
			}
			return false;
		}
		void reserve(int newcapacity) {
			int oldcapacity = capacity();
			int sz = size();
			if (newcapacity > oldcapacity) {

				T* temp = new T[newcapacity];

				for (int i = 0; i < sz; i++) {
					temp[i] = start[i];
					
				}

				delete[] start;
				
				start = temp;
				finish = start + sz;
				
				end_of_storage = start + newcapacity;
				
				
			}
		}
		void resize(int newsize,const T& data=T()) {
			if (newsize < size()) {
				finish = start+newsize;
				return;
			}
			if (capacity() < newsize) {
				reserve(capacity() * 2+3);
			}
			
			auto it = finish;
			
			finish = start + newsize;

			while (it != finish) {
				*it = data;
				it++;
			}
			
		}
		void push_back(const T& data) {
			if (finish == end_of_storage) {
				reserve(capacity() * 2 + 1);
			}
			*finish = data;
			finish++;
		}
		void pop_back() {
			finish--;
		}
		void erase(int pos) {
			if (pos > size()) {
				cout << "error" << endl;
			}
			for (int i = pos - 1; i < size(); i++) {
				start[i] = start[i + 1];
			}
			finish--;
		}
		~Vector()
		{
			if (start) {
				delete[] start;
				start = finish = end_of_storage = nullptr;
			}
		}
	private:

		Itreator start;
		Itreator finish;
		Itreator end_of_storage;
	};
}

此代码在vs2019可以成功编译。