C++:模拟实现vector
目录
成员变量与迭代器
size
capacity
empty
迭代器有关函数
实现默认成员函数的前置准备
reserve
编辑
编辑
push_back
构造函数
无参构造
迭代器区间构造
n个val来进行构造
析构函数
拷贝构造函数
赋值重载
增删查改
clear
resize
pop_back
insert
erase
重载[]
print_Container
成员变量与迭代器
我们还是需要在一个命名空间里模拟实现vector,防止和标准库里的起冲突。
namespace zh
{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;};
}
解释说明:
1.vector是一个非常通用的容器,是一个动态大小的数组,可以存储任意类型的元素,并且能够自动调整大小以适应元素的添加和删除。所以我们的模拟实现要写成类模板。
2.vector可以看做顺序表的升级,但是模拟实现vector跟我们以往实现顺序表有所不同,顺序表是使用一个动态开辟的数组、数组有效元素个数size和数组容纳最大有效数据的个数capacity维护的,而模拟实现vector需要三个(模板参数)T* 类型的指针,而vector的迭代器功能恰恰又和T*类型指针类似,所以干脆把T*封装成迭代器。当然迭代器需要有两个版本,普通版本和const版本。
3.参数的含义
_start指向数组首元素,_finish指向最后一个有效元素的下一个位置, _end_of_storage指向数组空间末尾。
通过三个指针也可以模拟出size和capacity的功能。
size
返回有效数据个数的函数。
size_t size() const
{return _finish - _start;
}
capacity
返回数组最大容纳有效数据个数(容量大小)的函数。
size_t capacity() const
{return _end_of_storage - _start;
}
empty
判断数组是否为空,判断_start与_finish是否相等即可。
bool empty() const
{return _finish == _start;
}
迭代器有关函数
主要实现begin函数和end函数。
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}
实现默认成员函数的前置准备
reserve
用于vector数组空间不足时扩容的函数(扩容成n个空间)。
void reserve(size_t n)
{if (n > capacity()) //n大于数组容量才扩容{size_t oldsize = size(); //用oldsize避免新_start和老_finish的问题T* tmp = new T[n];//memcpy(tmp, _start, size() * sizeof(T)); //这里是浅拷贝,如果是内置类型,没问题 //如果vector存的是自定义类型,就是大坑for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];}delete _start; //这里delete_start,_finish 和_end_of_storage是野指针//更新成员变量_start = tmp;_finish = tmp + oldsize; _end_of_storage = tmp + n;}
}
reserve有几个问题需要注意:
1.开空间的时候要使用new而不要用malloc,因为malloc只是去开空间,不会去调用构造函数。
2.新_start和_finish的问题。
错误示范。
将原有数据拷贝到新空间后,释放了旧空间的资源,_strat指向了新的空间,但是_finish和_end_of_storage还是指向旧空间,这两个指针就变成野指针了。而最关键的是_finish不能被正确赋值。
3.memcpy浅拷贝问题
memcpy(tmp, _start, size() * sizeof(T));
memcpy是浅拷贝,如果vector存的是内置类型,那么浅拷贝就没有问题,如果存的是自定义类型,那浅拷贝就是个大坑。假如vector存的是string类型,那么扩容时,将数据从旧空间拷贝到新空间时,因为是浅拷贝,所以两个空间里的string的_str是同一个地址,释放旧空间的时候就连带这把新空间的资源也释放了。
这样就扩容失败了,因为你把原空间的数据丢失了,而且搞不好有可能程序还会崩溃。
要解决这个问题,我们就得手动实现深拷贝, 因为new出来的空间如果是自定义类型的话就自动调用构造函数初始化了,所以这里走的是赋值重载来实现深拷贝。
push_back
用于在数组末尾尾插一个元素的函数。
void push_back(const T& x)
{//插入之前先判断空间是否足够if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}//插入元素,更新_finish*_finish = x;_finish++;
}
构造函数
vector的构造函数我们实现无参构造、迭代器区间构造和n个val构造。
无参构造
无参构造其实我们并不需要写,因为已经在成员变声明时给了缺省值,编译器自动生成的无参构造函数走初始化列表满足需求了。但是由于我们写了其他构造函数,编译器就不自动生成了。
这里时候可以自己写无参构造,也可以用default强制编译器生成(C++11的用法)。
//构造
/*vector()
{}*///c++11 强制生成构造
vector() = default;
迭代器区间构造
//类模板的成员函数,还可以继续是函数模版
template<class InputIerator>
vector(InputIerator first, InputIerator last)
{while (first != last){push_back(*first); ++first;}
}
这里给这个函数再套一层模板是为了让vector不仅能用vector的迭代器区间构造,还能用其他容器(list、string等)的迭代器来进行构造。
这里又有个问题,就是while循环判断条件的!=不能改成<,因为<对于vector的迭代器时可以的,但是对于其他容器的迭代器,如list,last不一定比first要大。
n个val来进行构造
vector(size_t n, const T& val = T())
{//先开好空间reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}
}
使用的时候val可能不传参,所以要给缺省值。
因为val的类型不确定,可能是内置类型,也可能是自定义类型。
在不传参使用缺省值时
对于自定义类型,比如strng,先调用构造函数构造一个匿名对象,再拷贝构造给val。(编译器会优化,直接对val进行构造),这样val就有了缺省值。
对于内置类型,本来是没有构造函数的说法的,但是为了适应这里,也支持类似类那种使用构造函数初始化的方式。
int a = int();
int b = int(2);
int c(3);
cout << a << endl;
cout << b << endl;
cout << c << endl;
析构函数
直接delete就可以了,把三个迭代器置空。
//析构
~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}
拷贝构造函数
先开好空间,然后尾插就可以了。
//拷贝构造
vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}
赋值重载
首先实现一个交换函数,然后传值调用,将两个对象交换即可。
//void swap(vector& v) 可以这样写
void swap(vector<T>& 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;
}
增删查改
clear
不需要真的删除,直接将更改_finish的值即可。
void clear()
{_finish = _start;
}
resize
控制有效数据个数。
- 若n < size,直接将_finish更改为_start + n即可。
- 若_size < n < capacity或者n > capacity,直接扩容成n个空间(空间足够就不会扩容),从_finish拷贝足够数量的val即可。
void resize(size_t n, T val = T())
{if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n) {*_finish = val;++_finish;}}
}
pop_back
先判断数组是否为空,尾删一个元素,_finish-- 即可。
void pop_back()
{//判断下数组是否为空assert(!empty());--_finish;
}
insert
在pos位置插入一个元素。
iterator insert(iterator pos, const T& x) //pos不会为0,因为是有效的迭代器
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage) //涉及到扩容,pos会失效,pos指向原来的空间{size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}//插入元素,更新*pos = x;++_finish;return pos;
}
注意的问题:
1.如果插入涉及到了扩容,要提前把pos相对于首元素的相对长度记录下来,扩容完毕后,更新pos。因为扩容会导致pos失效。
2.插入之后要返回新元素的迭代器。(这里其实也算迭代器是失效了,因为pos指向的元素发生了更改,迭代器失效了就不要在使用了。)
erase
删除pos位置的元素,删除完后返回删除元素下一位置的迭代器。
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;
}
抛出一个问题,利用迭代器删除vector中所有的偶数。
错误做法
auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){it = v.erase(it);}it++;
}
删完一个偶数后,it已经是下一元素的迭代器了,it不需要++了。
正确做法
auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){it = v.erase(it);}else{++it;}
}
重载[]
为了方便访问和修改数组中的元素。
T& operator[](size_t i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}
print_Container
通用打印容器函数,套一层模板即可。
注意:
template<class Container>
void print_Container(const Container& v)
{//typename vector<T>::const_iterator it = v.begin(); //typename标定为类型 //从没有实例化的类模板取出来的可能是类型或者成员变量,编译器无法区分auto it = v.begin(); while (it != v.end()){cout << *it << ' ';++it;}cout << endl;/*for (auto num : v){cout << num << ' ';}cout << endl;*/
}
从未实例化的类取出来的有可能是类型或者成员变量,要加关键字typename告诉编译器是类型,不加的话会发生编译错误。
当然直接用auto更方便。
拜拜,下期再见😏
摸鱼ing😴✨🎞
相关文章:

C++:模拟实现vector
目录 成员变量与迭代器 size capacity empty 迭代器有关函数 实现默认成员函数的前置准备 reserve 编辑 编辑 push_back 构造函数 无参构造 迭代器区间构造 n个val来进行构造 析构函数 拷贝构造函数 赋值重载 增删查改 clear resize pop_back inser…...
Leecode SQL 184. Department Highest Salary 找出tie
Department Highest Salary 注意!要找出 tie 的 highest salary! Write a solution to find employees who have the highest salary in each of the departments. Return the result table in any order. The result format is in the following ex…...

[Redis][典型运用][缓存]详细讲解
目录 0.什么是缓存?1.使用Redis作为缓存1.为什么用?2.如何用? 2.缓存的更新策略0.前言1.定期生成2.实时生成 3.缓存相关问题1.缓存预热(Cache Preheating)2.缓存穿透(Cache Penetration)3.缓存雪崩(Cache Avalanche)4.缓存击穿(Cache Breakdo…...

GPG error golang 1.19
1. 问题描述及原因分析 在飞腾2000的服务器,OS为Kylin Linux Advanced Server release V10环境下,docker版本为18.09.0(docker-engine-18.09.0-101.ky10.aarch64),基于容器镜像golang:1.19编译新的容器镜像࿰…...
Linux如何查看每个文件及文件夹的大小
查看当前目录下每个文件夹的大小,包括其内部所有文件: du -sh *-s:仅显示每个文件夹的总大小,而不是每个文件。-h:以人类可读的格式显示。...

Word样式的同步与重置
有时候我们需要修改Word中的样式,实现排版的个性化。 如何同步样式到其他电脑上? Word中的样式是由Normal.dotm文件控制的,对样式所有的设置和修改,都会保存到这个问题件中,所以我们只需要在设置好样式以后ÿ…...

力扣 —— 跳跃游戏
题目一(中等) 给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1&…...

SOCKS5代理和HTTP代理哪个快?深度解析两者的速度差异
在现代互联网环境中,使用代理IP已经成为了许多人日常生活和工作的必备工具。无论是为了保护隐私,还是为了访问某些特定资源,代理IP都扮演着重要的角色。今天,我们就来聊聊SOCKS5代理和HTTP代理,看看这两者到底哪个更快…...

工具介绍---效率高+实用
Visual Studio Code (VS Code) 功能特点: 智能代码提示:内置的智能代码提示功能可以自动完成函数、变量等的输入,提高代码编写速度。插件丰富:支持成千上万的扩展插件,例如代码片段、主题、Linting等,能够…...

本地部署开源在线PPT制作与演示应用PPTist并实现异地远程使用
文章目录 前言1. 本地安装PPTist2. PPTist 使用介绍3. 安装Cpolar内网穿透4. 配置公网地址5. 配置固定公网地址 前言 本文主要介绍如何在Windows系统环境本地部署开源在线演示文稿应用PPTist,并结合cpolar内网穿透工具实现随时随地远程访问与使用该项目。 PPTist …...

leetcode_238:除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂…...

网络协议详解--IPv6
IPv6产生背景 (1)地址空间的耗尽:因特网呈指数级发展,导致IPv4地址空间几乎耗尽。虽然采用了子网划分、CIDR和NAT地址转换技术,但这没有从根源解决地址耗尽的问题 (2)IP层安全需求的增长&#x…...

阿里云域名注册购买和备案
文章目录 1、阿里云首页搜索 域名注册2、点击 控制台3、域名控制台 1、阿里云首页搜索 域名注册 2、点击 控制台 3、域名控制台...

【经典机器学习算法】谱聚类算法及其实现(python)
🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏: 🏀深度学习_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 1. 前言 2. 前…...

【Linux】Linux环境基础开发工具使用
Linux开发工具 Linux编辑器-vim使用 1. vim的基本概念 vim的三种模式,分别是命令模式(command mode)、插入模式(Insert mode)和底行模式(last line mode)。 正常/普通/命令模式: …...

Halcon基础系列1-基础算子
1 窗口介绍 打开Halcon 的主界面主要有图形窗口、算子窗口、变量窗口和程序窗口,可拖动调整位置,关闭后可在窗口下拉选项中找到。 2 显示操作 关闭-dev_close_window() 打开-dev_open_window (0, 0, 712, 512, black, WindowHandle) 显示-dev_display(…...

【AI大模型】深入Transformer架构:编码器部分的实现与解析(上)
目录 🍔 编码器介绍 🍔 掩码张量 2.1 掩码张量介绍 2.2 掩码张量的作用 2.3 生成掩码张量的代码分析 2.4 掩码张量的可视化 2.5 掩码张量总结 🍔 注意力机制 3.1 注意力计算规则的代码分析 3.2 带有mask的输入参数: 3.…...

spring学习日记-day7-整合mybatis
一、学习目标 spring整合MyBatis的原理主要涉及到将MyBatis的Mapper映射文件交由Spring容器管理,并将其注入到MyBatis的SqlSessionFactory中,从而实现两者的整合。 二、整合mybatis 1.写一个mybatis测试案例 项目结构: 1.数据库 CREATE DA…...

【YOLO目标检测行人与车数据集】共5607张、已标注txt格式、有训练好的yolov5的模型
目录 说明图片示例 说明 数据集格式:YOLO格式 图片数量:5607 标注数量(txt文件个数):5607 标注类别数:2 标注类别名称:person、car 数据集下载:行人与车数据集 图片示例 数据集图片: …...
JMeter中线程组、HTTP请求的常见参数解释
在JMeter中,线程组和HTTP请求是进行性能测试的两个核心组件。以下是它们的一些常见相关参数的解释: 线程组参数 线程数 指定模拟的用户数,即并发执行的线程数。 Ramp-Up时间(秒) 指定所有线程启动的时间间隔。在这…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...