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

2024-05-31 12:12

本文主要是介绍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

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.