【初阶与进阶C++详解】第九篇：vector

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

文章目录

💎一、vector使用

🏆1.vector定义

vector()（重点）无参构造vector（size_type n, const value_type& val = value_type()）构造并初始化n个valvector (const vector& x); （重点）拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

intmain(){

    vector<int> first;//构造一个int类型容器
    vector<int>second(4,100);// 初始化4个100
    vector<int>third(second.begin(), second.end());// 区间初始化，将second从begin开始初始化到end
    vector<int>fourth(third);//拷贝构造//迭代器使用注意//注意迭代器解引用之后对用的string还是char
    vector<string>v1;
    v1.push_back("你好！");
    string s ="hello!";
    vector<char>v6(s.begin(), s.end());return0;}

🏆2.vector iterator 的使用

函数名称功能说明operator[] （重点）返回pos位置的字符，const string类对象调用begin+ endbegin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器rbegin + rendrbegin获取最后一个字符的迭代器 + rend获取第一个字符位置的迭代器范围forC++11支持更简洁的范围for的新遍历方式

intmain(){//1.下标+[]for(size_t i =0; i < v.size();++i){
        v[i]+=1;}//2.迭代器
    vector<int>::iterator it = v.begin();while(it != v.end()){*it -=1;
        cout <<*it <<" ";++it;}//3.范围forfor(auto e : v){
        cout << e <<" ";}return0;}

🏆3.迭代器失效问题

迭代器底层是一个指针，迭代器失效本质是迭代器底层对应指针所指向的空间被销毁了，有以下情况

1.扩容，增容，导致原有的空间被释放（但是迭代器指针依旧指向原空间变成野指针），比如：resize、reserve、insert、assign、
push_back等 。

voidTestVector1(){
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int>::iterator it = v.begin();while(it != v.end()){if(*it %2==0)//在偶数之前插入内容{//程序内出现了扩容，it原先指向的空间已经被释放//v.insert(it, 99);是错误写法//需要去insert中更新迭代器，具体看insert实现//下面是正确写法
            it = v.insert(it,99);    
            it++;}

        it++;}for(auto ch : v){
        cout << ch <<" ";}
    cout << endl;

2.erase导致数据删除，迭代器指向的位置意义变了

voidTestVector1(){
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    vector<int>::iterator it = v.begin();while(it != v.end()){if(*it %2==0)// 迭代器失效，因为删除会导致后面的数据往前挪动，迭代器还指向原来的位置，但是原来的位置上数据变了//错误写法：v.erase(it);
                    it = v.erase(it);// 正确写法，给迭代器重新赋值++it;}for(auto e : v){
        cout << e <<" ";}
    cout << endl;}

总结： 使用迭代器前记得对迭代器赋值，可以避免迭代器失效的问题产生。

💎二、vector模拟实现

🏆1.vector无参构造函数/析构函数/用n个val进行构造（注意重载）

template<classT>classvector{public://定义迭代器，在vector中，迭代器其实就是一个原生指针T*typedef T* iterator;typedefconst T* iterator;//无参初始化vector():_start(nullptr),_finish(nullptr),_endofstoage(nullptr){}~vector(){if(_start){delete[]_start;
            _start = _finish = _endofstoage =nullptr;}}vector(size_t n,const T& val =T()):_start(nullptr),_finish(nullptr),_endofstoage(nullptr){//1.写法一//resize(n, val);//2.写法二reserve(n);for(size_t i =0; i < n;++i){push_back(val);}}vector(int n,const T& val =T()):_start(nullptr),_finish(nullptr),_endofstoage(nullptr){resize(n, val);}private:
    iterator _start;//指向开头
    iterator _finish;//指向结尾数据的下一个位置
    iterator _endofstoage;//指向空间尾部};

如果我们只实现==vector(size_t n, const T& val = T())==这个版本不可以，如果出现以下情况

vector<char>v1(10,'x')//(int, char)可以成功调用
vector<int>v2(10,11)//(int, int)不能成功调用

第一个会去匹配vector(size_t n, const T& val = T())，因为类型符合

第二个回去匹配vector(InputIterator frist, InputIterator last)，因为他们类型最相似，一个是(int, int)，另一个是模板参数，然而匹配之后，由于传过去是int类型解引用就会报错，解决办法是，函数重载一个

🏆2.vector空间增长

size获取数据个数capacity获取容量大小empty判断是否为空resize（重点）改变vector的sizereserve （重点）改变vector放入capacity

1. capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的，单次增容多，浪费就会多
2. resize开空间会初始化
3. reserve只负责开辟空间,会修改原有空间template<classT>classvector{public://定义迭代器，在vector中，迭代器其实就是一个原生指针T*typedef T* iterator;typedefconst T* iterator; size_t size()const{return _finish - _start;} size_t capacity()const{return _endofstoage - _finish;} iterator begin(){return _start;} iterator end(){return _finish;} iterator begin()const{return _start;} iterator end()const{return _finish;}voidreserve(size_t n){//提前更新sz防止后面_start被更新,计算出原有的长度 size_t sz =size();if(n >capacity()){ T* tmp =new T[n];if(_start)//只有_start不为空才能进行拷贝操作{//memcpy(tmp, _start, size()*sizeof(T));//使用memcpy会存在浅拷贝问题//当遇到自定义类型比如string类，vector<T>，所以我们要一个一个拷贝数据for(size_t i =0; i <size();++i){ tmp[i]= _start[i];//手动赋值，当成员是自定义类型的时候，会调用重载}delete[] _start;} _start = tmp;} _finish = _start + sz; _endofstoage = _start + n;}//T()的含义是用模板参数的构造函数作为缺省值voidresize(size_t n, T val =T()){if(n >capacity()){reserve(n);}if(n >size()){while(_finish < _start + n){*_finish = val;++_finish;}}else{ _finish = _start + n;}}private://指针 iterator _start;//指向开头 iterator _finish;//指向结尾数据的下一个位置 iterator _endofstoage;//指向空间尾部};

🏆3.vector增删查改

push_back（重点）尾插pop_back （重点）尾删find查找。（注意这个是算法模块实现，包含< algorithm >头文件）insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[] （重点）像数组一样访问

template<classT>classvector{public://定义迭代器，在vector中，迭代器其实就是一个原生指针T*typedef T* iterator;typedefconst T* iterator;
    iterator insert(size_t pos,const T& x){//检查合法性assert(pos >= _start && pos <= _finish);//扩容//扩容之后pos失效(野指针)了，需要更新posif(_finish == _endofstoage){
            size_t n = pos - _start;
            size_t newcapacity = capacit y()==0?4:capacity()*2;reserve(newcapacity);
            pos = _start + n;}//挪动数据
        iterator end = _finish-1;while(end >= pos){*(end +1)=*end;--end;}*pos = x;++_finish;return pos;}
    iterator erase(size_t pos){assert(pos >= _start && pos <= _finish);
        iterator it = pos +1;while(it != _finish){*(it -1)=*it;++it;}--_finish;return pos;}//使用引用传参防止深拷贝voidpush_back(const T& x){//如果满了if(_finish == _endofstoage){
            size_t newcapacity =capacity()==0?4:capacity()*2;reserve(newcapacity);}*_finish = x;
        _finish++;}voidpop_back(){if(_finish > _start){
            _finish--;}}
    T&operator[](size_t pos){assert(pos <size());return _start[pos];}const T&operator[](size_t pos)const{assert(pos <size());return _start[pos];}voidclear(){
        _finish = _start;}boolempty(){returnsize()==0;}private://指针
    iterator _start;//指向开头
    iterator _finish;//指向结尾数据的下一个位置
    iterator _endofstoage;//指向空间尾部};

🏆4.vector的迭代器区间构造/拷贝构造/赋值

template<classT>classvector{public://定义迭代器，在vector中，迭代器其实就是一个原生指针T*typedef T* iterator;typedefconst T* iterator;//迭代区间构造，利用指针解引用尾插内容，（如果没有空间会reserve扩容）template<classInputIterator>vector(InputIterator frist, InputIterator last):_start(nullptr),_finish(nullptr),_endofstoage(nullptr){while(frist != last){push_back(*frist);++frist;}}//使用库函数swap交换thsi和tmp成员变量，构造完成之后，tmp生命周期结束voidswap(vector<T>& v){
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endofstoage, v._endofstoage);}//拷贝构造//利用迭代器构造一个tmp对象，再与this交换vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstoage(nullptr){
        vector<T>tmp(v.begin(), v.end());swap(tmp);}//直接传值，将传过来的值与this交换
    vector<T>&operator=(vector<T> v){swap(v);return*this;}private:
    iterator _start;//指向开头
    iterator _finish;//指向结尾数据的下一个位置
    iterator _endofstoage;//指向空间尾部};

🏆5.自定义类型的拷贝问题

为什么在的reserve实现中，使用赋值重载，而没有使用memcpy？

leetcode118杨辉三角

classSolution{public:
    vector<vector<int>>generate(int numRows){//定义一个二维数组vv
        vector<vector<int>> vv;//初始化行数
        vv.resize(numRows);for(size_t i =0; i < vv.size();++i){//每一行递增
            vv[i].resize(i+1,0);//每一行的第一个和最后一个初始化为1
            vv[i][0]=1;
            vv[i][vv[i].size()-1]=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-1]+vv[i-1][j];}}}return vv;}};

1. 目前两层vector进行嵌套]使用，外层的vector存放的是内层vector的对象。
2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
3. 如果只用memcpy进行浅拷贝，相当于新的空间里面存放的是的确是新的vector对象，但这些vector对象存放的却是原有数据的指针，而原本的数据已经被我们delete掉了，出现了野指针问题。