您现在的位置是:首页 > 正文

STL之vector模拟实现

2024-04-01 05:58:10阅读 4

🎩前言

vector的中文意思是向量,他可以容纳很多类型的数据,因此vector也被称为容器

看到前面的解释可能你一脸蒙逼,下面我给出两种简单的理解。

  1. 可以把vector理解为是一个可以动态增长的数组,一个数组可以存储多个相同类型的数据。
  2. 也可以理解成是一个顺序表,里面可以存储不同类型的数据
  3. 其实这两种说法本质都是一样的,因为顺序表就是用数组实现的。

  • vector是c++的一个类,他像前面我介绍过的string类(没看过的同学看这里:)一样,有public函数,也有private成员。vector高级的点在于它广泛应用迭代器,这样极大的提高了效率,也增加了难度

    在vector中,可以把迭代器理解成是一个指针,通过指针实现各个函数接口。但这并不意味着所有的迭代器都是指针。比如在list中,就不是指针。

我们先看一下整体框架

namespace jmy
{
	//使用模板
	template<class T>
	class vector
	{

		public:
			typedef T* iterator;
			//这句话必须放在里面,他是public类型的,才能被访问,否则就是私有的,不能访问
			
	//函数实现...
	
		private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;

	};
}
	

下面看图加深理解

🎩构造函数

构造函数的作用是给成员初始化。
让所有的指针都指向null即可。

		//不带参数的构造函数
		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}

🎩析构函数

析构函数的作用是释放空间,并且置成空指针。

		//清理资源
		~vector()
		{
		delete[]_start;
		_start=nullptr;
		_finish=_endofstroage=nullptr;
		}

🎩reserve

扩容函数,当要插入数据单数容量不够的时候调用这个函数

		void reserve(const size_t n)
		{
			int sz = size();
			if (n > capacity())
			{
				T* tmp = new T[n];
				//第一次进来的时候,capacity是0,给了个2,旧空间是空。(_start是空),就不需要拷贝。为了避免这种情况,判断一下
				if (_start)
				{
					for (int = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[]_start;
				}
				
				_start = tmp;
				//增完容之后,要让指针指向对的位置
				_finish = tmp + sz;
				_endofstorage = tmp + n;
			}
		}

注意这里我把原数据拷贝过来用的是赋值。有的同学可能会想到使用memcpy或者使用strcpy。


下面我解释一下这两个函数为什么不行

  1. memcpy。用于内存复制,这是内存拷贝函数
    用memcpy的主要问题:他是浅拷贝,但是我们需要使用深拷贝。
  2. strcpy,用于复制字符串到另一个空间里,这是字符串拷贝函数。
  3. mem系列的函数是按字节拷贝的,如果传过来的T是int类型,那么就可以使用mem系列的函数,但是T也可能是其他类型的,这时使用mem系列的函数就会出现问题。

🎩push_back

  • 这个函数是在最后位置插入x
  • 基本操作步骤:
    先检查容量是否够用,如果不够就扩容—>在最后的位置插入x—>更新_finish

  • 一共有两种写法:
  1. 普通方式
  2. 复用insert(我将在后面实现)
		void push_back(const T& x)
		{
			if (_endofstorage == _finish)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;//finish是最后一个元素的位置,直接解引用放进去数据即可
			_finish++;

		}

下面是复用insert之后的代码

		void push_back(const T& x)
		{

//			如果复用insert
			insert(_finish,x);
		}

🎩pop_back

这个函数很简单,让_finish减1即可。


  • 一共有两种写法:
  1. 普通方式
  2. 复用erase(我将在后面实现)
		void pop_back()
		{
			assert(_start<_finish);
			_finish--;

		}

下面是复用erase的代码

		void pop_back()
		{
			//如果复用erase
			erase(_finish - 1);
		}

🎩 insert

  • 这个函数是在pos位置插入x

  • 基本操作步骤:
    如果需要增容,就先增容–》把pos之后的数据依次往后移一位—〉在pos位置插入x----》更新指针
		void insert(iterator pos, const T& x)
		{
			assert(pos <=_finish);
			//可能需要扩容
			if (_endofstorage == _finish)
			{
				size_t n = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + n;

			}
			iterator end = _finish-1;
			while(end>=pos)//这里可以相等,就可以让pushback复用他
			{
			*(end+1) = *end;
			--end;
			}
			*pos = x;
			++_finish;
		}

🎩 erase

  • 这个函数是在pos位置删除一个数据,结果返回当前位置的下一个位置。

  • 基本操作步骤:
    从pos位置开始,后面的值依次往前覆盖—》更新指针,返回pos
		//删除pos位置的元素。结果返回当前位置的下一个位置
		iterator erase(iterator pos)
		{
			assert(pos < _finish);
			iterator it = pos;
			while (it<_finish)
			{
				*it = *(it + 1);
				++it;
			}
			--_finish;
			return pos;
		}

🎩size

		size_t size() const
		{
			return _finish - _start;
		}

🎩capacity

		size_t capacity() const
		{
			return _endofstorage - _start;
		}

🎩resize

  • 不仅开空间,还要初始化(初始化成缺省值)。

  • 它分成3种情况
  1. n<size时,让_finish指向n的位置即可。
  2. n>capacity,先进行扩容–》把从_finish开始位置往后支撑缺省值–〉更新_finish指针
  3. size<n<capacity,直接改变_finish即可。
void resize(size_t n,const T&val=T())
		{
			if (n < size())
			{
				_finish = _start+n;
			}

			else
			{
				iterator it = _finish;
				if (n > capacity())
				{
					reserve(n);
					//这里不用memset的原因
					//	memxx系类的函数是按字节赋值的,但是对于自定义类型,他不能处理
					while (it < _start+n)
					{
						*_finish = val;
						++it;
					}
					_finish = _start+n;
				}
			}
			
			
		}

🎩operator[]

实现这个函数的目的:可以像数组一样的到某个数据。

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

🎩operator=

  • 赋值函数,把v3的值赋给v1

  • 这个函数有两种写法

1.普通方法
2. 调用swap(推荐使用这个)


方法1

		//赋值函数v1=v3
		//方法1
		 vector<T>& operator=(const vector<T> & v)
		{
			if(this!=&v)
			{
				//先释放v1(旧空间) 
				delete[]_start;
				//让旧空间指向新的空间
				_start = new T[v.capacity()];
				memcpy(_start, v._start, sizeof(T)* v.size());

			}
		return *this;
		}

方法2

		 //赋值函数v1=v3
		 //方法2
		 vector<T>& operator=( vector<T> v)
		 {
			 swap(v);//this省略不写
			 return *this;
		 }

🎩swap

自己构造函数swap,这是一个浅拷贝,可以提高效率。如果使用默认的swap,是深拷贝,代价很大。

		 void swap(vector<T>& v)
		 {
		 //这里调用的是std命名空间的swap函数
			:: swap(_start, v._start);
			:: swap(_finish, v._finish);
			:: swap(_endofstorage, v._endofstorage);
		 }

网站文章

  • node.js连接MongoDB数据库,db.collection is not a function完美解决

    node.js连接MongoDB数据库,db.collection is not a function完美解决

    解决方法一、 mongodb数据库版本回退: 这个错误是出在mongodb的库中,在nodejs里的写法和命令行中的写法不一样,3.0的api已经更新和以前的版本不不一样,我们在npm中没指定版本号的安装就默认安装的是3.0版本。 可以参考3.0的api文档:http://mongodb.github.io/node-mongodb-native/3.0/api/ 在项目中找到packag...

    2024-04-01 05:58:02
  • JS中第三方库

    网站:https://www.bootcdn.cn库:moment.js 日期处理类的库(体积较大) day.js处理日期的(体积较小)

    2024-04-01 05:57:18
  • 【java学习】进程、线程、程序

    【java学习】进程、线程、程序

    1,概念 (1)分类 ①守护线程(Daemon Thread) 用户线程可以通过System.exit(status)(status为0时表示正常退出,非0表示非正常退出)来退出JVM。 父线程是守护线程子线程默认为守护线程,父线程是用户线程子线程默认为用户线程。父线程在创建子线程后,启动子线程之前,可以调用Thread实例的setDaemon方法来修改线程属性。 当没有用户线程...

    2024-04-01 05:57:12
  • php程序怎么导入数据库,php 简单数据库导入程序[.sql文件]

    php 简单数据库导入程序[.sql文件]function insert_file($file,$replace=&#39;&#39;){global $Charset;$readfiles=read...

    2024-04-01 05:57:03
  • python子进程模块subprocess详解与应用实例 之二

    1.2. Popen 对象 Popen类的实例有下列方法: 1. Popen.poll() 检查子进程是否已经结束,设置并返回返回码值。 2. Popen.wait() 等待子进程结束,设置并返回返回码值。 WARNING: 当使用 stdout=PIPE 或 stderr=PIPE 并且子进程生成了足够多的输出信息到管道,以至于管道阻塞,将会造成死锁。 使用 com

    2024-04-01 05:56:19
  • shell脚本之批量添加用户

    shell脚本之批量添加用户

    1 #/bin/bash 2 for i in {1..10};do 3 if id user$i &amp;&gt; /dev/null;then 4 echo &quot;This user is exists&quot; 5 else 6 adduser user$i &amp;&gt;/...

    2024-04-01 05:56:12
  • 优化JavaScript代码

    优化JavaScript代码

    我google一下,已有人翻译了此文.感觉比我翻译的要好!是译言站翻译的见www.yeeyan.com/articles/view/92135/47626/dz原文见:http://code.google.com/intl/zh-CN/speed/articles/optimizing-javascript.html不合适的地方,请大家指出来!希望对你有用!...

    2024-04-01 05:56:05
  • python将图片生成二进制的两种方式(java读取)

    文章目录tobytes()生成带格式的二进制 以程序中生成的词云图为例(方便测试,我把生成图片调小了) wc = WordCloud(font_path=font_path, scale=1, col...

    2024-04-01 05:55:27
  • 计算机控制与技术课程设计报告书,计算机控制技术课程设计书报告书.doc

    on二阶环节电压跟踪控制系统的设计(采用PC机、JK实验装置)专 业:自动化 专业班 级:2008 级 8(7)班组 员:姚 亮刘 凤罗 威 李 延 ...

    2024-04-01 05:55:19
  • python优化算法工具包_12种Python 机器学习 &amp; 数据挖掘工具包,一定让你受益匪浅...

    python优化算法工具包_12种Python 机器学习 &amp; 数据挖掘工具包,一定让你受益匪浅...

    作为一种解释型语言,Python的设计哲学强调代码的可读性和简洁的语法(尤其是使用空格缩进划分代码块,而非使用大括号或者关键词)。相比于C++或Java,Python让开发者能够用更少的代码表达想法。...

    2024-04-01 05:55:12