【C++】手撕vector类(从会用到理解)

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

一、标准库中的vector类

1.1 vector类介绍

1.2 vector的常用接口

1.2.1 常用的构造函数

1.2.2 容量操作接口

(1)size

(2)capacity

(3)empty

(4)resize

(5)reserve

1.2.3 访问和遍历

(1)operator[]

(2)迭代器

(3)at

(4)back

(5)front

1.2.4 vector的增删查改

(1)push_back

(2)pop_back

(3)find

(4)insert

(5)erase

(6)swap

(7)assign

(8)clear

1.3 迭代器失效

二、模拟实现vector类


一、标准库中的vector类

1.1 vector类介绍

vector用于表示大小可以变化的数组。 

与数组类似,vector也采用连续的存储空间来存储元素,也就是说我们可以和数组一样使用下标对vector进行随机访问。但是相对于不能改变空间大小的数组而言,vector的优势在于它的大小可以动态改变。

前面我们学习了string类,对于同样使用顺序表结构的vector类而言,二者的很多地方是相通的,例如vector也可以进行尾插和尾删等操作。

vector是一个模板类,在使用时我们需要给出元素的类型。

vector类中通常有三个迭代器类型的成员变量,分别指向vector的开头、最后一个有效元素的后一位和vector的结尾

iterator _start;
iterator _finish;
iterator _end_of_storage;

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

所以,vector的有效元素个数就等于_finish - _start,容量等于_end_of_storage - _start

我们通过vector类中的接口就能对这三个迭代器进行操作,从而完成增删查改等功能

在使用vector类时,必须包含头文件<vector>和using namespace std;

1.2 vector的常用接口

1.2.1 常用的构造函数

vector();

vector类的默认构造函数,构造一个没有元素的空容器

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

vector(size_type n, const value_type& val = value_type());

构造一个vector类对象并用n个val初始化

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

vector(const vector& x);

vector类的拷贝构造函数

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

Template<class InputIterator>

vector(InputIterator first, InputIterator last);

使用迭代器进行初始化构造

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

1.2.2 容量操作接口

(1)size

size_type size() const;

获取有效元素个数

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(2)capacity

size_type capacity() const;

获取容量大小

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(3)empty

bool empty() const;

判断容器是否为空

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(4)resize

void resize(size_type n, value_type val = value_type());

将有效元素的个数修改为n,并且如果n大于原来的size,多出来的地方用val填充

如果没有给出val,就用0填充

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(5)reserve

void reserve(size_type n);

改变容量大小

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

1.2.3 访问和遍历

(1)operator[]

reference operator[](size_type n);

const_reference operator[](size_type n) const;

用下标访问vector

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(2)迭代器

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

迭代器,用于获取容器中第一个元素的位置和最后一个元素的下一个位置

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

reverse_iterator rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

反向迭代器,rbegin获取容器中最后一个元素的位置,rend获取容器中的第一个元素的前一个位置

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

需要注意,反向迭代器rit也要用++而不是--

(3)at

reference at(size_type n);

const_reference at(size_type n) const;

返回容器中位置n处的元素的引用

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(4)back

reference back();

const_reference back() const;

返回容器中最后一个元素的引用

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(5)front

reference front();

const_reference front() const;

返回容器中第一个元素的引用

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

1.2.4 vector的增删查改

(1)push_back

void push_back(const value_type& val);

从容器尾部插入一个元素

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(2)pop_back

void pop_back();

从容器尾部删除一个元素

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(3)find

template <class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last, const T& val);

在两个迭代器区间寻找val并返回其所在处的迭代器

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

需要注意的是,该函数并非vector的成员函数,是标准库中的函数,多个容器共用该find函数

(4)insert

iterator insert(iterator position, const value_type& val);

void insert(iterator position, size_type n, const value_type& val);

在position位置插入元素

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

对于这类可能会修改容量的函数,容易导致迭代器失效的问题,后面我们会详细讲

所以insert函数不仅需要完成插入元素的工作,有时还需要返回新的迭代器

(5)erase

iterator erase(iterator position);

iterator erase(iterator first, iterator last);

删除position位置的元素或者 [first,last) 区间的所有元素

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(6)swap

void swap(vector& x);

交换两个vector的数据空间

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(7)assign

template <class InputIterator>

void assign(InputIterator first, InputIterator last);

void assign(size_type n, const value_type& val);

为vector指定新内容,替换其当前内容并修改size

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

(8)clear

void clear();

从vector中删除所有元素,不改变容量大小

例如:

【C++】手撕vector类(从会用到理解),C++,c++,开发语言

 

1.3 迭代器失效

迭代器的底层实际上就是一个指针或指针的封装,例如vector的迭代器就是一个原生态指针

当迭代器底层的指针指向的空间被销毁时,如果继续在程序中使用该迭代器,就会造成程序崩溃,这就是迭代器失效

对于vector,会导致迭代器失效的操作有:

  • 可能造成空间改变的操作,如resize、reserve、insert、assign、push_back等

以上函数在使用时都可能会导致vector扩容,在扩容时原空间会被释放,迭代器就会指向一块被释放的空间

  • 删除操作

假设有迭代器pos,使用pos删除pos对应位置的元素后,该迭代器对应的元素发生改变,属于迭代器失效

如果pos刚好对应最后一个元素,删除后迭代器pos就超出了有效元素范围,可能导致非法访问,属于迭代器失效

迭代器失效后,如果我们需要继续使用迭代器,给迭代器重新赋值即可


二、模拟实现vector类

知道了vector类中各种常用接口的用法后,我们就可以开始自己手撕一个自己的vector类了

为了不和标准库中的vector类冲突,我们可以开一个自己的命名空间

#include <iostream>
#include <assert.h>
#include <string>
using namespace std;

namespace Eristic
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		vector()
			//此处包括下面的初始化列表都可以换用缺省值
			:_start(nullptr)
			,_finish(nullptr)
			,_end_of_storage(nullptr)
		{}

		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(v.capacity());
			for (size_t i = 0; i < v.size(); ++i)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
		}

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector<T>& operator=(vector<T>& v)
		{
			if (this != &v)
			{
				reserve(v.capacity());
				for (size_t i = 0; i < v.size(); ++i)
				{
					_start[i] = v._start[i];
				}
				_finish = _start + v.size();
				return *this;
			}
		}

		iterator begin()
		{
			return _start;
		}

		const_iterator cbegin() const
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator cend() const
		{
			return _finish;
		}

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

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

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

		void resize(size_t n, T val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			if (n > size())
			{
				if (n > capacity())
					reserve(n);
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

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

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

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

		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t range = pos - _start; //在扩容前需要记录相对位置
				//在插入数据时发生了扩容,迭代器的位置会发生改变,叫做迭代器失效
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + range; //将pos也更新到新的位置
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			iterator start = pos + 1;
			while (start < _finish)
			{
				*(start - 1) = *start;
				++start;
			}
			--_finish;
			return pos;
		}

		T& front()
		{
			return *_start;
		}

		const T& front() const
		{
			return *_start;
		}

		T& back()
		{
			return *(_finish - 1);
		}

		const T& back() const
		{
			return *(_finish - 1);
		}

		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()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

如有错误,欢迎在评论区指出

完.文章来源地址https://www.toymoban.com/news/detail-843398.html

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

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

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

相关文章

  • 【手撕Spring源码】深度理解SpringMVC【上】

    既然我们讨论SpringMVC那么就必然绕不开一个东西叫做DispatcherServlet。 DispatcherServlet是SpringMVC的核心Servlet,也叫做前端控制器。它的主要作用是调度请求并将请求分发给相应的处理器。 我们要注意: DispatcherServlet由Servlet容器创建,并且它的生命周期也是Servlet那套体系由Servle

    2024年02月07日
    浏览(42)
  • 【C++】常用到的“using namespace std;”到底是什么?

    在初学C++时,在包含完头文件之后,我们常常会看到这么一句话:using namespace std; 比如: 首先需要声明的是:它不是什么“固定动作”,不是必须这么写的。 namespace,顾名思义,命名空间。 而using namespace ,则是展开命名空间。 std是C++标准库的命名空间。 因此,using namesp

    2024年02月14日
    浏览(58)
  • iOS 小组件开发 && iOS 小组件开发用到的技术

    iOS 小组件开发 iOS小组件开发是指在iOS设备的主屏幕上添加自定义的小组件,用于显示特定的信息或提供简化的交互。iOS 14及更高版本引入了小组件功能,使用户能够在主屏幕上自定义并快速访问相关内容。 以下是iOS小组件开发的基本步骤: 设计小组件:首先,你需要设计小

    2024年02月11日
    浏览(56)
  • 【初中生讲机器学习】14. 手撕公式,一篇带你理解逻辑回归!

    创建时间:2024-03-03 最后编辑时间:2024-03-10 作者:Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏,很高兴遇见你~ 我是 Geeker_LStar,一名初三学生,热爱计算机和数学,我们一起加油~! ⭐(●’◡’●) ⭐ 那就让我们开始吧! 嘿嘿,好几篇前,好像是在线性回归那篇

    2024年04月10日
    浏览(49)
  • 程序员如何把ChatGPT用到开发中

    问:ChatGPT是程序员的好帮手?还是要干掉程序员? ChatGPT最近火到不行,在短短几个月时间里,OpenAI打造的ChatGPT就从一个弱小无助的AI聊天程序发展成几乎无所不知、无所不能的强大AI大脑。如果大家留心过ChatGPT的新闻,就会发现它似乎每天都能在科技板块的头条里抢到几个

    2024年02月01日
    浏览(50)
  • 单片机开发用到的intrins.h文件

    intrins.h文件内容如下: 常用的是上面8个函数,分为三类:循环移位、空操作指令、测试清零指令 1. 循环移位:_cror_/_iror_/_lror_/_crol_/_irol_/_lrol_ _cror_/_crol_:字符循环右移/字符循环左移; -iror_/_irol_:整数循环右移/整数循环左移; _lror_/_lrol_:长整数循环右移/长整数循环左移

    2023年04月26日
    浏览(47)
  • 带你深入理解“栈”(c语言 c++和stl Stack三个版本的模拟实现)

    目录 一.栈的概念及结构 二.栈的实现(c语言版) 2.1静态增长的栈 2.2动态增长的栈 2.3动态栈的模拟实现    1.栈的初始化   2.入栈  3.出栈 4.获取栈顶元素 5.获取栈中有效数据个数 6.检查栈是否为空 7.栈的销毁 三.C++ 版本模拟实现栈  1.C++版本的源代码 四.c语言版本的源代码

    2024年02月08日
    浏览(47)
  • 图形编辑器开发:一些会用到的简单几何算法

    大家好,我是前端西瓜哥。 开发图形编辑器,你会经常要解决一些算法问题。本文盘点一些我开发图形编辑器时遇到的简单几何算法问题。 判断两个矩形是否发生碰撞(或者说相交),即两个矩形有重合的区域。 常见使用场景: 使用选择工具 框选 图形(框选策略除了相交

    2024年02月16日
    浏览(54)
  • 数据结构---手撕图解单链表---phead的多种传参方式对比和辅助理解

    前面我们知道了顺序表,当顺序表的容量到达上限后就需要申请新的空间,而申请新空间就会遇到一些问题 1.当利用realloc函数进行申请新空间时,会涉及到开辟新空间–拷贝原有数据–释放原空间这三个步骤,而这三个步骤会有不小的损耗 2.增容一般是2倍的增长,势必会有

    2024年02月17日
    浏览(54)
  • 数据结构:手撕图解单链表---phead的多种传参方式对比和辅助理解

    前面我们知道了顺序表,当顺序表的容量到达上限后就需要申请新的空间,而申请新空间就会遇到一些问题 1.当利用realloc函数进行申请新空间时,会涉及到开辟新空间–拷贝原有数据–释放原空间这三个步骤,而这三个步骤会有不小的损耗 2.增容一般是2倍的增长,势必会有

    2024年02月15日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包