vector类模拟实现(c++)(学习笔记)

这篇具有很好参考价值的文章主要介绍了vector类模拟实现(c++)(学习笔记)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基本框架:

namespace xty
{

	template<class T>
	class vector 
	{
	public:
		typedef T* iterator;
	///
	//...
	///

	private:
		iterator _strat;  //起始位置
		iterator _finish;  //最后一个元素的下一个地址
		iterator _end_of_storage;  //容量的最后一个元素

	};
}

vector的大致形状如下:黄色代表每天满的地方。
vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记

构造函数

使用初始化列表实现一个简单的无参构造函数。

		//无参构造函数
		vector()
			:_finish(nullptr),
			_start(nullptr),
			_end_of_storage(nullptr)
		{}

析构函数

记住要带[]即可。

		~vector()
		{
			delete[] _start; //用带括号的
			_start = nullptr;
			_finish = nullptr;
			_end_of_storage = nullptr;
		}

[]

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

push_back

size()

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

capacity()

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

reserve()

因为push_back涉及到扩容函数,需要实现reserve()。

如下示例:

		void  reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tem = new T[n];
				if (_start)
				{
					memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
					delete[] _start;
				}
				_start = tem;
				_finish = _start + size();   //error
				_end_of_storage = _start + n;
			}
		}

问题1:_finish赋值出错,出bug了,是因为size()函数,调用了空指针,导致报错。
改正:
因为delete之后,原数据就被清空了,所以可以提前保存一下size()的大小。

		void  reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tem = new T[n];
				const size_t sz = size();  //提前保存sz
				if (_start)
				{
					memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
					delete[] _start;
				}
				_start = tem;
				_finish = _start + sz;  //使用sz赋值
				_end_of_storage = _start + n;
			}
		}

push_back()

逻辑比较简单,在vector的尾部添加一个val,就需要一些前置函数。

		//尾插
		void push_back(const T& val)
		{

			//满了扩容
			if (_finish  == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

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

迭代器实现

该逻辑也比较简单,注意实现const的版本。

非const和const版本


		typedef T* iterator;
		typedef const T* const_iterator;
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}


		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

pop_back()

尾删。


		bool empty()
		{
			return _start == _finish;
		}

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

resize()

和string逻辑差不多。

		void resize(size_t n, const T& val = T())
		{
			//一样大,直接返回
			if (n == size())   
			{
				return;
			}
			if (n<size())   //小于直接修改_finish
			{
				while (n != size())
				{
					--_finish; 
				}
			}
			else
			{
				if (n > capacity())   //大于容量先扩容
				{
					reserve(n);
				}
				while (n != size())
				{
					push_back(val);
				}
			}
		}

优化:该函数多次调用push_back()使用while,效率低。

		void resize(size_t n, const T& val = T())
		{
			if (n == size())
			{
				return;
			}
			if (n < size())
			{ 
				_finish = _start + n;  //直接移动_finish
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}
				while (_finish != _start + n)  //使用指针操作,减少调用
				{
					*_finish = val;
					_finish++;
				}
			}
		}

insert()***重点

传入迭代器的位置,插入一个元素。

		void insert(iterator pos ,const T& val)
		{
			//检测pos位置是否合法
			assert(pos >= _start);
			assert(pos <= _finish);
			// 满了需要扩容
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			
			//从后往前移动
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}

			*pos = val;   //在该位置赋值
			_finish++;

		}

算法问题1:会造成迭代器失效,迭代器失效,实际就是迭代器底层对应指针所指[空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
该程序正常来说没有问题,当出现扩容的时候,reserve()会删除原来的空间,去申请新的空间,因此会导致pos指向的那段空间被释放掉,pos变成野指针。

改正:记录插入的相对位置,扩容后根据相对位置更新pos的值。

		void insert(iterator pos, const T& val)
		{
			//检测pos位置是否合法
			assert(pos >= _start);
			assert(pos <= _finish);
			// 满了需要扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;//扩容前记住相对位置
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;    //扩容后重新给pos值
			}
			//从后往前移动
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}

			*pos = val;   //在该位置赋值
			_finish++;

		}

算法问题2:执行insert后,如果扩容,pos位置已经改变了,而函数外面的pos因为是值传递,并没有修改,同样导致了野指针的问题。(迭代器再一次失效!
解决办法:

  1. pos传引用可以吗?
    不可以。如下图:如果传入v.begin(),会报错。因为begin()是传值返回,传值返回有一个临时变量,而临时变量具有常性,不能被修改,insert里面就不能修改了!
    vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记
  2. 通过返回值解决可以吗?
    可以,我们可以利用insert返回值的特性,来更新pos防止失效!
    如下图:这样就解决问题了。vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记

最终版本:

		iterator insert(iterator pos, const T& val)
		{
			//检测pos位置是否合法
			assert(pos >= _start);
			assert(pos <= _finish);
			// 满了需要扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;//扩容前记住相对位置
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;    //扩容后重新给pos值
			}
			//从后往前移动
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}

			*pos = val;   //在该位置赋值
			_finish++;

			return pos;
		}

总结:使用insert后,我们默认迭代器失效!因为我们不知道何时执行扩容操作,因此需要重新对pos赋值,防止这类情况发生!

erase()***重点

指定位置执行删除操作。

		void erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			auto end = pos + 1;
			while (end < _finish)
			{
				//后给前,从前往后
				*(end - 1) = *end;
				end++;
			}

			_finish--;
		}

问题1:erase会导致迭代器失效?
==会导致!==如果删除最后一个位置,最后一个位置就变成了空位置,导致pos也指向了不该指向的位置。因此,erase()执行过后,应该重新给pos赋值再使用!

最终版本:添加返回值。

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			auto end = pos + 1;
			while (end < _finish)
			{
				//后给前,从前往后
				*(end - 1) = *end;
				end++;
			}

			_finish--;
			return pos;
		}

最后给大家一个例子自己感受:
该例子在VS2019会报错

#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}

	return 0;
}
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
			++it;
	}
	return 0;
}

再谈构造函数!

这次实现一个可以规定数量和内容的构造函数。

//正常实现
		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			size_t len = n;
			while (n--)
			{
				push_back(val);
			}
		}
		//构造函数由迭代器实现
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

当我们满心欢喜的实现好这两个构造函数后,想要测试一下。结果报错了。
输入: vector vx(10,5);
vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记
这是为什么呢?因为10,5都被编译器认为是int类型,而编译器在函数重载时,会自动调用最合适的,而它认为第二个函数更适合自己(),因此解引用的时候产生非法间接寻址!

因此我们需要再次实现一个int型的函数重载!

		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			size_t len = n;
			while (len--)
			{
				push_back(val);
			}
		}

迭代器构造还支持以下方法:

	int a[] = { 1, 2, 3 };
	vector<int> v4(a, a + 3);
	for (auto e : v4)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

拷贝构造函数****(重点)

如果我们不自己实现拷贝构造函数,编译器就会默认生成一个,但是编译器默认生成的是浅拷贝,不可以。


		//拷贝构造
		vector(const vector<T>& v)
		{
			//扩容
			reserve(v.capacity());
			memcpy(_start, v._start, sizeof(T) * v.size());
			_finish = _start + v.size();
		}

现在我们写完这个函数的拷贝构造之后,看看是否有问题:

vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记
提前告诉大家,这个程序会崩溃,因为memcpy()实现的是浅拷贝,他仅仅会拷贝v3的首尾指针,并不会开一个新的空间去存储相应的字符串。所以,程序结束时,调用析构函数,会连续析构两次!

**解决办法:**不适用memcpy()自己实现深拷贝,使用‘=’即可实现,因为string赋值操作就是深拷贝,string的赋值,就会先开空间,再拷贝!

vector类模拟实现(c++)(学习笔记),C++,c++,学习,笔记


		//拷贝构造
		vector(const vector<T>& v)
		{
			//扩容
			reserve(v.capacity());
			//memcpy(_start, v._start, sizeof(T) * v.size());
			for (size_t i = 0; i <v.size(); i++)
			{
				_start[i] = v._start[i];   //变成string对象的拷贝
			}
			_finish = _start + v.size();
		}

但是reverse()也会产生这个浅拷贝的问题,因此将reserve也应该改成深拷贝。

		void  reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tem = new T[n];
				const size_t sz = size();  //提前保存sz
				if (_start)
				{
					//memcpy(tem, _start, sizeof(T)*size()); //拷贝过去
					for (size_t i = 0; i < size(); i++)
					{
						tem[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tem;
				_finish = _start + sz;  //使用sz赋值
				_end_of_storage = _start + n;
			}
		}

这样vector的问题就解决了。但是vector<vector<int>>还有问题!!!请看赋值重载的部分。

=运算符重载***(重点)

这里暴露了一个问题,就是虽然外面的vector是深拷贝,但是里面的vector是浅拷贝,是由于没有写vector的赋值重载,再补充一个赋值重载即可!

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		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类模拟实现(c++)(学习笔记),C++,c++,学习,笔记

运算符重载和拷贝构造这里写的不太详细,后续还会补充!文章来源地址https://www.toymoban.com/news/detail-743632.html

到了这里,关于vector类模拟实现(c++)(学习笔记)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [C++]:11.模拟实现vector

    1.vector.h vector.h中其实包含了许多的头文件,我们在cpp中包含文件的时候头文件中还会去展开这四个头文件关于vector类主要在这个stl_vector.h中。 2.stl_vector.h 1.构造: ps:在当前的学习阶段看源码不要一行一行去看因为水平不足所以非常多基本上是看不懂的所以不要去一行一行去

    2024年01月16日
    浏览(43)
  • STL 关于vector的细节,vector模拟实现【C++】

    _start指向容器的头,_finish指向容器当中 有效数据 的下一个位置,_endofstorage指向整个容器的尾 先开辟一块与该容器大小相同的空间,然后将该容器当中的数据一个个拷贝过来即可,最后更新_finish和_endofstorage的值即可。 深拷贝版本一: 注意: 不能使用memcpy函数 , 如果vec

    2024年02月15日
    浏览(45)
  • 【C++ STL】vector模拟实现

    2023年05月17日
    浏览(51)
  • 【C++】vector容器的模拟实现

    目录 一,框架设计 二,构造函数 三,析构函数 四,赋值运算符 五,容器接口的实现 1,迭代器实现 2,“ [] ”运算符的实现 3,swap交换和resize重设大小 4,insert插入和erase删除 介绍:         本文,我们重点实现vector容器的用法,这里要注意的是vector容器可以接纳任意类

    2024年02月02日
    浏览(55)
  • C++——vector类及其模拟实现

    前言:前边我们进行的string类的方法及其模拟实现的讲解。这篇文章将继续进行C++的另一个常用类——vector。 vector和string一样, 隶属于C++中STL标准模板库中的一个自定义数据类型 ,实际上就是 线性表 。 两者之间有着很多相似,甚至相同的方法 。 但是它们也有着很大的不

    2024年04月13日
    浏览(41)
  • 【C++】vector模拟实现及其应用

    vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。 本质讲,vector使用动态分

    2023年04月25日
    浏览(47)
  • C++ STL vector 模拟实现

    ✅1主页:我的代码爱吃辣 📃2知识讲解:C++之STL 🔥3创作者:我的代码爱吃辣 ☂️4开发环境:Visual Studio 2022 💬5前言:上次我们已经数字会用了vector,这次我们对其底层更深一步挖掘,其中重点是,Vector中一些深浅拷贝问题。 目录 一.Vector模拟实现的整体框架 二. Vector的构

    2024年02月13日
    浏览(35)
  • C++中的vector类模拟实现

    目录 vector模拟实现 vector类设计 vector类构造函数 vector类根据个数构造函数 vector类根据迭代器区间构造函数 vector类拷贝构造函数 vector类赋值运算符重载函数 vector类析构函数 vector类获取有效数据个数函数 vector类获取容量大小函数 vector类begin()函数 vector类end()函数 vector类reser

    2024年04月13日
    浏览(38)
  • C++:vector使用以及模拟实现

    和我们原来讲的string不同, vector并不是类,是一个类模板,加类型实例化以后才是类。 vector是表示 可变大小数组 的序列容器。 像数组一样 ,vector也采用的连续存储空间来存储元素,但是容量可以动态改变。 和其它容器相比,vector访问元素、尾插、尾删较高效,但不在尾部

    2024年02月11日
    浏览(43)
  • 【C++】vector模拟实现+迭代器失效

    铁汁们,今天给大家分享一篇vector模拟实现 + 迭代器失效,来吧,开造⛳️ 指向最后一个空间的下一个位置 💡 iterator _endofstorage 指向存储第一个有效数据空间的位置 💡 iterator _start 指向存储最后一个有效数据空间的下一个位置 💡 iterator _finish 在成员变量声明处给缺省值,

    2024年02月21日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包