重庆市建设网站,外贸选品网站,ps做电商网站流程图,橘子seo历史查询vector的模拟实现 总结 vector.hTest.cpp vector.h
1、迭代器的实现
#pragma oncenamespace JPC
{templateclass Tclass vector{public://对于存储空间是连续的结构而言#xff0c;可以用原身指针来 模拟实现 迭代器。typedef T* iterator;typedef const T* const_i… vector的模拟实现 总结 vector.hTest.cpp vector.h
1、迭代器的实现
#pragma oncenamespace JPC
{templateclass Tclass 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 (ncapacity()){//先开辟新空间T* tmp new T[n];//如果旧空间数据存在再将旧空间的数据拷贝到新空间并且销毁旧空间if (_start){//memcpy(tmp,_start,sizeof(T)*size()); //浅拷贝//由 浅拷贝 改成 深拷贝for (size_t i0;isize();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而言模拟实现存在以下三种情况//1ncapacity(), 需要扩容 初始化//2nsize()只需要 初始化//3nsize(), 只需要 缩容void resize(size_t n,const T valT()){//扩容if (ncapacity()){reserve(n);}if (nsize()){//初始化填值while (_finish_startn){*_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 valT()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i0;in;i){push_back(val);}}//(3)(嵌套模板)去构造 vectortemplate class InputIteratorvector(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 vectorT 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(vectorT v){::swap(_start,v._start);::swap(_finish, v._finish);::swap(_end_of_storage, v._end_of_storage);}(2)现代思维找个打工人tmp再复用构造函数 v1(v);//vector(const vectorT v)// :_start(nullptr)// , _finish(nullptr)// , _end_of_storage(nullptr)//{// vectorT tmp(v.begin(),v.end());// swap(tmp);//}//赋值运算符重载// v1v; (现代思维)vectorT operator(vectorT v)//返回值vectorT 是为了实现 连 参数用传值拷贝便于出了函数的作用域就销毁了{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 (endpos){*(end1) *(end);--end;}//最后插入数据*pos x;_finish;return pos;}//删除iterator erase(iterator pos){assert(pos_start pos_finish);iterator begin pos;while (begin_finish-1){*begin *(begin1);begin;}--_finish;return pos;}private:iterator _start; // _start为 vector存储的首个数据的地址指针iterator _finish; // _finish为 存储的末尾数据的下一个数据的地址iterator _end_of_storage; //_end_of_storage为 vector内开辟的最后一个空间的下一个空间的地址。};
一、测试 迭代器遍历、下标遍历、尾插、尾删
//测试 迭代器遍历、下标遍历、尾插、尾删
void test_vector1()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//下标[]遍历for (size_t i0;iv.size();i){v[i];}//迭代器遍历vectorint::iterator it v.begin();while (it ! v.end()){--(*it);cout *it ;it;}cout endl;v.pop_back();v.pop_back();for (size_t i0;iv.size();i){cout v[i] ;}cout endl;二、测试 const_iterator
//测试 const_iteratorvoid Func(const vectorint v){vectorint::const_iterator it v.begin();while (it ! v.end()){//(*it); //无法改变 *it 的值cout *it ;it;}cout endl;}void test_vector2(){const vectorint v(8,8);//const修饰的对象只能在定义的时候初始化(赋值)后面无法再改变。Func(v);}三、用下标[]遍历测试 insert 和 erase
//用下标[]遍历测试 insert 和 erasevoid test_vector3(){vectorint 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(){vectorint 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(){vectorint 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 % 20){itv.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(){vectorint 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 % 20)//{// v.erase(it);//}//it;//有迭代器更新的代码if ((*it) % 20){itv.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);vectorint v(s1.begin(),s1.end());//这儿从char进行整型提升到int, 最后打印出ascall码值。for (auto e:v){cout e ;}cout endl;}八、测试拷贝构造函数
//测试拷贝构造函数void test_vector8(){vectorint 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;//拷贝构造vectorint v1(v);for (auto e : v){cout e ;}cout endl;}
九、测试 赋值运算符重载 //测试 赋值运算符重载void test_vector9(){vectorint 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;vectorint 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(){vectorint v1;v1.resize(10,0);for (auto e:v1){cout e ;}cout endl;vectorint 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:vectorvectorint generate(int numRows){vectorvectorint 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.hint main()
{JPC::test_vector11();return 0;
}
