STL 关于vector的细节，vector模拟实现【C++】-Toy模板网

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

STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

vector成员变量

STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言
_start指向容器的头，_finish指向容器当中有效数据的下一个位置，_endofstorage指向整个容器的尾

默认成员函数

构造函数

		//构造函数
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}

拷贝构造

先开辟一块与该容器大小相同的空间，然后将该容器当中的数据一个个拷贝过来即可，最后更新_finish和_endofstorage的值即可。

深拷贝版本一：

		//拷贝构造（深拷贝）
		vector(const vector<T> & v)
			//v1= v
			//vector( vector * this ,const vector<T>& v)

		{
			//开空间
			this->_start =  new T[size(T) * v.capacity()];
			//拷贝数据
			memcpy(this->_start, v._start, sizeof(T) * v.size()  );
			this->_finish = v._start + v.size();//更新_finish
			this->_endofstorage = v._start + v.capacity();//更新 _endofstorage
		}

注意：不能使用memcpy函数，
如果vector存储的数据是内置类型或无需进行深拷贝的自定义类型时，使用memcpy函数可以
但当vector存储的数据是需要进行深拷贝的自定义类型时，不能使用memcpy
举个例子
如果vector存储的数据是string类的时候

void test_vector9()
	{
		vector<string> v;
		v.push_back("111111111111111");
		v.push_back("222222222222222");
		v.push_back("333333333333333");
		v.push_back("444444444444444");
		v.push_back("555555555555555");//memcpy拷贝出现了问题

		for (auto & e : v) //string拷贝代价比较大
		{
			cout << e << " ";
		}
		cout << endl;
	}

memcpy函数进行拷贝构造的话，那么reserve函数申请的tmp当中存储的每个string的成员变量的值，与vector 当中的每个对应的string成员都指向同一个字符串空间,
STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

delete释放空间，如果是自定义类型时，依次调用数组每个对象的析构函数，再释放整个空间，也就是说tmp现在指向一块被释放的空间，即tmp是野指针
STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

总结：
问题：vector是深拷贝 , 但是vector空间上存的对象是string的数组使用memcpy导致string对象的浅拷贝

如何解决：

		void reserve( size_t n)
		{
 			if (n > capacity())//扩容 
			{
				size_t sz = size();//用sz记录size 
				T * tmp = new T[n];
				if (_start != nullptr) //如果原空间不为空再拷贝数据
				{
					//memcpy(tmp, _start, sizeof(T) * sz);//将_start的数据拷贝到tmp中
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];//调用string的赋值重载进行深拷贝
					}
					delete[] _start;//释放_start的空间 
				}

				_start = tmp; //将tmp的地址给_start，以便_finish和_endofstorage的更新
				_finish = _start + sz;//更新_finish
				_endofstorage = _start + n;//更新_endofstorage 

			  } 
		}

STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

结论：如果vector当中存储的元素类型是内置类型（int）或浅拷贝的自定义类型（Date），可以使用memcpy函数进行进行拷贝构造，但如果vector当中存储的元素类型是深拷贝的自定义类型（string），则不可以使用memcpy函数

深拷贝版本二：

使用范围for（或是其他遍历方式）对容器v进行遍历，在遍历过程中将容器v中存储的数据一个个尾插过来即可。

		//拷贝构造第二种版本（深拷贝）
		vector( const vector<T>& v)
			//v1=v
			//vector( vector *this , const vector<T> v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			//开空间
			reserve(v.capacity());

			//拷贝数据
			for (auto e : v)
			{
				push_back(e); //将v的数据插入到v1中
			}
		}

注意：在使用范围for对容器v进行遍历的过程中，变量e就是每一个数据的拷贝，然后将e尾插到构造出来的容器当中。就算容器v当中存储的数据是string类，在e拷贝时也会自动调用string的拷贝构造（深拷贝），所以也能够避免出现与使用memcpy时类似的问题。

赋值运算符重载函数

vector的赋值运算符重载当然也涉及深拷贝问题，我们这里也提供两种深拷贝的写法：

先释放原来的空间，再开辟一块和容器v大小相同的空间，然后将容器v当中的数据一个个拷贝过来，最后更新_finish和_endofstorage的值即可。

深拷贝版本一

		//赋值重载版本一
		vector<T>  &  operator=(vector<T> v)
			//v1=v
		//	vector<T>& operator=(vector<T> *this , vector<T> v)
		{
			//释放原来的空间
			delete [] _start;
			//开辟空间 
			_start = new T[v.capacity()];
			//拷贝数据 
			for (size_t i =0 ; i < v.size(); ++ i)
			{ 
				_start[i]= v[i];
			}
			//更行相关边界条件
			_finish = _start + v.size();
			_endofstorage = _start + v.capacity();
			return *this;
		 }

首先在右值传参时并没有使用引用传参，因为这样可以间接调用vector的拷贝构造函数，然后将这个拷贝构造出来的容器v与左值进行交换，此时就相当于完成了赋值操作，而容器v会在该函数调用结束时自动析构。

深拷贝版本二（推荐）

  //赋值重载版本二
		 vector<T> & operator= ( vector<T> v) //编译器接收右值的时候自动调用拷贝构造函数
			 //vector<T>& operator= ( vector<T> *this ,vector<T> v)
			 //v1=v
		{
			 //this->swap(v)
			 swap(v);//v1 和v交换
			 return *this;
		}

版本二的理解：
STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

析构函数

对容器进行析构时，首先判断该容器是否为空容器，若为空容器，则无需进行析构操作，若不为空，则先释放容器存储数据的空间，然后将容器的各个成员变量设置为空指针即可。

	//析构函数
		~vector()
		{
			//_start==nulllptr 就不需要析构了
			if (_start != nullptr)
			{

				delete[]_start;
				_start = _finish = _endofstorage = nullptr;
			}
		}

迭代器

STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

begin

vector当中的begin函数返回容器的首地址

普通版本

        iterator begin()
		{
			return _start;
		}

const版本

	 const_iterator begin() const
		{
			return _start;
		}

end

end函数返回容器当中有效数据的下一个数据的地址。

普通版本

		 iterator end()
		 {
			 return _finish;
		 }

const 版本

	 const_iterator end() const
		 {
			 return _finish;
		 }

size和capacity

两个指针相减的结果，即这两个指针之间对应类型的数据个数，所以size可以由_finish - _start得到，而capacity可以由_endofstorage - _start得到。

STL 关于vector的细节，vector模拟实现【C++】,c++,rpc,开发语言

size_t size()const
{
	return _finish - _start; //返回容器当中有效数据的个数
}
size_t capacity()const
{
	return _endofstorage - _start; //返回当前容器的最大容量
}

resize

1、n > size

将size扩大到n，扩大的数据为val，若val未给出，就用缺省值

2、n < size

改变_finish的指向，直接将容器的size缩小到n即可

		 void resize(  size_t n ,  const T& val =  T()   )//缺省值是匿名对象,c++对内置类型进行了升级
		 {
			 //n<size 缩容
			 if (n < size())
			 {
				 _finish = _start + n;
		     }
			 else	 //扩容
			 {
				 reserve(n);
				 //插入数据
				 while (_finish!=_start+n)
				 {
					 *_finish = val;
					 _finish++;
				}
			 }
		
		 }

注意： c++把内置类型也看作成类，它们也有默认构造函数，所以在给resize函数的参数val设置缺省值时，设置为T( )即可

reserve

1、n>capacity()，将capacity扩大到n或大于n。
2、n<capacity() ，什么也不做。

	void reserve( size_t n)
		{
			if (n > capacity())//扩容 
			{
				size_t sz = size();//用sz记录size 
				T * tmp = new T[n];
				if (_start != nullptr) //如果原空间不为空再拷贝数据
				{
					memcpy(tmp, _start, sizeof(T) * sz);//将_start的数据拷贝到tmp中
					delete[] _start;//释放_start的空间 
				}

				_start = tmp; //将tmp的地址给_start，以便_finish和_endofstorage的更新
				_finish = _start + sz;//更新_finish
				_endofstorage = _start + n;//更新_endofstorage 

			  } 
		}

注意：
1 在进行操作之前需要提前记录当前容器当中有效数据的个数。

2 拷贝容器当中的数据时，不能使用memcpy函数进行拷贝

[ ]

const 版本

		 const T & operator[] (size_t pos) const
			// const T& operator[] (  T const * this,size_t pos) 
		{
			 assert(pos < size());
			 return  _start[pos];

		}

普通版本


		  T& operator[] (size_t pos) 
			 // const T& operator[] (  T  * this,size_t pos) 
		 {
			 assert(pos < size() );
			 return  _start[pos];

		 }

push_back

要尾插数据首先得判断容器是否已满，若已满则需要先进行增容，然后将数据尾插到_finish指向的位置，再将_finish++即可

void push_back(const T & x )
		{
			//如果容量满了
			if (_finish == _endofstorage)
				//扩容
			{
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve (newcapacity);//扩容
			}
			*_finish = x;
			_finish++;//_finish指针后移
		}

pop_back

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

insert

insert函数可以在所给迭代器pos位置插入数据，在插入数据前先判断是否需要增容，然后将pos位置及其之后的数据统一向后挪动一位，以留出pos位置进行插入，最后将数据插入到pos位置即可。

		 iterator insert(iterator pos, const T& x)
		 {
			 assert(pos >= _start && pos <= _finish);	
			 //如果容量满了，需要扩容 
			 if (_finish == _endofstorage)
			 {
				 size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				 //扩容会开辟一段新的空间 ，把数据从原空间拷贝到新空间，并且释放原空间，但是此时pos这个迭代器还是指向原空间
				 //会导致pos迭代器失效 —更新pos迭代器
				 size_t len = pos - _start;
				 reserve(newcapacity);
				 pos = _start + len;
			  }
			 //容量未满
			 iterator end = _finish -1;
			 //挪动数据
			 while (end>=pos)
			 {
				 *(end + 1) = *(end);
  				 --end;
			 }
			 //插入数据 
			 (*pos) = x;
			 _finish++;
			 return pos;
		 }

insert以后可能会出现迭代器失效
解决方案：再下一次使用迭代器之前，对迭代器重新赋值即可

erase

erase函数可以删除所给迭代器pos位置的数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将pos位置之后的数据统一向前挪动一位，将pos位置的数据覆盖即可

		 //错误的版本
		 //void erase(iterator pos)
		 //{
			// assert(pos >= _start && pos < _finish);
			// iterator it = pos + 1;
			// while (it != _finish)//挪动数据
			// {
			//	 *(it - 1) = *(it);
			//	 it++;
			// }
			// _finish--;
		 //}

		 //正确的版本
		 iterator erase(iterator pos)
		 {
			 assert(pos >= _start && pos < _finish);
			 iterator it = pos + 1;
			 while (it!= _finish)//挪动数据
			 {
				 *(it - 1) = *(it);
				 it++;
			 }
			 _finish--;
			 return pos;
		
		  }

erase 在使用的时候可能会有迭代器失效的问题
解决方案：我们可以接收erase函数的返回值（erase函数返回删除元素的后一个元素的新位置）

swap

swap函数用于交换两个容器的数据，我们可以直接调用库当中的swap函数将两个容器当中的各个成员变量进行交换即可。

		void swap(vector<T> & v)//交换数据
		{
			std::swap(_start , v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

注意：这里调用库里的swap模板函数，需要在swap函数之前加上“std::”，告诉编译器在c++标准库寻找swap函数，否则编译器编译时会认为你调用的是正在实现的swap函数（就近原则）。

下面是测试代码

#pragma once //防止头文件重复包含
#include<assert.h>
#include <string.h>
#include<iostream>
using namespace std;
namespace cxq
{

	//Vector类存储的数据是任意类型，所以需要设置模板参数
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef  const T* const_iterator;
	public:
		//构造函数
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}
		//析构函数
		~vector()
		{
			//_start==nulllptr 就不需要析构了
			if (_start != nullptr)
			{

				delete[]_start;
				_start = _finish = _endofstorage = nullptr;
			}
		}
		//拷贝构造（深拷贝）
		vector( const vector<T> & v)
			//v1= v
			//vector( vector * this ,const vector<T>& v)

		{
			//开空间
			_start =  new T[sizeof(T) * v.capacity()];
			//拷贝数据
		//	memcpy(this->_start, v._start, sizeof(T) * v.size()  );
		 for(size_t i =0 ; i <v.size() ; ++i)
		 {
		   _start[i] = v._start[i] ;
		 }
			this->_finish = v._start + v.size();//更新_finish
			this->_endofstorage = v._start + v.capacity();//更新 _endofstorage
		}

		拷贝构造第二种版本（深拷贝）
		//vector( const vector<T>& v)
		//	//v1=v
		//	//vector( vector *this , const vector<T> v)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _endofstorage(nullptr)
		//{
		//	//开空间
		//	reserve(v.capacity());

		//	//拷贝数据
		//	for (auto e : v)
		//	{
		//		push_back(e); //将v的数据插入到v1中
		//	}
		//}
		void swap(vector<T> & v)//交换数据
		{
			std::swap(_start , v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		赋值重载版本一
		//vector<T>  &  operator=(vector<T> v)
		//	//v1=v
			vector<T>& operator=(vector<T> *this , vector<T> v)
		//{
		//	//释放原来的空间
		//	delete [] _start;
		//	//开辟空间 
		//	_start = new T[v.capacity()];
		//	//拷贝数据 
		//	for (size_t i =0 ; i < v.size(); ++ i)
		//	{ 
		//		_start[i]= v[i];
		//	}
		//	//更行相关边界条件
		//	_finish = _start + v.size();
		//	_endofstorage = _start + v.capacity();
		//	return *this;
		// }

	  //赋值重载版本二
		 vector<T> & operator= ( vector<T> v) //编译器接收右值的时候自动调用拷贝构造函数
			 //vector<T>& operator= ( vector<T> *this ,vector<T> v)
			 //v1=v
		{
			 //this->swap(v)
			 swap(v);//v1 和v交换
			 return *this;
		}
			    


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

		 const_iterator end() const
		 {
			 return _finish;
		 }
		size_t capacity() const
		{
			return _endofstorage - _start;
		}
		size_t size() const
		{
			return _finish - _start;
		}
		void push_back(const T & x )
		{
			如果容量满了
			//if (_finish == _endofstorage)
			//	//扩容
			//{
			//	size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
			//	reserve (newcapacity);//扩容
			//}
			//*_finish = x;//?
			//_finish++;
			
			insert(end(), x);
			
		}

		void pop_back()
		{
			erase(  --end()  );
		}
		 const T & operator[] (size_t pos) const
			// const T& operator[] (  T const * this,size_t pos) 
		{
			 assert(pos < size());
			 return  _start[pos];

		}

		  T& operator[] (size_t pos) 
			 // const T& operator[] (  T  * this,size_t pos) 
		 {
			 assert(pos < size() );
			 return  _start[pos];

		 }
		 iterator insert(iterator pos, const T& x)
		 {
			 assert(pos >= _start && pos <= _finish);	
			 //如果容量满了，需要扩容 
			 if (_finish == _endofstorage)
			 {
				 size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				 //扩容会开辟一段新的空间 ，把数据从原空间拷贝到新空间，并且释放原空间，但是此时pos这个迭代器还是指向原空间
				 //会导致pos迭代器失效 —更新pos迭代器
				 size_t len = pos - _start;
				 reserve(newcapacity);
				 pos = _start + len;
			  }
			 //容量未满
			 iterator end = _finish -1;
			 //挪动数据
			 while (end>=pos)
			 {
				 *(end + 1) = *(end);
  				 --end;
			 }
			 //插入数据 
			 (*pos) = x;
			 _finish++;
			 return pos;
		 }

		 //错误的版本
		 //void erase(iterator pos)
		 //{
			// assert(pos >= _start && pos < _finish);
			// iterator it = pos + 1;
			// while (it != _finish)//挪动数据
			// {
			//	 *(it - 1) = *(it);
			//	 it++;
			// }
			// _finish--;
		 //}

		 //正确的版本
		 iterator erase(iterator pos)
		 {
			 assert(pos >= _start && pos < _finish);
			 iterator it = pos + 1;
			 while (it!= _finish)//挪动数据
			 {
				 *(it - 1) = *(it);
				 it++;
			 }
			 _finish--;
			 return pos;
		
		  }

		 void resize(  size_t n ,  const T& val =  T()   )//缺省值是匿名对象,c++对内置类型进行了升级
		 {
			 //n<size 缩容
			 if (n < size())
			 {
				 _finish = _start + n;
		     }
			 else	 //扩容
			 {
				 reserve(n);
				 //插入数据
				 while (_finish!=_start+n)
				 {
					 *_finish = val;
					 _finish++;
				}
			 }
		
		 }
		void reserve( size_t n)
		{
 			if (n > capacity())//扩容 
			{
				size_t sz = size();//用sz记录size 
				T * tmp = new T[n];
				if (_start != nullptr) //如果原空间不为空再拷贝数据
				{
					//memcpy(tmp, _start, sizeof(T) * sz);//将_start的数据拷贝到tmp中
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];//调用string的赋值重载进行深拷贝
					}
					delete[] _start;//释放_start的空间 
				}

				_start = tmp; //将tmp的地址给_start，以便_finish和_endofstorage的更新
				_finish = _start + sz;//更新_finish
				_endofstorage = _start + n;//更新_endofstorage 

			  } 
		}





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

	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		for (size_t i =0 ; i< v.size(); i++)
		{
			v[i];
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		
	}
	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);
		v.push_back(6);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.insert(v.begin(), 100);
		for (size_t i = 0; i < v.size(); i++)
		{
			v[i];
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int>::iterator  pos = v.begin() + 3;
		v.insert(pos, 20);

		// insert以后迭代器可能会失效(扩容)
		// 记住，insert以后就不要使用这个形参迭代器了，因为他可能失效了
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_vector3()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(6);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<int>::iterator it = v1.begin();
	
		//删除所有的偶数 
		while (it != v1.end())
		{
			//判断偶数
			if (*it % 2 == 0)
			{
				it = v1.erase(it);
			}
			//不是偶数
			else
			{
			
				it++;
			}
 		}
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
//	void test_vector4()
//	{
//		vector<int> v1;
//		v1.push_back(1);
//		v1.push_back(2);
//		v1.push_back(3);
//		v1.push_back(4);
//		v1.push_back(5);
//
//		for (auto e : v1)
//		{
//			cout << e << " ";
//		}
//		cout << endl;
//
//		/*v1.erase(v1.begin());*/
//		auto it = v1.begin()+4;
//		v1.erase(it);
//		//erase以后迭代器失效，不能访问
//		//vs进行了强制检查
//		cout << *it << endl;
//		it++;
//		cout << *it << endl;
//
//		for (auto e : v1)
//		{
//			cout << e << " ";
//		}
//		cout << endl;
//	}
	void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		v.resize(10, 4);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_vector6()
	{
		vector<int> v;
		v.resize(10, 0);
		int i = 0;
		int j = int();//内置类型，c++有了模板之后就升级了
		int k = int(1);
	}
	void test_vector7()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		vector<int> v1(v);

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

	}
	void test_vector8()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<int> v2;
		v2.resize(10, 1);
		v1 = v2;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void test_vector9()
	{
		vector<string> v;
		v.push_back("111111111111111");
		v.push_back("222222222222222");
		v.push_back("333333333333333");
		v.push_back("444444444444444");
		v.push_back("555555555555555");

		for (auto & e : v) //string拷贝代价比较大
		{
			cout << e << " ";
		}
		cout << endl;
	}
}