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

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<