当前位置： 首页 > article >正文

【C++】——vector深度剖析模拟实现

article 2024/11/17 10:52:48

低头赶路，敬事如仪

目录

1、模拟vector

1.1底层结构

1.2构造析构

1.3尾插扩容

1.4迭代器

1.5增删查改

1.6模拟中的注意事项

2、vector模拟补充

2.1迭代器区间构造问题

2.2memcpy深浅拷贝问题

2.3动态二维数组的模拟及遍历

1、模拟vector

想要模拟实现自己的vector，得知其所以然！

分析一下STL源码里的vector底层成员变量

可以看到是三个迭代器类型成员变量，迭代器类型是什么呢？

经过typedef的底层指针，而T类型是模版类的参数。

大致框架如图：

1.1底层结构

根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。

namespace xc
{
	//设置成模板 兼容各种参数 但是不能分离编译否则链接错误
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;

	private:
		iterator _start = nullptr;//指向容器开始
		iterator _finish = nullptr;//指向有效数据下一个位置
		iterator _end_of_storage = nullptr;//指向空间容量的下一个位置
	};
}

写出三个迭代器（指针）后，我们可以接着实现构造函数：需要初始化三个迭代器，所以我们给予初始值nullptr。然后进行开辟空间。

1.2构造析构

实现常用的构造析构以及赋值重载

/*	vector()
	{}*/
	//C++11 强制生成默认构造
	vector() = default;

	//优先匹配构造函数，防止非法的间接寻址问题
	vector(size_t n, const T& val = T())
	{
		reserve(n);
		for (size_t i=0; i < n; i++)
		{
			push_back(val);
		}
	}
	vector(int n, const T& val = T())
	{
		reserve(n);
		for (int i=0; i < n; i++)
		{
			push_back(val);
		}
	}
	vector(long long n, const T&val = T())
	{
		reserve(n);
		for (long long i=0; i < n; i++)
		{
			push_back(val);
		}
	}

	//类模板的成员函数还可以继续是函数模板
	template<class InputIterator>  //写成模板是为了兼容所有容器
	vector(InputIterator first, InputIterator last)
	{
		while(first != last)
		{
			push_back(*first);
			++first;
		}
	}

	// v1(v)
	vector(const vector<T>& v)
	{
		reserve(v.size());
		for (auto& e : v)
		{
			push_back(e);
		}
	}

	void clear()
	{
		_finish = _start;
	}

	 v1=v
	//vector<T>& operator=(const vector<T>&v)
	//{
	//	if (this != &v)
	//	{
	//		clear();
	//		reserve(v.size());
	//		for (auto& e : v)
	//		{
	//			push_back(e);
	//		}
	//	}
	//	return *this;
	//}

	void swap(vector<T>&v)
	{
		std::swap(_start, v._start);
		std::swap(_finish, v._finish);
		std::swap(_end_of_storage, v._end_of_storage);
	}
	//现代写法 V1=v
	vector<T>& operator=(const vector<T> v)
	{
		swap(v);
		return *this;
	}

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

1.3尾插扩容

想要实现尾插的操作，根据之前的经验，可以知道需要复用一些常用的简单接口（size() capacity() reserve() 等）

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

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

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

//void reserve(size_t n)
//{
//	if (n > capacity())
//	{
//		T* tmp = new T[n];
//		memcpy(tmp, _start, sizeof(T));
//		delete[]_start;

//		_start = tmp;
//		_finish = _start + size();//这是错误的  _start 已经是扩容后的 start了 而size调用的是 finish - start
//									//解决方法 可以先更新 finish 或者记录一下 size的值
//		_end_of_storage = _start + n;
//	}
//}

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();
		T* tmp = new T[n];
		memcpy(tmp, _start, size()*sizeof(T));

		delete[] _start;

		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

void reseize(size_t n, T val = T())//内置类型也具有的构造析构等函数行为 但是并没有概念
{
	if (n < size())
	{
		_finih = _start + n;
	}
	else
	{
		reserve(n);
		while (_finsh < _start+n)
		{
			*_finish++ = val;
		}
	}
}

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

注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

1.4迭代器

所需要实现的迭代器其实很简单，对指针 typedef 即可

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; }

实现了简单的迭代器，我们可以测试一下 迭代器遍历和范围for遍历

void test_vector1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;

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

这里我们为了后续方便封装一个打印函数

template<class T>
void print_vector(const vector<T>& v)
{
	vector<T>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;
}

可是这居然报错

为什么呢？没有实例化的类模板里面取东西，编译器是分不清 const_iterator 是静态成员变量还是类型的，在前面加一个 typename 显示告诉编译器是类型即可

template<class T>
void print_vector(const vector<T>& v)
{
	typename vector<T>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;
}

1.5增删查改

void insert(iterator pos, const T& x)
{
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	iterator end = _finish;
	while (pos < end)
	{
		*end = *(end - 1);
		--end;
	}
	*pos = x;
	++_finish;
}

看起来没什么问题，但是存在着迭代器失效的风险

pos仍指向原来的空间！记录相对位置，修正一下pos即可

void insert(iterator pos, const T& x)
{
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;//记录相对位置
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish;
	while (pos < end)
	{
		*end = *(end - 1);
		--end;
	}
	*pos = x;
	++_finish;
}

值得注意的是STL里的 insert有返回值！

这是为什么呢？还是防止迭代器失效的一种措施。

void test_vector2()
{
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	print_vector(v);

/*	v.insert(v.begin() + 1, 10);
	print_vector(v);*/
	int x;
	cin >> x;// x==2
	auto pos = find(v.begin(), v.end(), x);//没找到返回 last 左闭右开区间
	if (pos != v.end())
	{
		v.insert(pos, 40);//pos 可以理解为下标位置 也可以理解为原来位置数据前面插入一个数据
		print_vector(v);
		(*pos) *= 10;//期望将x乘以10 但是是插入的40*10  并没有指向原来的数据
						//归为迭代器失效一类
	}
	print_vector(v);

}

如果这里还发生了扩容呢？？就是将push的5给删掉

这是什么鬼？我们不是已经修正了pos的位置吗？显然这里的p已经失效了！形参是无法改变实参的，我们修正了pos，但是影响不了p

传const 引用过去影响实参。但不是常量引用的话 ，下面代码会报错！

因为函数调用返回的参数是临时变量，且临时变量具有常性。

而事实上加了const引用里面的pos就无法修正了！我们的思路错了，STL的操作是加一个返回值 （返回的是新插入数据的下标）

iterator insert(iterator  pos, const T& x)
{
	assert(pos <= _finish && pos >= _start);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;//记录相对位置
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish;
	while (pos < end)
	{
		*end = *(end - 1);
		--end;
	}
	*pos = x;
	++_finish;
	return pos;
}

所以 insert后不能再访问find 的 p 想要访问得更新！

增删查改：

iterator insert(iterator  pos, const T& x)
{
	assert(pos <= _finish && pos >= _start);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;//记录相对位置
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator end = _finish;
	while (pos < end)
	{
		*end = *(end - 1);
		--end;
	}
	*pos = x;
	++_finish;
	return pos;
}

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

size_t find(T val = T())
{
	for (auto it = _start; it < _finish; it++)
	{
		if (*it == val)
		{
			return it - _start;
		}
	}
	return -1;
}

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

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

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

1.6模拟中的注意事项

  • 规定：类模板在没有实例化时，迭代器无法读取！编译器不能区分这里const_iterator是类型还是静态成员变量。要想解决：第一可以在前面加上typename用来证明这里是类型；第二用auto，让编译器判断为类型
  • 内置类型是没有构造函数的概念，但为了兼容模板（T val = T( ) ），可以被视为具有默认构造函数的行为
void reseize(size_t n, T val = T())//内置类型具有的构造析构等函数行为，并没有对应概念
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish < _start+n)
		{
			*_finish++ = val;
		}
	}
}
  •  c++11中有强制生成默认构造的操作，即使类中已有其他构造函数，也能强制生成。eg：vector( ) = default

  • 类里面可以用类名替代类型（特殊化），类外面规定：类名不能代表类型
//类里面可以用类名替代类型（特殊化）
//vector & operator=(vector v)
vector<T>& operator= (vector<T> v)
{
    swap(v);
    return *this;
}
  • 类模板的成员函数，还可继续是函数模板
//类模板的成员函数还可以继续是函数模板
template<class InputIterator>  //写成模板是为了兼容所有容器
vector(InputIterator first, InputIterator last)
{
	while(first != last)
	{
		push_back(*first);
		++first;
	}
}

2、vector模拟补充

2.1迭代器区间构造问题

//C++11 强制生成默认构造
vector() = default;


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

//类模板的成员函数还可以继续是函数模板
template<class InputIterator>  //写成模板是为了兼容所有容器
vector(InputIterator first, InputIterator last)
{
	while(first != last)
	{
		push_back(*first);
		++first;
	}
}

这个是对迭代器区间进行的构造函数，思路很简单，把迭代器区间的数据依次尾插就可以了（这里之所以另外使用一个新的模版，而不是使用vector类的模版，是为了兼容其他容器类型）。这样就可以通过一个现有的类型来构造容器。
但是出乎意料的是出现了一个问题： C2100 非法的间接寻址 （编译层面的问题） 。非法的间接寻址的造成原因有很多：

  1. 空指针引用：当一个指针没有被初始化或者为NULL时，对它进行间接寻址操作会导致非法访问。
  2. 野指针引用：当一个指针超出了它所指向的内存范围，或者已经被释放但仍然被引用时，进行间接寻址操作也会导致非法访问。
  3. 类型不匹配：如果试图将指针转换为不兼容的类型进行间接寻址，也会导致非法访问。

为什么报错在迭代器构造呢？因为编译器会寻找最合适的函数，但是这里与我们期望所违背！！

为了解决编译器选择的问题，可以多枚举几个构造函数：

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

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

这样可以做到优先匹配vector(int n,T val = T());，我们的问题也就解决了。 

2.2memcpy深浅拷贝问题

我们测试一下自定义类型的vector（这里以string为例）：

void vector_test6() {
	vector<string> v1;
	v1.push_back("11111");
	v1.push_back("22222");
	v1.push_back("33333");
	v1.push_back("44444");
    //再次插入扩容
	v1.push_back("55555");

	print_vector(v1);
}

程序崩溃了

分析：
<1> memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
<2> 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃

解决方法：

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();
		T* tmp = new T[n];
		//memcpy(tmp, _start, size()*sizeof(T));//浅拷贝
		for (size_t i = 0; i < old_size; i++)
		{
			tmp[i] = _start[i];//自定义类型的话 也是会调用自定义类型的赋值重载
		}
		delete[] _start;

		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

2.3动态二维数组的模拟及遍历

结构框架图：

//二维数组
vector<int>v(3, 1);
vector<vector<int>>vv(5, v);

vv[2][1] = 2;
//与上述等价  vv.operator[](2).operator[](1) = 2;
for (size_t i = 0; i < vv.size(); i++)
{
	for (size_t j = 0; j < vv[i].size(); j++)
	{
		cout << vv[i][j] << ' ';
	}
	cout << endl;
}
cout << endl;

for (auto it = vv.begin(); it != vv.end(); it++)
{
	for (auto jt = (*it).begin(); jt != (*it).end(); jt++)
	{
		cout << *jt << ' ';
	}
	cout << endl;
}
cout << endl;

auto it1 = vv.begin();
/*auto it2 = (*it1).begin();*/
while (it1 != vv.end())
{
	auto it2 = (*it1).begin();//更新it2 指针在堆上分配，所以可以看见内存不是连续分配的
	while (it2 != (*it1).end())
	{
		cout << *it2 << ' ';
		it2++;
	}
	cout << endl;
	it1++;
}
cout << endl;

for (auto row : vv)
{
	for (auto column : row)
	{
		cout << column << ' ';
	}
	cout << endl;
}
cout << endl;

应用：杨辉三角

// 以杨慧三角的前n行为例：假设n为5
void test2vector(size_t n)
{
	// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
	vector<vector<int>> vv(n);
	// 将二维数组每一行中的vecotr<int>中的元素全部设置为1
	for (size_t i = 0; i < n; ++i)
		vv[i].resize(i + 1, 1);
	// 给杨慧三角出第一列和对角线的所有元素赋值
	for (int i = 2; i < n; ++i)
	{
			for (int j = 1; j < i; ++j)
			{
				vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
			}
	}
}

构造一个vv动态二维数组，vv中总共有n个元素，每个元素 都是vector类型的，每行没有包含任何元素，n为5时如下所示：


http://www.kler.cn/a/321041.html

相关文章：

  • 深入探索 Kubernetes 安全容器：Kata Containers 与 gVisor
  • 第三百二十三节 Java线程教程 - Java同步器
  • MongoDB自定义顺序排序
  • __VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined
  • 华为云前台展示公网访问需要购买EIP，EIP流量走向
  • 一文了解Android中的AudioFlinger
  • Go语言中的互斥锁与竞争问题
  • 【Kubernetes】常见面试题汇总（二十九）
  • 《深度学习》—— ResNet 残差神经网络
  • 【OSS安全最佳实践】降低因账号密码泄露带来的未授权访问风险
  • 【小程序】微信小程序课程 -2 快速上手
  • 论文不会写怎么办？推荐这5款AI论文工具帮你一键搞定！
  • 【隐私计算篇】利用多方安全计算MPC实现VGG16人脸识别隐私推理
  • C++学习笔记（34）
  • 【MySQL】字符集与Collation
  • MySQL 预处理语句：强大的数据库工具
  • en造数据结构与算法C# 用Unity实现简单的群组行为算法 之 分散
  • 运算符两边的数据类型
  • [数据库] Redis学习笔记（一）：介绍、安装、基本数据结构、常见命令
  • 在Windows系统上安装的 zstd C++ 库
  • ADB 安装教程：如何在 Windows、macOS 和 Linux 上安装 Android Debug Bridge
  • Spring 事务与 MySQL 事务：深度解析与实战指南
  • 使用docker创建zabbix服务器
  • 2024华为杯E题成品文章已出！
  • 使用Crawler实例进行网页内容抓取
  • 制造企业为何需要PLM系统？PLM系统解决方案对制造业重要性分析