vector.h

1、迭代器的實(shí)現(xiàn)

#pragma oncenamespace JPC
{template<class T>class vector{public://對(duì)于存儲(chǔ)空間是連續(xù)的結(jié)構(gòu)而言，可以用原身指針來 模擬實(shí)現(xiàn) 迭代器。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,以及實(shí)現(xiàn)下標(biāo)遍歷及修改：[]

//求出 capacity \ size,以及實(shí)現(xiàn)下標(biāo)遍歷及修改：[]//求出 capacitysize_t capacity()const{return _end_of_storage - _start;}//求出 sizesize_t size()const{return _finish - _start;}//實(shí)現(xiàn)下標(biāo)遍歷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、取得首、尾數(shù)據(jù)

//取得首數(shù)據(jù)T& front(){assert(size()>0);return *_start;}//取得尾數(shù)據(jù)T& back(){assert(size()>0);return *(_finish-1);}

4、預(yù)先開辟空間：reserve

//預(yù)先開辟空間void reserve(size_t n){//預(yù)先保留 size() 的大小，因?yàn)橐坏?delete過后，size()就變成0了size_t sz = size(); if (n>capacity()){//先開辟新空間T* tmp = new T[n];//如果舊空間數(shù)據(jù)存在，再將舊空間的數(shù)據(jù)拷貝到新空間，并且銷毀舊空間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

//對(duì)于resize而言，模擬實(shí)現(xiàn)存在以下三種情況：//（1）n>capacity(), 需要擴(kuò)容 + 初始化//（2）n>size()，只需要 初始化//（3）n<size(), 只需要 縮容void resize(size_t n,const T& val=T()){//擴(kuò)容if (n>capacity()){reserve(n);}if (n>size()){//初始化填值while (_finish<_start+n){*_finish = val;++_finish;}}else{//縮容_finish = _start + n;}}

6、構(gòu)造函數(shù)

//構(gòu)造函數(shù)//(1)無參的構(gòu)造函數(shù)vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//（2）用n個(gè)val去構(gòu)造 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)(嵌套模板)去構(gòu)造 vectortemplate <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}

7、拷貝構(gòu)造函數(shù) 與 賦值運(yùn)算符重載

//拷貝構(gòu)造函數(shù)(深拷貝)//（1）傳統(tǒng)思維: 進(jìn)行深拷貝，重新開個(gè)空間，拷貝數(shù)據(jù)過去// v1(v);vector(const vector<T>& v){//重新開空間_start = new T[v.size()];//拷貝數(shù)據(jù)過去//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)現(xiàn)代思維：找個(gè)打工人tmp，再?gòu)?fù)用構(gòu)造函數(shù) v1(v);//vector(const vector<T>& v)//	:_start(nullptr)//	, _finish(nullptr)//	, _end_of_storage(nullptr)//{//	vector<T> tmp(v.begin(),v.end());//	swap(tmp);//}//賦值運(yùn)算符重載// v1=v; (現(xiàn)代思維)vector<T>& operator=(vector<T> v)//返回值vector<T>& 是為了實(shí)現(xiàn) 連= ；參數(shù)用傳值拷貝，便于出了函數(shù)的作用域就銷毀了{this->swap(v);return *this;}

8、析構(gòu)函數(shù)

//析構(gòu)函數(shù)~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

9、尾插、尾刪； 插入、刪除

//尾插void push_back(const T& x){先檢測(cè) 是否需要擴(kuò)容//if (_finish==_end_of_storage)//{//	reserve(capacity()==0 ? 4:capacity()*2);//}再插入數(shù)據(jù)//*_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);//先檢測(cè)是否需要擴(kuò)容if (_finish==_end_of_storage){//在擴(kuò)容之前需要記錄好pos的位置size_t len = pos - _start;reserve(capacity()==0 ? 4:capacity()*2);//擴(kuò)容之后重新確定pos的位置pos = _start + len;}//再 從后往前 逐個(gè)挪動(dòng)數(shù)據(jù)iterator end = _finish - 1;while (end>=pos){*(end+1) = *(end);--end;}//最后，插入數(shù)據(jù)*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存儲(chǔ)的首個(gè)數(shù)據(jù)的地址（指針）iterator _finish; // _finish為 存儲(chǔ)的末尾數(shù)據(jù)的下一個(gè)數(shù)據(jù)的地址iterator _end_of_storage; //_end_of_storage為 vector內(nèi)開辟的最后一個(gè)空間的下一個(gè)空間的地址。};

一、測(cè)試 迭代器遍歷、下標(biāo)遍歷、尾插、尾刪

//測(cè)試 迭代器遍歷、下標(biāo)遍歷、尾插、尾刪
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);//下標(biāo)[]，遍歷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;

二、測(cè)試 const_iterator

//測(cè)試 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修飾的對(duì)象，只能在定義的時(shí)候初始化(賦值)，后面無法再改變。Func(v);}

三、用下標(biāo)[]遍歷，測(cè)試 insert 和 erase

//用下標(biāo)[]遍歷，測(cè)試 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;}

四、測(cè)試 insert時(shí)，迭代器失效的狀況

 //測(cè)試 insert時(shí)，迭代器失效的狀況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); //當(dāng)需要在pos位置插入數(shù)據(jù)時(shí)，遇到了vector需要擴(kuò)容的情況；注意在擴(kuò)容之后，pos已經(jīng)失效了（因?yàn)閜os指向的是原來數(shù)組中的某個(gè)位置，現(xiàn)在舊數(shù)組已經(jīng)銷毀了）。}for (auto e:v){cout<< e <<" ";}cout << endl;}

五、補(bǔ)充：insert的迭代器失效

//補(bǔ)充：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);//要求在所有偶數(shù)前面插入該偶數(shù)二倍的數(shù)auto it = v.begin();while (it != v.end()){if (*it % 2==0){it=v.insert(it,(*it)*2);//迭代器失效的原因:(1)當(dāng)沒有提前reserve時(shí)：因?yàn)閿U(kuò)容導(dǎo)致的野指針問題。（2）當(dāng)提前進(jìn)行reserve時(shí)：pos指向的位置已經(jīng)不是原來的值了（因?yàn)閿?shù)據(jù)挪動(dòng)）++it;++it;}else{++it;}}for (auto e:v){cout << e << " ";}cout << endl;}

六、erase的迭代器失效——原因是:(pos指向的位置已經(jīng)不再是原來的值了【由于數(shù)據(jù)挪動(dòng)】)

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);//要求刪除所有的偶數(shù)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;}//結(jié)論: insert/erase pos位置時(shí)，不要直接訪問pos。一定要更新，直接訪問可能會(huì)導(dǎo)致各種出乎意料的結(jié)果，這就是所謂的迭代器失效。//【要認(rèn)為pos失效了，不要訪問】

七、測(cè)試構(gòu)造函數(shù)(嵌套模板類的，參數(shù)是迭代器區(qū)間)

//測(cè)試構(gòu)造函數(shù)(嵌套模板類的，參數(shù)是迭代器區(qū)間)void test_vector7(){std::string s1("hello,world");vector<int> v(s1.begin(),s1.end());//這兒：從char進(jìn)行整型提升到int, 最后打印出ascall碼值。for (auto e:v){cout<< e <<" ";}cout << endl;}

八、測(cè)試拷貝構(gòu)造函數(shù)

//測(cè)試拷貝構(gòu)造函數(shù)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;//拷貝構(gòu)造vector<int> v1(v);for (auto e : v){cout << e << " ";}cout << endl;}

九、測(cè)試 賦值運(yùn)算符重載

 //測(cè)試 賦值運(yùn)算符重載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;}

十、測(cè)試 resize 的功能

//測(cè)試 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]數(shù)組的容量大小vv[i].front() = vv[i].back() = 1; //先將 vv[i]數(shù)組中的第一個(gè)和最后一個(gè)元素置為1}//計(jì)算出剩余位置的數(shù)值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() 是匿名對(duì)象}}

Test.cpp

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