vector的使用,以及部分功能的模拟实现(C++)

1.vector的介绍及使用

1.1 vector的介绍

vector是STL容器中的一种常用的容器,和数组类似,由于其大小(size)可变,常用于数组大小不可知的情况下来替代数组。

vector也是一种顺序容器,在内存中连续排列,因此可以通过下标快速访问,时间复杂度为O(1)。但是,连续排列也意味着大小固定,数据超过vector的预定值时vector将自动扩容。

1.2 vector的使用

在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的。

1.2.1 vector的定义

(constructor)构造函数声明接口说明
vector()(重点)无参构造
vector(size_type n, const value_type& val = value_type())构造并初始化n个val
vector (const vector& x); (重点)拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

举例:

#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int>v1;vector<int>v2(5,5);vector<int>v3(v2);vector<int>v4(v2.begin(), v2.end());return 0;
}

结果:

 1.2.2 vector iterator 的使用

iterator的使用接口说明
begin + end(重点)获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下 一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置 的reverse_iterator

举例:

void test2()
{vector<int>v2(5, 5);vector<int>::iterator it = v2.begin();while (it != v2.end()){cout << *it << " ";it++;}
}

结果:

 1.2.3 vector 空间增长问题

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize改变vector的size
reserve改变vector的capacity

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

通过下面一段代码来演示:

void test3()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

vs下的结果:

making foo grow:

capacity changed: 1

capacity changed: 2

capacity changed: 3

capacity changed: 4

capacity changed: 6

capacity changed: 9

capacity changed: 13

capacity changed: 19

capacity changed: 28

capacity changed: 42

capacity changed: 63

capacity changed: 94

capacity changed: 141

g++运行结果:

making foo grow:

capacity changed: 1

capacity changed: 2

capacity changed: 4

capacity changed: 8

capacity changed: 16

capacity changed: 32

capacity changed: 64

capacity changed: 128

b)reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。

举例:

void test4()
{vector<int> v;size_t sz = v.capacity();v.reserve(100);   // 提前将容量设置好,可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

结果:

c)resize在开空间的同时还会进行初始化,影响size。

 1.2.3 vector 增删查改

vector增删查改接口说明
push_back(重点)尾插
pop_back (重点)尾删
find查找。(注意这个是算法模块实现,不是vector的成员接口)
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] (重点)像数组一样访问

push_back和pop_back演示:

void test5()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl;v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl;
}

结果:

 find(这个是算法里面的函数,需要配合迭代器使用)演示:

void test6()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;vector<int>::iterator pos=find(v.begin(), v.end(), 3);cout << pos-v.begin() <<endl;
}

结果:

find函数第一个参数是迭代器的起始位置,第二参数是结束位置,第三个是寻找的对象,找到则返回第一次找到该对象位置的迭代器,否则返回结束位置。

insert和erase演示:

void test7()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (auto& e : v){cout << e << " ";}cout << endl;v.insert(v.begin() + 2, 10);for (auto& e : v){cout << e << " ";}cout << endl;v.erase(v.end()-1);for (auto& e : v){cout << e << " ";}cout << endl;
}

结果:

这个第一个参数都是需要传迭代器来确定需要插入,或删除的位置。

swap演示:

void test8()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2;v2.push_back(5);v2.push_back(4);v2.push_back(3);v2.push_back(2);v2.push_back(1);cout << "v1:";for (auto& e : v1){cout << e << " ";}cout << endl;cout << "v2:";for (auto& e : v2){cout << e << " ";}cout << endl;v1.swap(v2);cout << "v1:";for (auto& e : v1){cout << e << " ";}cout << endl;cout << "v2:";for (auto& e : v2){cout << e << " ";}cout << endl;
}

结果:

 operator[]演示:

void test9()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;
}

结果:

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

vector在底层实现中,其实类里面并不是像小编之前数据结构中,那样有三个成员:T* arr,size_t size,size_t capacity,而是T* _start,T* _finish,T* end_of_storage。

_start表示有效元素开始的迭代器位置,_finish表示有效元素结束下一个迭代器位置,_end_of_storage表示空间大小结束下一个迭代器位置。

 2.1实现默认构造函数

这里为了和STL库里面的vector区分用命名空间进行隔离,这里利用缺省参数,初始化列表进行初始化:

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

2.2析构函数

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

2.3元素个数size(),空间大小capacity()

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

2.4迭代器实现begin(),end()

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

这里需要重载const修饰的类型,如果是元素类型是const例如:const T,以及范围for使用时对象是const修饰时,就需要重载这种const的end(),begin(),才能使用。

2.5重载[]

const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}

 这里也需要重载const修饰的类型,和上面begin(),end()实现的原因是一样的。

2.6 开辟空间大小void reserve(size_t n)

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];//注意这里不能使用memcpy(tmp,_start,sizeof(T)*oldsize)来赋值for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}

这里首先判断n是否大于capacity(),如果小于就不做处理,大于就需要扩容,这里需要保存size()大小,如果将tmp赋给_start时,这是_start已经更新,再利用size()去确定_finish就会有问题。

 其次就是不能用memcpy来赋值

用下面的例子来解释:

int main()
{iu::vector<string> v1;v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");v1.push_back("1111111111111111111111111");for (const auto& e : v1){cout << e << endl;}cout << endl;return 0;
}

结果:

这里是为什么?这里空间大小不够,所以要扩容,其实是memcpy浅拷贝导致的,这里delete[]释放空间之后,但是浅拷贝,还是指向原来的释放的空间,再去访问就是野指针,就出错了。

2.7 控制元素个数void resize(size_t n,const T& val=T())

void resize(size_t n,const T& val=T())
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}
}

首先判断是否小于size(),小于就直接将_finish位置向前调整即可,大于就需要先扩容,因为在前面实现的reserve中有判断是否需要扩容,所以这里直接将n传给reverse,自然会判断,然后再将增加的元素个数,初始化为val,调整_finish位置。

2.8 插入元素iterator insert(iterator pos, const T& x)

iterator insert(iterator pos, const T& x)
{assert(pos <= _finish && pos >= _start);if (_finish == _end_of_storage)//更新迭代器{size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;return pos;
}

这里首先判断空间是否已满,满了需要扩容,再插入,这里和前面reserve有相同的问题,扩容之后,_start指向一块新的空间,但pos还是指向原来释放掉的空间,所以需要更新迭代器,确定原来len,再更新pos,在将pos及之后的数据依次向后移动一位,再插入x,返回pos位置。

 2.9 删除元素iterator erase(iterator pos)

iterator erase(iterator pos)
{assert(pos <= _finish && pos >= _start);auto it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}--_finish;return pos;
}

直接将pos+1位置的数据都向前移动一位,实现数据覆盖,然后_finish--就相当于删除pos位置元素,返回pos位置。

2.10 尾插void push_back(const T& val = T()),尾删void pop_back()

void push_back(const T& val = T())
{insert(end(), val);
}
void pop_back()
{assert(size() > 0);--_finish;
}

这里尾插直接复用insert函数,第一个参数直接传end()位置的迭代器,第二传插入的元素,尾删直接_finish--就行了。

2.11 拷贝构造函数

vector(const vector<T>& v)
{reserve(v.size()); for (auto e : v){push_back(e);}
}

 this开辟和v一样大的元素个数相等的空间大小,再将v中的元素,依次尾插到this中。

2.12 赋值运算符重载

void swap(vector<int>& v)
{std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

 这里利用前面(string)中讲的现代写法,利用swap函数,注意这里形参,不能传引用,如果传引用,交换后会影响实参,这里传参走拷贝构造给v,出了作用域会销毁,不会影响实参。

2.13 其他几种构造函数

2.13.1vector(int n, const T& value = T())

vector(int n, const T& value = T())
{resize(n, value);
}

这里直接调用resize,就可以了,resize里面有扩容,并赋值操作,直接复用就行了。

2.13.2 vector(InputIterator first, InputIterator last)

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

这是利用迭代器初始化,将frist到last位置,依次尾插到this即可。

 举例:

void test6()
{iu::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto& e : v1){cout << e << " ";}cout << endl;iu::vector<int>v2(v1.begin()+2,v1.end());for (auto& e : v2){ cout << e << " ";}
}

结果:

2.13.3  vector(std::initializer_list<T> it)

vector(std::initializer_list<T> it)
{reserve(it.size());for (auto e : it){push_back(e);}
}

首先this开辟和it一样大的元素个数相等的空间大小,再将it中的元素,依次尾插到this中。这个initializer_list类型,可以类似于数组。

 举例:

void test6()
{iu::vector<int>v1 = {1,2,3,4,5,6};for (auto& e : v1){cout << e << " ";}cout << endl;
}

结果:

3.迭代器失效问题讨论

3.1插入

看下面这段代码:

int main()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);auto it = v1.begin() + 2;// insert以后,默认迭代器都失效了,不要使用v1.insert(it, 10);cout << *it << endl;
}

结果:

注意这里问题是,空间大小为4,再插入就需要扩容,扩容之后,it还指向原来的位置,但扩容之后,_start位置已经改变,相当于it为野指针,就失效了,但如果不扩容的话,有些编译器可以通过,可能正确,但不能去以编译器为准,就默认insert之后迭代器就失效了,要再用就重新初始化。

3.2 删除

看下面这段代码:(删除所有的偶数)

void test9()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (const auto& e : v1){cout << e <<" ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl;
}

结果:

这里编译器vs会直接报错,因为在vs下检查非常严格,只要是erase,insert之后编译器直接就失效了,虽然vs下并不会缩容,但也会报错,如果在要缩容的编译器下,那肯定也是失效了,这里需要更新迭代器。

改进后:

void test9()
{iu::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (const auto& e : v1){cout << e <<" ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it=v1.erase(it);//每删除一次就更新一次迭代器}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl;
}

结果:

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

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

相关文章

【Postgres_Python】使用python脚本批量创建和导入多个PG数据库

之前批量创建和导入数据库分为2个python脚本进行&#xff0c;现整合优化代码合并为一个python脚本&#xff0c;可同步实现数据库的创建和数据导入。之前的文章链接&#xff1a; 【Postgres_Python】使用python脚本批量创建PG数据库 【Postgres_Python】使用python脚本将多个.S…

U-Net - U型网络:用于图像分割的卷积神经网络

U-Net是一种专为图像分割任务设计的卷积神经网络&#xff08;CNN&#xff09;&#xff0c;最初由Olaf Ronneberger等人于2015年提出。它被广泛应用于医学影像分析、遥感图像分割、自动驾驶和其他许多需要对图像进行像素级分类的任务中。U-Net具有强大的特征提取和恢复能力&…

ceph基本概念,架构,部署(一)

一、分布式存储概述 1.存储分类 存储分为封闭系统的存储和开放系统的存储&#xff0c;而对于开放系统的存储又被分为内置存储和外挂存储。 外挂存储又被细分为直连式存储(DAS)和网络存储(FAS)&#xff0c;而网络存储又被细分网络接入存储(NAS)和存储区域网络(SAN)等。 DAS(D…

联想电脑怎么用u盘装系统_联想电脑用u盘装win10系统教程

联想电脑怎么重装系统&#xff1f;在当今科技发展迅猛的时代&#xff0c;联想电脑已经成为了人们生活中不可或缺的一部分。然而&#xff0c;随着时间的推移&#xff0c;我们可能会遇到一些问题&#xff0c;例如系统崩溃或者需要更换操作系统。这时&#xff0c;使用U盘来重新安装…

基于ESP32-IDF驱动GPIO输出控制LED

基于ESP32-IDF驱动GPIO输出控制LED 文章目录 基于ESP32-IDF驱动GPIO输出控制LED一、点亮LED3.1 LED电路3.2 配置GPIO函数gpio_config()原型和头文件3.3 设置GPIO引脚电平状态函数gpio_set_level()原型和头文件3.4 代码实现并编译烧录 一、点亮LED 3.1 LED电路 可以看到&#x…

电路研究9.1.1——合宙 Air780EP 模组外围线路

本来要继续研究AT指令来着&#xff0c;结果发现后面还有之前用到的电路设计资料&#xff0c;所以就贴过来了。 5.3.2 工作模式&#xff1a; 注意&#xff1a;  当模块进入休眠模式或深度休眠模式后&#xff0c; VDD_EXT 电源会掉电&#xff0c;相应电压域的 GPIO 以及串口…

Apache Hive3定位表并更改其位置

Apache Hive3表 1、Apache Hive3表概述2、Hive3表存储格式3、Hive3事务表4、Hive3外部表5、定位Hive3表并更改位置6、使用点表示法引用表7、理解CREATE TABLE行为 1、Apache Hive3表概述 Apache Hive3表类型的定义和表类型与ACID属性的关系图使得Hive表变得清晰。表的位置取决于…

Flutter 改完安卓 applicationId 后App 闪退问题。

一、问题 当我们项目创建完&#xff0c;想 build.gradle 改 applicationId 的时候&#xff0c;再次执行的时候可能会出现 app 闪退问题&#xff0c; 控制台不显示任何错误提示 也不出现 Exit 停止运行的情况。&#xff08;像下方这样&#xff0c; 而 app 只是在模拟器中一闪而…

JavaScript笔记APIs篇01——DOM获取与属性操作

黑马程序员视频地址&#xff1a;黑马程序员前端JavaScript入门到精通全套视频教程https://www.bilibili.com/video/BV1Y84y1L7Nn?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p78https://www.bilibili.com/video/BV1Y84y1L7Nn?…

【2024年 CSDN博客之星】我的2024年创作之旅:从C语言到人工智能,个人成长与突破的全景回顾

我的2024年创作之旅&#xff1a;从C语言到人工智能&#xff0c;个人成长与突破的全景回顾 引言 回望2024年&#xff0c;我不仅收获了技术上的成长&#xff0c;更收获了来自CSDN平台上无数粉丝、朋友以及网友们的支持与鼓励。在这条创作之路上&#xff0c;CSDN不仅是我展示技术成…

回归人文主义,探寻情感本质:从文艺复兴到AI时代,我的情感探索之旅

回归人文主义&#xff0c;探寻情感本质&#xff1a;从文艺复兴到AI时代&#xff0c;我们的情感探索之旅 多年来&#xff0c;我们的团队一直关注人工智能&#xff0c;尤其是AI在音乐领域的应用研究。随着技术的不断演进&#xff0c;我们也不断反思&#xff1a;在“算法、代码、…

【java】签名验签防篡改研究测试

上一篇文章写了接口安全通过一次性校验码和 时间戳可以防接口重放攻击、本篇将通过 signatrue签名模式进行研究性&#xff0c;知其所以然 说明本次实验是验证签名合法性该前端使用不安全加密&#xff0c;存在安全风险密钥在jsp中暴露 1、实现原理 2、前端 将 username 和 p…

实战演示:利用ChatGPT高效撰写论文

在当今学术界&#xff0c;撰写论文是一项必不可少的技能。然而&#xff0c;许多研究人员和学生在写作过程中常常感到困惑和压力。幸运的是&#xff0c;人工智能的快速发展为我们提供了新的工具&#xff0c;其中ChatGPT便是一个优秀的选择。本文将通过易创AI创作平台&#xff0c…

Java实现简易银行账户管理系统

目录 1、项目概述 1.1 项目结构 1.2 技术栈 2、核心功能说明 2.1 账户管理 2.2 异常处理体系 3、设计理念解析 3.1 面向对象设计 3.2 关键设计点 4、使用指南 4.1 运行流程 4.2 注意事项 5、扩展建议 5.1增加功能 5.2优化方向 6、主要的功能模块代码说明 6.1exception 6.2main …

【2024年华为OD机试】(B卷,100分)- 数据分类 (Java JS PythonC/C++)

一、问题描述 题目描述 对一个数据a进行分类,分类方法为: 此数据a(四个字节大小)的四个字节相加对一个给定的值b取模,如果得到的结果小于一个给定的值c,则数据a为有效类型,其类型为取模的值;如果得到的结果大于或者等于c,则数据a为无效类型。 比如一个数据a=0x010…

使用飞桨AI Studio平台训练数据,并进行图像识别分析得牡丹花测试

&#x1f3bc;个人主页&#xff1a;【Y小夜】 &#x1f60e;作者简介&#xff1a;一位双非学校的大二学生&#xff0c;编程爱好者&#xff0c; 专注于基础和实战分享&#xff0c;欢迎私信咨询&#xff01; &#x1f386;入门专栏&#xff1a;&#x1f387;【MySQL&#xff0…

Next.js:构建大模型智能体GPT研究者应用的 Web开发框架

Next.js&#xff1a;构建大模型智能体GPT研究者应用的 Web开发框架 Next.js 基础知识 Next.js 是由 Vercel 公司开发维护的框架&#xff0c;极大地简化了 React 应用的开发流程。其核心特性包括&#xff1a; 服务器端渲染&#xff08;SSR&#xff09;与静态站点生成&#xff…

Redis vs. 其他数据库:深度解析,如何选择最适合的数据库?

一、如何为项目选择合适的数据库&#xff1f; 选择合适的数据库是一个复杂的过程&#xff0c;需要综合考虑多个因素。下面几个维度来详细阐述&#xff1a; 1.数据模型 关系型数据库&#xff08;RDBMS&#xff09;&#xff1a;适用于高度结构化、关联性强的数据&#xff0c;如电…

Linux内存管理(Linux内存架构,malloc,slab的实现)

文章目录 前言一、Linux进程空间内存分配二、malloc的实现机理三、物理内存与虚拟内存1.物理内存2.虚拟内存 四、磁盘和物理内存区别五、页页的基本概念&#xff1a;分页管理的核心概念&#xff1a;Linux 中分页的实现&#xff1a;总结&#xff1a; 六、伙伴算法伙伴算法的核心…

[Computer Vision]实验二:图像特征点提取

目录 一、实验内容 二、实验过程及结果 2.1 Harris角点检测 2.2 SIFT算法 三、实验小结 一、实验内容 采用Harris与SIFT分别提取特征点及对应的描述子&#xff0c;对比两者的区别&#xff08;特征点数量、分布、描述子维度、图像变化对二者的影响等&#xff09;利用特征匹…