C++vector 简单实现
一。概述
vector是我们经常用的一个容器,其本质是一个线性数组。通过对动态内存的管理,增删改查数据,达到方便使用的目的。
作为一个线性表,控制元素个数,容量,开始位置的指针分别是:
start /*是数组的首地址*/
finish /*是数组元素的终止位置,看下图*/
end_of_storage/*是数组元素的总容量,看下图*/
大概的样子:
我们通过操作此三个指针和内存的增加减少或者复制转移的方式完成vector的成员方法。
下面是类成员定义的展示:
template<class _Ty> #类模板中没 有内存分配器,我们在函数中自己malloc实现#
class MyVector
{
public:typedef _Ty value_type;typedef _Ty* pointer;typedef const _Ty* const_pointer;typedef _Ty& reference;typedef const _Ty& const_reference;typedef pointer iterator;typedef const_pointer const_iterator;typedef unsigned int size_type;
private:_Ty* _M_start;_Ty* _M_finish;_Ty* _M_end_of_storage;public:MyVector() :_M_start(nullptr), _M_finish(nullptr), _M_end_of_storage(nullptr) {}~MyVector() {clear();free(_M_start);}reference at(size_type pos){assert(pos >= 0 && pos < size());//return (*(pos + _M_start));return (_M_start[pos]);}const_reference at(size_type pos) const{assert(pos >= 0 && pos < size());return (*(pos + _M_start));}reference operator[](size_type pos){if (pos >= 0 && pos < size()) {return _M_start[pos];}else {std::cout << "error operator[]";exit(1);}}const_reference operator[](size_type pos) const{if (pos >= 0 && pos < size()) {return _M_start[pos];}else {std::cout << "error operator[]";exit(1);}}reference front(){return *_M_start;}const_reference front() const{return *_M_start;}reference back(){return *(_M_finish -1);}const_reference back() const{return *(_M_finish - 1);}_Ty* data(){return begin(); }const _Ty* data() const{return begin();}public:// 容量size_t size() const{return (size_t)(_M_finish - _M_start);}size_t capacity() const{return (size_t)(_M_end_of_storage - _M_start);}/*2/14*/bool empty()const{return size() > 0 ? true : false;}
二。重点成员方法解析
1.push_back尾部添加元素
不管pushback进的值是内置类型还是类类型,都应该是先创建一个空间,在此基础上生成对象实例化。实例化是在构造函数中进行的。
我们也要知道的是,一个进程的地址空间是4G,给定的数据(只读或是读、写数据)是固定大小,一旦容器像临时数组arr[100]的定义,那么的成员所占的内存如果过大或是动态的增减的难度,那么势必会不方便容器的使用,也不方便管理,所以使用动态内存来进行管理。
void push_back(const _Ty& val){if (_M_finish != _M_end_of_storage){new(_M_finish)_Ty(val);++_M_finish;}else {_M_insert_aux(end(),val);}}
_M_insert_aux 函数实现
_M_insert_aux函数中有一部分是从源空间的元素复制到新位置,此时挨个遍历,原位构造的方式相比于连续空间的赋值构造,我猜测后者效率更高一些(从cpuj计算的角度)。
void _M_insert_aux(iterator pos, const _Ty& val) //{//const size_t oldsize = size();const size_t len = size() != 0 ? (size() * 1.5 + 1) : 1;//iterator new_start = (_Ty*)malloc(sizeof(_Ty) * len);iterator start2 = (_Ty*)malloc(sizeof(_Ty) * len);//eg1:开始复制数据到新内存iterator newstart = start2;iterator newfinsh = _M_start;/*while (newfinsh != pos){new(newstart)_Ty(*newfinsh);++newstart;++newfinsh;}*//*new(newstart)_Ty(val);++newstart;*///eg1的另一种写法,测试:while (newfinsh != pos){memcpy(start2, _M_start, sizeof(_Ty)*(_M_finish-_M_start));newstart = _M_finish - _M_start + start2;newfinsh = _M_finish;}new(newstart)_Ty(val);++newstart;iterator it = _M_finish;while (newfinsh != _M_end_of_storage){++newfinsh;++newstart;}for (iterator it = _M_start; it != _M_finish; it++){it->~_Ty();}free(_M_start);_M_finish = newstart;_M_end_of_storage = len + start2;_M_start = start2;}
**2.operator =移动赋值
次函数需要注意的是什么形式时编译器调用的是赋值重载,什么形式时会调用拷贝构造。
隐式的拷贝构造:在创建对象性时的赋值,比如;
MyVector<Int> tmp= arr;
显示的拷贝构造则是:
MyVector<Int> tmp(arr);
如果你使用vector时的写法是隐式的,那么会调用拷贝构造完成对像的复制;
相反你使用显示的方式创建对象,也是会调用拷贝构造。
当你在创建对象后的赋值运算符的重载时才会调用vector的移动赋值函数
MyVector& operator= (const MyVector& V1)//在赋值运算符重载中不能在调用拷贝构造//因为this已经是一个对象,再拷贝构造创建一个对象,//是没什么意义的事情。{//arr.operator(V1);if (V1._M_start == nullptr&&_M_start ==nullptr) {return *this;}else if (this->_M_start == nullptr) { //拷贝构造/*iterator start = (_Ty*)malloc(sizeof(_Ty) * V1.capacity());_M_start = start;*/const_iterator it = V1.begin();while (it != V1._M_finish) {this->push_back(*it);++it;}/*_M_finish = ( _Ty* )it;_M_end_of_storage = V1.capacity()+_M_start;*/return *this;}else if (this->_M_start != nullptr) {if (this->size() >= V1.size()){/*for (iterator it = _M_start; it != _M_finish; ++it){it->~_Ty();}*/this->clear();iterator it = (_Ty*)V1.begin();while (it != V1._M_finish) {this->push_back(*it);++it;}return *this;}else {this->clear();free(_M_start);_M_start = nullptr;_M_finish = nullptr;this->_M_end_of_storage = nullptr;/* iterator start = (_Ty*)malloc(sizeof(_Ty) * V1.capacity());_M_start = start;*/iterator it = (_Ty*)V1.begin();//iterator it =V1._M_start;while (it != V1._M_finish) {this->push_back(*it);++it;}/*_M_finish = it;_M_end_of_storage = V1.capacity() + _M_start;*/return *this;}}}
3.拷贝构造
注意:在类的成员方法内部不要在类中几个默认的成员函数(构造,析构,赋值重载,取地址运算符的重载)中调用拷贝构造,没有什么意义。从面向对象编程的角度讲不符合现实世界的逻辑。
MyVector(const MyVector& V1){cout << this << endl;iterator start = (_Ty*)malloc(sizeof(_Ty) * V1.capacity());if (start == nullptr){std::cout << "malloc error" << std::endl;exit(1);}iterator finish = start;iterator p = V1._M_start;_M_start = start;while (p != V1._M_finish){new(finish)_Ty(*p);++p;++finish;}_M_finish = finish;_M_end_of_storage = _M_start + V1.capacity();}
4.erase
iterator erase(iterator _F, iterator _L){if (_F != _L){if (_L != _M_finish) copy(_L, _M_finish, _F);_M_finish = _M_finish - (_L - _F);memset(_M_finish , 0x00, sizeof(_Ty) * (_L - _F));}return _L;}iterator erase(iterator pos)//有返回值,迭代器返回{return erase(pos, pos + 1);/*if (pos != end()) //这个代码可被erase(pos,pos+1)替代{copy(pos+1,_M_finish,pos);(--_M_finish)->~_Ty();}return pos;*/}
需要注意的是,上面使用到memcpy/memmove/copy函数时,不能保证对有虚函数的类(能产生多态的类)可以继续使用多态。原因是虚函数表和虚表指针丢失,无法找到函数指针(虚表指针应该不丢失)。
相关文章:

C++vector 简单实现
一。概述 vector是我们经常用的一个容器,其本质是一个线性数组。通过对动态内存的管理,增删改查数据,达到方便使用的目的。 作为一个线性表,控制元素个数,容量,开始位置的指针分别是: start …...

通用缓存存储设计实践
目录介绍 01.整体概述说明 1.1 项目背景介绍1.2 遇到问题记录1.3 基础概念介绍1.4 设计目标1.5 产生收益分析 02.市面存储方案 2.1 缓存存储有哪些2.2 缓存策略有哪些2.3 常见存储方案2.4 市面存储方案说明2.5 存储方案的不足 03.存储方案原理 3.1 Sp存储原理分析3.2 MMKV存储…...

sheng的学习笔记Eureka Ribbon
Eureka-注册中心Eureka简介官方网址:https://spring.io/projects/spring-cloud-netflixEureka介绍Spring Cloud 封装了 Netflix 公司开发的 Eureka 模块来实现服务注册和发现(请对比Zookeeper)。Zooleeper nacos.Eureka 采用了 C-S 的设计架构。Eureka Server 作为服…...

零代码工具我推荐Oracle APEX
云原生时代零代码工具我推荐Oracle APEX 国内的低码开发平台我也看了很多,感觉还是不太适合我这个被WEB抛弃的老炮。自从看了Oracle APEX就不打算看其它的了。太强大了,WEB服务器都省了,直接数据库到WEB页面。功能很强大,震撼到我…...

InstructGPT方法简读
InstructGPT方法简读 引言 仅仅通过增大模型规模和数据规模来训练更大的模型并不能使得大模型更好地理解用户意图。由于数据的噪声极大,并且现在的大多数大型语言模型均为基于深度学习的“黑箱模型”,几乎不具有可解释性和可控性,因此&…...
SpringCloud-5_模块集群化
避免一台Server挂掉,影响整个服务,搭建server集群创建e-commerce-eureka-server-9002微服务模块【作为注册中心】创建步骤参考e-commerce-eureka-server-9001修改pom.xml,加入依赖同9001创建resources/application.yml9002的ymlserver: # 修改端口号por…...

AQS底层源码深度剖析-BlockingQueue
目录 AQS底层源码深度剖析-BlockingQueue BlockingQueue定义 队列类型 队列数据结构 ArrayBlockingQueue LinkedBlockingQueue DelayQueue BlockingQueue API 添加元素 检索(取出)元素 BlockingQueue应用队列总览图 AQS底层源码深度剖析-BlockingQueue【重点中的重…...
Kotlin协程:Flow的异常处理
示例代码如下:launch(Dispatchers.Main) {// 第一部分flow {emit(1)throw NullPointerException("e")}.catch {Log.d("liduo", "onCreate1: $it")}.collect {Log.d("liudo", "onCreate2: $it")}// 第二部分flow …...

qt下ffmpeg录制mp4经验分享,支持音视频(h264、h265,AAC,G711 aLaw, G711muLaw)
前言 MP4,是最常见的国际通用格式,在常见的播放软件中都可以使用和播放,磁盘空间占地小,画质一般清晰,它本身是支持h264、AAC的编码格式,对于其他编码的话,需要进行额外处理。本文提供了ffmpeg录…...
C#读取Excel解析入门-1仅围绕三个主要的为阵地,进行重点解析,就是最理性的应对上法所在
业务中也是同样的功能点实现。只是多扩展了很多代码,构成了项目的其他部分,枝干所在。但是有用的枝干,仅仅不超过三个主要的!所以您仅仅围绕三个主要的为阵地,进行重点解析,就是最理性的应对上法所在了 str…...
一起Talk Android吧(第五百一十八回:在Android中使用MQTT通信五)
文章目录 知识回顾问题描述解决过程经验分享各位看官们大家好,这一回中咱们说的例子是" 在Android中使用MQTT通信五",本章回内容与前后章节内容无关联。闲话休提,言归正转,让我们一起Talk Android吧! 知识回顾 我们在前面章回中介绍了如何使用MQTT通信,包含它…...

100种思维模型之混沌与秩序思维模型-027
人类崇尚秩序与连续性,我们习惯于我们的日常世界,它以线性方式运作,没有不连续或突跳。 为此,我们学会了期望各种过程以连续方式运行,我们的内心为了让我们更有安全感,把很多事物的结果归于秩序,…...

Java开发 - Redis初体验
前言 es我们已经在前文中有所了解,和es有相似功能的是Redis,他们都不是纯粹的数据库。两者使用场景也是存在一定的差异的,本文目的并不重点说明他们之间的差异,但会简要说明,重点还是在对Redis的了解和学习上。学完本…...
Python - 使用 pymysql 操作 MySQL 详解
目录创建连接 pymsql.connect() 方法的可传参数连接对象 conn pymsql.connect() 方法游标对象 cursor() 方法使用示例创建数据库表插入数据操作数据查询操作数据更新操作数据删除操作SQL中使用变量封装使用简单使用: import pymysqldb pymysql.connect(host,user…...

机器学习-卷积神经网络CNN中的单通道和多通道图片差异
背景 最近在使用CNN的场景中,既有单通道的图片输入需求,也有多通道的图片输入需求,因此又整理回顾了一下单通道或者多通道卷积的差别,这里记录一下探索过程。 结论 直接给出结论,单通道图片和多通道图片在经历了第一…...

考研复试——计算机组成原理
文章目录计算机组成原理1. 计算机系统由哪两部分组成?计算机系统性能取决于什么?2. 冯诺依曼机的主要特点?3. 主存储器由什么组成,各部分有什么作用?4. 什么是存储单元、存储字、存储字长、存储体?5. 计算机…...

硬件设计 之摄像头分类(IR摄像头、mono摄像头、RGB摄像头、RGB-D摄像头、鱼眼摄像头)
总结一下在机器人上常用的几种摄像头,最近在组装机器人时,傻傻分不清摄像头的种类。由于本人知识有限,以下资料都是在网上搜索而来,按照摄像头的分类整理一下,供大家参考: 1.IR摄像头: IRinfr…...
PTA:C课程设计(2)
山东大学(威海)2022级大一下C习题集(2)2-5-1 字符定位函数(程序填空题)2-5-2 判断回文(程序填空题)2-6-1 数字金字塔(函数)2-6-2 使用函数求最大公约数(函数)2-6-3 使用函数求余弦函…...

第四章:面向对象编程
第四章:面向对象编程 4.1:面向过程与面向对象 面向过程(POP)与面向对象(OOP) 二者都是一种思想,面向对象是相对于面向过程而言的。面向过程,强调的是功能行为,以函数为最小单位,考虑怎么做。面向对象&…...

Linux 安装npm yarn pnpm 命令
下载安装包 node 下载地址解压压缩包 tar -Jxf node-v19.7.0-linux-x64.tar.xz -C /root/app echo "export PATH$PATH:/app/node-v16.9.0-linux-x64" >> /etc/profile source /etc/profile ln -sf /app/node-v16.9.0-linux-x64/bin/npm /usr/local/bin/ ln -…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...