C++:vector增删查改模拟实现

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


前言

提前在这说明下,vector增删查改模拟实现的成员变量博主采用SGI版本。下面给出其库中成员变量是哪些,后续的模拟实现都基于此。

C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法
我们发现库中定义了3个T*的变量。同时3个成员变量的意义如下:

C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法

一、迭代器

1.1 非const迭代器:begin()、end()

typedef T* iterator;

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

1.2 const迭代器:begin()、end()

typedef const T* const_iterator;

const_iterator begin()const
{
	return _start;
}

const_iterator end()const
{
	return _finish;
}

二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现

2.1 构造函数

我们先来看看vector库中的构造类型如下:
C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法
我们知道有三种构造方式,下面给出各种的实现方式。

2.1.1 无参构造

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

2.1.2 迭代器区间构造

template<class InputIterator>//使用模板是为了,当数据类型匹配时就可以使用
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

2.1.3 n个值构造

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

//防止定义vector<int>这种类型走迭代区间的构造函数,我们在多实现一个以下类型函数
//当使用vector<int>类型的去构造时,此时调用的构造函数两个参数都是int。所有他会走最匹配的函数,即迭代器区间构造生成的构造函数,程序会出错。
//而下面给出了现成的最匹配构造函数,编译器调用时就不会走模板。
vector(int n, const T& value = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(value);
	}
}

2.2 拷贝构造

拷贝构造我们先调用开好一块空间,在依次插入数据即可。

//vector(const vector& x) //库中实现模式, 直接使用类名。但C++,类型不是类名。
//这里各位读者了解下这里直接类名做类型也正确即可,但不建议各位这样做。
vector(const vector<T>& v)
{
	reserve(v.capacity());//后面会给出实现
	for (auto& e : v)
	{
		push_back(e);
	}
}

2.3 赋值重载

赋值重载这里我们不要传引用,而是直接传参即可。编译器调用拷贝构造生成形参后,在调用swap()函数依次交换形参和this即可。

//赋值重载
void swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v_endofstorage);
}

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

3 析构函数

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

三、容量相关:capacity()、size()、reserve()、resize()

3.1 capacity()

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

3.2 size()

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

3.3 reserve()

由于stl中我们一般不缩容,所以先判断reserve的空间大小是否比当前空间容量大。
如果reserve的空间更大,所以我们需要先开好目标大小的空间,在将原数据拷贝过去,最后析构原来空间即可。
但下面这两种实现方式对吗?

第一种:

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)//如果原来空间有数据,拷贝到新空间
		{
			memcpy(tmp, _start, sizeof(T) * size());
			delete[] _start;
		}
		//更新_start、_finish、_endofstorage。指向新空间中相应位置
		_start = tmp;
		_finish = _start + size();
		_endofstorage = _start + n;
	}
}

先说结论:上诉这段代码是错的。
在我们调试后会发现_finish的值没有更新。(这里大家自行验证下接口)

原因:(win11画图一直很模糊,博主也很无奈,各位将就看吧)
C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法


第二种:
为了解决上诉问题,我们可以先记录_finish和_start的偏移量,用来代替size()函数。
所以初学者很容易写出以下代码:

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();//记录_finish 和 _start 的偏移量
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);
			delete[] _start;
		}

		_start = tmp;
		_finish = _start + sz;//不能用size()代替sz,否则会导致迭代器失效
		_endofstorage = _start + n;
	}
}

那这是否正确呢?答案是否定的。
我们来看看下面这种场景:
C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法


实际上对于这种情况,可以自己循环依次赋值即可。内置类型直接拷贝数据;内置类型调用赋值重载,是一种深拷贝。

最终代码如下:

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();//记录_finish 和 _start 的偏移量
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);
			for (size_t i = 0; i < sz; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}

		_start = tmp;
		_finish = _start + sz;//不能用size()代替sz,否则会导致迭代器失效
		_endofstorage = _start + n;
	}
}

3.4 resize()

resize逻辑还是很简单的。
首先判断resize()的目标大小n和有效数据个数size()谁大。如果有效个数size()更大,只需更改_finish即可;否则要先进行扩容(reserve会将原有数据拷贝到新空间),然后从_finish开始向扩充的空间插入新的值。

代码如下:

//const会延长匿名对象的生命周期, 匿名对象具有常性
//模板出来后,对类进行了升级,内置类型也有构造函数
//void resize(size_t n, T val = T())
void resize(size_t n, const T& val = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish < _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
}

四、operator[ ]重载

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

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

五、元素相关:insert、erase、push_back、pop_back

5.1 insert()

任意位置插入数据,首先需判断是否需要扩容。然后将插入位置pos开始往后的数据向后移动,最后将新数据插入到pos处即可。
tips:

  • 如果发生扩容,需要先记录pos和_start之间的偏移量。在将pos位置跟新,指向新空间中对应位置。否则会导致迭代器失效
void insert(iterator pos, const T& x)
{
	assert(pos >= _start);
	assert(pos <= _finish);
	if (_finish == _endofstroage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}

	//挪动数据
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}

	//插入数据
	*pos = x;
	_finish++;
}

5.2 erase()

任意位置删除数据,只需要从pos+1开始,将后续数据全部依次向前移动覆盖,最后更新_finish即可。

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

	iterator it = pos + 1;
	while (it < _finish)
	{
		*(it - 1) = *it;
		++it;
	}

	--_finish;

	return pos;
}

5.2.1 erase迭代器失效

void testvector4()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	auto it = v.begin();
	while (it < v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
			it++;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

上述代码本意是将偶数全部删除,结果本该是1 、5。但结果却是:
C++:vector增删查改模拟实现,C++经典收录,c++,开发语言,笔记,stl,学习方法
为什么呢?
这是因为我们删除元素后,后续数据会补上空缺。所以当使用erase后,迭代器会失效。(上述结果是g++的实现机制,在vs2019下上述代码会直接报错。原因在于vs2019对erase后的空间做强制检查,不允许访问)。为此stl库给出的解决方案是接受删除位置的下一个元素的返回值。(这也是为什么整个模拟实现中只有erase函数具有返回值),并接收返回值。

正确删除偶数方法:

void testvector4()
	{
		//std::vector<int> v;
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		auto it = v.begin();
		//迭代器失效
		/*while (it < v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}
				it++;
		}*/

		while (it < v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				it++;
			}
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

5.3 push_bach()

头插复用insert函数即可。

void push_back(const T& x)
{
	//if (_finish == _endofstroage)
	//{
	//	reserve(capacity() == 0 ? 4 : capacity() * 2);
	//}

	插入数据
	//*_finish = x;
	//_finish++;

	insert(_finish, x);
}

5.4 pop_back()

复用erase,尾删

void pop_back()
{
	erase(--end());
}

六、所有代码

vector增删查改模拟实现gitee链接文章来源地址https://www.toymoban.com/news/detail-755117.html

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

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

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

相关文章

  • C++:stack、queue、priority_queue增删查改模拟实现、deque底层原理

    我们先来看看 stack的相关接口有哪些: 从栈的接口,我们可以知道栈的接口是一种特殊的vector,所以我们完全可以使用vector来模拟实现stack。 因此我们可以将底层容器定义成模板,然后将容器类变量作为成员变量进行封装。在实现satck的各种接口时,通过成员变量来调用底层

    2024年02月03日
    浏览(45)
  • 【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

    list使用文章 析构函数   在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node,用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。       因为list的底层实现

    2024年02月14日
    浏览(50)
  • 【C++】STL——string的模拟实现、常用构造函数、迭代器、运算符重载、扩容函数、增删查改

    string使用文章   这里我们 实现常用的第四个string(const char* s)和析构函数     拷贝构造函数实现:   在堆上使用new为当前对象的成员变量_str分配内存空间,大小为s._capacity + 1字节,即字符串的容量加上一个结束符\\0的空间。   我们使用深拷贝而不是浅拷贝,

    2024年02月15日
    浏览(55)
  • C++_String增删查改模拟实现

    本篇博客仅仅实现存储字符的string。同时由于C++string库设计的不合理,博主仅实现一些最常见的增删查改接口! 接下来给出的接口都是基于以下框架: 博主在这仅仅提供如 无参和带参默认构造 接口: 小tips: C++string标准库中,无参构造并不是空间为0,直接置为空指针。而

    2024年02月04日
    浏览(45)
  • MyBatis注解开发---实现增删查改和动态SQL

    目录 相关导读 1. 环境搭建 (1)创建持久层接口,并在接口方法上定义Sql语句  

    2023年04月18日
    浏览(45)
  • 【C++庖丁解牛】实现string容器的增删查改 | string容器的基本接口使用

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 函数名称 功能说明 push_back 在字符串后尾插字符c append 在字符串后追加一个字符串 operator+= (重点) 在字符

    2024年03月14日
    浏览(69)
  • 认识Mybatis并实现增删查改

    目录 一.Mybatis特性 二.常见持久层技术的比较 三.搭建Mybaits环境 四.使用Mybatis  五.通过Mybatis实现增删改  六.实现数据库的查询操作 定制化SQL:MyBatis允许开发人员编写、优化和管理自定义的SQL语句,可以满足复杂查询和存储过程等高级操作的需求。 避免JDBC代码:MyBatis抽象了

    2024年02月12日
    浏览(42)
  • C++ 模拟实现vector

    目录 一、定义 二、模拟实现 1、无参初始化 2、sizecapacity 3、reserve 4、push_back 5、迭代器 6、empty 7、pop_back 8、operator[ ] 9、resize 10、insert 迭代器失效问题 11、erase 12、带参初始化 13、迭代器初始化 14、析构函数 15、深拷贝 16、赋值运算符重载 完整版代码测试代码 本次参考SGI版

    2024年02月04日
    浏览(43)
  • 【C++】vector模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月13日
    浏览(43)
  • C++模拟实现vector

    目录 1.代码实现 2.注意事项 1.成员变量 2. 不能使用memcpy函数拷贝数据 1.用string类型测试时,要考虑到vs可能把数据存储在数组buffer里面 3.insert函数中指针的失效性 1.加引用,那么就不能传常量,比如v.begin() + 3 2.加引用,就只能传变量了  4.erase成员函数的指针的失效性 这边以

    2024年02月17日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包