绵阳梓潼网站制作公司

【C++】STL---vector的模拟实现(超级详细，万字详解)-创新互联

文章目录
  • 前言
  • vector的成员属性
  • 构造函数
  • size函数
  • cacpcity函数
  • begin和end函数
  • reserve函数
  • insert函数
  • push_back函数
  • []操作符重载
  • 析构函数
  • 拷贝构造函数
  • 赋值操作符重载
  • erase函数
  • pop_back
  • 反向迭代器
    • 反向迭代器模板
    • 反向迭代器的构造函数
    • ++运算符重载
    • - -运算符重载
    • *引用操作符重载
    • ！=操作符重载
    • ==操作符重载
    • rbegin函数
    • rend函数
    • ->重载
  • 总结

专注于为中小企业提供网站设计、成都网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业阜阳免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了近1000家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
前言

vector 是一个顺序容器，简单来说就是一个可以扩容的数组。它的数据在内存中是连续存储的。这也就意味着它支持随机访问(下标访问)，而这篇文章将会带着大家模拟实现一个vector的容器。

vector的成员属性

vector是一个顺序容器，那么我们需要给它分配空间。那么我们可以用三个迭代器来指向，_start迭代器指向第一个位置，_finish指向有效数据的下一个位置，而_endofstorage指向开辟空间大小的最后一个位置。

代码:

templateclass vector
{public:
	//普通迭代器
	typedef T* iterator;
	//const迭代器
	typedef const T* const_iterator;
private:
	iterator _start;
	iterator _finish;
	iterator _endofstorage;
	
};
构造函数

接下来我们就要给vector初始化，这里用2种初始化方式，一种是普通初始化。而一种是迭代器区间初始化。
普通初始化：什么也不干，迭代器初始化成空指针。
迭代器区间初始化：把迭代器区间的所有值一一加到当前的vector对象种。

普通初始化代码：

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

迭代器区间初始化：

//迭代器区间初始化
	templatevector(InputIterator first, InputIterator last)
		:_start(nullptr)
		,_finish(nullptr)
		,_endofstorage(nullptr)
	{while (first != last)
		{	//把迭代器数据依次插入当前对象
			push_back(*first);//尾部插入数据的函数，在下面实现
			++first;
		}
	}
size函数

size函数返回vector的长度，也就是已经存放的数据个数，我们直接返回_finish - _start的值即可。

size_t size()
	{return _finish - _start;
	}

如果是const对象，我们也要返回一个长度

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

cacpcity函数返回vector的容量，也就是能存放的数据的大个数，我们直接返回_endofstorage - _start的值即可。

size_t cacpcity()
	{return _endofstorage - _start;
	}

如果是const对象，我们也要返回

size_t cacpcity()const
	{return _endofstorage - _start;
	}
begin和end函数

begin 获取 迭代器开始位置，end 获取迭代器结束位置。

直接返回_start 和 _finish

iterator begin()
		{	return _start;
		}
		iterator end()
		{	return _finish;
		}

当我们的容器是const的时候，我们需要返回const迭代器。所以还需要对begin和end函数进行函数重载。

iterator begin()
		{	return _start;
		}
		iterator end()
		{	return _finish;
		}

		const_iterator begin()const
		{	return _start;
		}
		const_iterator end()const
		{	return _finish;
		}
reserve函数

reserve函数是用来改变容量的，但是对于缩容我们不做处理，reserve只做增容处理。

我们可以分以下步骤:

  1. 开辟一块指定大小的空间(只增容)。
  2. 把原_start空间的数据拷贝到新空间。
  3. 更新_finish。
  4. 释放原来的_start。
  5. 更新_start 和 _endofstorage

代码:

void reserve(size_t n)
	{//n比当前容量大
			if (cacpcity()< n)
			{		//开辟n个空间
				T* tmp = new T[n];
				//拷贝
				for (int i = 0; i< size(); i++)
				{*(tmp + i) = *(_start + i);
				}
				//更新_finish
				_finish = tmp + size();
				//销毁旧空间
				delete[] _start;
				//更新
				_start = tmp;
				_endofstorage = _start + n;
			}
	}
insert函数

insert函数是在容器指定位置插入一个数据，而实现insert后我们可以复用insert实现push_back尾插函数。
而这个指定位置，我们用迭代器来表示。插入完后，我们返回插入数据的迭代器位置，方便迭代。

	指定位置插入
		iterator insert(iterator pos, const T& val)
		{	//pos必须在 _start  - _finish之间
			assert(pos >= _start && pos<= _finish);
			//判断空间是否足够
			if (_finish == _endofstorage)
			{		size_t len = pos - _start;
				//空间不够，增容，是0增容4，不是0增容2倍
				reserve(cacpcity() == 0 ? 4 : 2 * cacpcity());
				pos = _start + len;
			}
			//把pos - finish 的位置都往后移动
			iterator end = _finish;
			while (end >pos)
			{		*(end) = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
			//返回pos迭代器
			return pos;
		}
push_back函数

push_back是一个尾插函数，而我们前面实现过insert，所以可以直接复用。

void push_back(const T& val)
		{	//复用insert
			insert(end(), val);
		}
[]操作符重载

我们要支持下标访问，可以重载[]操作符，给定一个下标，返回_start+下标的解引用的引用即可。

T& operator[](const T& val)
		{	return *(_start + val);;
		}

如果是const对象，那么我们不允许修改[]的值。

const T& operator[](const T& val)const
		{	return *(_start + val);;
		}
析构函数

直接释放_start的空间即可。

~vector()
		{	delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
拷贝构造函数

我们可以用 被拷贝对象的迭代区间实例化一个对象，再把当前对象与这个对象进行交换。
然后出了函数，实例化的对象会被自动析构。

void swap(vector& v)
		{	std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		vector(const vector& v)
		{	vectortmp(v.begin(), v.end());
			//交换
			swap(tmp);
		}
赋值操作符重载

直接用拷贝构造构造一个，然后和当前对象交换。

vector& operator=(const vectorv)
		{	vector v2(v);
			swap(v2);
			return *this;
		}
erase函数

eraser函数是在指定位置删除，我们依旧通过迭代器的方式删除。删除后，返回原来下标的迭代器。

代码:

iterator erase(iterator pos)
		{	//pos必须在start - finish区间，且 size不能为空
			assert(size() >0);
			assert(pos >= _start && pos< _finish);
			int len = pos - _start;
			//从pos的下一个位置开始，往前覆盖
			iterator begin = pos + 1;
			while (begin != _finish)
			{		*(begin - 1) = *begin;
				++begin;
			}
			_finish--;

			return pos;
		}
pop_back

pop_back是一个尾删函数，也就是删除最后一个数据，我们可以复用erase

void pop_back()
		{	erase(end() - 1);
		}

end是指向最后一个数据的下一个位置，所以 -1 就是最后一个数据。

反向迭代器

反向迭代器我们需要再有一个类来封装它，目的是为了让它具有复用性。不仅让它可以在 vector中使用，在list里也可以复用 。

反向迭代器模板

我们可以用模板来接收，目的是为了让它既能生成普通反向迭代器，也可以生成带有const的反向迭代器。iterator是传过来的普通迭代器，Ref是返回解引用后的值，Ptr是返回指针。

templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:	
private:
	iterator reverse_iterator;
};
反向迭代器的构造函数

反向迭代器其实就是正向迭代器封装，只是++操作变–，–操作变++

_reverse_iterator(iterator it)
		:_it(it)
	{}
++运算符重载

反向迭代器的++是普通迭代器的- -

//前置++
	self& operator++()
	{--_it;
		return *this;
	}
	//后置++
	self operator++(int)
	{self tmp(*this);
		--_it;
		return tmp;
	}
- -运算符重载

反向迭代器的- - 是正向迭代器的++

//前置--
	self& operator--()
	{++_it;
		return *this;
	}
	//后置--
	self operator--(int)
	{self tmp(*this);
		++_it;
		return tmp;
	}
*引用操作符重载

根据官方的stl，解引用返回的其实是它反向迭代器的前一个位置。
因为起始位置是在最后一个数据的下一个位置。
在这里插入图片描述
所以返回它的前一个位置即可

Ref operator*()
	{iterator tmp = (*this)._it;
		return *(--tmp);
	}

然后我们在主类里面加上模板。

typedef _reverse_iteratorreverse_iterator;
typedef _reverse_iteratorconst_reverse_iterator;

在这里插入图片描述

！=操作符重载

比较地址相不相等，直接返回结果即可。

bool operator!=(const self& it)
	{return _it != it._it;
	}

	bool operator!=(const self& it)const
	{return _it != it._it;
	}
==操作符重载

一样，直接返回结果即可。

bool operator==(const self& it)
	{return _it == it._it;
	}

	bool operator==(const self& it)const
	{return _it == it._it;
	}
rbegin函数

rbegin函数返回最后一个数据的下一个位置，也就是_finish，那我们就用_finish实例化一个反向迭代器。

reverse_iterator rbegin()
		{	return reverse_iterator(_finish);
		}

对于const容器，我们返回const的反向迭代器

const_reverse_iterator rbegin()const
		{	return const_reverse_iterator(_finish);
		}
rend函数

rend函数就是第一个元素，我们用_start实例化反向迭代器然后返回。

reverse_iterator rend()
		{	return reverse_iterator(_start);
		}

const 容器返回const的反向迭代器

const_reverse_iterator rend()const
		{	return const_reverse_iterator(_start);
		}
->重载

如果我们vector存的是一个对象类型，我们还需要支持->访问。所以重载->操作符。

Ptr operator->()
	{		return &operator*();;
	}

我们->也要返回前一个地址，而*操作符返回的是解引用后的值，我们对这个值取地址即可。

全部代码:
vector.h全部代码:

#pragma once
#include
#include#include"reverse_iterator.h"
using namespace std;
namespace wyl
{templateclass vector
	{public:
		//普通迭代器
		typedef T* iterator;
		//const迭代器
		typedef const T* const_iterator;
		//反向迭代器
		typedef _reverse_iteratorreverse_iterator;
		typedef _reverse_iteratorconst_reverse_iterator;

		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}
		//迭代器区间初始化
		templatevector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{	while (first != last)
			{		//把迭代器数据依次插入当前对象
				push_back(*first);
				++first;
			}
		}

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

		void swap(vector& v)
		{	std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		vector(const vector& v)
		{	vectortmp(v.begin(), v.end());
			//交换
			swap(tmp);
		}

		T& operator[](const T& val)
		{	return *(_start + val);
		}

		vector& operator=(const vectorv)
		{	vector v2(v);
			swap(v2);
			return *this;
		}

		const T& operator[](const T& val)const
		{	return *(_start + val);;
		}

		size_t size()
		{	return _finish - _start;
		}

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


		size_t cacpcity()
		{	return _endofstorage - _start;
		}
		size_t cacpcity()const
		{	return _endofstorage - _start;
		}

		void reserve(size_t n)
		{	//n比当前容量大
			if (cacpcity()< n)
			{		//开辟n个空间
				T* tmp = new T[n];
				//拷贝
				for (int i = 0; i< size(); i++)
				{*(tmp + i) = *(_start + i);
				}
				//更新_finish
				_finish = tmp + size();
				//销毁旧空间
				delete[] _start;
				//更新
				_start = tmp;
				_endofstorage = _start + n;
			}
		}

		指定位置插入
		iterator insert(iterator pos, const T& val)
		{	//pos必须在 _start  - _finish之间
			assert(pos >= _start && pos<= _finish);
			//判断空间是否足够
			if (_finish == _endofstorage)
			{		size_t len = pos - _start;
				//空间不够，增容，是0增容4，不是0增容2倍
				reserve(cacpcity() == 0 ? 4 : 2 * cacpcity());
				pos = _start + len;
			}
			//把pos - finish 的位置都往后移动
			iterator end = _finish;
			while (end >pos)
			{		*(end) = *(end - 1);
				--end;
			}
			*pos = val;
			++_finish;
			//返回pos迭代器
			return pos;
		}

		iterator erase(iterator pos)
		{	//pos必须在start - finish区间，且 size不能为空
			assert(size() >0);
			assert(pos >= _start && pos< _finish);
			int len = pos - _start;
			//从pos的下一个位置开始，往前覆盖
			iterator begin = pos + 1;
			while (begin != _finish)
			{		*(begin - 1) = *begin;
				++begin;
			}
			_finish--;

			return pos;
		}

		void pop_back()
		{	erase(end() - 1);
		}

		iterator begin()
		{	return _start;
		}
		iterator end()
		{	return _finish;
		}

		const_iterator begin()const
		{	return _start;
		}
		const_iterator end()const
		{	return _finish;
		}
		//反向迭代器
		reverse_iterator rbegin()
		{	return reverse_iterator(_finish);
		}

		const_reverse_iterator rbegin()const
		{	return const_reverse_iterator(_finish);
		}

		reverse_iterator rend()
		{	return reverse_iterator(_start);
		}

		const_reverse_iterator rend()const
		{	return const_reverse_iterator(_start);
		}


		void push_back(const T& val)
		{	//复用insert
			insert(end(), val);
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;

	};


	void a(const vector& v)
	{for (int i = 0; i< v.size(); i++)
		{	//v[i] = 10;
			cout<< v[i]<< " ";
		}
	}
	void test1()
	{vectorv;
		v.push_back(1);
		cout<< v.size()<< ","<< v.cacpcity()<< endl;
		v.push_back(2);
		cout<< v.size()<< ","<< v.cacpcity()<< endl;
		v.push_back(3);
		cout<< v.size()<< ","<< v.cacpcity()<< endl;
		v.push_back(4);
		v.push_back(5);
		cout<< v.size()<< ","<< v.cacpcity()<< endl;
		
		vector::iterator it = v.begin();
		//while (it != v.end())
		//{//	
		//	cout<< *it<< " ";
		//	++it;
		//}
		for (int i = 0; i< v.size(); i++)
		{	v[i] = 10;
			cout<< v[i]<< " ";
		}
		a(v);

	}

	void test2()
	{vectorv;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		//v.erase(v.begin());
		//v.erase(v.end()-1);


		vectorv2 = v;
		vector::reverse_iterator rit = v2.rbegin();
		while (rit != v2.rend())
		{	
			cout<< *rit<< " ";
			++rit;
		}
	}
	struct Date
	{int _year;
		int _month;
		int _day;
		Date(int year = 1,int month = 1,int day = 1)
			:_year(year)
			,_month(month)
			,_day(day)
		{}
	};

	void b(const vector& v)
	{vector::const_reverse_iterator rit = v.rbegin();
		while (rit != v.rend())
		{	cout<< rit->_year<< " "<< rit->_month<< " "<< rit->_day<< endl;
			++rit;
		}
	}

	void test3()
	{vectorv;
		v.push_back(Date(2022, 1, 1));
		v.push_back(Date(2022, 2, 1));
		v.push_back(Date(2022, 3, 1));
		b(v);

	}
}

反向迭代器封装的类的全部代码
reverse_iterator.h

#pragma once

templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:	
	_reverse_iterator(iterator it)
		:_it(it)
	{}
	//前置++
	self& operator++()
	{--_it;
		return *this;
	}
	//后置++
	self operator++(int)
	{self tmp(*this);
		--_it;
		return tmp;
	}

	//前置--
	self& operator--()
	{++_it;
		return *this;
	}
	//后置--
	self operator--(int)
	{self tmp(*this);
		++_it;
		return tmp;
	}

	Ref operator*()
	{iterator tmp = (*this)._it;
		return *(--tmp);
	}

	Ptr operator->()
	{return &operator*();
	}

	bool operator!=(const self& it)
	{return _it != it._it;
	}

	bool operator!=(const self& it)const
	{return _it != it._it;
	}

	bool operator==(const self& it)
	{return _it == it._it;
	}

	bool operator==(const self& it)const
	{return _it == it._it;
	}


private:
	iterator _it;
};

主main函数文件代码
test.cpp

#include"vector.h"

void vectorTest()
{//wyl::test1();
	wyl::test3();

}

int main()
{vectorTest();
}
总结

代码是跟着博客边写，边测，没问题才写上博客的。而后续还会为大家更新更多关于stl的知识，以及一些容器的模拟实现。而反向迭代器具有复用性，也就是这次实现了，下次模拟实现其他容器时可以直接带进去用。实际中vector的使用频率也很高，手动实现一次vector对学习stl的帮助也非常大。后续会持续为大家更新关于C/C++，数据结构以及linux操作系统等知识，如果觉得讲的还可以，可以三连关注一下。如果哪里有写的不对的地方，也欢迎大家指出。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前名称：【C++】STL---vector的模拟实现(超级详细，万字详解)-创新互联
网站链接：http://myzitong.com/article/dgoejj.html

其他资讯