模拟实现vector超详解（C++）

发布时间：2024-05-05 15:01

\"模拟实现vector超详解（C++）_第1张图片\"

各位小伙伴们，大家好！我是bug。今天我们来谈谈vector的相关内容：
（代码可能会有一点问题，请各位老铁指正 ）

文章目录

  • 一、vector的概念
  • 二、vector的用法
    • （1）vector对象的创建
    • （2）vector的遍历
    • （3）vector的reserve和resize
    • （4）迭代器失效问题****
  • 三、vector的模拟实现

一、vector的概念

Vector： vector是C++标准模板库中的部分内容。它是动态增长的对象数组，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。

二、vector的用法

vector的常用接口：

construct（构造函数） 用法
vector() 无参构造函数
vector（size_type n, const value_type& val = value_type()） 构造初始化n个val
vector (const vector& x); 拷贝构造
vector (InputIterator first, InputIterator last); 迭代器初始化构造
遍历操作 用法
operator[] 数组
begin 获取第一个数据位置的iterator/const_iterator
end 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin 获取最后一个数据位置的reverse_iterator
rend 获取第一个数据前一个位置的reverse_iterator
操作空间/容量 用法
size 获取数据个数
capacity 获取容量大小
empty 判断是否为空
resize 改变vector的size
reserve 改变vector的capacity
修改操作 用法
push_back 尾插
pop_back 尾删
insert 在position之前插入数据
erase 删除position位置的数据
swap 交换两个vector的数据空间

（1）vector对象的创建

vector创建对象的方式有很多，比如：
使用默认构造函数
使用带参构造函数
使用拷贝构造函数
使用赋值运算符重载
使用迭代器区间进行构造
创建匿名对象

代码⬇️ ⬇️：

	//有参数构造
	vector<int> v1(5, 4);
	//无参数构造
	vector<int> v2;
	//拷贝构造
	vector<int> v3(v1);
	//迭代器区间进行构造
	vector<int> v4(v1.begin(), v1.end());
	//赋值运算符重载
	vector<int> v5 = v1;
	//匿名对象
	vector<int>();

（2）vector的遍历

string有三种遍历的方式：
通过[]的重载像数组一样遍历。
通过迭代器进行遍历。
通过范围for进行的遍历

代码⬇️ ⬇️：

//遍历,和string类似，这里就不详细演示了
	vector<int> v(4, 5);

	//[]重载
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << \" \";
	}
	cout << endl;

	//迭代器
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

	//范围for
	for (auto e : v)
	{
		cout << e << \" \";
	}
	cout << endl;

注意❗️ ❗️

（1）[]的重载有const和非const版本的。
（2）迭代器有const和非const版本的，C98中直接将begin、end进行重载。在C11中为了区别const和非const迭代器，引入了cbegin和cend。（和begin、end的const版本就名字不同）
（3）范围for的本质是迭代器，程序运行过程中，编译器会把范围for替换成迭代器进行操作。同时范围for是通过赋值的方式进行遍历（将数据赋给变量），如果要修改，就要使用引用。

（3）vector的reserve和resize

测试代码⬇️ ⬇️：

vector<int> v(4, 5);
	//打印容量
	cout << v.capacity() << endl;

	v.reserve(3);
	cout << v.capacity() << endl;

	v.reserve(8);
	cout << v.capacity() << endl;
	//只能扩容，和string一样

	v.resize(2);
	//打印容量
	cout << v.capacity() << endl;
	//遍历
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

	v.resize(12, 0);
	//要重新对it赋值，因为扩容之后迭代器begin发生了改变
	//这里的begin是原生指针
	it = v.begin();
	//打印容量
	cout << v.capacity() << endl;

	while (it != v.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

（4）迭代器失效问题****

迭代器失效有两种情况：
1.、会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
2、erase删除数据
解决方法：对it重新赋值。

这里我们来仔细谈谈迭代器失效：
在vector的类中，我们并没有实现find函数，我们使用的是算法里面的查找函数，当我们使用insert进行插入、或者使用erase删除等操作时，都需要找到数据的位置然后进行相应的操作。

但是会有这几种情况发生：

（1）使用insert等接口时，底层空间发生了改变。

从底层的角度我们不难发现，以扩容为例，过程大致分为这么几个步骤：

使用新容量开辟一块新空间
将原有空间的数据拷贝到新空间中
释放_start指向的原有空间
将新空间的指针赋给_start

这个时候我们之前使用的find函数返回的指针仍然指向之前的那片空间(被释放掉了)，即这个指针就是野指针了。
在vector中，为了解决这个问题，采取了返回iterator的方式。即通过insert返回新的指针，指向之前查找的那个数字。

（2）使用erase时，我们要进行连续删除。

举个栗子：删除vector对象中所存储的奇数：

这个代码有什么问题吗？⬇️ ⬇️（vs上编不过）

#include
#include

using std::cin;
using std::cout;
using std::endl;
using std::vector;
int main()
{
	vector<int> v(4, 5);
	auto it = std::find(v.begin(), v.end(), 5);
	while (it != v.end())
	{
		v.erase(it);
		it++;
	}
	cout << endl;

	return 0;
}

如图分析：
\"模拟实现vector超详解（C++）_第2张图片\"
在上图这情况下，结果看起来是没有什么问题，但是如果是下面这种呢？
\"模拟实现vector超详解（C++）_第3张图片\"

即每次删除一个奇数数据后，会跳过一个数据同时判断下一个数据是否是奇数。当发生极端情况，即最后一个数据是奇数,被删除后，it发生了自增操作，就会直接越过end，然后不断的循环越界。（迭代器就失效了）
所以为了避免这种情况，我们同样采用了返回iterator的形式，通过返回一个修正值来避免迭代器失效。

代码⬇️ ⬇️：

#include
#include

using std::cin;
using std::cout;
using std::endl;
using std::vector;
int main()
{
	vector<int> v(4, 5);
	auto it = std::find(v.begin(), v.end(), 5);
	while (it != v.end())
	{
		//通过接收erase返回后的修正值防止迭代器失效
		it = v.erase(it);
		it++;
	}
	cout << endl;

	return 0;
}

总结：解决迭代器失效的方法就是重新对it进行赋值操作。

三、vector的模拟实现

这里我们来实现一个简易的vector⬇️ ⬇️：

	typedef _Tp* iterator;
	typedef const _Tp* const_iterator;
//构造函数
vector()
vector(size_t n, const _Tp& val = _Tp())
vector(const vector& v1)
vector(InputIterator start, InputIterator finish)

void swap(vector& v)
vector& operator=(const vector& v1)

//遍历操作
_Tp& operator[](size_t i)
const _Tp& operator[](size_t i)const
iterator begin() const
iterator end() const
const_iterator cbegin()const
const_iterator cend()const

//扩容操作
void reserve(size_t n)
void resize(size_t n, _Tp val = _Tp())

//增删操作
void push_back(const _Tp& t)
void pop_back(size_t n)
iterator insert(iterator pos, const _Tp& val)
iterator insert(iterator pos, size_t n, const _Tp& val)
iterator erase(iterator pos)
iterator erase(iterator start, iterator finish)

//其他
void clear()
bool empty()

完整代码⬇️ ⬇️：

#include
#include
#include

using std::cin;
using std::cout;
using std::endl;
using std::istream;
using std::ostream;

namespace lz
{
	template<class _Tp>
	class vector
	{
	public:
		//迭代器
		typedef _Tp* iterator;
		typedef const _Tp* const_iterator;

		iterator begin() const { return _start; }
		iterator end() const { return _finish; }
		const_iterator cbegin()const { return _start; }
		const_iterator cend()const { return _finish; }

		typedef _Tp* InputIterator;

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

		// 构造函数
		vector(InputIterator start, InputIterator finish)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (start != finish)
			{
				push_back(*start);
				start++;
			}
		}

		vector(size_t n, const _Tp& val = _Tp())
			:_start(new _Tp[n])
			, _finish(_start + n)
			, _end_of_storage(_finish)
		{
			auto it = begin();
			while (it != _finish)
			{
				*it = val;
				it++;
			}
		}

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

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

		// 拷贝构造函数
		vector(const vector& v1)
		{
			reserve(v1.capacity());
			for (size_t i = 0; i < v1.size(); i++)
			{
				*(_start + i) = *(v1._start + i);
			}
			_finish = _start + v1.size();
		}

		// 赋值运算符重载
		vector& operator=(const vector& v1)
		{
			vector<_Tp> tmp(v1);
			swap(tmp);
			return *this;
		}

		// []重载
		_Tp& operator[](size_t i)
		{
			return _start[i];
		}

		const _Tp& operator[](size_t i)const
		{
			return _start[i];
		}

		// 交换函数swap
		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);

		}

		// 扩容 reserve
		void reserve(size_t n)
		{
			size_t sz = size();
			if (n > capacity())
			{
				_Tp* tmp = new _Tp[n];
				if (!empty())//判断是否为空
				{
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
				}

				delete[]_start;
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

		// 扩容+初始化 resize
		void resize(size_t n, _Tp val = _Tp())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else if (n > size())
			{
				if (n > capacity())
				{
					reserve(n);
				}
				for (size_t i = size(); i < n; i++)
				{
					*(_start + i) = val;
				}
				_finish = _start + n;
			}

		}

		// 尾插 push_back单个数据
		void push_back(const _Tp& t)
		{
			if (_end_of_storage == _finish)
			{
				size_t new_capacity = (capacity() == 0 ? 4 : capacity() * 2);

				reserve(new_capacity);
			}

			*_finish = t;
			_finish++;
		}

		// 插入 insert单个数据
		iterator insert(iterator pos, const _Tp& val)
		{
			assert(pos >= _start && pos <= _finish);
			size_t sz = _finish - pos;
			if (_finish == _end_of_storage)
			{
				size_t new_capacity = (capacity() == 0 ? 4 : capacity() * 2);
				reserve(new_capacity);
				pos = _finish - sz;
			}

			for (iterator it = _finish; it >= pos; it--)
			{
				*it = *(it - 1);
			}

			_finish++;
			*pos = val;
			return pos + 1;
		}
		//插入insert多个数据
		iterator insert(iterator pos, size_t n, const _Tp& val)
		{
			assert(pos >= _start && pos <= _finish);
			size_t sz = _finish - pos;
			if (_end_of_storage <= pos + n)
			{
				size_t new_capacity = n + _end_of_storage - pos;
				reserve(new_capacity);
				pos = _finish - sz;
			}

			iterator it = pos;
			for (iterator i = pos; i < n + pos; i++)
			{
				it = insert(it, val);
			}
			return pos + n;
		}

		// 尾删 pop_back单个数据
		void pop_back(size_t n)
		{
			if (!empty())
			{
				if (n > size())
				{
					n = size();
				}
				_finish -= n;
			}
		}

		// 删除 erase(单个数据)
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos;
			while (it != _finish)
			{
				it++;
				*(it - 1) = *it;
			}
			//防止为空时，_finish跑到_start前面了
			if (!empty())
				_finish--;
			return pos - 1;
		}

		//删除一个迭代器区间数据
		iterator erase(iterator start, iterator finish)
		{
			assert(start >= _start && _finish >= finish);
			size_t sz = finish - start;
			size_t it = sz;
			while (it)
			{
				start = erase(start);
				it--;
			}
			return finish - sz;
		}

		//清理
		void clear()
		{
			_finish = _start;
		}

		// 判空 empty
		bool empty()
		{
			return _start == _finish;
		}

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

void Test1()//构造函数
{
	lz::vector<int> v1(4, 5);
	lz::vector<int> v2;
	lz::vector<int> v3(v1);
	lz::vector<int> v4 = v3;
	lz::vector<int> v5(v4.begin(), v4.end());
	//lz::vector();

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

void Test2()//erase
{
	lz::vector<int> v(3, 5);
	auto it1 = std::find(v.begin(), v.end(), 5);
	while (it1 != v.end())
	{
		it1 = v.erase(it1);
		it1++;
	}
	auto it2 = v.begin();
	while (it2 != v.end())
	{
		cout << *it2 << \" \";
		it2++;
	}
	cout << endl;

}

void Test3()//push_back+insert
{
	lz::vector<int> v1;
	lz::vector<int> v2(3, 1);

	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	v1.push_back(7);
	//打印容量
	cout << \"capacity = \" << v1.capacity() << endl;

	auto it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

	auto tmp1 = std::find(v1.begin(), v1.end(), 4);
	tmp1 = v1.insert(tmp1, 1);

	//打印容量
	cout << \"capacity = \"<< v1.capacity() << endl;
	v1.insert(tmp1, 2);

	it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

}

void Test4()//reserve+resize
{
	lz::vector<int> v1(3, 5);
	v1.reserve(3);
	cout << \"capacity = \" << v1.capacity() << endl;

	v1.reserve(8);
	cout << \"capacity = \" << v1.capacity() << endl;

	v1.resize(4);//默认初始值
	cout << \"capacity = \" << v1.capacity() << endl;//容量不变
	auto it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;

	v1.resize(20, 9);
	cout << \"capacity = \" << v1.capacity() << endl;

	it = v1.begin();//对it进行重新赋值
	while (it != v1.end())
	{
		cout << *it << \" \";
		it++;
	}
	cout << endl;
}

void Test5()//clear+empty
{
	lz::vector<int> v;
	//判空
	cout << v.empty() << endl;

	//插入数据
	v.push_back(4);
	v.push_back(4);
	v.push_back(4);
	v.push_back(4);
	for (auto e : v)
	{
		cout << e << \" \";
	}

	cout << endl;

	v.clear();
	//容量不变
	cout << \"capacity = \" << v.capacity() << endl;
	//清除数据后，不打印
	for (auto e : v)
	{
		cout << e << \" \";
	}

	cout << endl;
}

int main()
{
	Test5();
	return 0;
}

今天的内容到这里就结束了，希望各位小伙伴能够从中有所收获，我们下期再见！
\"模拟实现vector超详解（C++）_第4张图片\"

\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0

相关推荐

如何选择合适的自动化测试工具？

关于“你以为你是谁？”

Java foreach语句的用法

Java入门篇之Java与javac命令的爱恨情仇

A Comprehensive Survey on Graph Neural Networks论文阅读笔记

JavaScript实现带粒子效果的进度条

SQL注入&PostgreSQL&SQLserver&实战

Java数据结构与算法（堆排序）

C#：特性

4.2 APP_UI ----Appium工具介绍以及元素定位

hive on spark 安装配置 详解

6. Nginx虚拟主机

【人脸识别】基于garbor特征提取和SVM的人脸识别matlab仿真

【服务器数据恢复】IBM某型号存储RAID5数据恢复案例

SpringBoot详解自定义Stater的应用

如何7周成为数据分析师

汽车CAN总线数据帧分类及格式详解

【C语言进阶14——文件操作（1）】

基于Android Studio经典蓝牙APP---继上一次的完善版

[windows]安装gcc/g++

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号