C++第二十二弹---vector深度剖析及模拟实现(下)

2024-05-31 12:12
文章标签 c++ 实现 剖析 深度 模拟 vector 第二十二

本文主要是介绍C++第二十二弹---vector深度剖析及模拟实现(下)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 ✨个人主页： 熬夜学编程的小林

💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】

目录

1、容量操作

2、内容修改操作

3、打印函数

4、迭代器失效

4.1、什么是迭代器失效

4.2、哪些操作会引起迭代器失效

总结

1、容量操作

size()、capacity()

获取容器的有效数据个数(连续内存空间的指针相减计算的就是间隔的元素个数)和分配给当前空间的大小，以元素个数表示。

size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _endofstorage - _start;
}

 reserve(size_t n)

扩容。如果n大于当前容量则扩容，小于等于当前容量则不处理。

void reserve(size_t n)//将容量个数扩大到n
{if (n > capacity())//大于容量才扩容{size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;//加[]_start = tmp;//_finish = _start + size();//_start的地址改变了 size()结果变化_finish = _start + old_size;_endofstorage = _start + n;}
}

这里我们开空间完成的是一个深拷贝的过程，用 memcpy 将旧数组中的数据拷贝到新数组，但是memcpy 在这里基于字节的拷贝，即浅拷贝，那么，如果我们vector实例化为string类，这里string类进行浅拷贝会涉及到二次释放等问题。

解决办法：

通过一个循环，使用赋值操作符(自定义类型会调用赋值操作符重载)逐个拷贝旧数组中的元素到新数组。

void reserve(size_t n)//将容量个数扩大到n
{if (n > capacity())//大于容量才扩容{size_t old_size = size();T* tmp = new T[n];for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];//调用赋值操作符重载，深拷贝}delete[] _start;//加[]_start = tmp;//_finish = _start + size();//_start的地址改变了 size()结果变化_finish = _start + old_size;_endofstorage = _start + n;}
}

 注意：

需要提前计算原空间的大小，防止后面计算的大小是错误的，因为扩容的时候_start指针会修改指向，而_finish还指向原空间。

resize(size_t n)

调整容器的大小，使其包含n个元素。

如果n小于当前容器大小，则内容将减少到其前n个元素，删除超出的元素（并销毁它们）。

如果n大于当前容器大小，则通过在末尾插入所需数量的元素来扩展内容，以达到n的大小。如果指定了val，则将新元素初始化为val，否则初始化为缺省值。

如果n也大于当前容器容量，则自动重新分配所分配的存储空间。

void resize(size_t n,const T& val=T())//将容量修改为n个，并初始化为val
{if (n > capacity()){//扩容reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}else{//删除_finish = _start + n;//更改_finish位置即可，一般不缩容}
}

注意：

当 n 小于当前容量时，只需修改 _finish 指向即可，一般情况不缩容，如需缩容，可以调用shrink_to_fit()缩容函数。

2、内容修改操作

push_back()

尾插数据。即在_finish位置插入数据，在插入数据之前需要判断空间是否已满。

void push_back(const T& val)
{if (_finish == _endofstorage)//扩容{reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = val;++_finish;
}

 pop_back()

尾删数据(有数据才能删)。删除最后一个数据，修改_finish指向即可。

void pop_back()
{assert(!empty());--_finish;
}

empty()

判断容器是否为空(判断_start与_finish指向是否一致)，为空返回true，否则返回false。 

bool empty()
{return _start == _finish;
}

insert() 

在pos位置插入数据。

1.使用断言保证在[_start,_finish]区间插入数据

2.判断是否需要扩容，扩容则可能出现迭代器失效情况，则需要提前计算pos 位置与 _start之间的距离。

3.将[pos,_finish)之间的数据都向后挪动一步，再pos位置插入数据。

4.最后返回新的pos位置。

iterator insert(iterator pos, const T& val)//在pos位置插入val
{assert(pos >= _start);assert(pos <= _finish);//扩容if (_finish == _endofstorage){size_t len = pos - _start;//标记pos与原数组起点的长度reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;//扩容_start的指向修改，pos也需修改}//移动数据iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}//填充数据*pos = val;++_finish;return pos;//返回新的pos位置
}

 erase()

删除pos位置的数据。

1.使用断言保证在[_start,_finish)区间删除数据，此处跟插入不同，不能删除_finsih位置数据

2.将[pos + 1,_finish)之间的数据都向前挪动一步。

iterator erase(iterator pos)//删除pos位置数
{assert(pos >= _start);assert(pos < _finish);//iterator it = pos;iterator it = pos + 1;while (it < _finish){//*it = *(it + 1);//it = pos; 越界*(it - 1) = *it;it++;}--_finish;return pos;
}

erase 返回值是一个迭代器，指向原来pos位置的下一个位置，即删除操作之后的pos位置。

push_back()  pop_back()

尾插和尾删函数，使用insert()和erase()函数调用。

void push_back(const T& val)
{insert(end(), val);//在end()位置插入数据
}void pop_back()
{erase(end() - 1);//删除end()前面位置数据
}

3、打印函数

print_vector()

打印vector容器的数据(任意类型)。

template<class T>//函数模板
void print_vector(const vector<T>& v)
{//前面加typename则没有问题，表示iterator是一个类型//typename vector<T>::iterator it = v.begin();auto it = v.begin();//此处使用auto则可以避免此问题while (it != v.end()){cout << *it << " ";it++;//指向下一个位置}cout << endl;
}

 注意：

显示访问迭代器时，需要在前面加关键字typename保证iterator是一个类型，或者直接使用auto。

4、迭代器失效

4.1、什么是迭代器失效

迭代器的作用：主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装。

迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。我们可以从以下三步进行分析：

  • [1]迭代器的本质就是指针，迭代器失效就是指针失效。
  • [2]指针失效：指针指向的空间是非法的。
  • [3]指针指向非法空间：指向了被释放的空间 或者 越界访问 。

4.2、哪些操作会引起迭代器失效

  1. 所有可能会引起扩容的操作都可能会导致迭代器失效。如：resize、reserve、insert、assign、push_back等  --------------  野指针引起的迭代器失效
  2. 指定位置的插入和删除都会都可能会导致迭代器失效。如: insert 、erase -----------------   迭代器指向的位置意义发生改变

注意：

上述可能会引起迭代器失效的问题，代码中基本已经解决，如果uu们发现解决的有问题可以私信博主喔！！！

总结


本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！

这篇关于C++第二十二弹---vector深度剖析及模拟实现(下)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1017887。

相关文章

Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2