vector的模拟实现 总结

vector.h

1、迭代器的实现

#pragma oncenamespace JPC
{template<class T>class vector{public://对于存储空间是连续的结构而言，可以用原身指针来 模拟实现 迭代器。typedef T* iterator;typedef const T* const_iterator;//普通迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const iterator begin()const{return _start;}const iterator end()const {return _finish;}

2、求出 capacity \ size,以及实现下标遍历及修改：[]

//求出 capacity \ size,以及实现下标遍历及修改：[]//求出 capacitysize_t capacity()const{return _end_of_storage - _start;}//求出 sizesize_t size()const{return _finish - _start;}//实现下标遍历T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

3、取得首、尾数据

//取得首数据T& front(){assert(size()>0);return *_start;}//取得尾数据T& back(){assert(size()>0);return *(_finish-1);}

4、预先开辟空间：reserve

//预先开辟空间void reserve(size_t n){//预先保留 size() 的大小，因为一旦 delete过后，size()就变成0了size_t sz = size(); if (n>capacity()){//先开辟新空间T* tmp = new T[n];//如果旧空间数据存在，再将旧空间的数据拷贝到新空间，并且销毁旧空间if (_start){//memcpy(tmp,_start,sizeof(T)*size()); //浅拷贝//由 浅拷贝 改成 深拷贝for (size_t i=0;i<size();++i){tmp[i] = _start[i];}cout << endl;delete[] _start;}//最后，确定新空间的 _start \ _finish \ _end_of_storage_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

5、resize

//对于resize而言，模拟实现存在以下三种情况：//（1）n>capacity(), 需要扩容 + 初始化//（2）n>size()，只需要 初始化//（3）n<size(), 只需要 缩容void resize(size_t n,const T& val=T()){//扩容if (n>capacity()){reserve(n);}if (n>size()){//初始化填值while (_finish<_start+n){*_finish = val;++_finish;}}else{//缩容_finish = _start + n;}}

6、构造函数

//构造函数//(1)无参的构造函数vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//（2）用n个val去构造 vectorvector(size_t n,const T& val=T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i=0;i<n;++i){push_back(val);}}//(3)(嵌套模板)去构造 vectortemplate <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}

7、拷贝构造函数 与 赋值运算符重载

//拷贝构造函数(深拷贝)//（1）传统思维: 进行深拷贝，重新开个空间，拷贝数据过去// v1(v);vector(const vector<T>& v){//重新开空间_start = new T[v.size()];//拷贝数据过去//memcpy(_start,v._start,sizeof(T)*v.size());  //浅拷贝//由 浅拷贝 改成 深拷贝for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}cout << endl;_finish = _start + v.size();_end_of_storage = _start + v.size();}// v1.swap(v);void swap(vector<T>& v){::swap(_start,v._start);::swap(_finish, v._finish);::swap(_end_of_storage, v._end_of_storage);}(2)现代思维：找个打工人tmp，再复用构造函数 v1(v);//vector(const vector<T>& v)//	:_start(nullptr)//	, _finish(nullptr)//	, _end_of_storage(nullptr)//{//	vector<T> tmp(v.begin(),v.end());//	swap(tmp);//}//赋值运算符重载// v1=v; (现代思维)vector<T>& operator=(vector<T> v)//返回值vector<T>& 是为了实现 连= ；参数用传值拷贝，便于出了函数的作用域就销毁了{this->swap(v);return *this;}

8、析构函数

//析构函数~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

9、尾插、尾删； 插入、删除

//尾插void push_back(const T& x){先检测 是否需要扩容//if (_finish==_end_of_storage)//{//	reserve(capacity()==0 ? 4:capacity()*2);//}再插入数据//*_finish = x;//++_finish;insert(end(),x);}//尾删void pop_back(){//删除，防止越界了assert(_finish>_start);--_finish;}//插入iterator insert(iterator pos,const T& x){assert(pos>=_start && pos<=_finish);//先检测是否需要扩容if (_finish==_end_of_storage){//在扩容之前需要记录好pos的位置size_t len = pos - _start;reserve(capacity()==0 ? 4:capacity()*2);//扩容之后重新确定pos的位置pos = _start + len;}//再 从后往前 逐个挪动数据iterator end = _finish - 1;while (end>=pos){*(end+1) = *(end);--end;}//最后，插入数据*pos = x;++_finish;return pos;}//删除iterator erase(iterator pos){assert(pos>=_start && pos<_finish);iterator begin = pos;while (begin<_finish-1){*begin = *(begin+1);++begin;}--_finish;return pos;}private:iterator _start;  // _start为 vector存储的首个数据的地址（指针）iterator _finish; // _finish为 存储的末尾数据的下一个数据的地址iterator _end_of_storage; //_end_of_storage为 vector内开辟的最后一个空间的下一个空间的地址。};

一、测试 迭代器遍历、下标遍历、尾插、尾删

//测试 迭代器遍历、下标遍历、尾插、尾删
void test_vector1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//下标[]，遍历for (size_t i=0;i<v.size();++i){++v[i];}//迭代器遍历vector<int>::iterator it = v.begin();while (it != v.end()){--(*it);cout<< *it <<" ";++it;}cout << endl;v.pop_back();v.pop_back();for (size_t i=0;i<v.size();++i){cout<< v[i] <<" ";}cout << endl;

二、测试 const_iterator

//测试 const_iteratorvoid Func(const vector<int>& v){vector<int>::const_iterator it = v.begin();while (it != v.end()){//++(*it); //无法改变 *it 的值cout<< *it <<" ";++it;}cout << endl;}void test_vector2(){const vector<int> v(8,8);//const修饰的对象，只能在定义的时候初始化(赋值)，后面无法再改变。Func(v);}

三、用下标[]遍历，测试 insert 和 erase

//用下标[]遍历，测试 insert 和 erasevoid test_vector3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;v.insert(v.end(),5);for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;v.erase(v.end()-1);v.erase(v.begin());for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;}

四、测试 insert时，迭代器失效的状况

 //测试 insert时，迭代器失效的状况void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()){cout<< *it <<" ";++it;}cout << endl;auto p = find(v.begin(),v.end(),3); //支持了迭代器，就支持了stl里面的findif (p != v.end()){v.insert(p,30); //当需要在pos位置插入数据时，遇到了vector需要扩容的情况；注意在扩容之后，pos已经失效了（因为pos指向的是原来数组中的某个位置，现在旧数组已经销毁了）。}for (auto e:v){cout<< e <<" ";}cout << endl;}

五、补充：insert的迭代器失效

//补充：insert的迭代器失效void test_vector5(){vector<int> v;//v.reserve(10);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//要求在所有偶数前面插入该偶数二倍的数auto it = v.begin();while (it != v.end()){if (*it % 2==0){it=v.insert(it,(*it)*2);//迭代器失效的原因:(1)当没有提前reserve时：因为扩容导致的野指针问题。（2）当提前进行reserve时：pos指向的位置已经不是原来的值了（因为数据挪动）++it;++it;}else{++it;}}for (auto e:v){cout << e << " ";}cout << endl;}

六、erase的迭代器失效——原因是:(pos指向的位置已经不再是原来的值了【由于数据挪动】)

void test_vector6(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//要求删除所有的偶数auto it = v.begin();while (it != v.end()){没有迭代器更新的代码//if (*it % 2==0)//{//	v.erase(it);//}//++it;//有迭代器更新的代码if ((*it) % 2==0){it=v.erase(it); //要更新迭代器，也就是pos的位置}else{++it;}}for (auto e:v){cout<< e <<" ";}cout << endl;}//结论: insert/erase pos位置时，不要直接访问pos。一定要更新，直接访问可能会导致各种出乎意料的结果，这就是所谓的迭代器失效。//【要认为pos失效了，不要访问】

七、测试构造函数(嵌套模板类的，参数是迭代器区间)

//测试构造函数(嵌套模板类的，参数是迭代器区间)void test_vector7(){std::string s1("hello,world");vector<int> v(s1.begin(),s1.end());//这儿：从char进行整型提升到int, 最后打印出ascall码值。for (auto e:v){cout<< e <<" ";}cout << endl;}

八、测试拷贝构造函数

//测试拷贝构造函数void test_vector8(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto e:v){cout<< e <<" ";}cout << endl;//拷贝构造vector<int> v1(v);for (auto e : v){cout << e << " ";}cout << endl;}

九、测试 赋值运算符重载

 //测试 赋值运算符重载void test_vector9(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto e:v){cout << e << " ";}cout << endl;vector<int> v1;v1.push_back(0);v1.push_back(0);v1.push_back(0);v1.push_back(0);v1.push_back(0);v1 = v;for (auto e : v1){cout << e << " ";}cout << endl;}

十、测试 resize 的功能

//测试 resize的功能void test_vector10(){vector<int> v1;v1.resize(10,0);for (auto e:v1){cout<< e <<" ";}cout << endl;vector<int> v2;v2.reserve(10);v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);v2.resize(8,8);for (auto e:v2){cout << e << " ";}cout << endl;v2.resize(20,20);for (auto e : v2){cout << e << " ";}cout << endl;v2.resize(3,3);for (auto e : v2){cout << e << " ";}cout << endl;}

十一、打印出 杨辉三角形

//打印出 杨辉三角形
class Solution
{
public:vector<vector<int>> generate(int numRows){vector<vector<int>> vv;vv.resize(numRows);for (size_t i = 0; i < vv.size(); ++i){vv[i].resize(i + 1, 0); //先确定好各 vv[i]数组的容量大小vv[i].front() = vv[i].back() = 1; //先将 vv[i]数组中的第一个和最后一个元素置为1}//计算出剩余位置的数值for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){if (vv[i][j] == 0){vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}for (size_t i = 0; i < vv.size(); ++i){for (size_t j = 0; j < vv[i].size(); ++j){cout << vv[i][j] << " ";}cout << endl;}return vv;}};void test_vector11(){Solution().generate(5); //前面的 Solution() 是匿名对象}}

Test.cpp

#include <iostream>
#include <assert.h>
using namespace std;#include "vector.h"int main()
{JPC::test_vector11();return 0;
}