C++ Vector的模拟实现

Hello！！大家早上中午晚上好！！昨天我们练习了vector的使用，今天就来实现一下吧！！！

一、构建vector

1.1首先实现vector需要两个文件

一个.h文件用来声明和定义所使用到的类、变量、函数等；

一个.cpp文件用来对实现好的代码测试；

因为vector是模版类，所以最好定义和声明写在统一文件内；

1.2明确实现vector类需要用到的变量和方法

需要用到的变量：

①一个start指针指向头；

②一个finish指针指向有效数据末尾；

③一个endofstorage指针指向存储空间末尾；

需要实现的方法：

①vector的构造函数（包括用n个val构造、开n个空间并初始化为0构造）；

②vector的拷贝构造；

③vector的赋值重载；

④vector的析构函数；

⑤vector的迭代器；

⑥vector的尾插尾删；

⑦vector的任意位置插入删除；

⑧vector下标访问（operator[]）；

⑨vector开空间并初始化函数resize；

⑩vector开空间不初始化函数reserve；

1.3声明到头文件再逐个实现

为了避免跟库里的vector名字冲突，自己开辟一个命名空间

#pragma once
//类型、变量、函数等的声明文件
namespace ldc
{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public:iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;vector(size_t n, const T& val = T());vector(const vector<T>& v);vector<T>& operator=(const vector<T>& v);~vector();void push_back(const T& val);void pop_back();iterator insert(iterator pos, const T& val);iterator erase(iterator pos);T& operator[](size_t n);const T& operator[](size_t n)const;void resize(size_t n,const T&val=T());void reserve(size_t n);private:T* _start;T* _finish;T* _endofStorage;};
}

二、方法实现

2.1vector的构造函数

因为vector用n个val初始化构造，和开n个空间初始化为0构造类似resize函数，所以先实现resize跟reserve函数再复用就行；

实现前先把待会要用到的函数实现了先：

	const T& operator[](size_t n)//下标访问不可修改{return _start[n];}T& operator[](size_t n)//下标访问可以修改{return _start[n];}size_t size()//返回有效元素个数{return _finish - _start;}size_t capacity()//返回容量{return _endofStorage - _start;}

2.2resize、reserve的实现

void resize(size_t n, const T& val = T())//开空间初始化
{if (n < size()){_finish = _start + n;}else{reserve(n);for (size_t i = size(); i < n; i++){_start[i] = val;}_finish = _start + n;}
}
void reserve(size_t n)//开空间不初始化
{if (n > capacity()){T* tmp = new T[n];size_t size = size();for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + size;_endofStorage = _start + n;}
}

2.3迭代器的实现

iterator begin()//返回开始位置的迭代器
{return _start;
}
iterator end()//返回结束位置的迭代器
{return _finish;
}
const_iterator begin()const//const 迭代器
{return _start;
}
const_iterator end()const
{return _finish;
}

2.4 构造函数

	vector():_start(nullptr), _finish(nullptr), _endofStorage(nullptr){}vector(size_t n, const T& val = T()){resize(n, val);//复用resize}

测试一下：

int main()
{ldc::vector<int> v1;for (auto e : v1){cout << e << " ";}cout << endl;ldc::vector<int> v2(3);for (auto e : v2){cout << e << " ";}cout << endl;ldc::vector<int> v3(2, 2);for (auto e : v3){cout << e << " ";}cout << endl;return 0;
}

没问题，继续实现拷贝构造跟赋值；

2.5拷贝构造跟赋值重载

vector(const vector<T>& v)
{size_t cap = v.capacity();T* temp = new T[cap];for (size_t i=0;i<v.size();i++){temp[i] = v[i];}_start = temp;_finish = _start + v.size();_endofStorage = _start+cap;
}
void swap(vector<T>& v)//用swap函数交换
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofStorage, v._endofStorage);
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

测试：

int main()
{ldc::vector<int> v1(3, 2);ldc::vector<int> v2(3,1);ldc::vector<int> v3(v1);for (auto e : v3){cout << e << " ";}cout << endl;v1 = v2;for (auto e : v1){cout << e << " ";}cout << endl;return 0;
}

没问题，接着实现vector的增删改

三、vector的增删查改

3.1任意位置插入

	iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _endofStorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//防止迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}++_finish;*pos = val;return pos;}

3.2 任意位置删除

	iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos;while (end+1<_finish){*end = *(end + 1);++end;}--_finish;return pos;}

3.3尾插、尾删复用insert、erase

		void push_back(const T& val){insert(end(), val);}void pop_back(){erase(end()-1);}

3.4测试

int main()
{ldc::vector<int> v1(3, 3);v1.insert(v1.begin() + 1, 6);v1.push_back(6);for (auto e : v1){cout << e << " ";}cout << endl;v1.erase(v1.begin());v1.pop_back();for (auto e : v1){cout << e << " ";}cout << endl;return 0;
}

ok没问题；

四、完成

//.h文件
#pragma once
//类型、变量、函数等的声明和定义文件
#include <assert.h>
namespace ldc//命名空间
{template<class T>//模版类class vector{typedef T* iterator; //迭代器typedef const T* const_iterator;//const 迭代器public:iterator begin()//返回开始{return _start;}iterator end()//返回末尾{return _finish;}const_iterator begin()const//返回的指向的内容不可修改{return _start;}const_iterator end()const{return _finish;}const T& operator[](size_t n)const //下标访问（只读）{return _start[n];}T& operator[](size_t n)//下标访问，读写{return _start[n];}size_t size()const//获取有效数据个数{return _finish - _start;}size_t capacity()const//获取容量大小{return _endofStorage - _start;}vector()//默认构造:_start(nullptr), _finish(nullptr), _endofStorage(nullptr){}vector(size_t n, const T& val = T())//n个val构造{resize(n, val);//复用resize}void reserve(size_t n)//开空间不初始化{if (n > capacity()){T* tmp = new T[n];size_t sz = size();for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + sz;_endofStorage = _start + n;}}void resize(size_t n, const T& val = T())//开空间初始化{if (n < size()){_finish = _start + n;}else{reserve(n);for (size_t i = size(); i < n; i++){_start[i] = val;}_finish = _start + n;}}vector(const vector<T>& v)//拷贝构造{size_t cap = v.capacity();_start = new T[cap];for (size_t i=0;i<v.size();i++){_start[i] = v[i];}_finish = _start + v.size();_endofStorage = _start+cap;}void swap(vector<T>& v)//两个vector对象交换{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofStorage, v._endofStorage);}vector<T>& operator=(vector<T> v)//赋值重载{if(_finish!=v._finish)swap(v);return *this;}~vector()//析构{if (_start){delete[] _start;}_start = _finish = _endofStorage = nullptr;}void push_back(const T& val)//尾插{insert(end(), val);}void pop_back()//尾删{erase(end()-1);}iterator insert(iterator pos, const T& val)//任意位置插入{assert(pos >= _start && pos <= _finish);if (_finish == _endofStorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//防止迭代器失效问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}++_finish;*pos = val;return pos;}iterator erase(iterator pos)//任意位置删除{assert(pos >= _start && pos < _finish);iterator end = pos;while (end+1<_finish){*end = *(end + 1);++end;}--_finish;return pos;}private:T* _start;T* _finish;T* _endofStorage;};
}