vector的模拟实现

ljw695

发布于 2024-10-18 08:11:59

890

发布于 2024-10-18 08:11:59

文章被收录于专栏：ljw

开头

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

namespace Ljw
{
	template<class T>
	class   vector
	{	
        public:
		typedef T* iterator;
		typedef const T*  const_iterator;
        	private:
		iterator _start;//为开头的指针
		iterator _finish; //为实际数量的指针
		iterator _end; //为空间的指针
	};
}

构造函数，初始化列表

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

析构函数

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

长度

	size_t size()
	{
		return _finish - _start;//指针减指针为数
	}

空间

size_t capacity()
{
	return _end - _start;//指针减指针为数
}

迭代器

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

扩容

void reserve(size_t n)
{	
	if (n > capacity())
	{
		//提前保存
		size_t k = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * k);
		
			//改正string的问题
			for (int i = 0; i <  k; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}	
		//_finish = tmp + size();//_start的原来空间已经释放，需要tmp,或者可以提前保存size()的大小,
		                                        //因为size()返回的是_finish-_start,_start的指向已经变了所以，size()的大小是不确定的，
												// 可以提前存size()的大小,这样就解决了指向改变的问题，可以在if外面，里面也可以，因为扩容才会改变指向
		_start = tmp;
		_finish = _start + k;
		_end = _start + n;
	}
}

_finish = tmp + size();//_start的原来空间已经释放，需要tmp,或者可以提前保存size()的大小,//因为size()返回的是_finish-_start,_start的指向已经变了所以，size()的大小是不确定，// 可以提前存size()的大小,这样就解决了指向改变的问题，可以在if外面，里面也可以，因为扩容才会改变指向

尾插

void push_back(const T& v)
{
	/*if (_finish==_end )
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	*_finish = v;
	_finish++;*/

	insert(end(), v);
}

[]的模拟实现

	T&operator[](size_t pos)
	{
		assert(pos < size());
		return _start[pos];//等价于*(_start+pos)
	}
	const T& operator[](size_t pos)const
	{
		assert(pos < size());
		return _start[pos];
	}

insert的模拟实现

//insert的模拟实现，vector中的insert是用迭代器实现的,库里会返回pos这个位置

iterator insert(iterator pos,const T&v)
{
	assert(pos <= _finish&&pos>=_start);//这是迭代器之间的比较
	if (_finish == _end)
	{
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	} 
	//扩容后pos还是指向旧空间，所以要提前保存然后再指向新的pos位置
	iterator  end = _finish - 1;
	while (end>=pos)
	{
		//_start[end] = _start[end+1];是不对的，因为是end迭代器，迭代器类似于指针
		*(end + 1)= *(end);
		end--;
	}
	*_finish = v;
	_finish++;
	return pos;
}

erase的模拟实现

//erase的模拟实现，库里会返回删除位置的下一个位置,用的也是迭代器

iterator erase(iterator pos)
{
	assert(pos >= _start && pos < _finish);
	iterator i = pos;
	while (i<_finish)
	{
		*i = *(i + 1);
		i++;
	}
	_finish--;
	return pos;
}

尾删

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

resize的模拟实现

//resize的模拟实现,同样分为三种情况,resize扩容后会初始化，而reserve不用初始化也就是size（_finish不会变）

void resize(size_t n,const T&v =T())//此处的T()类似于int(2),等价于int i=2,不过匿名构造下一行就会销毁
{
	//举个例子_finish为8，_end为12，resize(5),
	//会把_finish变为5，resize(10)会插入两个v，resize(15)会扩容加初始化
	if (n <=capacity())
	{
		if (n < size())
		{
			_finish = _start + n;
		}
		else
		{
			size_t i = size();
			while (i!=n)
			{
				_start[i] = v;
				i++;
			}
			_finish = _start + n;
		}
	}
	else
	{
		reserve(n);
		size_t i = size();
		while (i != n)
		{
			_start[i] = v;
			i++;
		}
		_finish = _start + n;//如果是例子中的第二种情况_finish还在8处，所以要重新指向
	}
}

深拷贝模拟,vector<int>v1(v)

vector(vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _end(nullptr)
{
	//先new一个新空间,保证两个空间一致
	_start = new T[v.capacity()];
	//memcpy(_start, v._start, v. size() * sizeof(T));
	
	//改正string的问题
	for (int i = 0; i < v.size(); i++)
	{
		_start[i] = v._start[i];
	}
	_finish = _start + v.size();
	_end = _start + v.capacity();
}

swap的模拟实现

void swap(vector<T>&v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end, v._end);
}

=的模拟实现

	vector<T>&operator=(vector<T> v)
	{
		swap(v);
		return *this;
	}

vector<int>v(10,1)

//vector<int>v(10,1),模拟实现开10个空间，并初始化为1
vector(size_t n,const T&x=T())//匿名对象为了别的类也可以用
{
	resize(n, x);
}
vector(int n, const T& x = T())//匿名对象为了别的类也可以用
{
	resize(n, x);
}

支持多样类型的迭代器

	template<class TT>
	vector(TT first,TT last)
	{
		while (first != last)
		{
			push_back(*first);
			first++;
		}
	}

text

//尾插push_back
void text1()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//[]的模拟实现
void text2()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (int i = 0; i < 6; i++)
	{
		v[i]++;
		cout << v[i] << " ";
	}
	cout << endl;
}

//insert的模拟实现，vector中的insert是用迭代器实现的
void text3()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	v.insert(v.begin() + 3, 7);
	for (int i = 0; i < 7; i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	//记住insert以后就不要使用这个形参的迭代器了，因为它可能失效了
	auto  it = v.begin() + 3;//等价于下一行
	Ljw::vector<int>::iterator it1 = v.begin() + 3;
	*it = 10;
	cout << endl;
}

//erase的模拟实现，库里会返回删除位置的下一个位置,用的也是迭代器
//记住erase以后就不要使用这个形参的迭代器了，因为它可能失效了
//用erase测试删除所有偶数
void text4()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	v.insert(v.begin() + 3, 7);
	v.erase(v.begin()+4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it=v.erase(it);
		}
		else//需要加一个else，如果两个偶数挨在一起的时候，
			   //删除第一个后，会返回下一个偶数的位置，然后没有else就会++就错过了一个
		it++;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//尾删
void text5()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.pop_back();
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//resize的模拟实现,同样分为三种情况,resize扩容后会初始化，而reserve不用初始化也就是size（_finish不会变）
void text6()
{
	Ljw::vector<int> v;
	v.reserve(10);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);
	v.push_back(8);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size()<<" "<<v.capacity() << endl;
	v.resize(12, 0);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//深拷贝模拟,vector<int>v1(v);
void text7()
{
	Ljw::vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	Ljw::vector<int>v1(v);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;	
}

//=的模拟实现
void text8()
{
	Ljw::vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	Ljw::vector<int>v1(v);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	v1.push_back(88);
	cout << endl;
	Ljw::vector<int>v2;
	v2 = v1;
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
}
//测试vector<string>v,
//vector上是深拷贝，是string的数组，
//使用reserve中的memcpy导致string对象发生浅拷贝
//修改resFerve
void text9()
{
	Ljw::vector<string>v;
	v.push_back("111");
	v.push_back("222");
	v.push_back("333");
	v.push_back("444");
	v.push_back("555");
	v.push_back("666");
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout <<endl;
}

//vector<int>(10,1),模拟实现开10个空间，并初始化为1
void text10()
{
	Ljw::vector<int>v(10,1);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//多种类型迭代器的测试
void text11()
{
	Ljw::vector<int>v(10, 1);
	Ljw::vector<int>v1(v.begin(), v.end());
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	Ljw::vector<string>v2(10, "111");
	Ljw::vector<string>v3(v2.begin(), v2.end());
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

	int a[] = { 1,2,3,4,5 };
	Ljw::vector<int>v4(a, a + 5);//左闭右开
	for (auto e : v4)
	{
		cout << e << " ";
	}
}

总代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace Ljw
{
	template<class T>
	class   vector
	{
		public:
			typedef T* iterator;
			typedef const T*  const_iterator;
		
		//构造函数，初始化列表
		vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_end(nullptr)
		{}

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

		//长度
		size_t size()
		{
			return _finish - _start;//指针减指针为数
		}

		//空间
		size_t capacity()
		{
			return _end - _start;//指针减指针为数
		}

		//迭代器
		const_iterator begin() const
		{
			return _start;
		}
		//迭代器
		const_iterator end() const
		{
			return _finish;
		}
		//const迭代器
		iterator begin() 
		{
			return _start;
		}
		//迭代器
		iterator end() 
		{
			return _finish;
		}
		//扩容
		void reserve(size_t n)
		{	
			if (n > capacity())
			{
				//提前保存
				size_t k = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * k);
				
					//改正string的问题
					for (int i = 0; i <  k; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}	
				//_finish = tmp + size();//_start的原来空间已经释放，需要tmp,或者可以提前保存size()的大小,
				                                        //因为size()返回的是_finish-_start,_start的指向已经变了所以，size()的大小是不确定的，
														// 可以提前存size()的大小,这样就解决了指向改变的问题，可以在if外面，里面也可以，因为扩容才会改变指向
				_start = tmp;
				_finish = _start + k;
				_end = _start + n;
			}
		}

		//尾插
		void push_back(const T& v)
		{
			/*if (_finish==_end )
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = v;
			_finish++;*/

			insert(end(), v);
		}
		//[]的模拟实现
		T&operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];//等价于*(_start+pos)
		}
		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return _start[pos];
		}

		//insert的模拟实现，vector中的insert是用迭代器实现的,库里会返回pos这个位置
		iterator insert(iterator pos,const T&v)
		{
			assert(pos <= _finish&&pos>=_start);//这是迭代器之间的比较
			if (_finish == _end)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;
			} 
			//扩容后pos还是指向旧空间，所以要提前保存然后再指向新的pos位置
			iterator  end = _finish - 1;
			while (end>=pos)
			{
				//_start[end] = _start[end+1];是不对的，因为是end迭代器，迭代器类似于指针
				*(end + 1)= *(end);
				end--;
			}
			*_finish = v;
			_finish++;
			return pos;
		}

		//erase的模拟实现，库里会返回删除位置的下一个位置,用的也是迭代器
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator i = pos;
			while (i<_finish)
			{
				*i = *(i + 1);
				i++;
			}
			_finish--;
			return pos;
		}

		//尾删
		void pop_back()
		{
			//_finish--;
			erase(end()-1);
		}

		//resize的模拟实现,同样分为三种情况,resize扩容后会初始化，而reserve不用初始化也就是size（_finish不会变）
		void resize(size_t n,const T&v =T())//此处的T()类似于int(2),等价于int i=2,不过匿名构造下一行就会销毁
		{
			//举个例子_finish为8，_end为12，resize(5),
			//会把_finish变为5，resize(10)会插入两个v，resize(15)会扩容加初始化
			if (n <=capacity())
			{
				if (n < size())
				{
					_finish = _start + n;
				}
				else
				{
					size_t i = size();
					while (i!=n)
					{
						_start[i] = v;
						i++;
					}
					_finish = _start + n;
				}
			}
			else
			{
				reserve(n);
				size_t i = size();
				while (i != n)
				{
					_start[i] = v;
					i++;
				}
				_finish = _start + n;//如果是例子中的第二种情况_finish还在8处，所以要重新指向
			}
		}

		//深拷贝模拟,vector<int>v1(v);
		vector(vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end(nullptr)
		{
			//先new一个新空间,保证两个空间一致
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, v. size() * sizeof(T));
			
			//改正string的问题
			for (int i = 0; i < v.size(); i++)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_end = _start + v.capacity();
		}

		//swap的模拟实现
		void swap(vector<T>&v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end, v._end);
		}

		//=的模拟实现
		vector<T>&operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		//vector<int>v(10,1),模拟实现开10个空间，并初始化为1
		vector(size_t n,const T&x=T())//匿名对象为了别的类也可以用
		{
			resize(n, x);
		}
		vector(int n, const T& x = T())//匿名对象为了别的类也可以用
		{
			resize(n, x);
		}

		//支持多样类型的迭代器
		template<class TT>
		vector(TT first,TT last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

	private:
		iterator _start;//为开头的指针
		iterator _finish; //为实际数量的指针
		iterator _end; //为空间的指针
	};
}
 
//尾插push_back
void text1()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//[]的模拟实现
void text2()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (int i = 0; i < 6; i++)
	{
		v[i]++;
		cout << v[i] << " ";
	}
	cout << endl;
}

//insert的模拟实现，vector中的insert是用迭代器实现的
void text3()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	v.insert(v.begin() + 3, 7);
	for (int i = 0; i < 7; i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
	//记住insert以后就不要使用这个形参的迭代器了，因为它可能失效了
	auto  it = v.begin() + 3;//等价于下一行
	Ljw::vector<int>::iterator it1 = v.begin() + 3;
	*it = 10;
	cout << endl;
}

//erase的模拟实现，库里会返回删除位置的下一个位置,用的也是迭代器
//记住erase以后就不要使用这个形参的迭代器了，因为它可能失效了
//用erase测试删除所有偶数
void text4()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	v.insert(v.begin() + 3, 7);
	v.erase(v.begin()+4);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it=v.erase(it);
		}
		else//需要加一个else，如果两个偶数挨在一起的时候，
			   //删除第一个后，会返回下一个偶数的位置，然后没有else就会++就错过了一个
		it++;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//尾删
void text5()
{
	Ljw::vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(5);
	v.push_back(6);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.pop_back();
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//resize的模拟实现,同样分为三种情况,resize扩容后会初始化，而reserve不用初始化也就是size（_finish不会变）
void text6()
{
	Ljw::vector<int> v;
	v.reserve(10);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);
	v.push_back(8);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v.size()<<" "<<v.capacity() << endl;
	v.resize(12, 0);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//深拷贝模拟,vector<int>v1(v);
void text7()
{
	Ljw::vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	Ljw::vector<int>v1(v);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;	
}

//=的模拟实现
void text8()
{
	Ljw::vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	Ljw::vector<int>v1(v);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	v1.push_back(88);
	cout << endl;
	Ljw::vector<int>v2;
	v2 = v1;
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
}
//测试vector<string>v,
//vector上是深拷贝，是string的数组，
//使用reserve中的memcpy导致string对象发生浅拷贝
//修改resFerve
void text9()
{
	Ljw::vector<string>v;
	v.push_back("111");
	v.push_back("222");
	v.push_back("333");
	v.push_back("444");
	v.push_back("555");
	v.push_back("666");
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout <<endl;
}

//vector<int>(10,1),模拟实现开10个空间，并初始化为1
void text10()
{
	Ljw::vector<int>v(10,1);
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

//多种类型迭代器的测试
void text11()
{
	Ljw::vector<int>v(10, 1);
	Ljw::vector<int>v1(v.begin(), v.end());
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	Ljw::vector<string>v2(10, "111");
	Ljw::vector<string>v3(v2.begin(), v2.end());
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

	int a[] = { 1,2,3,4,5 };
	Ljw::vector<int>v4(a, a + 5);//左闭右开
	for (auto e : v4)
	{
		cout << e << " ";
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除

vector