模拟实现STL容器之vector

文章目录

  • 前言
  • 1.大体思路
  • 2.具体代码实现
    • 1.类模板的创建
    • 2.构造函数
      • 1.无参构造
      • 2.拷贝构造 迭代器构造和给定n个val值构造以及析构函数
    • 3.空间扩容
      • 1.reserve
      • 2.resize
    • 4.操作符重载
      • 1.[ ]重载
      • 2.赋值运算符重载
    • 5.数据增加和删除
      • 1.尾插
      • 2.任意位置插入
      • 3.任意位置删除
      • 4.尾删
    • 6.一些其他接口
  • 3.总结

前言

本文主要对vector容器的实现进行讲解,vector我们在使用的感觉它有点像数组,它也是个类模板,可以根据需要实例化出不同的模板类用于存储数据。它的底层实现也是像之前实现的顺序表。本文主要参考库中的vector实现,通过模拟实现让我们对容器理解更加深刻。


1.大体思路

这个vector容器底层也和顺序表类似,在实现的时候我们可以先去看看库中源码。这里就不放出库中源码截图了。直接说结论吧:库中的vector类模板主要有以下几个成员:_start _finish _end_of_storage这个3个成员变量,有之前实现顺序表的基础相信很容易看出来,_start肯定是指向存储数据首地址的,finish是存储末尾数据位置的后一个位置,end是指向存储数据的空间最后一个位置,也就是相当于capacity。这个3个成员变量是指针类型,这是为了后续实现迭代器比较方便于才这样设计的。大概了解成员变量的组成后,就可以着手实现了。这里我们也仿照库中实现按照类模板的方式去实现。

2.具体代码实现

1.类模板的创建

namespace Ly
{
	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起冲突。这里的vector底层存储数据的那一套和顺序表类似,可以天然的使用原生指针作为迭代器。这里为了图方便就不走初始化列表了,直接给缺省值。

2.构造函数

构函数这里有很多细节需要注意,有些地方需要复用其他成员函数。这里为了理清逻辑我们先画图分析一下。

在这里插入图片描述

具体问题如下图以string为例

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

在实现vector的时候会涉及到更深层次的拷贝的,相当于要做两次深拷贝处理,这点需要我们注意

1.无参构造

vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}

这里的无参构造很简单,不过多的赘述了。我们主要看看下面的几种构造。

2.拷贝构造 迭代器构造和给定n个val值构造以及析构函数

vector(size_t n,const T & val)
		{
			    reserve(n);
				for (int i = 0; i < n; ++i)
				{
					push_back(val);
				}
		}

这里直接复用reserve进行扩容然后复用尾插插入数据这两个接口下面会介绍具体实现的,这里先不着急。

vector(const vector<T>& val)
		{
			_start = new T[val.capacity()];
			for (size_t i = 0; i < val.size(); i++)
			{
				_start[i] = val._start[i];
			}
			_finish = _start + val.size();
			_end_of_storage = _start + val.capacity();
			
			/*_start = new T[val.capacity()];
			memcpy(_start, val._start, sizeof(T)*val.size());
			_finish = _start + val.size();
			_end_of_storage = _start + val.capacity();*/

		}

这个拷贝构造我们采用赋值形式的进行数据的拷贝,如果是自定义类型这个赋值会调用后续实现的operator=函数,如果不是自定义类型就是直接赋值和memcpy一样的处理方式,这样就不会出现问题了。这个_finish和_end_of_storage记得及时更新。至于为啥采用赋值的形式我上面说的很清楚了,这里就不在赘述了。还有需要注意的类名<T>才是类型这点在之前的模板博客中提到过。

// 重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

这里迭代器构造的时候需要在定义一个模板参数,这样这个迭代器构造函数可以传任意容器的迭代器作为参数进行构造。

补充一个构造

//避免模板示例化的时候误调上面的迭代器构造
		vector(int n, const T& val)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

理论上将,提供了vector(size_t n, const T& value = T())之后vector(int n, const T& value = T())就不需要提供了,但是对于: vector v(2, 1); 编译器在编译时,认为T已经被实例化为int,而2和1编译器会默认其为int类型 就不会走vector(size_t n, const T& value = T())这个构造方法, 最终选择:vector(InputIterator first, InputIterator last)因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int但是10和5根本不是一个区间,编译时就报错了故需要增加该构造方法


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

		}

这里析构函数也很简单,释放空间后直接置空。


3.空间扩容

1.reserve

void reserve(size_t n)
		{  //需要提前之前的size的大小保存起来确定_finsh的位置
			size_t sz = size();
			if (n > capacity())
			{
				T* tem = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < val.size(); i++)
					{
						_start[i] = val._start[i];
					}
					delete[] _start;
				}
				_start = tem;
				_end_of_storage = tem + n;
				_finish = tem+sz;
			}

		}

只有当n大于capccity的时候才会进行扩容处理,其中扩容的时候会涉及到数据的拷贝所以我们这里还是采用赋值的形式来处理,之前实现的时候是采用memcpy进行直接拷贝上面说了这种拷贝处理是有问题的,所以采用赋值的形式。这里要加上一个判断,_start为空的时候调用resreve实际上是构造函数调用它进行扩容,这个时候reserve只是单独的扩容而已。还有一点需要注意之前的sz需要保存起来。这为啥需要保存起来呢?我们知道这3个成员变量都是指针,如何确定3个指针的指向呢?_start很容易确定,剩下的两个都可以通过_start来确定,_start+size=_finish,_start+capacity=end_of_storage,然而我们的size和capacity都是通过上述两个成员变量和_start相减来确定的。假如我们先更新了_start,那么_finish=_start+size 然而size=_finish -_start等价代换之后_finish=_start+_finsh-_start=_finish,相当于_finish没有更新。所以我们需要提前保存sz。


2.resize

void resize(int n,  const T& val=T())
		{  //相当于删除数据
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}
				while (_finish != _end_of_storage)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

这里有一些细节需要注意。关于这个n的3种分类情况我就不多说了,和string类似处理。我们看到形参是给了缺省值的,我们知道对于内置类型来说是没有构造函数这么一说的那如果T实例化成内置类型怎么办呢,C++中为了配合模板的使用,内置类型也是有构造函数的,但是只是限于在使用模板的时候,还有一点我们看到给的缺省值是个匿名对象,我们知道匿名对象的使用周期很短只有一行,这里为啥还是使用呢?被const加&修饰的匿名对象生命周期会被延长,需要注意的是匿名对象具有常性如果不加const会报错。

4.操作符重载

操作符重载我们的重点放在赋值运算符重载上,这是后续很多地方都需要用到的。

1.[ ]重载

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

[ ]重载支持下标访问这点就不多说了和string类似的处理。

2.赋值运算符重载

//这个是引用作为参数
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endOfStorage, v._end_of_storage);
		}
       //这个是传值传参 不影响实参
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

我看到这个赋值重载是传值传参不是传引用传参,所以不会影响实参,这个形参是临时变量,但是这个临时变量会调用拷贝构造,所以这个临时变量的存储数据的空间也是独立的,我们在调用swap和这个临时变量进行交换即可,这样就完成了一次赋值操作。交换后实际上影响的是这个临时变量,这样处理极为巧妙。这里的细节主要在这个swap函数和这个重载函数的形参的传递形式上。


5.数据增加和删除

1.尾插

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

这里尾插的时候需要注意一下如果capacity为0这个时候需要将它修正为不为0的数,这样才会正常的扩容。如果原有的空间满了我们按照二倍的方式进行扩容。

2.任意位置插入

iterator insert(iterator pos, const T& val)
		{  
			assert(pos >= _start && pos <= _finish);
			if (_finish == _end_of_storage)
			{  //防止扩容之后迭代器失效
				int len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = _start + len;
			}
			iterator end = _finish;
			while (end>pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = val;
			++_finish;
			return pos;
		}

这里有个特别重要的点就是迭代器失效问题,这是为啥呢?我们在进行插入的时候会进行扩容,扩容之后这个pos就会变成野指针,扩容的时候原有的空间被释放了重新申请的空间,为了避免这种情况,我们提前记录好pos和_start之间的间距。剩下的就是挪动数据了,这个挪动数据不用像之前string那样考虑什么无符号整形减的时候会数值会变大。但是注意我们在外部调用这个插入接口的时候,外部的迭代器可能会失效买这个时候需要更新重新接收插入之后的pos值,返回值我们也设置为迭代器类型便于接收新的pos位置。

3.任意位置删除

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

迭代器都是常用!=来判断遍历的,这里我们也按照这样的方式遍历。我们考虑一个问题删除的时候迭代器会失效吗?从代码上看删除数据不需要扩容貌似迭代器不会失效,我们来看看如下的情况:

在这里插入图片描述

从图我们看出删除的时候也会造成迭代器失效,如果这个图中的it在去访问就是非法操作。vs中对于这点处理的比较严格直接会断言报错,Liunx下有相对宽松一点,程序有时候不会报错。

4.尾删

void pop_back()
		{
			assert(!empty());
			--_finish;
		}

这里尾插就更简单了_finish–即可,注意删除的时候vector不能为空

6.一些其他接口

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

这里迭代器实现就比较简单了,vector的迭代器可以直接用原生指针来实现。这里const的迭代器没有写,这个实现就是把iterator换成const_iterator即可,也很简单

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

上面这些接口很简单没啥好说的,看代码就能懂。


3.总结

关于这个vetcor实现,其中最值得注意的几个点是:1.拷贝构造的时候可能涉及到更深层次的拷贝我们这里不采用memcpy的方式处理,memcpy处理内置类型没啥问题,如果是自定义类型就会出现问题,我们采用赋值的方式进行数据的拷贝,这样对于自定义类型来说会调用拷贝构造,对于内置类型处理方式和memcpy是一样的,因为我们别的构造函数调用了这个尾插,使所以尾插也是使用的直接赋值的形式。2.第二点就是这个赋值重载的时候调用swap,这个形参的使用是个细节需要注意。3.第三点就是迭代器在使用的可能会造成迭代器失效的问题,这点需要考虑清楚,不然会有很严重的问题。所以我们在使用迭代器的时候一定要注意及时更新迭代器。

以上内容如有问题,欢迎指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/1393.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

HTTP协议详解(上)

目录 前言&#xff1a; 认识URL HTTP协议方法 通过Fiddler抓包 GET和POST之间典型区别 header详解 HTTP响应状态码 常见状态码解释 状态码分类 HTTP协议报文格式 小结&#xff1a; 前言&#xff1a; HTTP协议属于应用层协议&#xff0c;称为超文本传输协议&#xff…

Canvas百战成神-圆(1)

Canvas百战成神-圆 初始化容器 <canvas id"canvas"></canvas>canvas{border: 1px solid black; }让页面占满屏幕 *{margin: 0;padding: 0; } html,body{width: 100%;height: 100%;overflow: hidden; } ::-webkit-scrollbar{display: none; }初始化画笔…

一天吃透TCP面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…

Activity工作流(三):Service服务

3. Service服务 所有的Service都通过流程引擎获得。 3.1 RepositoryService 仓库服务是存储相关的服务&#xff0c;一般用来部署流程文件&#xff0c;获取流程文件&#xff08;bpmn和图片&#xff09;&#xff0c;查询流程定义信息等操作&#xff0c;是引擎中的一个重要的服务。…

SpringCloud笔记(Hoxton)——Netflix之Ribbon负载均衡

Ribbon使用 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡工具&#xff0c;简单的说&#xff0c;Ribbon是Netflix 发布的开源项目&#xff0c;主要功能是提供客户端软件的负载均衡算法&#xff0c;将Netflix的中间层服务连接在一起。Ribbon客户端组件提供…

好久没写过Qt了,写个Qt回味一下信号与槽

界面效果界面类.h#include <QtWidgets/qmainwindow.h>#include <QtWidgets/qwidget.h>#include <QtWidgets/qplaintextedit.h>#include <QtWidgets/qboxlayout.h>#include <QtWidgets/qlineedit.h>#include <QtWidgets/qpushbutton.h>//#p…

海思SD3403/SS928V100开发(7)mcp2515-SPI转CAN驱动开发

1. 前言 需求: 需要一路can进行收发 分析: 根据目前使用较多的方案是使用主控端SPI接口 接入MCP2515芯片进行CAN协议转换 硬件: MCP2515->SPI2->SS928 2. Uboot开发 2.1 pinmux复用配置 2.1.1 修改uboot参数表 路径: osdrv/tools/pc/uboot_tools/ SS928V100…

Linux用户和权限 —— 操作演示

Linux用户和权限——操作演示认知root用户用户、用户组管理查看权限控制修改权限控制- chmod修改权限控制- chownLinux系列&#xff1a; Linux基本命令 —— 操作演示 认知root用户 root用户(超级管理员) 无论是Windows、MacOS、Linux均采用多用户的管理模式进行权限管理。…

【5G RRC】NR测量事件介绍

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…

基于 gma 绘制古代洛阳 5 大都城遗址空间分布地图

了解 gma gma 是什么&#xff1f; gma 是一个基于 Python 的地理、气象数据快速处理和数据分析函数包&#xff08;Geographic and Meteorological Analysis&#xff0c;gma&#xff09;。gma 网站&#xff1a;地理与气象分析库。 gma 的主要功能有哪些&#xff1f; 气候气象&a…

使用vite创建vue3工程

定义 什么是vite&#xff1f;-----新一代前端构建工具 优势 开发环境中&#xff0c;无需打包操作&#xff0c;可快速的冷启动---最牛的地方轻量快速的热重载&#xff08;HMR&#xff09;---一修改代码就局部刷新&#xff0c;webpack也具备&#xff0c;但vite更快真正的按需编…

【SpringBoot项目实战】瑞吉外卖优化篇

文章目录优化背景搭建环境缓存短信验证码缓存菜品数据Spring CacheSpring Cache介绍原理Spring Cache常用注解Spring Cache使用方式缓存套餐数据读写分离问题分析Mysql主从复制Mysql主从复制配置前置准备主库Master配置从库Slave配置读写分离Sharding-JDBC介绍项目实现读写分离…

分布式微服务架构下网络通信的底层实现原理

在分布式架构中&#xff0c;网络通信是底层基础&#xff0c;没有网络&#xff0c;也就没有所谓的分布式架构。只有通过网络才能使得一大片机器互相协作&#xff0c;共同完成一件事情。 同样&#xff0c;在大规模的系统架构中&#xff0c;应用吞吐量上不去、网络存在通信延迟、我…

GPT-4最震撼我的一点

昨天我看了一遍OpenAI发的视频和论文&#xff0c;最震撼我的并不是根据手绘草图生成HTML页面代码&#xff0c;因为草图太简单&#xff0c;对于复杂的有交互的界面&#xff0c;还不知道它的能力究竟如何&#xff0c;能不能生成准确的、清晰的代码&#xff0c;我再实验一下再给大…

Python截图自动化工具

1、展示部分源码(写的比较乱&#xff0c;哈哈) 2、功能展示 1&#xff09;首页 2&#xff09;按钮截图(用于自动翻页) 3&#xff09;保存位置按钮(选择图片保存的位置) 4&#xff09;重复次数&#xff0c;就是要截取多少次 5&#xff09;定位截屏(截取的内容&#x…

面试造火箭?GitHub顶级“java 复习宝典“一一攻克!star破数十万

前言去年离职四处找了几个月&#xff0c;看清行情后还是决定从事后端开发。上周腾讯那边打电话过来叫我准备面试&#xff08;提前批&#xff09;&#xff0c;一面选择的是电话面&#xff0c;题目一道接一道&#xff0c;人都懵了不过幸好&#xff0c;我有复习宝典&#xff0c;一…

计算机面试常见问答题目

英语口语 自我介绍 Hello, teachers. My name is Wang Xu. I come from Ningxia. I graduated from the School of Computer Science, Xi an Jiaotong University, majoring in Internet of Things. Next, I will introduce myself from four aspects. First of all, I studi…

解读Flaky Test

软件质量保障:所寫即所思&#xff5c;一个阿里质量人对测试的所感所悟。Flaky Tests是什么&#xff1f;初识Flaky Tests源于一个Python库-flaky&#xff0c;flaky是Nose和Pytest的一个扩展库&#xff0c;可以自动重试执行不稳定的测试。在理想情况下&#xff0c;我们期望测试可…

并发基础之线程池(Thread Pool)

目录前言何为线程池线程池优势创建线程池方式直接实例化ThreadPoolExecutor类JUC Executors 创建线程池线程池挖掘Executors简单介绍ThreadPoolExecutor核心类ThreadPoolExecutor 类构造参数含义线程池运行规则线程设置数量结语前言 相信大家都知道当前的很多系统架构都要求高…

SpringBoot(微服务)注册分布式Consul

Consul是什么 Consul是一个基于HTTP的服务发现工具&#xff0c;用于配置和管理系统和服务之间的依赖关系。它提供了一个简单的方式来注册、发现和配置服务&#xff0c;并包括健康检查、负载均衡和故障转移等功能。 Consul是一种分布式系统&#xff0c;用于在大型分布式系统中实…
最新文章