企业官网建设流程全解析

目录

一 vector的介绍及使用
1、vector的介绍
2、vector的使用

二 vector在OJ中的使用

三 vector深度剖析及模拟实现

一、vector的介绍及使用
1、vector的介绍

std::vector是动态顺序数组，底层是一块连续堆内存；会自动扩容，下标随机访问O(1)

2、vector的使用

1.2.1 vector的构造

• 可以不传参构造
• 可以构造并初始化n个val，val类型是第一个模板参数
• 可拷贝构造
• 可使用迭代器进行初始化构造

//无参构造vector<int>v1;vector<string>v2;//构造并初始化n个valvector<int>v3(10,1);//拷贝构造vector<int>v4(v3);//用迭代器初始化构造vector<int>v5(v3.begin(),v3.end());

1.2.2 vector iterator的使用

这里vector的迭代器与string的迭代器大致相同，而且由于范围for底层有迭代器实现，所以范围for也适用于vector

//initializer_list也可以用来初始化vector,initializer_list有迭代器//{...}先传给initializer_list，再用范围for将里面的值赋值到v中vector<int>v={1,2,3,4,5,6,7,8,9,10};constvector<int>const_v={1,2,3};for(vector<int>::iterator it1=v.begin();it1!=v.end();it1++){cout<<*it1<<" ";}cout<<endl;for(vector<int>::const_iterator it2=const_v.begin();it2!=const_v.end();it2++){cout<<*it2<<" ";}cout<<endl;//倒着遍历for(vector<int>::const_reverse_iterator it3=const_v.crbegin();it3!=const_v.crend();it3++){cout<<*it3<<" ";}

1.2.3 vector空间增长问题

• size_type size() const;获取数据个数
• size_type capacity() const;获取容量大小
• bool empty() const;判断是否为空
• void resize (size_type n, value_type val = value_type());改变vector的size
• void reserve (size_type n);改变vector的capacity
  
  1.2.4 vector增删查改
  
• void push_back (const value_type& val);尾插
• void pop_back();尾删
• template <class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val);查找（在算法模块，不是vector的成员函数）
• iterator insert (iterator position, const value_type& val);在position位置前插入val
• iterator erase (iterator position);删除position位置数据
• void swap (vector& x);交换两个vector的数据空间
• reference operator[] (size_type n);像数组一样访问vector

vector<int>v;intold_capacity=v.capacity();cout<<old_capacity<<endl;for(inti=1;i<100;i++){v.push_back(i);if(v.capacity()!=old_capacity){old_capacity=v.capacity();cout<<old_capacity<<endl;}}v.insert(find(v.begin(),v.end(),10),{1,2});for(auto&e:v){cout<<e<<" ";}cout<<endl;intnum;cin>>num;v.erase(find(v.begin(),v.end(),num));for(auto&e:v){cout<<e<<" ";}

二、vector在OJ中的使用
2.1 只出现一次的数字
只出现一次的数字

intsingleNumber(vector<int>&nums){//0与任何数异或的结果都是任何数intn=0;for(auto&e:nums){n^=e;}returnn;}

2.2 杨辉三角OJ
杨辉三角OJ

vector<vector<int>>generate(intnumRows){vector<vector<int>>vv;vv.resize(numRows,vector<int>());for(inti=0;i<numRows;i++){vv[i].resize(i+1,1);}//从第三行第二列开始初始化for(inti=2;i<vv.size();i++){for(intj=1;j<vv[i].size()-1;j++)vv[i][j]=vv[i-1][j]+vv[i-1][j-1];}returnvv;}

2.3 删除排序数组中的重复项
删除排序数组中的重复项

intremoveDuplicates(vector<int>&nums){if(nums.size()==1)return1;intdst=0,src=1;while(src<nums.size()){if(nums[src]>nums[dst])nums[++dst]=nums[src];src++;}returndst+1;}

2.4 只出现一次的数II
只出现一次的数II

intsingleNumber(vector<int>&nums){map<int,int>mp;for(constauto&e:nums){mp[e]++;}intans;for(auto&t:mp){if(t.second==1){ans=t.first;break;}}returnans;}

2.5 只出现一次的数字III
只出现一次的数字III

vector<int>singleNumber(vector<int>&nums){vector<int>ans;map<int,int>mp;for(auto&e:nums){mp[e]++;}intcnt=0;for(auto&t:mp){if(t.second==1){ans.push_back(t.first);cnt++;}if(cnt==2)break;}returnans;}

2.6 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字

intMoreThanHalfNum_Solution(vector<int>&numbers){// write code heresort(numbers.begin(),numbers.end());returnnumbers[numbers.size()/2];}

2.7 电话号码字母组合
电话号码字母组合

classSolution{public:vector<string>ans;string ret;vector<vector<char>>vv={{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};voiddfs(string&digits,intpos){if(pos==digits.size()){ans.push_back(ret);return;}intn=digits[pos]-'2';for(intj=0;j<vv[n].size();j++){ret.push_back(vv[n][j]);dfs(digits,pos+1);ret.pop_back();}}vector<string>letterCombinations(string digits){dfs(digits,0);returnans;}};

三 vector深度剖析及模拟实现

• 迭代器失效问题：
  迭代器的主要作用就是让算法能够不关心底层数据结构，其底层实际是一个指针。因此迭代器失效，实际是迭代器底层对应指针指向的空间被销毁了，使用一块已经被销毁的空间，会使程序崩溃。
  1.会使迭代器失效的操作有：会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、assign、push_back等
  2.erase操作：
  在vs环境下，会对失效的迭代器进行严格检查，所以在erase操作后，应更新迭代器。而在Linux下，g++对迭代器失效检测并不非常严格，但为保证代码的可移植性，最好要更新迭代器
  3.与vector类似，string在进行插入+扩容操作后，迭代器也会失效
• 扩容时将原数据拷贝进新空间时的操作：
  不能使用memcpy，因为当vector中存储的是自定义类型时，如string类型，memcpy只会进行浅拷贝，将存储数据的_str地址拷贝过来，而释放原空间资源时，_str已被销毁，因此要调用深拷贝的拷贝构造将原数据拷贝进新空间。

vector.h:

#pragmaonce#include<iostream>#include<cassert>#include<utility>#include<string>#include<type_traits>usingnamespacestd;namespacemyspace{template<classT>classvector{public:typedefT*iterator;typedefconstT*const_iterator;iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorcbegin(){return_start;}const_iteratorcend(){return_finish;}vector()=default;vector(vector<T>&v){reserve(v.capacity());for(auto&e:v){*_finish=e;++_finish;}}vector(initializer_list<T>il){reserve(il.size());for(auto&e:il){push_back(e);}}template<classInputIterator,class=typenameenable_if<!is_integral<InputIterator>::value>::type>vector(InputIterator first,InputIterator last){iterator it=first;while(it!=last){push_back(*it);it++;}}vector(size_t n,constT&val=T()){reserve(n);while(_finish!=_start+n){*_finish=val;++_finish;}}~vector(){delete[]_start;_finish=_endofstorage=_start=nullptr;}vector<T>&operator=(vector<T>tmp){swap(tmp);return*this;}size_tsize(){return_finish-_start;}size_tcapacity(){return_endofstorage-_start;}voidreserve(size_t n){if(n>capacity()){size_t old_size=size();T*tmp=newT[n];for(size_t i=0;i<old_size;i++){tmp[i]=_start[i];}delete[]_start;_start=tmp;_finish=_start+old_size;_endofstorage=_start+n;}}voidresize(size_t n,constT&x=T()){if(n>size()){reserve(n);while(size()<n){*_finish=x;++_finish;}}else{_finish=_start+n;}}constT&operator[](size_t pos)const{assert(pos<size());return_start[pos];}T&operator[](size_t pos){assert(pos<size());return_start[pos];}boolempty(){return_finish==_start;}voidpush_back(constT&x){if(_finish==_endofstorage){reserve(capacity()==0?4:capacity()*2);}*_finish=x;++_finish;}voidpop_back(){assert(size()>0);--_finish;}iteratorinsert(iterator pos,constT&val){assert(pos>=_start);assert(pos<=_finish);if(_finish==_endofstorage){intsub=pos-_start;reserve(capacity()==0?4:capacity()*2);pos=_start+sub;}iterator end=_finish;while(end!=pos){*end=*(end-1);end--;}*pos=val;_finish++;returnpos;}iteratorerase(iterator pos){assert(pos>=_start);assert(pos<_finish);iterator end=pos;while(end!=_finish-1){*end=*(end+1);end++;}--_finish;returnpos;}voidclear(){_finish=_start;}voidswap(vector&v){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}private:T*_start=nullptr;T*_finish=nullptr;T*_endofstorage=nullptr;};}

test.cpp:

#include"vector.h"namespacemyspace{template<classContainer>voidPrint(Container&v){for(auto&e:v){cout<<e<<" ";}cout<<endl;}voidtest01(){vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.pop_back();vector<int>v2={1,2,3,4,5,6};v2.insert(v2.begin()+3,100);Print(v);Print(v2);//删除v2中的偶数for(vector<int>::iterator it=v2.begin();it!=v2.end();){if((*it)%2==0){//防止it迭代器失效要更新迭代器it=v2.erase(it);}elseit++;}Print(v2);vector<int>v3(v2.begin(),v2.end()-1);Print(v3);vector<int>v4(5,5);Print(v4);v4=v3;Print(v4);cout<<v4.size()<<endl;v4.resize(10);cout<<v4.size()<<endl;}voidtest02(){vector<string>v;v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");Print(v);}}intmain(){myspace::test02();return0;}