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

在这里插入图片描述

文章目录

  • 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.rhkb.cn/news/105338.html

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

相关文章

【Android】Mobile-Security-Framework-MobSF Manifest 静态扫描规则

前言 移动安全框架&#xff08;MobSF&#xff09;是一个自动化的一体化移动应用程序&#xff08;Android/iOS/Windows&#xff09;测试、恶意软件分析和安全评估框架&#xff0c;能够执行静态和动态分析。MobSF支持移动应用程序二进制文件&#xff08;APK、XAPK、IPA和APPX&am…

深度学习论文: WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation

深度学习论文: WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation WinCLIP: Zero-/Few-Shot Anomaly Classification and Segmentation PDF: https://arxiv.org/pdf/2303.14814.pdf PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTorch代码: h…

java使用swing制作桌面图形应用的实例教程

本篇文章主要讲解&#xff0c;java编程语言通过swing制作桌面图形应用的实例教程&#xff0c;通过一个简单的个人信息提交表单界面&#xff0c;让你了解swing的布局管理、窗口图标设置、编译和运行以及窗口菜单的设置。 日期&#xff1a;2023年8月25日 实际效果 弹出新窗口帮助…

一种分解多种信号模式非线性线性调频的方法研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Azure应用程序网关

文章目录 什么是应用程序网关实战演练创建虚拟网络创建虚拟机创建应用程序网关测试搭建结果 什么是应用程序网关 Azure应用程序网关是一种托管服务&#xff0c;用于提供安全、可缩放的 Web 应用程序前端点的应用程序传送控制和保护。它可以通过 SSL 终止、cookie 基于会话持久…

uniapp 安卓平台签名证书(.keystore)生成

安装JRE环境 下载jre安装包&#xff1a;https://www.oracle.com/java/technologies/downloads/#java8安装jre安装包时&#xff0c;记录安装目录(例:C:\Program Files\Java\jdk-20)打开命令行&#xff08;cmd&#xff09;&#xff0c;将JRE安装路径添加到系统环境变量 d: se…

使用vlc在线播放rtsp视频url

1. 2. 3. 工具链接&#xff1a; https://download.csdn.net/download/qq_43560721/88249440

数据分析案例-汽车客户信息数据可视化分析(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

学习开发振弦采集模块的注意事项

学习开发振弦采集模块的注意事项 &#xff08;三河凡科科技/飞讯教学&#xff09;振弦采集模块是一种用来实时采集和处理振弦信号的电子设备&#xff0c;在工业、航空、医疗等领域都有广泛应用。学习开发振弦采集模块需要注意以下几点&#xff1a; 一、硬件选择 首先需要选择…

word文档中输入“打钩”的4种方法

我们利用Word来制作一些填写单、待办表、计划表类的文档时&#xff0c;都会输入一些特殊符号&#xff0c;比如方框内“打钩”的勾选符号&#xff0c;那么这个符号应该怎么输入呢&#xff1f; 接下来&#xff0c;我就给你们介绍几种简单实用的方法&#xff0c;其中第三种是小编…

Spark项目Java和Scala混合打包编译

文章目录 项目结构Pom完整文件编译查看 实际开发用有时候引用自己写的一些java工具类&#xff0c;但是整个项目是scala开发的spark程序&#xff0c;在项目打包时需要考虑到java和scala混合在一起编译。 今天看到之前很久之前写的一些打包编译文章&#xff0c;发现很多地方不太对…

【软件测试面试题】网页崩溃的原因是什么?如何排查?

网页崩溃的原因 1. 代码错误 网页中存在错误或不完善的代码可能导致崩溃。例如&#xff0c;语法错误、逻辑错误、变量未定义等。这些错误可能会导致浏览器无法正确解析网页&#xff0c;从而导致崩溃。 2. 资源加载问题 网页中引用的资源&#xff08;如CSS文件、JavaScript文…

【linux】2 make/Makefile和gitee

文章目录 一、Linux项目自动化构建工具-make/Makefile1.1 背景1.2 实例代码1.3 原理1.4 项目清理 二、linux下第一个小程序-进度条2.1 行缓冲区2.2 进度条 三、git以及gitee总结 ヾ(๑╹◡╹)&#xff89;" 人总要为过去的懒惰而付出代价ヾ(๑╹◡╹)&#xff89;" 一…

【点击新增一个下拉框 与前一个内容一样 但不能选同一个值】

点击新增一个下拉框 与前一个内容一样 但不能选同一个值 主要是看下拉选择el-option的disabled,注意不要混淆 <el-form label-width"120px" :model"form" ref"form" style"color: #fff"><template v-for"(trapolicy, i…

生成地图展示【Python思路】

# 1.导包 import json from pyecharts.charts import Map #导入关于编写地图的包 from pyechart.options import * #全局设置# 2.得到地图对象 map Map()# 3.打开事先准备好的JSON数据文件 f open("D:/Typora 记事本/notebook/Python/Exercise_data/疫情.txt",&…

2023CCF图形学启明星计划夏令营感想记录

这篇就是纯日记了&#xff0c;想记录一下参加这个夏令营的感想&#xff0c;中间的一些过程&#xff0c;毕竟这对我来说算是一段难忘的经历。 一、了解到的渠道 我个人是比较喜欢图形渲染的&#xff0c;之前也学过GAMES的课程&#xff0c;然后偶然的一天&#xff0c;GAMES101里…

TypeScript初体验

1.安装编译TS工具包 npm i -g typescript 2. 查看版本号 tsc -v 3.创建ts文件 说明&#xff1a;创建一个index.ts文件 4.TS编译为JS tsc index.ts 5.执行JS代码 node index.js 6.简化TS的步骤 6.1安装 npm i -g ts-node 6.2执行 ts-node index.ts

redis 7高级篇1 redis的单线程与多线程

一 redis单线程与多线程 1.1 redis单线程&多线程 1.redis的单线程 redis单线程主要是指Redis的网络IO和键值对读写是由一个线程来完成的&#xff0c;Redis在处理客户端的请求时包括获取 (socket 读)、解析、执行、内容返回 (socket 写) 等都由一个顺序串行的主线程处理…

数据分享|R语言PCA主成分、lasso、岭回归降维分析近年来各国土地面积变化影响...

全文链接&#xff1a;http://tecdat.cn/?p31445 机器学习在环境监测领域的应用&#xff0c;着眼于探索全球范围内的环境演化规律&#xff0c;人类与自然生态之间的关系以及环境变化对人类生存的影响&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 课题着眼于…

秒杀系统的业务流程以及优化方案(实现异步秒杀)

先看基本的业务流程 那么我们可以看到整个流程都是一个线程来完成的&#xff0c;这样的话耗时还是很长的&#xff0c;那么可不可以采用多线程去实现呢&#xff1f; 首先我们要思考怎么对业务进行拆分&#xff0c;可以想象一个我们去饭店点餐&#xff0c;会有前台接待&#xff…