vector类详解及重要函数实现

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

         今日主菜:vector类

         主厨:邪王真眼

          所属专栏:c++专栏

          主厨的主页:Chef‘s blog

坚持下去,成功不是目的,而是结果!


前言:

           刚刚开始学c++,相信很多朋友对这门新的语言都充满了好奇,那么今天就来份硬菜满足一下各位,铛铛铛铛,c++第二座大山:STL容器之vector,他来了!

【本节目标】

  • 1.vector的介绍及使用

  • 2.vector深度剖析及模拟实现

1.vector的介绍

  • 1. vector是表示可变大小数组的序列容器。
  • 2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  • 3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
  • 4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  • 5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
  • 6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起listforward_list统一的迭代器和引用更好。
  • 使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习

二.成员变量

  • _start(指向有效空间的头)
  • _finish(指向有效空间的尾)
  • _end_of_storage(指向可用空间的尾)

2.1细节:

  1. 三个成员变量均迭代器(此刻即指针)
  2. 在声明处使用缺省值,赋值为nullptr

2.2代码展示:

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};

二、默认成员函数

2.1构造函数(constructor)

2.1.1

第一个参数是存放元素个数,第二个是每个初始化的值并且是缺省参数

vector(size_t n,T val=T()):_start(new T[n]), _finish(_start + n), _end_of_storage(_finish)
{iterator it = _start;while (it != _finish){*it = val;it++;}
}

注意,我们缺省参数值不是'\0'或0,而是T(),T是数据类型,T()是匿名构造,不过这里可能有朋友要问了:“自定义类型可以匿名构造我懂,但是内置类型也可以吗?”你别说,还真行。

但是指针的内置类型只有在这种模板中才可以用例如:

具体原因不用去了解,只要知道在这里有这个用法就行了。

2.1.2迭代器区间构造

  1. 使用类模板,可以传任意类型的迭代器
  2. 迭代器访问,条件最好使用不等于(!=)

为什么不用大于或小于呢,在string,vector很容易写出大于小于的重载,可是链表呢树呢?他们的空间不连续啊,所以从普适性的角度来看还是用!=更合适。

template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

2.2析构函数(destructor)

~vector()
{delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;
}

2.3拷贝构造函数

2.3.1传统写法:

细节:memcpy可能造成浅拷贝,带来危害。例如vector<vector<int>>,则元素类型是vector<int>,使用memcpy会导致将vector<int>对象直接拷贝而没有重新开辟空间,并对vector<int>对象进行复制

所以我们用=赋值,因为已经对=进行了重载,属于深拷贝。

vector(vector<T>&v1)
{size_t size = v1.size();iterator it = new T[size];//memcpy(it, v1._start, sizeof(T) * size);for (int i = 0; i < v1.size(); i++){it[i] = v1[i];}_start = it;_finish = _start + size;_end_of_storage = _start + v1.capacity();
}

2.3.2现代写法:
通过迭代器区间实现,先构造临时对象,再用swap函数使*this和tmp交换

vector(vector<T>& v1){vector<T>tmp(v1.begin(), v1.end());swap(tmp);}
void swap(vector<T>v)
{swap(_start, v1._start);swap(_finish, v1._finish);swap(_end_of_storage, v1._end_of_storage);
}

2.4 赋值运算操作符重载(operator=)

2.4.1传统写法

vector<T> operator=(vector<T>&v1)
{if (&v1 != this){size_t size = v1.size();iterator it = new T[size];//memcpy(it, v1._start, sizeof(T) * size);for (int i = 0; i < v1.size(); i++){it[i] = v1[i];}delete[]_start;_start = it;_finish = _start + size;_end_of_storage = _start + v1.capacity();}return *this;
}

2.4.2现代写法

  1. 传参变成传值,这样就会拷贝构造出一个临时对象
  2. 再使用vector中的swap,交换*this和tmp的值,完成赋值重载
vector<T> operator=(vector<T>v1)
{swap(v1);return *this;
}

三.迭代器

3.1 begin

迭代器的实现和编译器有关,不同的编译器有不同的实现方式。这里用指针来实现迭代器。

同时,重载了普通迭代器和const迭代器。

typedef T* iterator;
typedef const T* const_iterator;	
iterator begin(){return _start;}const_iterator begin()const{return _start;}

3.2 end

迭代器遵循左闭右开的原则,begin指向首元素,end指向末元素的下一位。

iterator end()
{return _finish;
}
const_iterator end()const
{return _finish;
}

关于rbegin和rend我们之后再讲

四、容量

4.1 size

获取当前有效数据个数

细节:const修饰,保证普通和const类型vector类都能访问

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

4.2 capacity

获取当前最大有效容量

细节:

capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。

size_t capacity()const
{return _end_of_storage - _start;
}

4.3 reserve

细节:

  • 只扩容,不缩容
  • 用赋值重载,进行深拷贝
  • 记得保存size的大小。因为更新_start后还没有更新_finish,所以此时size()的值是没有意义的。
  • 只修改capacity,不修改size
  • reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
	void reserve(size_t Size){if(Size>capacity()){int size_ = size();iterator it = new T[Size];for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];}delete[] _start;_start = it;_finish = _start + size_;_end_of_storage = _start + Size;}}

4.4 resize

改变当前有效数据个数

细节:

  1. 只扩容不缩容
  2. 如果n<size,则减少有效个数,如果n>size,则填充指定值,直至达到n个
  3. 运用赋值重载,实现深拷贝
  4. capacity和size都修改
void resize(size_t Size,T val=T())
{if (Size <= size()){_finish = _start + Size;}else{if (size > capacity()){iterator it = new T[Size];for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];}_start = it;_finish = _start + Size;_end_of_storage = _finish;}for (iterator it = _start + size(); it < _start + Size; it++){*it = val;}}
}

4.5 empty

判断是否为空

细节:const修饰,保证普通和const类型vector类都能访问

bool empty()const
{return _finish - _start == 0;
}

五、修改

5.1 push_back

尾插

细节:需要扩容时,判断容量是否为空

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

5.2 pop_back

尾删

细节:断言vector不为空,才进行删除

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

5.3 insert

指定位置插入

细节:

  1. 断言判断pos的合法性
  2. 扩容前,先保存pos的相对位置,扩容后,刷新pos并返回,防止迭代器失效
  3. 接受返回值,防止迭代器失效
  4. iterator insert(iterator pos,T&val)
    {assert(pos <= _finish);assert(pos >= _start);if (_finish == _end_of_storage){int Pos = pos - _start;int Size = size();iterator it = new T[capacity() == 0 ? 4 : capacity() * 2];memcpy(it, _start, size() * sizeof(T));_start = it;_finish = _start + Size;_end_of_storage = _finish;pos = _start + Pos;}iterator end = _finish;while (end > pos){*end = *(end - 1);}*end = val;_finish++;return pos;
    }

    5.4 erase

    指定位置删除

    细节:

  5. 断言判断pos的合法性
  6. 返回指向删除元素的后一位的迭代器,防止迭代器失效
iterator erase(iterator pos)
{assert(pos < _finish);assert(pos >= _start);iterator it = pos;while (pos < _finish-1){*pos = *(pos + 1);pos++;}_finish--;return it;
}
void erase(iterator begin,iterator end)
{assert(begin < _finish);assert(begin >= _start);assert(end <= _finish);assert(end>= _start);assert(begin <= end);iterator a = begin;iterator b = end;while (b < _finish){*a = *b;a++, b++;}_finish = _start + size()-(end - begin);
}

5.5 swap

交换两个vector类的值

细节:使用std库中的swap函数,交换各个成员变量的值

void swap(vector<T>v)
{swap(_start, v1._start);swap(_finish, v1._finish);swap(_end_of_storage, v1._end_of_storage);
}

5.6 operator[ ]

为了方便的访问元素,我们重载了[ ]运算符。同时,也分为普通版本和const版本,对应const对象和非const对象

T& operator[](const int i)
{assert(i < size());return *(_start + i);
}
const T& operator[](const int i)const
{assert(i < size());return *(_start + i);
}

5.7 vector 迭代器失效问题。(重点)

5.7.1问题分析

迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:vector的迭代器就是原生态指针T* 。因此迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有: 
  • 1.会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、 push_back、
  • 2.erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。
  • 3.注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端
  • 4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效

5.7.2问题解决

迭代器失效解决办法:在使用前,对迭代器重新赋值即可

5.8 使用memcpy拷贝问题

假设模拟实现的 vector 中的 reserve 接口中,使用 memcpy 进行的拷贝,以下代码会发生什么问题?

问题分析:

1. memcpy 是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素, memcpy 既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy 的拷贝实际是浅拷贝。

 

结论:如果对象中涉及到资源管理时,千万不能使用 memcpy 进行对象之间的拷贝,因为 memcpy 浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

总结

在学习了string的基础之上,可以很明显发现vector的学习成本降低了不少,函数名和用法大体相同。但是,我们依旧遇到了新的问题与挑战,如深拷贝,迭代器失效等。不过都被一一克服了,ok,那么,vector,over!

客官留个赞再走吧

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284723.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

抖音IP属地怎么更改

抖音是一个非常受欢迎的短视频平台&#xff0c;吸引了无数用户在上面分享自己的生活和才艺。然而&#xff0c;随着快手的火爆&#xff0c;一些用户开始担心自己的IP地址会被他人获取&#xff0c;引起个人隐私风险。那么&#xff0c;抖音用户又该如何更改到别的地方呢&#xff1…

babyos 学习记录

宏定义头文件 将一个宏定义取不同的数据到不同的数组中&#xff1b; 侵入式链表 struct list_head { struct list_head *next, *prev; }; // 添加&#xff08;list_add_tail/list_add&#xff09;、删除、查找 xx.h // 定义一个用于链表管理的结构体 typedef sturct{ xxx …

2024-03-24 思考-MBTI-简要记录

摘要: 2024-03-24 思考-MBTI-简要记录 MBTI16型人格: MBTI16型人格在人格研究和评价中得到了广泛的应用。MBTI是一种基于瑞士心理学家荣格在理论基础上发展起来的人格分类工具。为了准确判断个人的心态偏好&#xff0c;将每个人分为16种不同的人格类型。这种分类方法不仅为我们…

Websocket + Vue使用

这里有一篇文档可以参考一下> 闪现 POM文件 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId><version>2.7.0</version> </dependency> WebSocketConf…

手撕算法-删除有序数组中的重复项

描述 很简单&#xff0c;就是&#xff0c;遇到重复的&#xff0c;只留一个&#xff0c;保存在数组的左半边。如&#xff1a;[0,0,1,1,1,2,2,3,3,4]变为[0,1,2,3,4] 分析 使用双指针。slow指针代表没重复的数应该放置的位置&#xff0c;fast表示遍历的不重复数字的位置&…

【Linux更新驱动、cuda和cuda toolkit】

目录 1. 更新显卡驱动1.1. 查看当前显卡驱动版本1.2. 删除原始显卡驱动1.3. 删除CUDA Toolkit1.4. 在NVIDIA官网找到2080Ti对应的最新驱动程序 2. 更新CUDA Toolkit2.1. 下载CUDA Toolkit2.2. 安装.run2.3. 添加环境变量2.4. 检查是否安装好了 最近需要更新服务器的显卡驱动和C…

SpringBoot3使用响应Result类返回的响应状态码为406

Resolved [org.springframework.web.HttpMediaTypeNotAcceptableException: No acceptable representation] 解决方法&#xff1a;Result类上加上Data注解

文件包含一-WEB攻防-PHP应用文件包含LFIRFI伪协议编码算法无文件利用黑白盒

演示案例&#xff1a; 文件包含-原理&分类&利用&修复黑盒利用-VULWEB-有无包含文件白盒利用-CTFSHOW-伪协议玩法 #文件包含-原理&分类&利用&修复 1、原理 程序开发人员通常会把可重复使用的函数写到单个文件中&#xff0c;在使用某些函数时&#xff0c…

YOLOV5 改进:替换backbone为Swin Transformer

1、前言 本文会将YOLOV5 backbone更换成Swin Transformer 具体为什么这样实现参考上文:YOLOV5 改进:替换backbone(MobileNet为例)-CSDN博客 这里只贴加入的代码 训练结果如下: 2、common文件更改 在common文件中加入下面代码: 这里是swin transformer的实现,参考:…

React函数组件Hook

问题: 相对于类组件, 函数组件的编码更简单, 效率也更高, 但函数组件不能有state (旧版) 解决: React 16.8版本设计了一套新的语法来让函数组件也可以有state Hook 是 React 16.8 的新增特性。它可以让你在不编写 class 的情况下使用 state 以及其他的 React 特性 Hook也叫钩子…

软件测试 -- Selenium常用API全面解答(java)

写在前面 // 如果文章有问题的地方, 欢迎评论区或者私信指正 目录 什么是Selenium 一个简单的用例 元素定位 id定位 xpath定位 name定位 tag name 定位和class name 定位 操作元素 click send_keys submit text getAttribute 添加等待 显示等待 隐式等待 显示等…

【网络安全】CobaltStrike 使用

本文章仅用于信息安全学习&#xff0c;请遵守相关法律法规&#xff0c;严禁用于非法途径。若读者因此作出任何危害网络安全的行为&#xff0c;后果自负&#xff0c;与作者无关。 Cobalt Strike是一款渗透测试神器&#xff0c;Cobalt Strike已经不再使用MSF而是作为单独的平台使…

[NLP] 初窥000001

NL(natural language)–自然语言 人类的语言–中文&#xff0c;英语&#xff0c;法语 NLP(Natural Language Processing)–自认语言处理 计算机处理人类语言的技术&#xff0c;它包含翻译、智能问答、文本分类、情感分析等常见应用。 CV(Computational Vision) 感知NLP 认知…

Vue使用font-face自定义字体详解

目录 1 介绍2 使用2.1 语法2.2 属性说明2.3 Vue使用案例2.3.1 全局定义字体2.3.2 在页面使用 3 注意事项 1 介绍 font-face 是 CSS 中的一个规则&#xff0c;它允许你加载服务器上的字体文件&#xff08;远程或者本地&#xff09;&#xff0c;并在网页中使用这些字体。这样&am…

【C语言】——指针四:字符指针与函数指针变量

【C语言】——指针四&#xff1a;字符指针与函数指针变量 一、字符指针二、函数指针变量2.1、 函数指针变量的创建2.2、两段有趣的代码 三、typedef关键字3.1、typedef的使用3.2、typedef与define比较 四、函数指针数组 一、字符指针 在前面的学习中&#xff0c;我们知道有一种…

LeetCode Python - 71. 简化路径

目录 题目描述解法运行结果 题目描述 给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &#xff08;以 ‘/’ 开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中&#xff0c;一个点&#xff08;.&…

【电气安全】ASCP电气防火限流式保护器/末端回路线路保护

为什么要使用电气防火限流式保护器&#xff1f; 应急管理部消防救援局统计&#xff0c;在造成电气火灾事故的原因中&#xff0c;最为主要的当为末端线路短路&#xff0c;在电气火灾事故中占比高达70%以上。如何效预防末端线路短路引发的电气火灾事故&#xff1f; 现阶段最为常…

jmeter断言使用方法

断言主流的有两种&#xff1a;响应断言、JSON断言 响应断言 1、http请求添加响应断言 2、三种作用域&#xff1a;第一种既作用主请求又作用子请求、只作用主请求、只作用子请求。我们默认选中间的仅作用主请求即可。 3、测试字段和匹配规则 测试字段一般选择响应文本即可&am…

Springboot家乡特色推荐系统

目录 背景 技术简介 系统简介 界面预览 背景 在当今这个网络迅猛发展的时代&#xff0c;计算机技术已经广泛应用于我们生活的每个角落&#xff0c;互联网在经济和日常生活等多个方面扮演着至关重要的角色&#xff0c;它已成为人们分享资源和快速交流信息的关键平台。在中国…

灯塔:CSS笔记(5)

定位&#xff1a; 1.标准流 1.块级元素独占一行->垂直布局 2.行内元素/行内块元素一行显示多个->水平布局 2.浮动 可以让原本垂直布局的 块级元素变成水平布局 3.定位 1.可以让元素自由的摆放在网页的任意位置 2.一般用于盒子之间的层叠情况 使用定位的步骤 1.…