【C++】用模板实现顺序表

冷不防 2022-06-07 08:08 195阅读 0赞

使用模板写出来的类或函数，与类型无关，下面用模板实现顺序表

template <typename T>
    class Vector
    {
    public:
    	typedef T* Iterator;
    	Vector()//构造函数
    		: _start(0)
    		, _finish(0)
    		, _endofstorage(0)
    	{}
    	Vector(const T* arr, size_t size)
    		: _start(new T[size])
    		, _finish(_start + size)//_finish(_start)
    		, _endofstorage(_start + size)
    	{
    		for (size_t i = 0; i < size; i++)
    			_start[i] = arr[i];//*_finish++ = arr[i];
    	}
    	Vector(const Vector<T>& v)//拷贝构造
    	{
    		size_t size = v.Size();
    		_start = new T[size];
    		for (size_t i = 0; i < size; i++)
    			_start[i] = v._start[i];
    		_finish = _start + size;
    		_endofstorage = _finish;
    	}
    	Vector& operator=(const Vector<T>& v)//赋值
    	{
    		size_t size = v.Size();
    		if (this != &v)
    		{
    			T* tmp = new T[size];
    			for (size_t i = 0; i < size; i++)
    				tmp[i] = v._start[i];
    			delete[] _start;
    			_start = tmp;
    			_finish = _start + size;
    			_endofstorage = _finish;
    		}
    		return *this;
    	}
    	~Vector()//析构
    	{
    		if (_start)
    		{
    			delete[] _start;
    			_start = NULL;
    		}
    	}
    	//Iterator
    	Iterator Begin()    //迭代器
    	{
    		return _start;
    	}
    	Iterator End()
    	{
    		return _finish;
    	}
    	//Modify//
    	void PushBack(const T& data)   //尾插
    	{
    		_CheckCapacity();
    		*_finish = data;
    		_finish++;
    	}
    	void PopBack()//尾删
    	{
    		assert(_start < _finish);
    		_finish--;
    	}
    	void Insert(size_t pos, const T& data)//任意位置插入
    	{
    		assert(pos <= Size());
    		_CheckCapacity();
    		for (size_t i = Size(); i > pos; i--)
    			_start[i] = _start[i - 1];
    		_start[pos] = data;
    		_finish++;
    	}
    	void Erase(size_t pos)//任意位置删除
    	{
    		assert(pos <= Size());
    		for (size_t i = pos; i < Size(); i++)
    			_start[i] = _start[i + 1];
    		_finish--;
    	}
    	/Capacity///
    	size_t Size()const//大小
    	{
    		return _finish - _start;
    	}
    	size_t Capacity()const//容量
    	{
    		return _endofstorage - _start;
    	}
    	bool Empty()const//叛空
    	{
    		if (_finish == _start)
    			return true;
    		return false;
    	}
    	void Resize(size_t newSize, const T& data = T())//改变大小
    	{
    		size_t oldsize = Size();
    		size_t capacity = Capacity();
    		if (newSize <= oldsize)
    			_finish = _start + newSize;
    		else if (newSize > oldsize && newSize <= capacity)
    		{
    			for (size_t i = oldsize; i < newSize;i++)
    				*_finish++ = data;
    			
    		}
    		else
    		{
    			T* tmp = new T[newSize];
    			for (size_t i = 0; i < oldsize; i++)
    				tmp[i] = _start[i];
    			for (size_t i = oldsize; i < newSize; i++)
    				tmp[i] = data;
    			delete[] _start;
    			_start = tmp;
    			_finish = _start + newSize;
    			_endofstorage = _start + newSize;
    		}
    	}
    	Element Access//
    	T& operator[](size_t index)
    	{
    		assert(index <= Capacity());
    		return _start[index];
    	}
    	const T& operator[](size_t index)const
    	{
    		assert(index <= Capacity());
    		return _start[index];
    	}
    	T& Front()//头元素
    	{
    		return *_start;
    	}
    	const T& Front()const
    	{
    		return *_start;
    	}
    	T& Back()//尾元素
    	{
    		return *(_finish-1);
    	}
    	const T& Back()const
    	{
    		return *(_finish-1);
    	}
    	void Clear()
    	{
    		_finish = _start;
    	}
    	template<class T>
    	friend ostream& operator<<(ostream& _cout, const Vector<T>& v)//输出运算符重载
    	{
    		for (size_t i = 0; i < v.Size(); i++)
    			_cout << v._start[i] <<" ";
    		return _cout;
    	}
    private:
    	void _CheckCapacity()
    	{
    		size_t size = Size();
    		size_t capacity = Capacity();
    		size_t newCapacity = 2 * capacity + 3;
    		if (size >= capacity)
    		{
    			T* tmp = new T[newCapacity];
    			for (size_t i = 0; i < size; i++)
    				tmp[i] = _start[i];
    			delete[] _start;
    			_start = tmp;
    			_finish = _start + size;
    			_endofstorage = _start + newCapacity;
    		}
    	}
    private:
    	T* _start;
    	T* _finish;
    	T* _endofstorage;
    };

memcpy实际上是浅拷贝，因此对于涉及到空间创建释放时，需要用for循环，for循环中的赋值运算符经过自己的重载，不会再出现浅拷贝的问题了。

如果使用迭代器实现任意位置的插入与删除，我们可以将代码改为如下：

void Insert(Iterator pos, const T& data)
    	{
    		_CheckCapacity();
    		Iterator i = End();
    		for (; i != pos; i--)
    			*i = *(i - 1);
    		*pos = data;
    		_finish++;
    	}
    	void Erase(Iterator pos)
    	{
    		Iterator end = End();
    		for (Iterator i = pos; i != --end; i++)
    			*(i) = *(i + 1);
    		_finish--;
    	}

迭代器实际上就是个指针，在使用任意位置插入的时候，如果finish==endofstorage时，我们会扩容，即（开辟更大的新空间，复制元素，释放旧空间），此时新空间已经不是旧空间了，原先的旧空间由于被释放了，End()已经找不到了。而我们前面写的插入，由于传参为插入位置的下标，不存在这样的问题。