vector的实现
目录
1.vector的底层
2.vector构造函数的实现
①构造函数
②拷贝构造
3.访问函数实现
3.1迭代器iterator
3.2下标+[]访问
4.析构函数和计算size、capacity、swap简单函数的实现
①析构函数：
②计算size：
③计算capacity：
④swap函数
5. reserve（提前开空间函数实现）
6.尾插尾删函数
7.insert指定位置插入实现
8.设计程序验证
源代码（vector.h）
1.vector的底层
我们在之前的文章顺序表的实现中了解到：
其底层存在一个指向动态开辟数组的指针、一个表示元素个数的size和一个表示顺序表容量大小的capacity。
而vector使用了一个start、一个finish和一个end_of_storage,虽然二者的表示形式不同，实则都有相同的道理，如图：
现在我们就依据此来实现一下vector。
2.vector构造函数的实现
①构造函数
class vector
{
public:vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}
private://全缺省为空iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;
}②拷贝构造
//①传统写法//vector(const vector<T>& v)//{// _start = new T[v.capacity()];//先开空间// memcpy(_start, v._start, v.size() * sizeof(T));// _finish = _start + v.size();// _endofstorage = _start + v.capacity();//}//②现代写法vector(const vector<T>& v){reserve(v.capacity());//首先开一个与旧空间一样的新空间for (const auto& e : v)//添加引用&，防止深拷贝{push_back(e);//复用push_back函数}}③析构函数
~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}3.访问函数实现
3.1迭代器iterator
①普通迭代器可读可写：
//普通迭代器 可读可写
typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}②const迭代器可读不可写：
//const迭代器 可读不可写
typedef const T* const_iterator;
const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}3.2下标+[]访问
①普通函数，可读可写：
//①可读可写T& operator[](size_t pos){assert(pos < size());//检查是否越界return _start[pos];//返回pos位置字符的引用，既可读又可写}②const函数，可读不可写：
//②可读不可写const T& operator[](size_t pos) const {assert(pos < size());//检查是否越界return _start[pos];//返回pos位置字符的引用，既可读又可写}4.析构函数和计算size、capacity、swap简单函数的实现
①析构函数：
//析构函数~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}②计算size：
size_t size() const{return _finish - _start;}③计算capacity：
size_t capacity() const{return _endofstorage - _start;}④swap函数
void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}有了swap函数，我们就可以复用swap函数实现赋值构造函数：
//赋值vector<T>& operator=(vector<T> v)//注意这里不能添加&引用，如v3=v1//无&引用表示v是v1的临时拷贝，v3再拷贝v，出了作用域v就会被销毁，不会改变v1//而加上&引用则直接表示v1与v3交换了，即可以认为这里实现了swap函数的功能{swap(v);//复用swap函数return *this; }5. reserve（提前开空间函数实现）
void reserve(size_t n){if (n > capacity())//如果原容量<需要的新空间，就开辟新空间{T* tmp = new T[n];//开辟新空间if (_start)//判断原vector是否为空{//如果原vector不为空，就将从_start位置开始的n*sizeof(T)个数据拷贝到新空间tmp里memcpy(tmp, _start, n * sizeof(T));delete[] _start;//释放旧空间}//再指向新空间_start = tmp;_finish = _start + size();_endofstorage = _start + capacity()；}这样写程序出现了bug：
这是因为
因为size()=_finish - _start;
所以_finish=_start+_finish-_start=_finish
可是这里的_start已经指向了新空间，而_finish指向的还是旧空间
一个空间的末尾 - 另一个空间的开头 ==== 错误！
_endofstorage = _start + capacity();
同样的道理，capacity()还是旧空间，_start是新空间 也= 错误！
所以这里正确的做法应该是_endofstorage = _start + n;
正确代码：
void reserve(size_t n){if (n > capacity())//如果原容量<需要的新空间，就开辟新空间{size_t old = size();//在扩容之前将size()先保存一下T* tmp = new T[n];//开辟新空间if (_start)//判断原vector是否为空{//如果原vector不为空，就将从_start位置开始的old*sizeof(T)个数据拷贝到新空间tmp里memcpy(tmp, _start, old * sizeof(T));delete[] _start;//释放旧空间}//再指向新空间_start = tmp;_finish = _start + old;_endofstorage = _start + n;}}完成了reserve函数，我们就可以复用reserve函数实现拷贝构造的现代写法：
//②现代写法vector(const vector<T>& v){reserve(v.capacity());//首先开一个与旧空间一样的新空间for (const auto& e : v)//添加引用&，防止深拷贝{push_back(e);//复用push_back函数}}6.尾插尾删函数
//尾插函数void push_back(const T& x){if (_finish == _endofstorage)//判断vector有没有满{size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//如果满了就扩容reserve(newcapacity);}//扩容之后赋值*_finish = x;++_finish; }//尾删函数void pop_back(){assert(size() > 0);--_finish;}7.insert指定位置插入实现
void insert(iterator pos, const T& x)//在pos位置之前插入x{assert(pos <= _finish && pos >= _start);//检查pos是否合法//检查vector是否充满if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容}//把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置memmove(pos + 1, pos, sizeof(T) * (_finish - pos));*pos = x;//挪动之后再把x放到pos位置++_finish;}这段代码在实际运行时有时会出现错误，这是为什么呢？
原因是：
reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
观察reserve函数：不扩容还好，当发生扩容时，reserve会销毁旧空间
此时_start指向新空间，pos仍然指向旧空间，pos在扩容之后失效了
因此这里的解决办法就是计算偏移量，更新一下pos的值
正确代码：
void insert(iterator pos, const T& x)//在pos位置之前插入x{assert(pos <= _finish && pos >= _start);//检查pos是否合法//检查vector是否充满if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容pos = _start + len;}//把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置memmove(pos + 1, pos, sizeof(T) * (_finish - pos));*pos = x;//挪动之后再把x放到pos位置++_finish;}8.设计程序验证
void test_vector(){vector <int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//迭代器访问vector <int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";++it;}cout << endl;//范围for访问for (auto e : v1){cout << e << " ";}cout << endl;//下标+[]访问for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;}
源代码（vector.h）
#pragma once#include <iostream>
#include <assert.h>using namespace std;namespace xxk
{template<class T>class vector{public:typedef T* iterator;//普通迭代器 可读可写typedef const T* const_iterator;//const迭代器 可读不可写//构造函数vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}//拷贝构造//①传统写法//vector(const vector<T>& v)//{// _start = new T[v.capacity()];//先开空间// memcpy(_start, v._start, v.size() * sizeof(T));// _finish = _start + v.size();// _endofstorage = _start + v.capacity();//}//②现代写法vector(const vector<T>& v){reserve(v.capacity());//首先开一个与旧空间一样的新空间for (const auto& e : v)//添加引用&，防止深拷贝{push_back(e);//复用push_back函数}}//赋值vector<T>& operator=(vector<T> v)//注意这里不能添加&引用，如v3=v1//无&引用表示v是v1的临时拷贝，v3再拷贝v，出了作用域v就会被销毁，不会改变v1//而加上&引用则直接表示v1与v3交换了，即可以认为这里实现了swap函数的功能{swap(v);//复用swap函数return *this; }//析构函数~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}//迭代器begin()和end()实现//普通迭代器 可读可写iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器 可读不可写const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//size capacity函数size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}//下标+[]访问函数的实现//①可读可写T& operator[](size_t pos){assert(pos < size());//检查是否越界return _start[pos];//返回pos位置字符的引用，既可读又可写}//②可读不可写const T& operator[](size_t pos) const {assert(pos < size());//检查是否越界return _start[pos];//返回pos位置字符的引用，既可读又可写}//reserve扩容函数//error：//void reserve(size_t n)//{// if (n > capacity())//如果原容量<需要的新空间，就开辟新空间// {// T* tmp = new T[n];//开辟新空间// if (_start)//判断原vector是否为空// {// //如果原vector不为空，就将从_start位置开始的n*sizeof(T)个数据拷贝到新空间tmp里// memcpy(tmp, _start, n * sizeof(T));// delete[] _start;//释放旧空间// }// //再指向新空间// _start = tmp;// _finish = _start + size();// //因为size()=_finish - _start;// //所以_finish=_start+_finish-_start=_finish// //可是这里的_start已经指向了新空间，而_finish指向的还是旧空间// //一个空间的末尾 - 另一个空间的开头 ==== 错误！// _endofstorage = _start + capacity();// //同样的道理，capacity()还是旧空间，_start是新空间 也= 错误！// //所以这里正确的做法应该是_endofstorage = _start + n;// }//}void reserve(size_t n){if (n > capacity())//如果原容量<需要的新空间，就开辟新空间{size_t old = size();//在扩容之前将size()先保存一下T* tmp = new T[n];//开辟新空间if (_start)//判断原vector是否为空{//如果原vector不为空，就将从_start位置开始的old*sizeof(T)个数据拷贝到新空间tmp里memcpy(tmp, _start, old * sizeof(T));delete[] _start;//释放旧空间}//再指向新空间_start = tmp;_finish = _start + old;_endofstorage = _start + n;}}//resize函数//尾插函数void push_back(const T& x){if (_finish == _endofstorage)//判断vector有没有满{size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//如果满了就扩容reserve(newcapacity);}//扩容之后赋值*_finish = x;++_finish; }//尾删函数void pop_back(){assert(size() > 0);--_finish;}//指定位置插入（insert）函数//error://void insert(iterator pos, const T& x)//在pos位置之前插入x//{// assert(pos <= _finish && pos >= _start);//检查pos是否合法// //检查vector是否充满// if (_finish == _endofstorage)// {//reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容观察reserve函数：不扩容还好，当发生扩容时，reserve会销毁旧空间此时_start指向新空间，pos仍然指向旧空间，pos在扩容之后失效了因此这里的解决办法就是计算偏移量，更新一下pos的值// }// //把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置// memmove(pos + 1, pos, sizeof(T) * (_finish - pos));// *pos = x;//挪动之后再把x放到pos位置// ++_finish;//}void insert(iterator pos, const T& x)//在pos位置之前插入x{assert(pos <= _finish && pos >= _start);//检查pos是否合法//检查vector是否充满if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容pos = _start + len;}//把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置memmove(pos + 1, pos, sizeof(T) * (_finish - pos));*pos = x;//挪动之后再把x放到pos位置++_finish;}//swap函数void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}private://全缺省为空iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};void test_vector(){vector <int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//迭代器访问vector <int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";++it;}cout << endl;//范围for访问for (auto e : v1){cout << e << " ";}cout << endl;//下标+[]访问for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;}
}