当前位置: 首页 > news >正文

【C++ STL】手撕vector,深入理解vector的底层

vector的模拟实现

  • 前言
  • 一.默认成员函数
    • 1.1常用的构造函数
      • 1.1.1默认构造函数
      • 1.1.2 n个 val值的构造函数
      • 1.1.3 迭代器区间构造
      • 1.1.4 initializer_list 的构造
    • 1.2析构函数
    • 1.3拷贝构造函数
    • 1.4赋值运算符重载
  • 二.元素的插入,删除,查找操作
    • 2.1 operator[]重载函数
    • 2.2 push_back函数:尾插一个元素
    • 2.3 pop_back函数:尾删一个元素
    • 2.4 insert函数:指定位置插入元素
    • 2.5 erase:删除指定位置的元素
  • 三.front和back函数以及迭代器的实现
    • 3.1 front函数: 获取第一个元素
    • 3.2 back函数: 获取最后一个元素
    • 3.3 begin和end函数
    • 3.4 swap函数

前言

vector是一个类模板,它本质是一个顺序表,通过我们之前的学习,我们一般会这样来定义一个顺序表:

template<class T>
class vector
{T* _a;size_t _size;size_t _capacity;
};

这种定义方式当然是可以的,但是我们通过看P.J.版本的stl的源码会发现,其中对vector的定义大概是这样的:

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;//当前容量的下一个位置};

他是通过三个指针来维护这个顺序表的,我们这篇博客也是采用这种定义方式来实现一个简易版vector的.

一.默认成员函数

1.1常用的构造函数

1.1.1默认构造函数

默认构造是实现一个空的vector,不分配任何内存
代码实现:

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}

测试用例:

int main()
{vector<int> v;cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;return 0;
}

输出结果:

size:0
capacity:0

1.1.2 n个 val值的构造函数

初始化一个vector,其中用n个val值得对象来填充.
代码示例:

		void reserve(size_t n)  {if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//不可以这样写,因为如果vector中存的类型是自定义类型,存在浅拷贝的问题//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}vector(size_t n, const T& val = T()){//考虑到扩容带来的效率低下问题,我们可以提前开好足够大的空间reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

测试用例:

int main()
{vector<int> v2(10 , 1);cout << "size:" << v2.size() << endl;cout << "capacity:" << v2.capacity() << endl;return 0;
}

输出结果:

size:10
capacity:10

1.1.3 迭代器区间构造

代码实现:

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

测试用例:

int main()
{string s1 = "aaaaaaa";vector<char> v3(s1.begin(), s1.end());return 0;
}

输出结果:
在这里插入图片描述

1.1.4 initializer_list 的构造

用一个初始化列表来构造
代码实现:

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

测试用例:

int main()
{vector<int> v4{ 1,2,3,4,5,6,7,8,9 };return 0;
}

输出结果:
在这里插入图片描述

1.2析构函数

析构函数:完成对象中的资源的回收清理,防止出现内存泄露.

代码实现:

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

1.3拷贝构造函数

代码实现:

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

测试用例:

int main()
{	vector<int> v4{ 1,2,3,4,5,6,7,8,9 };vector<int> v5 = v4;return 0;
}

输出结果:
在这里插入图片描述

1.4赋值运算符重载

代码实现:

		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;}

这里复用的是拷贝构造,拷贝构造我们已经测试过了没有什么问题,这里应该也是正常的,这里就不测试了.

二.元素的插入,删除,查找操作

2.1 operator[]重载函数

这里我们需要重载两个版本,一个是普通对象调用,另一个是const对象调用.
代码实现:

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

测试用例:

int main()
{vector<int> v1{ 1,2,3,4,5,6,7,8,9 };for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5 6 7 8 9

2.2 push_back函数:尾插一个元素

代码实现:

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

测试用例:

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

输出结果:

1 2 3 4 5

2.3 pop_back函数:尾删一个元素

实现思路:
1.将_finish指针向前移动一位,即删除最后一个元素。
2.当size已经为0,即vector中已经没有数据时,就不再删除.
代码实现:

		void pop_back(){assert(size() > 0);--_finish;}

测试用例:

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

输出结果:

1 2 3 4 5
1 2 3 4

2.4 insert函数:指定位置插入元素

这里需要注意迭代器失效的问题,如果不了解什么是迭代器失效的小伙伴,可以去:vector ,里面有迭代器失效场景的详细介绍.
代码实现:

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

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.insert(v1.begin() + 2, 1000);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;return 0;
}

输出结果:

1 2 3 4 5
1 2 1000 3 4 5

2.5 erase:删除指定位置的元素

erase同样也要注意迭代器失效.我们要通过返回一个更新之后的迭代器来避免迭代器失效场景的出现.

代码实现:

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

测试用例:

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;v1.erase(v1.begin() + 2);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;}return 0;
}

输出结果:

1 2 3 4 5
1 2 4 5

三.front和back函数以及迭代器的实现

3.1 front函数: 获取第一个元素

代码实现:

		T& front(){assert(size() > 0);return _start[0];}const T& front() const{assert(size() > 0);return _start[0];}

3.2 back函数: 获取最后一个元素

代码实现:

		T& front(){assert(size() > 0);return _start[0];}const T& front() const{assert(size() > 0);return _start[0];}

3.3 begin和end函数

代码实现:

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

3.4 swap函数

代码实现:

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

希望对大家有所帮助,感谢观看!

相关文章:

【C++ STL】手撕vector,深入理解vector的底层

vector的模拟实现 前言一.默认成员函数1.1常用的构造函数1.1.1默认构造函数1.1.2 n个 val值的构造函数1.1.3 迭代器区间构造1.1.4 initializer_list 的构造 1.2析构函数1.3拷贝构造函数1.4赋值运算符重载 二.元素的插入,删除,查找操作2.1 operator[]重载函数2.2 push_back函数:…...

【Android】CarWatchDog I/O监控服务

Android Car WatchDog I/O监控服务 背景&#xff1a; 某基于Android 13的车载系统。 某天长时间测试一款3方&#xff08;非SystemApp&#xff09;时&#xff0c;该款应用偶发闪退现象。 通过日志分析&#xff0c;发现应用被系统的 Car WatchDog&#xff08;喂狗服务&#xff…...

如何使用 Django 框架进行用户认证的详细指南,涵盖用户注册和登录功能的实现。

当然!下面是关于如何使用 Django 框架进行用户认证的详细指南,涵盖用户注册和登录功能的实现。 掌握 Django 用户认证的艺术 Django 是一个强大的 Python Web 框架,以其灵活性和高效性著称。无论你是新手还是经验丰富的开发者,理解和实现用户认证都是 Web 开发中的一项核心…...

C++ 语言特性21 - 别名模板

一&#xff1a;概述 别名模板是 C11 引入的&#xff0c;用于为一个模板类型定义别名&#xff0c;从而简化复杂的模板类型定义。它结合了 using 关键字&#xff0c;可以对模板类型进行重新命名&#xff0c;使代码更加简洁和可读。 1. 作用 定义模板类型的别名。简化复杂的模板类…...

Jenkins pipeline配置示例

前提条件&#xff1a;已经安装Jenkins并能正常启动 如果Jenkins安装启动遇到问题可以参考&#xff1a; 1.创建pipeline 点击新建项目&#xff1a; 输入名称&#xff0c;选择pipeline&#xff1a; 进入配置页面&#xff0c;如果要配置GitHub Webhook要勾选&#xff1a;<fo…...

Navicat for MySQL 常见问题

一、 创建连接失败问题 创建连接后&#xff0c;报错&#xff1a;1251 -Client does not support authentication protocal by server;consider upgrading MySQL client 原因&#xff1a;环境冲突 解决办法 &#xff1a; windowsR 打开 services.msc 找S开头&#xff1a;SQ…...

Windows:win11旗舰版连接无线显示器,连接失败

摘要&#xff1a;win11系统通过 miracast 无线连接到长虹电视的时候&#xff0c;一直连接不上。查看电脑又是支持 miracast 协议&#xff0c;后续发现关闭防火墙即可正常连接。 一、问题现状 最近公司里新换了电视&#xff0c;打算把笔记本电脑投屏到电视上。由于 HDMI 插拔不…...

Android2024.2.1升级错误

提示 Gradle 版本不兼容&#xff0c;升级后就报错了 。 1.gradle安装包镜像 distributionBaseGRADLE_USER_HOME distributionPathwrapper/dists //distributionUrlhttps\://services.gradle.org/distributions/gradle-8.5-bin.zip distributionUrlhttps://mirrors.cloud.tencen…...

【PHP陪玩系统源码】游戏陪玩系统app,陪玩小程序优势

陪玩系统开发运营级别陪玩成品搭建 支持二开源码交付&#xff0c;游戏开黑陪玩系统: 多客陪玩系统&#xff0c;游戏开黑陪玩&#xff0c;线下搭子&#xff0c;开黑陪玩系统 前端uniapp后端php&#xff0c;数据库MySQL 1、长时间的陪玩APP源码开发经验&#xff0c;始终坚持从客户…...

Arduino UNO R3自学笔记20 之 Arduino如何测定电机速度?

注意&#xff1a;学习和写作过程中&#xff0c;部分资料搜集于互联网&#xff0c;如有侵权请联系删除。 前言&#xff1a;在学习了Arduino的相关基础知识后&#xff0c;现在做个综合应用&#xff0c;给旋转的电机测速。 1.实验目的 测定旋转电机的转速。 2.实验器材-编码器 …...

ChatGPT全新功能Canvas上线:开启智能编程与写作新篇章

引言 随着人工智能技术的迅猛发展&#xff0c;OpenAI旗下的明星产品ChatGPT不断推出创新功能&#xff0c;以满足用户在各个领域的需求。2024年10月3日&#xff0c;OpenAI正式宣布了ChatGPT的全新功能——Canvas。这一功能基于先进的GPT-4o模型开发&#xff0c;为用户提供了一个…...

南沙C++信奥赛陈老师解一本通题 2005:【20CSPJ普及组】直播获奖

【题目描述】 NOI2130 即将举行。为了增加观赏性&#xff0c;CCF 决定逐一评出每个选手的成绩&#xff0c;并直播即时的获奖分数线。本次竞赛的获奖率为 w%w%&#xff0c;即当前排名前 w%w% 的选手的最低成绩就是即时的分数线。 更具体地&#xff0c;若当前已评出了 pp 个选手的…...

Llama 3.2 视觉能力评估

Meta 发布了 Llama 3 模型的新版本&#xff1b;这次&#xff0c;有四种模型用于不同的目的&#xff1a;两个多模态模型&#xff0c;Llama 3.2 11B 和 90B&#xff0c;以及两个用于边缘设备的小型语言模型&#xff0c;1B 和 3B。 这些是 Meta AI 的首批多模态模型&#xff0c;基…...

前端性能优化 面试如何完美回答

前言 性能优化是目前在面试中被问到非常多的问题&#xff0c;主要就是通过各种算和技术来提高页和应用的速度和用户体前端性能优化的问题并不好回答 在回答的时候干万不要掉进一个误区&#xff0c;认为性能优化只是几个技术点而已&#xff0c;事实上性能优化涉及到的是多方面的…...

程序猿成长之路之设计模式篇——设计模式简介

无论是对于代码质量还是代码可维护性、可扩展性&#xff0c;使用合适的设计模式都能够起到促进提升的作用&#xff0c;此外在软考的软件工程师、系统架构师职称考试中&#xff0c;设计模式也是必考的一块内容&#xff0c;因此我打算开拓一个新的专栏简单介绍一下设计模式&#…...

基于Node2Vec的图嵌入实现过程

目录 一、引言二、Node2Vec&#xff08;原理&#xff09;2.1 随机游走&#xff08;Random Walk&#xff09;2.2 嵌入学习2.3 Node2Vec 的优势 三、使用 Node2Vec 进行图嵌入&#xff08;实践&#xff09;3.1 读取和转换 JSON 文件为 Graph 对象3.2 训练 Node2Vec 模型3.3 二维嵌…...

国庆刷题(day4)

C语言&#xff1a; C&#xff1a;...

如何在 Python 3 中制作一个计算器程序

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 简介 Python 编程语言是处理数字和求解数学表达式的强大工具。这种特性可以用来制作有用的程序。 本教程介绍了如何在 Python 3 中制作…...

搭建shopify本地开发环境

虽然shopify提供了在线编辑器的功能&#xff0c;但是远不及本地编辑器方便高效&#xff0c;这篇文章主要介绍如何在本地搭建shopify开发环境&#xff1a; 1、安装nodejs 18.2 2、安装git 3、安装shopify cli ,使用指令: npm install -g shopify/clilatest 4、安装ruby 5、…...

【在Linux世界中追寻伟大的One Piece】进程信号

目录 1 -> 信号入门 1.1 -> 生活角度的信号 1.2 -> 技术应用角度的信号 1.3 -> 注意 2 -> 信号的概念 2.1 -> 用kill -l命令可以查看系统定义的信号列表 2.2 -> 信号处理常见方式 3 -> 产生信号 3.1 -> Core Dump 3.2 -> 调用系统函数…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...