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

╰半橙微兮° 2024-03-30 15:40 52阅读 0赞

#### 文章目录 ####

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

--------------------

## 前言 ##

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

--------------------

## vector的成员属性 ##

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

代码:

template<class T>
    class 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)
    	{
        		
    	}

迭代器区间初始化：

//迭代器区间初始化
    	template <class InputIterator>
    	vector(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<T>& v)
    		{
        
    			std::swap(_start, v._start);
    			std::swap(_finish, v._finish);
    			std::swap(_endofstorage, v._endofstorage);
    		}
    
    		vector(const vector<T>& v)
    		{
        
    			vector<T> tmp(v.begin(), v.end());
    			//交换
    			swap(tmp);
    		}

## 赋值操作符重载 ##

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

vector<T>& operator=(const vector<int> v)
    		{
        
    			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是返回指针。

template<class iterator,class Ref,class Ptr>
    class _reverse_iterator
    {
        
    	typedef _reverse_iterator<iterator, Ref, Ptr> self;
    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，解引用返回的其实是它反向迭代器的前一个位置。  
因为起始位置是在最后一个数据的下一个位置。  
![在这里插入图片描述][dd780118718a4a1c960e1d394c03a8c1.png]  
所以返回它的前一个位置即可

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

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

typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef _reverse_iterator<const_iterator, const T&,const T*> const_reverse_iterator;

![在这里插入图片描述][799162485cd8433a8da1fe299af642b4.png]

### ！=操作符重载 ###

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

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<assert.h>
    #include<iostream>
    #include"reverse_iterator.h"
    using namespace std;
    namespace wyl
    {
        
    	template<class T>
    	class vector
    	{
        
    	public:
    		//普通迭代器
    		typedef T* iterator;
    		//const迭代器
    		typedef const T* const_iterator;
    		//反向迭代器
    		typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;
    		typedef _reverse_iterator<const_iterator, const T&,const T*> const_reverse_iterator;
    
    		vector()
    			:_start(nullptr)
    			, _finish(nullptr)
    			, _endofstorage(nullptr)
    		{
        
    		}
    		//迭代器区间初始化
    		template <class InputIterator>
    		vector(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<T>& v)
    		{
        
    			std::swap(_start, v._start);
    			std::swap(_finish, v._finish);
    			std::swap(_endofstorage, v._endofstorage);
    		}
    
    		vector(const vector<T>& v)
    		{
        
    			vector<T> tmp(v.begin(), v.end());
    			//交换
    			swap(tmp);
    		}
    
    		T& operator[](const T& val)
    		{
        
    			return *(_start + val);
    		}
    
    		vector<T>& operator=(const vector<int> v)
    		{
        
    			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<int>& v)
    	{
        
    		for (int i = 0; i < v.size(); i++)
    		{
        
    			//v[i] = 10;
    			cout << v[i] << " ";
    		}
    	}
    	void test1()
    	{
        
    		vector<int> v;
    		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<int>::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()
    	{
        
    		vector<int> v;
    		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);
    
    
    		vector<int> v2 = v;
    		vector<int>::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<Date>& v)
    	{
        
    		vector<Date>::const_reverse_iterator rit = v.rbegin();
    		while (rit != v.rend())
    		{
        
    			cout << rit->_year << " " << rit->_month << " " << rit->_day << endl;
    			++rit;
    		}
    	}
    
    	void test3()
    	{
        
    		vector<Date> v;
    		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
    
    template<class iterator,class Ref,class Ptr>
    class _reverse_iterator
    {
        
    	typedef _reverse_iterator<iterator, Ref, Ptr> self;
    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操作系统等知识，如果觉得讲的还可以，可以三连关注一下。如果哪里有写的不对的地方，也欢迎大家指出。

[dd780118718a4a1c960e1d394c03a8c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ab965f15e32e412e8484ad9f363178c7.png
[799162485cd8433a8da1fe299af642b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/68f0b69a55034566b9eae6b4f5f73d7d.png