【C++STL】“vector“容器的模拟实现

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

🎉博客主页：小智_x0___0x_

🎉欢迎关注：👍点赞🙌收藏✍️留言

🎉系列专栏：C++初阶

🎉代码仓库：小智的代码仓库

模拟实现

成员变量

	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _endofstorage = nullptr;

这里的iterator是typedef T* iterator;定义来的，T是模板参数。

_start是指向开始的指针变量。
_finish是指向最后一个元素的下一位的指针变量。
_endofstorage是指向当前最大容量处的指针变量。

template <class T>
class vector 
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
private:
	iterator _start = nullptr;
	iterator _finish = nullptr;
	iterator _endofstorage = nullptr;
};

【C++STL】“vector“容器的模拟实现,C++初阶,c++,stl,容器,vector

构造函数

这里我们模拟实现三种构造函数：

无参构造函数

vector()
	;_start(nullptr)
	,_finish(nullptr)
	,_endofstorage(nullptr)
	{}

直接初始化三个指针变量。

初始化n个val的构造函数

vector(size_t n, const T& val = T())
	; _start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	//开空间
	reserve(n);
	//初始化val
	for (size_t i = 0; i < capacity() ; i++)
	{
		_start[i] = val;
	}
	//也可以直接复用resize()
	//resize(n, val);
}

//构造函数重载防止构造时冲突
vector(int n, const T& val = T())
	; _start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	//开空间
	reserve(n);
	//初始化val
	for (size_t i = 0; i < capacity(); i++)
	{
		_start[i] = val;
	}
	//也可以直接复用resize()
	//resize(n, val);
}

迭代器区间构造函数


template<class InputIterator>//模板参数
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);//依次取出解引用并尾插
		++first;
	}
}

拷贝构造

vector(const vector<T>& v)
{
	//new一个capacity大小的空间
	_start = new T[v.capacity()];
	//逐个将值拷贝过去
	for (size_t i = 0; i < v.size(); i++)
	{
		_start[i] = v._start[i];
	}
	//重新写入_finish和_endofstorage的值
	_finish = _start + size();
	_endofstorage = _start + v.capacity();
}

析构函数

~vector()
{
	//如果_start为空的话就不做任何操作
	if (_start)
	{
		//释放_start申请的空间
		delete[] _start;
		//将三个成员变量全部置空
		_start = _finish = _endofstorage = nullptr;
	}
}

begin（）

typedef T* iterator;
typedef const T* const_iterator;
//普通类型迭代器
iterator begin()
{
	return _start;
}
//const 迭代器
const_iterator begin() const
{
	return _start;
}

end（）

typedef T* iterator;
typedef const T* const_iterator;
//普通迭代器
iterator end()
{
	return _finish;
}
//const 迭代器
const_iterator end() const
{
	return _finish;
}

swap（）

void swap(vevtor<T>& v)
{
	//逐个交换每个成员变量
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstorage, v._endofstorage);
}

reserve()

void reserve(size_t n)
{
	//判断如果n大于capacity的话就扩容否则不做任何操作
	if (n > capacity())
	{
		//先保存size后面delete之后size()就失效了
		size_t sz = size();
		//new一个n大小的tmp变量
		iterator tmp = new T[n];
		if (_start)//_start不为空进行数据的拷贝
		{
			//for循环逐个拷贝数据
			for (size_t i = 0; i < sz; i++)
			{
				tmp[i] = _start[i];
			}
			//释放之前的数据
			delete[] _start;
		}
		//重新更新三个成员变量
		_start = tmp;
		_finish = tmp + sz;
		_endofstorage = _start + n;
	}
}

这里需要注意的是交换数据的时候不能使用memcpy(tmp, _start, sizeof(T) * sz);
以这段代码为例：

vector<string> v;
v.push_back("11111");
v.push_back("22222");
v.push_back("33333");
v.push_back("44444");

我们来画图理解使用memcpy拷贝的情况>
【C++STL】“vector“容器的模拟实现,C++初阶,c++,stl,容器,vector

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

我们再来画图理解一下逐个拷贝的情况>
【C++STL】“vector“容器的模拟实现,C++初阶,c++,stl,容器,vector
【结论】： 如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

resize()

void resize(size_t n, const T& val = T())
{
	//判断是否需要扩容
	if (n < size())
	{
		_finish = _start + n;//n<size()的时候更新_finish的值
	}
	else
	{
		//复用reserve()来调整容量
		reserve(n);
		while (_finish != _start + n)
		{
			//刚刚调整出的空间逐个写入val
			*_finish = val;
			++_finish;
		}
	}
}

capacity()

size_t capacity() const
{
	return _endofstorage - _start;//_endofstorage - _start就是它的最大容量
}

size()

size_t size() const
{
	return _finish - _start;//_finish - _start就是它的元素个数
}

重载[]运算符

普通[]重载:

T& operator[](size_t pos)
{
	//断言检查pos的位置是否合法
	assert(pos < size());
	return _start[pos];//直接return返回
}

const []重载:

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

重载=赋值运算符

vector<T>& operator =(vector<T> v)//形参接收实参会调用拷贝构造，构造出v
{
	//交换*this和v
	swap(v);
	return *this;//返回*this
}

v的作用域在这个函数内，出了函数就会自动析构，我们把*this和v的内容进行了交换，完了出了作用域v也会帮我们析构掉交换之后v的空间。

insert()

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start && pos <= _finish);//断言检查pos位置的有效性
	if (_finish == _endofstorage)//判断容量是否已经满了
	{
		size_t len = pos - _start;//记录pos前面位置的元素个数
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		// 解决pos迭代器失效问题
		pos = _start + len;
	}
	iterator end = _finish - 1;//记录最后一个元素的位置
	while (end >= pos)//逐个往后挪数据
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;//给pos位置赋值x
	++_finish;//对应的_finish也要加1
	return pos;//返回pos位置
}

erase()

iterator erase(iterator pos)
{	
	assert(pos >= _start && pos < _finish);//断言检查pos位置的合法性
	iterator it = pos + 1;//保存pos下一个元素的地址
	while (it != _finish)
	{
		//逐个向前挪动数据
		*(it - 1) = *it;
		++it;
	}
	//对应的再将_dinish的值减1
	--_finish;
	return pos;//返回要删除的下一个位置即为新的pos
}

push_back（）

void push_back(const T& x)
{
	//传统写法
	/*if (_finish == _endofstorage)//判断是否需要扩容
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	//给_finish赋值x
	*_finish = x;
	//将_finish加1
	++_finish;*/
	
	//复用insert()给end位置插入x
	insert(end(), x);
}

pop_back（）

void pop_back()
{
	//复用erase()先是end()位置减1到最后一个元素的位置
	erase(--end());
}

完整代码

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

namespace CSDNYYDS {
	template <class T>
	class vector 
	{
	public:
		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;
		}

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

		vector()
		{}

		vector(size_t n, const T& val = T())
			; _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			//开空间
			reserve(n);
			//初始化val
			for (size_t i = 0; i < capacity() ; i++)
			{
				_start[i] = val;
			}
			//也可以直接复用resize()
			//resize(n, val);
		}

		vector(int n, const T& val = T())
			; _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			//开空间
			reserve(n);
			//初始化val
			for (size_t i = 0; i < capacity(); i++)
			{
				_start[i] = val;
			}
			//也可以直接复用resize()
			//resize(n, val);
		}
		//迭代器区间
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			for (size_t i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + size();
			_endofstorage = _start + v.capacity();
		}
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstorage = nullptr;
			}
		}
		void swap(vevtor<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;
		}
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				iterator tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = tmp + sz;
				_endofstorage = _start + n;
			}
		}

		void resize(size_t n,const T& val=T())
		{
			if (n < size())
			{
				_finsh = _start + n;
			}
			else
			{
				reserve(n);

				while (_finish!=_start+n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;

				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);

				// 解决pos迭代器失效问题
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);

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

			--_finish;

			return pos;
		}
		void pop_back()
		{
			erase(--end());
		}

		

		T& operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}


	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
};

动态二维数组的理解

【C++STL】“vector“容器的模拟实现,C++初阶,c++,stl,容器,vector

🍀小结🍀

今天我们认识了C++STL“vector“容器的模拟实现相信大家看完有一定的收获。
种一棵树的最好时间是十年前，其次是现在！ 把握好当下，合理利用时间努力奋斗，相信大家一定会实现自己的目标！加油！创作不易，辛苦各位小伙伴们动动小手，三连一波💕💕~~~，本文中也有不足之处，欢迎各位随时私信点评指正！
本节课的代码已上传gitee仓库文章来源地址https://www.toymoban.com/news/detail-575783.html

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