1. Toy模板网首页
  2. > Toy博客

【C++】手撕 Vector类

10月前 作者：手法king 分类：Toy博客 阅读(31) 违法举报

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

目录

1，vector类框架

2，vector ()

3，pinrt()

4，vector(int n, const T& value = T())

5，vector(const vector& v)

6，vector(InputIterator first, InputIterator last)

7，~vector()

8，iterator begin()

9，iterator end()

10，size() const

11，capacity() const

12，reserve(size_t n)

13，resize(size_t n, const T& value = T())

14，push_back(const T& x)

15，pop_back()

16，insert(iterator pos, const T& x)

17，erase(iterator pos)

18，empty()

19，operator[](size_t pos)

20，operator= (vector v)

21，总结

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

上面我们认识了 vector 类，有了一个大概的理解，下面我们来实现一下 vector 类的框架，来更好的熟悉 vector 类，也让我们对其有着更深的理解； 

1，vector类框架

我们先写一个 vector 类的基本框架；

namespace newVector
{
	template<class T>
	class vector
	{
	public:

		// Vector的迭代器是一个原生指针
		typedef T* iterator;

	private:

		iterator _start = nullptr; // 指向数据块的开始

		iterator _finish = nullptr; // 指向有效数据的尾

		iterator _endOfStorage = nullptr; // 指向存储容量的尾

	};
}

vector 类里面是可以包含很多类型的，所以我们用模板来表示，以应用各种场景，vector 类里面多用迭代器的方式来表示，vector 的迭代器其实就是一个原生指针；

_start 指向数据块的开始，_finish 指向有效数据的尾，_endOfStorage 指向存储容量的尾；

2，vector ()

vector()
{}

因为我们在构造框架的时候已经给了缺省值，所以可以不用在写了；

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

可以看到这里已经初始化了；

3，pinrt()

就是打印输出嘛，方便后续测试；

		void pinrt()
		{
			for (size_t i = 0; i < size(); i++)
			{
				cout << _start[i] << " ";
			}
		}

4，vector(int n, const T& value = T())

我们都会用，初始化 n 个 value；

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

有人不知道缺省值给个 T（）是什么意思，首先 T（）是匿名对象，默认就是编译器对内置类型的初始化； 

测试一下：

int main()
{
	newVector::vector<int> v1(5, 8);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

现在我们不给初始化的值试试：

int main()
{
	newVector::vector<int> v1(5);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

 默认初始化为0；

5，vector(const vector<T>& v)

拷贝构造（深拷贝）

		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];
			}
			_finish = _start + v.size();
		}

为什么不用 memcpy 呢，上面那个明显要便捷一点，因为 memcpy 是浅拷贝，如果遇到 T是string类的时候就会因为析构函数多次析构同一块空间而报错，而下面这个挨个赋值是深拷贝，他们两个 _start 不会指向同一块空间；

int main()
{
	newVector::vector<int> v1(5,8);
	newVector::vector<int> v2(v1);
	v2.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

可以看到也是 OK 的；

6，vector(InputIterator first, InputIterator last)

这个要配合模板使用，这代表一个范围，只要是同类型的都可以；

		template<class InputIterator>

		vector(InputIterator first, InputIterator last)
		{
			reserve(last - first + 1);
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

先扩容嘛，像这种区间都是左闭右开的，然后再挨个尾插即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

只要是同类型的都可以，像这种的数组都行；

7，~vector()

析构函数

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

delete 后面一定要带 [ ] ，因为析构的是一段连续的空间，就看做是数组即可，然后再将各个迭代器置空即可；

int main()
{
	newVector::vector<int> v1(5,8);
	v1.~vector();
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

8，iterator begin()

指向第一个元素的迭代器

		iterator begin()
		{
			return _start;
		}

直接返回 _start 即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << *v1.begin();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

9，iterator end()

指向最后一个元素下一个元素的迭代器

		iterator end()
		{
			return _finish;
		}

直接返回 _finish 即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << *v1.end();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

直接随机数了；

换个思路，试一下：

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << *(v1.end()-1);
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

我们找他前一个迭代器，果然是最后一个数；

10，size() const

返回有效数据个数

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

直接迭代器相减即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << v1.size();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

11，capacity() const

返回容量大小

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

直接迭代器相减即可，差值就是容量大小；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << v1.capacity();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

12，reserve(size_t n)

扩容

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old = size();
				if (_start)
				{
					//memcpy(tmp, _start, old * sizeof(T));
					for (size_t i = 0; i < old; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + old;
				_endOfStorage = _start + n;
			}
		}

当要扩容时才用的着，先判断，然后开辟一段需要的空间，之后就是拷贝赋值了，这里我们还是没有用 memcpy 因为是浅拷贝，然后再释放原空间，再将迭代器重新赋值即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << v1.capacity() << endl;

	v1.reserve(20);
	cout << v1.capacity() << endl;
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

一目了然；

13，resize(size_t n, const T& value = T())

更改有效数据个数，不够则填充，可以指定填充数据；

		void resize(size_t n, const T& value = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}
				while (_finish!=_start+n)
				{
					push_back(value);
				}
			}
		}

当缩减数据时直接把 _finish 往前移即可，当扩容时先扩容，然后进行填充；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr,arr+5);
	cout << v1.size() << endl;

	v1.resize(10);
	cout << v1.size() << endl;

	v1.resize(15, 6);
	cout << v1.size() << endl;
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

可以看到，当我们不指定填充时默认填充0；

14，push_back(const T& x)

尾插

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

首先要检查是否需要扩容，然后赋值，将 _finish 往后移一位即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	
	v1.push_back(6);
	v1.push_back(7);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

 插入十分成功；

15，pop_back()

尾删

		void pop_back()
		{
			assert(size() > 0);
			_finish--;
		}

像这种数组类型的，直接对其迭代器动手就行，直接 _finish 往前移一位即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	
	v1.pop_back();
	v1.pop_back();
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

删除非常顺利；

16，insert(iterator pos, const T& x)

指定位置插入

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			size_t old = pos - _start;
			if (_finish == _endOfStorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			pos = _start + old;
			memcpy(pos + 1, pos, (_finish - pos) * sizeof(T));
			*pos = x;
			_finish++;
			return pos;
		}

这里会面临一个迭代器失效的问题，当扩容后，原本的 pos 还是指向旧空间就失效了，所以我们要更新 pos ；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	
	auto pos = find(v1.begin(), v1.end(), 1);
	v1.insert(pos, 9);

	pos= find(v1.begin(), v1.end(), 5);
	v1.insert(pos, 9);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

完美插入；

17，erase(iterator pos)

擦除指定位置

		iterator erase(iterator pos)
		{
			assert(pos >= 0 && pos <= _finish);
			memcpy(pos, pos + 1, sizeof(T)*(_finish - pos));
			_finish--;
			return pos;
		}

先断言判断，然后直接往前移一位覆盖即可，再更新一下 _finish ;

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);

	auto pos = find(v1.begin(), v1.end(), 1);
	v1.erase(pos);

	pos = find(v1.begin(), v1.end(), 5);
	v1.erase(pos);
	v1.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

也是成功擦除了；

18，empty()

判空

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

当为空时返回真，反之亦然；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	cout << v1.empty() << endl;

	newVector::vector<int> v2;
	cout << v2.empty();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

19，operator[](size_t pos)

返回下标对应的值；

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

直接像数组一样取值返回即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	
	cout << v1[0] << " " << v1[4];
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

写法也是跟数组一样简单；

20，operator= (vector<T> v)

赋值，深拷贝

		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> v)
		{
			swap(v);
			return *this;
		}

直接一手交换即可；

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	newVector::vector<int> v1(arr, arr + 5);
	
	newVector::vector<int> v2 = v1;
	v2.pinrt();
	return 0;
}

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法

 

21，总结

我们就先搞一个大概的，其中还有很多分支，比如我们写的是擦除某个数据，其实也可以擦除某个范围，这些就靠大家去摸索，查阅文档了；

vector类的实现就到这里了；

加油！

【C++】手撕 Vector类,c++,算法,开发语言,数据结构,排序算法文章来源地址https://www.toymoban.com/news/detail-775655.html

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之栈详解（C语言手撕）

    数据结构之栈详解（C语言手撕）

    🎉个人名片： 🐼作者简介：一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉：GOTXX 🐼个人WeChat：ILXOXVJE 🐼本文由GOTXX原创，首发CSDN🎉🎉🎉 🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句：如果没有特别幸运，那就请特

    2024年03月19日
    浏览(48)
  • 数据结构之单链表详解（C语言手撕）

    数据结构之单链表详解（C语言手撕）

    ​ 🎉文章简介： 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 从图片中可以看出，链表的每个节点都是一个结构体，该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针； 在逻辑上

    2024年03月10日
    浏览(44)
  • 【数据结构与算法】手撕链表OJ题

    【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 思路一 ：一种比较普遍的方式，边遍历边找不同。我们可以通过定义两个指针，一个指向头节点，一个置为NULL。当遇到值为相同的时候，直接跳过去。指向下一位

    2024年02月10日
    浏览(43)
  • 手撕哈希表（HashTable）——C++高阶数据结构详解

    手撕哈希表（HashTable）——C++高阶数据结构详解

    小编是双非本科大一菜鸟不赘述，欢迎米娜桑来指点江山哦（QQ：1319365055） 🎉🎉非科班转码社区诚邀您入驻🎉🎉 小伙伴们，打码路上一路向北，彼岸之前皆是疾苦 一个人的单打独斗不如一群人的砥砺前行 这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！ 社

    2023年04月08日
    浏览(37)
  • [ 数据结构 -- 手撕排序算法第二篇 ] 冒泡排序

    [ 数据结构 -- 手撕排序算法第二篇 ] 冒泡排序

    手撕排序算法系列之：冒泡排序。 从本篇文章开始，我会介绍并分析常见的几种排序，大致包括 插入排序 ， 冒泡排序 ，希尔排序，选择排序，堆排序，快速排序，归并排序等。 大家可以点击此链接阅读其他排序算法：排序算法_大合集（data-structure_Sort） 本篇主要来手撕冒

    2024年02月11日
    浏览(59)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢，每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号，而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(66)
  • 【数据结构与算法篇】手撕排序算法之插入排序与希尔排序

    【数据结构与算法篇】手撕排序算法之插入排序与希尔排序

    ​👻内容专栏：《数据结构与算法篇》 🐨本文概括： 讲述排序的概念、直接插入排序、希尔排序、插入排序和希尔排序的区别。 🐼本文作者：花 碟 🐸发布时间：2023.6.13 排序 ：所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的

    2024年02月09日
    浏览(51)
  • 手撕数据结构与算法——树(三指针描述一棵树）

    手撕数据结构与算法——树(三指针描述一棵树）

    📖作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋阶段， 因为最近参加新星计划算法赛道(白佬)，所以加快了脚步，果然急迫感会增加动力 ——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的 📖作者主页：king南星 📖

    2024年01月17日
    浏览(56)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分：[begin, mid-1]，[mid, end] 3.2.2 正确划分：[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(49)
  • 追梦之旅【数据结构篇】——C语言手撕八大经典排序

    追梦之旅【数据结构篇】——C语言手撕八大经典排序

        😎博客昵称：博客小梦 😊最喜欢的座右铭：全神贯注的上吧！！！ 😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！ 😘博主小留言：哈喽！ 😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不

    2024年02月17日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包