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

C++ —— vector 的模拟实现

article 2024/9/22 22:51:19

目录

前言

1. vector深度剖析

 2. 基础框架

3. 核心接口

3.1 reserve

3.2 push_back 和 pop_back

3.3 print

 3.4 insert

3.5 erase

3.6 resize

4. 拷贝构造

4.1 构造与析构

4.2 拷贝构造 

4.3 赋值重载

4.4 迭代器区间

5. 使用memcpy拷贝问题

前言

接:C++ —— 关于vector-CSDN博客icon-default.png?t=O83Ahttps://blog.csdn.net/hedhjd/article/details/142334349?spm=1001.2014.3001.5501

1. vector深度剖析

 

 _start ：相当于begin，指向开始的位置
_finish ：相当于size，指向最后一个数据的位置
_end_of_storage ：相当于_capacity

 2. 基础框架

//因为vector是用模板写的，所以不能进行声明和定义分离，否则会出现链接错误
#pragma once
#include<assert.h>

 // _start ：相当于begin，指向开始的位置
//_finish ：相当于size，指向最后一个数据的下一个位置
//_end_of_storage ：相当于_capacity

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

		//迭代器
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		//const迭代器
		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}


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

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


		//可读可写
		T& operator[](size_t i)
		{
			assert(i < size());

			return _start[i];
		}

		//只读
		const T& operator[](size_t i) const
		{
			assert(i < size());

			return _start[i];
		}

		//判断是否为空
		bool empty()
		{
			return _start == _finish;
		}


	private:
		iterator _start = nullptr;//给个缺省值
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};

3. 核心接口

3.1 reserve

//修改之后
//扩容
void reserve(size_t n)
{
	if (n > capacity())
	{
		//提前将旧size赋给新size
		size_t old_size = size();
 
		//开辟新空间，创建临时变量
		//new出来的空间是初始化好的，所以可以直接用
		T* tmp = new T[n];

		//memcpy(tmp, _start, old_size * sizeof(T));
		/*如果T是string或者vector类型，就需要进行深拷贝
		 需要赋值进行拷贝数据，否则使用浅拷贝会导致内存泄漏
		*/
		for (size_t i = 0; i < old_size; i++)
		{
			//赋值就是string/vector的赋值，也就是深拷贝
			tmp[i] = _start[i];
		}
		//释放旧空间
		delete[] _start;
		//再把三个私有变量指向新空间
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

3.2 push_back 和 pop_back

/*T有可能是一个int,也有可能是一个string，还可能是一个vector，
所以需要传&，传&不改变需要加上一个const*/
//尾插
void push_back(const T& x)
{
	//先判断需不需要扩容
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}
	//如果不需要就直接插入到_finish的位置
	*_finish = x;
	++_finish;
}

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

3.3 print

如果给出的代码编译器不知道该代码是类型还是变量，所以导致识别不出来，那么可以在前面加上 typename 或者改为 auto 自动推导

//给print_vector套一层模板，让它被谁都可以使用
template<class T>
void print_vector(const vector<T>& v)
{
	//如果typename在没有实例化的类模板里面取东西，
	// 那么编译器不能区分这里const_iterator是类型还是静态成员变量
	//typename vector<T>::const_iterator it = v.begin();

	//那么使用auto可以自动推导，由v.begin()推导
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

将print彻底转换成模板，使所有类型都可以使用，不管是string，vector等等 

//将print彻底转换成模板，使所有类型都可以使用，不管是string，vector等等
template<class Container>
void print_container(const Container& v)
{
	/*auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;*/

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

 3.4 insert

insert在扩容后原来的pos位置就会失效，也就是迭代器失效，就相当于成为了野指针，解决方法是将扩容之前的位置记录下来在扩容后更新pos的位置

//在指定位置插入数据
void insert(iterator pos, const T& x)
{
    assert(pos >= _start);
	assert(pos <= _finish);

	// 扩容
	if (_finish == _end_of_storage)
	{
		/*为了防止迭代器失效的情况，先创建一个临时变量len
		记录扩容之前pos - _start的位置*/
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		//然后再更新pos的位置
		pos = _start + len;
	}

	//将最后一个数据的位置给临时变量end
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;

	++_finish;

	return pos;
}

3.5 erase

erase之后也会出现迭代器失效，所以需要先记录pos原来的位置然后再更新pos

//删除指定位置的数据
void erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator it = pos + 1;
	while (it != end())
	{
		*(it - 1) = *it;
		++it;
	}

	--_finish;
}

3.6 resize

用于改变vector的有效长度，也可以用来初始化指定长度的指定数据

三种情况：

1. 当n < size()时，删除多余的元素，直接缩容

2. 当size() < n < capacity()时，直接插入数据

3. 当capacity() < n时，先扩容再插入数据

//用于改变vector的有效长度
//也可以开辟n个空间，使用val去初始化
void resize(size_t n, T val = T())
{
	//n < size，删除数据
	if (n < size())
	{
		_finish = _start + n;
	}
	else//>=size
	{
		//扩容
		reserve(n);
		while (_finish < _start + n)
		{
			//插入数据val
			*_finish = val;
			++_finish;
		}
	}
}

4. 拷贝构造

4.1 构造与析构


	//默认构造
    vector()
	{}

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



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

4.2 拷贝构造 


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

4.3 赋值重载

//赋值重载的传统写法
//clear清除数据但是不释放空间
void clear()
{
	_finish = _start;
}

// v1 = v3
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 = v3
vector<T>& operator=(vector<T> v)
{
	swap(v);

	return *this;
}

4.4 迭代器区间

1. 类模版里的成员函数还能继续是函数模版

2. 在迭代器区间构造的函数时可以使用函数模版，这样可以使用任意容器的迭代器初始化，例如链表

//迭代器区间
// 类模板的成员函数，还可以继续是函数模版
//加上一个模板那么迭代器就可以是任意类型的迭代器
//需要推导
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

//可以直接使用size_t类型  使用n个val初始化
vector(size_t n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

//可以直接使用int类型  使用n个val初始化
vector(int n, const T& val = T())
{
	reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

5. 使用memcpy拷贝问题

memcpy拷贝问题的问题其实就是浅拷贝的原因

浅拷贝就是两个指针指向同一块空间，如果一个指针对该空间进行释放或者其他操作就会影响另一个指针导致内存泄漏等问题

所以最好使用深拷贝让两指针指向不同的空间然后使其数据保持一致

错误代码 


		//扩容
		//错误代码
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				//提前将旧size赋给新size
				size_t old_size = size();

				//开辟新空间，创建临时变量
				//new出来的空间是初始化好的，所以可以直接用
				T* tmp = new T[n];

				//将旧空间里的数据拷贝给新空间
				//将 _start指向的size() * sizeof(T)空间里的数据拷贝到临时变量tmp里去
				memcpy(tmp, _start, size() * sizeof(T));

				//释放旧空间
				delete[] _start;
				//再把三个私有变量指向新空间
				_start = tmp;
				_finish = tmp + old_size;
				_end_of_storage = tmp + n;
			}
		}

修改之后

//修改之后
//扩容
void reserve(size_t n)
{
	if (n > capacity())
	{
		//提前将旧size赋给新size
		size_t old_size = size();

		//开辟新空间，创建临时变量
		//new出来的空间是初始化好的，所以可以直接用
		T* tmp = new T[n];

		//memcpy(tmp, _start, old_size * sizeof(T));
		/*如果T是string或者vector类型，就需要进行深拷贝
		 否则使用浅拷贝会导致内存泄漏
		*/
		for (size_t i = 0; i < old_size; i++)
		{
			//赋值就是string/vector的赋值，也就是深拷贝
			tmp[i] = _start[i];
		}
		//释放旧空间
		delete[] _start;
		//再把三个私有变量指向新空间
		_start = tmp;
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}
}

感谢观看~


http://www.kler.cn/news/315266.html

相关文章：

  • 【计算机网络】运输层协议解析
  • Flutter - Win32程序是如何执行main函数
  • jmeter得到的文档数据处理
  • 后端接收数组，集合类数据
  • 数据结构之算法复杂度
  • 基于BiGRU+Attention实现风力涡轮机发电量多变量时序预测(PyTorch版)
  • 软考中级软件设计师——数据结构与算法基础学习笔记
  • 【图灵完备 Turing Complete】游戏经验攻略分享 Part.5 编程
  • 【若依RuoYi-Vue | 项目实战】帝可得后台管理系统（二）
  • Linux自主学习篇
  • oracle中NUMBER(1,0)的字段如何映射到c#中
  • 【设计模式-适配】
  • SSC377/D, 5M30 64/128MB, 1Tops1. 支持双摄，甚至三摄；2. 夜视全彩；3. 省内存、省带宽；4. 算力较大，适合新的算法模型；
  • 图像处理与分析
  • Spring的任务调度
  • 怎么在路由器上使用tcpdump抓包
  • Redisson 分布式锁的使用详解
  • Vue3中shallowRef和ref区别
  • 确保在AWS上的资源安全：构建坚不可摧的云安全防线
  • C++ prime plus-2-编程练习
  • 解决 Torch not compiled with CUDA enabled 问题 | MiniCPM3-4B 【应用开发笔记】
  • Android 短信验证码自动填充
  • Unity 设计模式 之 创建型模式 -【单例模式】【原型模式】 【建造者模式】
  • 【力扣】2376. 统计特殊整数
  • Linux：虚拟文件系统/proc和self进程
  • 某招标公告公示搜索引擎爬虫逆向
  • git配置SSH
  • 第二届Apache Flink极客挑战赛冠军比赛攻略_SkyPeaceLL队
  • 安卓开发，插件化换肤思路
  • 【Java】接口interface【主线学习笔记】