【C++】vector 模拟笔记

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

成员变量和迭代器

  下面有vector 存储示意图:vector 是一个左闭又开的空间,_finish 不能存储有效数据。vector 的 iteratorT 类型的指针,不要认为 iterator 就是指针,而且后面还有 list,map,set 等各种容器的迭代器,它们都不是原生指针。在这里我们 vector 写成模板,同时不能与库里面的空间产生冲突,我们需要自己定一个命名空间,具体代码看最下面的整体带代码。

【C++】vector 模拟笔记,C++,c++,后端,stl,开发语言

reserve()函数易错点

  扩容是异地扩容,需要开一块新的空间,然后把数据拷贝过去,再将原来的空间释放掉。这里注意必须开始首位指针的相对位置,异地扩容tmp赋值给_start,此时 _start和_finish 并不指向同一块空间,而 size() 却是由 _start和_finish 计算而来,由此出错。

错误代码: _finish=_start+size();

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t len = size();
		T* tmp = new T[n];
		if (_start)
		{
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + len;
		_end_of_storage = _start + n;
	}
}

【C++】vector 模拟笔记,C++,c++,后端,stl,开发语言

  假若对象是自定义类型那么还要完成深拷贝,深拷贝不能用 memcpy 拷贝,比如对象是 stringmemcpy 是值拷贝只会把*string对象的指针地址拷贝给另外一个对象,导致两个string对象的_str指针指向同一块数组空间,而析构两次。因此我们需要调用string类自己的赋值运算符重载函数进行赋值

错误代码: memcpy(_start, v._start, sizeof(T)*v.size() );

【C++】vector 模拟笔记,C++,c++,后端,stl,开发语言

迭代器区间初始化易错点

  当 T 类型为 int,运行这句代码 vector v1(10, 1); 就会报下面这个错误,说明它并没有调用上面这个函数。因为第一个形参为 size_t ,第二个实例化为 int,而实参两个都为int,且第二个用迭代器区间初始化函数,两个形参相同,此时更匹配第二个函数。调用第二个函数后对 int 解引用而报错
【C++】vector 模拟笔记,C++,c++,后端,stl,开发语言

错误代码: vector(size_t n, const T& val = T() );

vector(int n, const T& val = T())
{
	//参数用int而不用size_t避免当两个参数都为int时,与下面的用迭代器初始化函数冲突
	resize(n, val);
}
//用迭代器区间初始化
template<class in_T>
vector(in_T first, in_T last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

迭代器失效

  由上面的扩容逻辑可以知道,插入数据有时候需要扩容,而扩容是异地扩容,原来空间已经被释放了,那么指向原来空间的迭代器自然失效了。因此我们要更新迭代器,让 insert()和erase() 函数返回新的迭代器,新的迭代器和原来迭代器到 _start 的相对距离相等。虽然有时候插入迭代器并没有失效,但是考虑不同平台实现的封装和代码的可移植性,默认它就是会失效,vs库里面实现的也是默认失效,继续用直接报错文章来源地址https://www.toymoban.com/news/detail-588738.html

整体代码

#pragma once
#include <assert.h>
namespace Me
{
	template<class T>
	class vector
	{
	public:
		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;
		}

		//容量和size
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}
		size_t size() const
		{
			return _finish - _start;
		}

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

		//无参构造
		vector()
		{}
		//深拷贝
		//不用memcpy拷贝,因为对象可能是自定义类型,比如<string>,memcpy是值拷贝,
		//会导致两个string对象的_str指针指向同一块数组空间
		//而析构两次,因此我们需要调用赋值运算符重载函数进行拷贝
		
		//vector(const vector<T>& v)
		//{
		//	_start = new T[v.capacity()];
		//	for (size_t i = 0; i < v.size(); i++)
		//	{
		//		//调用赋值运算符重载
		//		_start[i] = v._start[i];
		//	}
		//	_finish = _start + v.size();
		//	_end_of_storage = _start + v.capacity();
		//}

		//现代写法
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				//会自动更新_finish指针
				push_back(e);
			}
		}
		//赋值运算符重载
		vector<T>& operator=(vector<T> v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
			return *this;
		}
		
		vector(int n, const T& val = T())
		{
			//参数用int而不用size_t避免当两个参数都为int时,与下面的用迭代器初始化函数冲突
			resize(n, val);
		}
		//用迭代器区间初始化
		template<class in_T>
		vector(in_T first, in_T last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//析构
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;
			}
		}

		//扩容和调整
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				//记录原来相对位置,后面_start和_finish并不指向同一块空间
				size_t len = size();
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size(); i++)
					{
						//这里和上面一样,必须深拷贝
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + len;
				_end_of_storage = _start + n;
			}
		}
		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++;
				}
			}
		}

		//打印
		void print()
		{
			for (auto e : *this)
			{
				cout << e << " ";
			}
			cout << endl;
		}

		//插入 迭代器使用一次后可能会失效,
		//因此要返回新的迭代器,旧的默认失效处理
		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish == _end_of_storage)
			{
				//扩容需要记录相对位置,以免迭代器失效
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;//更新迭代器
			}
			T* end = _finish;
			_finish++;
			while (end >= pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = x;
			return pos;
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void push_back(const T& x)
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;
			_finish++;
		}

		//删除 
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator end = pos;
			_finish--;//先-- 因为_finish不存储有效数据
			while (end < _finish)
			{
				*end = *(end + 1);
				end++;
			}
			return pos;
		}
		void pop_back()
		{
			--_finish;
		}
		void pop_front()
		{
			erase(begin());
		}

	private:
		T* _start = nullptr;
		T* _finish = nullptr;
		T* _end_of_storage = nullptr;
	};

}

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

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

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

相关文章

  • C++ —— STL容器【vector】模拟实现

    本章代码gitee仓库:vector模拟实现、vector源码 看源码发现 vector 是类模板定义的,成员是采用迭代器进行管理 当涉及到容器类时,通常有一些关键函数,如构造函数、析构函数和拷贝构造函数,它们负责初始化容器对象、销毁对象和进行对象的拷贝等 这里注意拷贝构造要实现

    2024年02月16日
    浏览(44)
  • 【c++】:STL中vector的模拟使用及模拟实现

        文章目录 前言 一.使用库中vector常用接口 二.vector的模拟实现 总结   上一篇我们讲解了STL中的string的使用和模拟实现,这次我们就来讲解STL中的vector,vector相对于string来说模拟实现会难一些,难点在于迭代器失效问题和深浅拷贝问题。 首先介绍一下vector: 1. vector是表示

    2024年01月21日
    浏览(42)
  • C++ stl容器vector的底层模拟实现

    目录 前言:   1.成员变量,容量与大小 2.构造函数 无参构造: 带参的使用值进行构造:  使用迭代器区间进行构造: 3.交换 4.拷贝构造 5.赋值重载 6.迭代器 7.扩容 reserve: resize: 8.插入与删除 insert: erase: insert迭代器失效问题: erase迭代器失效问题: 9.头插头删 10.[]重载

    2024年04月15日
    浏览(40)
  • 【C++】STL之vector功能及模拟实现

    目录 前沿 一、vector的使用  1、vector 构造函数的声明  2、vector 迭代器的使用  3、vector 空间增长问题  4、vector 的增删查改 二、vector的模拟实现  1、vector 的成员变量  2、迭代器  3、容量相关(resize, reserve)  4、数据访问相关  5、插入删除   5.1 任意位置插入   5.2 任意位置

    2024年02月16日
    浏览(38)
  • 【C++】STL——vector 深度剖析 及 模拟实现

    这篇文章我们来学习一下STL里面的vector,它属于STL中容器的一员,我们先来学习一下它的使用,然后,我们也会对vector进行一个深度的剖析和模拟实现。 1.1 vector的介绍 vector的文档介绍 vector 是表示大小可以更改的数组的序列容器: 其实大家可以认为 vector就是我们之前数据结

    2024年02月05日
    浏览(44)
  • C++ STL学习之【vector的模拟实现】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 The power of imagination makes us infinite. 想象力的力量使我们无限。 vector 是 STL 中的容器之一,其使用方法类似于数据结构中的 顺序表 ,得益于范型编程和 C++ 特性的加持, vector 更强大、更全能;在模拟实现

    2023年04月08日
    浏览(64)
  • 【C++初阶】STL详解(四)vector的模拟实现

    本专栏内容为:C++学习专栏,分为初阶和进阶两部分。 通过本专栏的深入学习,你可以了解并掌握C++。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注:为了防止与标准库当中的vector产生命名冲突

    2024年02月05日
    浏览(41)
  • 【C++】透过STL源码深度剖析及模拟实现vector

    鉴于读者的响应,打算将文章拆分一下,方便观看,基本接口可看 深入浅出STL之vector类 以下我所介绍的都是基于【SGI】版本的STL,对源码有兴趣的同学可以去看看 侯捷老师的《STL源码剖析》 然后呢我们就去调出【vector】的一些核心源码,这里我们主要关注的就是这个使用原

    2024年02月14日
    浏览(40)
  • 【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 和string的学习不同 vector即要掌握它的用法 更要会自己去实现一个vector 本章重点: 熟悉STL库中vector的接口函数 自己实现一个简易vector类 本

    2024年02月11日
    浏览(35)
  • [C++] STL_vector使用与常用接口的模拟实现

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

    2024年02月11日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包