我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C++ vector类的模拟实现方法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C++ vector类的模拟实现方法

vector和string虽然底层都是通过顺序表来实现的,但是他们利用顺序表的方式不同,string是指定好了类型,通过使用顺序表来存储并对数据进行操作,而vector是利用了C++中的泛型模板,可以存储任何类型的数据,并且在vector中,并没有什么有效字符和容量大小的说法,底层都是通过迭代器进行操作的,迭代器底层实现也就是指针,所以说,vector是利用指针对任何顺序表进行操作的。

在这里插入图片描述

vector属性

  • _start用于指向第一个有效元素
  • _finish用于指向最后一个有效元素的下一个位置
  • _endOfStorage用于指向已经开辟了的空间的最后一个位置的下一个位置vector的迭代器是原生态T*迭代器

template<class T>
class Vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;

private:
	iterator _start;
	iterator _finish;
	iterator _endOfStorage;
};

构造函数

  • 无参默认构造函数,将所有属性都置空
  • 以n个val初始化的构造函数,先开辟n个空间,再将这些空间的值都置为val,并更新_finish和_endOfStorage的位置
  • 通过迭代器传参初始化的构造函数,使用新的迭代器,通过尾插将数据插入到新的空间

使用新的迭代器的原因是使传入的迭代器可以是任意类型的,如果使用Vector的迭代器,那么传入的迭代器的类型只能和Vector的类型一样,这里拿string举例,创建一个char类型的Vector,Vector,但是传入的迭代器并不是char类型的,可以是字符数组的迭代器或者是string的迭代器。只要通过解引用是char类型就可以


//无参默认构造
	Vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_endOfStorage(nullptr)
	{}

	//n个val的构造函数
	Vector(int n, const T& val = T())
		:_start(new T[n])
		,_finish(_start +n)
		,_endOfStorage(_finish)
	{
		for (int i = 0; i < n; ++i)
		{
			_start[i] = val;
		}
	}

	//通过迭代器产生的构造函数
	template<class InputIterator>
	Vector(InputIterator first, InputIterator last)
		:_start(nullptr)
		, _finish(nullptr)
		, _endOfStorage(nullptr)
	{
		while (first != last)
		{
			pushBack(*first);
			++first;
		}
	}

运行结果在begin() 和end()实现中

size()和capacity()

指针相减得到的值就是这两个指针之间的元素个数


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

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

在这里插入图片描述

pushBack()

  • 检查容量,如果_finish和_endOfStorage指针相等,说明容量已经满了,需要开辟更大的空间
  • 在_finish位置插入新的数据
  • 更新_finish

void pushBack(const T& val)
	{
		//检查容量
		if (_finish == _endOfStorage)
		{
			size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
			reserve(newC);
		}

		//插入数据
		*_finish = val;
		//更新finish
		++_finish
	}

运行结果在begin() 和end()实现中

reserve

  • 检查n的合理性,reserve只能扩大不能缩小空间
  • 保存有效元素的个数,用于后面更新_finish使用
  • 申请空间并将数据拷贝到新的空间中,释放旧的空
  • 更新3个成员变量,注意_finish不能更新为_finish+size(),原因是size()是通过两指针运算得出来的,此时的_fiinsh已经指向了释放的空间,再去使用会出错,所以这也是有第二步的原因

以下代码存在浅拷贝问题,文章末尾会给出正确深拷贝代码和详细解释


	void reserve(size_t n)
	{
		//reserve只能扩大空间不能缩小空间
		if (n > capacity())
		{
			//保存有效元素
			size_t sz = size();
			//申请空间
			T* tmp = new T[n];
			//将数据拷贝到新的空间
			if (_start != nullptr)
			{
				//拷贝有效元素
				memcpy(tmp, _start, sizeof(T) * size());
				delete[] _start;
			}
			//更新
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}
	}

运行结果在begin() 和end()实现中

begin() 和end()


iterator begin()
	{
		return _start;
	}

	iterator end()
	{
		return _finish;
	}

	const_iterator begin() const
	{
		return _start;
	}

	const_iterator end() const
	{
		return _finish;
	}

在这里插入图片描述

有了begin()和end就可以使用范围for


template<class T>
void printVectorFor(Vector<T>& vec)
{
	for (auto& e : vec)
	{
		cout << e;
	}
	cout << endl;
}

在这里插入图片描述

[]运算符重载


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

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

在这里插入图片描述

resize()

  • n <= size 直接更新_finish的位置即可
  • size < n <= capacity,从_finish开始补充元素,补充到_start+n的位置,然后执行第一步
  • n > capacity 增容,执行第二和第一步

void resize(size_t n, const T& val = T())
	{
		//3.n >= capacity
		if (n > capacity())
		{
			reserve(n);
		}
		//2.size < n <= capacity
		if (n > size())
		{
			while (_finish != _start + n)
			{
				*_finish = val;
				++_finish;
			}
		}
		//1.n<=size
		_finish = _start + n;
	}

在这里插入图片描述

insert()

  • 检查插入的位置的有效性[_start, _finish)
  • 检查容量,由于增容会导致pos迭代器失效,所以我们可以先保存pos对于_start的偏移量offset,增容后,再将pos重新赋值pos=_start+offset
  • 移动元素,从后往前移动,最后将pos位置的元素置为val
  • 更新_finish

void insert(iterator pos, const T& val)
	{
		//检查位置有效性
		assert(pos >= _start || pos < _finish);
		//检查容量
		if (_finish == _endOfStorage)
		{
			//增容会导致迭代器失效
			//保存pos和_start的偏移量
			size_t offset = pos - _start;
			size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
			reserve(newC);
			//更新pos
			pos = _start + offset;
		}
		//移动元素
		iterator end = _finish;
		while (end != pos)
		{
			*end = *(end - 1);
			--end;
		}
		//插入
		*pos = val;
		//更新
		++_finish;
	}

在这里插入图片描述

erase()

  • 检查位置有效性
  • 移动元素,从前向后移动
  • 更新_finish

iterator erase(iterator pos)
	{
		//检查位置有效性
		assert(pos >= _start || pos < _finish);
		//移动元素,从前往后
		iterator start = pos + 1;

		while (start != _finish)
		{
			*(start - 1) = *start;
			++start;
		}
		//更新
		--_finish;
	}

在这里插入图片描述

void popBack()

利用erase接口进行尾删


void popBack()
	{
		if (size() > 0)
			erase(end() - 1);
	}

在这里插入图片描述

析构函数


~Vector()
	{
		if (_start)
		{
			delete[] _start;
			_start = _finish = _endOfStorage = nullptr;
		}
	}

算法库中的find

头文件<algorithm>


template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val)

参数内容(从迭代器的begin起到end中,找到val值,找到返回该值所在的迭代器,找不到返回end)

在这里插入图片描述

reserve的深浅拷贝问题

当我门使用自定义类型时,使用浅拷贝是效率最高的,但是当我们使用自定义类型时,并且存在内存资源的利用,就必须时刻注意存在的深浅拷贝问题。来看以下代码测试


void test()
{
	Vector<string> v;
	string str1 = "123";
	string str2 = "456";
	string str3 = "789";
	v.pushBack(str1);
	v.pushBack(str2);
	v.pushBack(str3);
}

调试结果:

在这里插入图片描述

当我们在插入第三个字符串时,就发生了内存异常的问题,我们来看看到底是什么问题。
第一次插入str1,没有问题

在这里插入图片描述

第二次插入str2,插入之前我们会扩容,会创建2倍大的空间tmp,然后通过memcpy内存拷贝(浅拷贝)将内容拷贝到tmp中,此时就有两个指向指向一个资源(123),拷贝完后delete[]要删除原有空间,将123释放后,其实现在新的空间的第一个元素指向的是一个已经释放了的空间,但是问题并没有暴露出来,第二个元素的插入也没有问题

在这里插入图片描述

第三次str3的插入,这次插入也会进行扩容,会先开辟一个2倍大的空间tmp,然后通过memcpy内存拷贝(浅拷贝)将内容拷贝到tmp中,此时有两个指针指向已经释放的资源(123),有两个指针指向资源(456),当拷贝完成后会释放旧的空间,当释放原指针指向的(456)时不会报错,原因和第二次插入原因一样。但是释放原有空的第一个指针时,就会发生内存报错异常,原因是资源(123)已经被释放了,如果再释放就属于二次释放,是不安全的。内存错误就报异常。

在这里插入图片描述

所以我们在扩容的时候不应该只是单纯的浅拷贝,也就是使用memcpy来拷贝内容,我们应该要使用深拷贝。将memcpy改为for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}
整体代码如下:


void reserve(size_t n)
	{
		//reserve只能扩大空间不能缩小空间
		if (n > capacity())
		{
			//保存有效元素
			size_t sz = size();
			//申请空间
			T* tmp = new T[n];
			//将数据拷贝到新的空间
			if (_start != nullptr)
			{
				//拷贝有效元素
				//memcpy(tmp, _start, sizeof(T) * size());
				//深拷贝
				for (size_t i = 0; i < sz; ++i)
				{
					//调用自定义类型的赋值运算符重载函数,完成深拷贝
					//前提是该重载函数也是深拷贝,string是STL库中,是被深拷贝处理过
					tmp[i] = _start[i];
				}
				delete[] _start;
			}
			//更新
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}
	}

到此这篇关于C++ vector类的模拟实现方法的文章就介绍到这了,更多相关C++ vector类模拟内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C++ vector类的模拟实现方法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

C++模拟实现vector的方法

今天小编给大家分享一下C++模拟实现vector的方法的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。1. 模拟实现vecto
2023-07-02

C++中如何模拟实现vector

这篇文章给大家分享的是有关C++中如何模拟实现vector的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。vector接口总览namespace nzb{//模拟实现vectortemplatec
2023-06-25

C++中STL vector的模拟实现示例

这篇文章主要介绍C++中STL vector的模拟实现示例,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!1. vector的介绍和使用vector是表示可变大小数组的序列容器。就像数组一样,vector也采用的连续存
2023-06-14

C++模拟实现vector流程详解

这篇文章主要介绍了C++容器Vector的模拟实现,Vector是一个能够存放任意类型的动态数组,有点类似数组,是一个连续地址空间,下文更多详细内容的介绍,需要的小伙伴可以参考一下
2022-11-13

C++模拟实现vector代码分析

本篇内容主要讲解“C++模拟实现vector代码分析”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++模拟实现vector代码分析”吧!vector的模拟实现#include
2023-07-05

c++中vector模拟实现的示例分析

这篇文章将为大家详细讲解有关c++中vector模拟实现的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。一、vector是什么?vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储
2023-06-14

详解C++中vector的理解以及模拟实现

vector是表示可变大小数组的序列容器。这篇文章主要为大家详细介绍了vector的理解以及模拟实现,文中的示例代码讲解详细,感兴趣的可以了解一下
2023-03-08

C++模拟实现vector示例代码图文讲解

这篇文章主要介绍了C++容器Vector的模拟实现,Vector是一个能够存放任意类型的动态数组,有点类似数组,是一个连续地址空间,下文更多详细内容的介绍,需要的小伙伴可以参考一下
2023-02-27

PHP模拟asp.net的StringBuilder类实现方法

本文实例讲述了PHP模拟asp.net的StringBuilder类实现方法。分享给大家供大家参考。具体如下: 在asp.net开发开发环境中,有一个StringBuilder类是比较常用的, 这个类用起来可以实现很方便的text文本的操作
2022-06-07

C++模拟实现string的方法详解

标准库类型string表示可变长的字符序列,使用string类型必须首先包含string的头文件。本文将利用C++模拟实现string,需要的可以参考一下
2022-11-13

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录