[C++] STL_vector使用与常用接口的模拟实现

news/2024/2/28 17:11:57

在这里插入图片描述

文章目录

  • 1、vector的介绍
  • 2、vector的使用
    • 2.1 vector的定义
    • 2.2 vector迭代器的使用
    • 2.3 vector的空间增长问题
  • 3、vector的增删查改
    • 3.1 push_back(重点)
    • 3.2 pop_back(重点)
    • 3.3 operator[](重点)
    • 3.4 insert
    • 3.5 erase
    • 3.6 swap

1、vector的介绍

vector文档介绍

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

2、vector的使用

vector在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的并且会模拟实现。

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);使用迭代器进行初始化构造

代码实现:

template<class T>class vector{public:typedef T* iterator;//typedef愿意给别人用就放在public,不想就放在privatetypedef const T* const_iterator;vector(){}vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}   }vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾
};

2.2 vector迭代器的使用

在 vector 中迭代器底层也是原生指针。

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

在这里插入图片描述
模拟实现:

typedef T* iterator;//typedef愿意给别人用就放在public,不想就放在private
typedef const T* const_iterator;iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

使用:
迭代器一般使用在遍历,我们来看一下。

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;//我们这里使用push_back来插入数据v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//迭代器方式遍历vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}return 0;
}

在这里插入图片描述

2.3 vector的空间增长问题

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

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

void reserve(size_t n)//reserve只扩不缩
{if (n > capacity()){T* tmp = new T[n];size_t sz = size();//这里必须先记下sz,_finish要是直接+size()会出问题//_start指的是新空间,调用size(),size()内部会出问题//因此先记下来后面用最合适if (_start){//memcpy是浅拷贝,会出问题//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}
}

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

void resize(size_t n, const T& value = T())//匿名对象/临时对象具有常性,需要const修饰
{if (n <= size())//缩容{_finish = _start + n;}else{reserve(n);//这里可以不用判断是否要扩容,reserve里面会判断while (_finish < _start + n){*_finish = value;++_finish;}}
}

其他几个接口比较简单,直接实现:

size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endOfStorage - _start;
}bool empty()
{return _finish - _start == 0;
}

注意:

在扩容的时候有一个区别,vs下capacity是按1.5倍增长的,g++是按2倍增长的。不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
我们来测试一下:

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;size_t sz = v.capacity();for (size_t i = 0; i < 100; i++){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed:" << sz << endl;}}return 0;
}

在这里插入图片描述
在这里插入图片描述

3、vector的增删查改

vector增删查改接口说明
push_back(重点)尾插
pop_back(重点)尾删
find查找
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[](重点)像数组一样访问

3.1 push_back(重点)

我们梳理尾插的思路:
1、先判断容量是否满了,如果满了先扩容。这里注意,尾插的时候是否为空,这里使用三木操作符进行判断一下,如果为空先扩4个空间,否则2倍扩法。
2、尾插,再++_finish。

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

3.2 pop_back(重点)

在尾删的时候我们依然是先判断
这次我们需要判空,用断言assert(_finish - _start != 0),再去尾删,让_finish–就好了,下一次尾插的时候直接覆盖。

void pop_back()
{assert(_finish-_start != 0);--_finish;//erase(end() - 1);
}

3.3 operator[](重点)

[]的重载就是返回pos位置上数据就可以,比较简单直接秒杀。
我们这里给两个接口,一个是只读的,一个是可以修改的。

T& operator[](size_t pos)//写
{assert(pos < size());//判断位置是否合法return _start[pos];
}const T& operator[](size_t pos)const//读
{assert(pos < size());return _start[pos];
}

3.4 insert

insert是在pos位置插入一个数据。
思路:
1、先判断pos位置是否合法;
2、判满,如果满了就需要扩容,在扩容的时候需要注意迭代器失效的问题;
3、因为插入数据就存在挪动数据,因此需要先挪动数据,我们 从后往前 依次后移一个位置的数据,挪到pos位置;
4、再去给pos位置插入数据,最后返回pos位置。

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;//先记下_start到pos位置的距离,因为扩容后迭代器pos就会失效reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;//新的空间需要更新迭代器pos}iterator end = _finish - 1;//挪动数据while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

3.5 erase

erase是删除pos位置的数据。
思路:
1、判断pos位置是否合法;
2、挪动数据,从 pos位置到尾 依次向前挪动数据,直接用pos+1的数据覆盖掉pos位置的数据即可;
3、–_finish,返回pos位置即可。

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;//挪动数据while (it < _endOfStorage){*(it - 1) = *it;++it;}--_finish;return pos;
}

3.6 swap

我们vector的swap直接套用库函数的swap来实现就好了。

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);
}

*** 本篇结束 ***


http://www.ppmy.cn/news/1060306.html

相关文章

Camunda 7.x 系列【29】消息 信号 条件启动事件

有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 消息启动事件1.1 概述1.2 案例演示2. 信号启动事件2.1 概述2.2 案例演示3. 条件启动事件…

日本公司如何注销 日本公司注销流程 日本公司变更

一、日本企业注销的条件是什么&#xff1f; 1、公司因经营不善、无法维持生计被依法宣告破产的&#xff1b; 2、公司登记使用期限届满、公司章程规定的营业期限届满或出现其他解散事由&#xff1b; 3、公司因发展布局需要或经营管理问题&#xff0c;合并、分立解散&#xff…

十一、pikachu之XXE

文章目录 1、XXE漏洞概述1.1 XML定义1.2 XML结果1.2 XML文档格式1.2.1 DTD内部文档声明1.2.2 DTD外部文档声明1.2.3 DTD声明 2、实战 1、XXE漏洞概述 XXE(xml external entity injection)&#xff1a;即xml外部实体注入漏洞&#xff0c;也就是说服务端接收和解析了来自用户端的…

CSS选择器-CSS3属性

CSS选择器-CSS3属性 持续更新… 1、CSS3的概念和优势 css3概念:是css的升级版本,新增加了一些模块 css3优点:完全向后兼容,可使用新的选择器和属性,能实现新的设计效果CSS3是CSS技术的升级版本&#xff0c;CSS3语言开发是朝着模块化发展的。以前的规范作为一个模块实在是太庞…

uniapp 开发微信小程序之新版隐私协议

自从微信小程序官方更新隐私协议&#xff0c;用户必须同意之后&#xff0c;才能获取个人信息&#xff0c;这就导致在获取用户信息之前&#xff0c;需要有个隐私协议弹窗 大致如下图&#xff1a; 微信小程序官方提供的API和 uniapp 开发的稍微有点区别&#xff0c;这里只记录 u…

【业务功能篇80】Springboot项目 maven配置仓库镜像settings文件分析

项目中我们需要依赖许多包&#xff0c;那么就涉及到maven配置文件&#xff0c;我们需要配置settings.xml文件&#xff0c;这里面会配置我们的本地仓库localRepository &#xff0c;远程仓库&#xff1a;仓库会有我们的依赖仓库repository和插件依赖仓库pluginRepository&#x…

【Spring Boot】SpringBoot实现社交网站用户主页的IP归属地显示功能代码

下面是一个简单的Spring Boot用户主页IP归属地显示功能的代码示例&#xff1a; 首先需要引入依赖&#xff1a; <dependency><groupId>com.maxmind.geoip2</groupId><artifactId>geoip2</artifactId><version>2.7.0</version> </…

Nmap扫描工具:详解每个关键参数的用途和意义

Nmap端口扫描 Nmap端口扫描目标规范&#xff1a;-iL 从一个文件中扫描主机列表--exclude 排除一些远程主机后再扫描--excludefile 排除文件中的列表 端口扫描状态&#xff1a;open(开放的)closed(关闭的)filtered(被过滤的)unfiltered(未被过滤的)open|filtered(开放或者被过滤…

python替换—Series.replace()与Series.str.replace()的区别及为何replace()无效的解决方法

文章目录 前言一、Series.replace()方法二、Series.str.replace()方法三、replace()与str.replace() 使用方法的区别四、常见的坑&#xff1a;python中replace方法不起作用 前言 在Pandas中&#xff0c;Series是一个由一维数组表示的DataFrame列&#xff0c;而replace和str.re…

Linux学习之NFS服务

《Linux 环境下 NFS 服务安装及配置使用》是一篇参考博客。 /etc/exports是NFS服务的配置文件&#xff0c;文件中的内容格式为&#xff1a; 共享目录的路径 允许访问的NFS客户端(共享权限参数1,共享权限参数2,共享权限参数3...)共享权限参数罗列如下&#xff1a; 参数作用ro只…

我裸辞去面试大公司python岗位了!

最近换工作了&#xff0c;坐标上海&#xff0c;裸辞&#xff0c;之前早有前辈们说过&#xff0c;“裸辞一时爽,一直裸辞一直爽”&#xff0c;这话一点不假&#xff0c;裸辞你要面临没有收入来源&#xff0c;但是每天眼睁睁看着各种花销不断支出的煎熬&#xff0c;我主要是觉得一…

深入解析:树结构及其应用

文章目录 学习树的基本概念理解树的遍历方式学习堆和优先队列的应用案例分析&#xff1a;使用堆进行Top K元素的查找结论 &#x1f389;欢迎来到数据结构学习专栏~深入解析&#xff1a;树结构及其应用 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT陈…

UltralSO软碟通制作Linux系统盘

第一步&#xff1a; 下载镜像 阿里云下载地址&#xff1a;https://mirrors.aliyun.com/centos-vault/ 按照需求选择系统版本&#xff0c;我这要求安装CentOS7.5的系统&#xff0c;我以CentOS7.5为例 第二步&#xff1a; 下载UltralSO软件 官网下载地址&#xff1a;https://cn.…

梳理系统学习R语言1-R语言实战-使用ggplot进行高阶绘图

以下为书中代码&#xff0c;会添加一些理解 library("ggplot2") ggplot(datamtcars,aes(xwt,ympg))geom_point()geom_point(pch17,color"blue",size2)geom_smooth(method"lm",color"red",linetype2)labs(title"Automobile Data&…

SpringBoot案例-配置文件-参数配置化

前言 目前我们已经完成了部门管理和员工管理功能接口的实现&#xff0c;阿里云OSS工具类中&#xff0c;我们会设置4个参数&#xff0c;分别是云服务域名、云服务ID和密码、文件存储的Bucket、就会存在以下问题&#xff1a;参数配置分散以及参数发生变化&#xff0c;就需要对应…

预防缓存穿透工具类

1. 前言 缓存穿透大家都知道&#xff0c;这里简单过一下 缓存和数据库中都没有的数据&#xff0c;而用户不断发起请求。比如查询id -1 的值 想着很多面向C端的查询接口&#xff0c;可能都需要做一下缓存操作&#xff0c;这里简单写了个自定义注解&#xff0c;将查询结果(包含…

portainer初体验

官方文档 安装 docker 这里采用的的是国内汉化的一个镜像&#xff0c;版本号2.16.2。 地址 docker run -d --restartalways --name"portainer" -p 9000:9000 -v /var/run/docker.sock:/var/run/docker.sock 6053537/portainer-ce体验 访问9000端口。 尝试&#x…

连锁餐饮行业的运维困局,向日葵远程控制提供“标准答案”

企业数字化转型的应用落地&#xff0c;在连锁餐饮行业是非常容易被顾客所感知到的&#xff0c;最典型的例子就是各种自助点餐设备。 往往在这些自助点餐设备的背后&#xff0c;还拥有一个覆盖进销存管理、供应链、客户反馈、巡店管理、视频监控等方面的完善的数字化系统&#…

本地编译angular提示内存溢出

本地遇到编译angular时&#xff0c;报如下错误&#xff1a; FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory 两种解决办法&#xff0c;具体如下&#xff1a; 设置环境变量&#xff0c;见图&#xff1a; 直接在…

网工内推 | 上市公司、国企招网工,五险一金,包吃包住

01 宁波领越智能设备有限公司 招聘岗位&#xff1a;网络工程师 职责描述&#xff1a; 1&#xff1a;负责集团内部网络运维安全管理工作和数据中心管理 2&#xff1a;挖掘和发现目前整体网络运行体系中存在的问题和不足&#xff0c;提出具体改进方案并推进实施。 3&#xff1a;…
最新文章