【c++】模板实现动态Vector

不念不忘少年蓝@ 2022-07-12 09:36 223阅读 0赞

在C++标准库里Vector是一种数据结构，一种顺序容器。

其中的元素是严格按照现行顺序排列储存的，通常实现为动态数组，操作和常规的数组类型类似；不同的是，Vector里的存储空间分配自动完成，可以根据需要动态夸大和缩小。

实现Vector的方法有很多，而C++模板实现是相对比较简单的一种。

首先实现一下各个部分的函数：

Vector的构造函数：

//构造函数
    	Vector(Vector<T>&s)
    		:_size(s._size)
    		, _capacity(s._capacity)
    	{
    		_data = new T[_capacity];
    		for (size_t i = 0; i < _szie; i++)
    		{
    			_data[i] = s._data[i];
    		}
    	}

Vector的析构函数

//析构函数
    	~Vector()
    	{
    		delete[] _data;
    		_size = _capacity = 0;
    	}

Vector的尾部插入和删除数据

//尾部插入一个数据
    	void PushBack(const T& x)
    	{
    		_checkcapacity();
    		_data[_size++] = x;
    	}
    	
    	//尾部删除一个数据
    	void PopBack()
    	{
    		assert(_size);
    		_size--;
    	}

Vector的头部插入和删除数据

//头部插入一个数据
    	void PushFront(const T& x)
    	{
    		_checkcapacity();
    		if (_size == 0)
    		{
    			_data[_size++] = x;
    		}
    		else
    		{
    			for (size_t i = _size; i > 0; i--)
    			{
    				_data[i] = _data[i-1];
    			}
    			_data[0] = x;
    			_size++;
    		}
    	}
    
    	//头部删除一个数据
    	void PopFront()
    	{
    		assert(_size);
    		for (size_t i = 0; i < _size; i++)
    		{
    			_data[i] = _data[i + 1];
    		}
    		_size--;
    	}

检测Vector的内存是否满并且开辟新的空间

//检查内存是否满并开辟新的空间
    	void _checkcapacity()
    	{
    		if (_size >= _capacity)
    		{
    			size_t newcapacity = _capacity * 2 + 3;
    			T* tmp = new T[newcapacity];
    
    			for (size_t i = 0; i < _size; i++)
    			{
    				tmp[i] = _data[i];
    			}
    			delete[] _data;
    			_data = tmp;
    			_capacity = newcapacity;
    		}
    	}

任意位置的插入数据和删除数据

//任意位置插入一个数据,默认位置是在pos的前面一个位置
    	void Insert(int pos, const T& x)
    	{
    		assert(pos >= 0 && pos <= (int)_size);
    		_checkcapacity();
    		for (int i = (int)_size; i>=pos; i--)
    		{
    			_data[i] = _data[i - 1];
    		}
    		_data[pos - 1] = x;
    		_size++;
    	}
    
    	//删除任意位置的数据
    	void Erase(size_t pos)
    	{
    		assert(_size);
    		fpr(size_t i = pos; i < _size - 1; i++)
    		{
    			_data[i] = _data[i + 1];
    		}
    		_size--;
    	}

拷贝构造函数

//拷贝构造
    	Vector(const Vector<T>& v)
    	{
    		_data = new T[v._size];
    		for (size_t i = 0; i < v._size; i++)
    		{
    			_data[i] = v._data[i];
    		}
    		_size = v._size; _capacity = v._size;
    	}

赋值运算符的重载函数

//赋值运算符重载
    	Vector<T>& operator=(Vector<T> v)
    	{
    		if (this != v)
    		{
    			T* tmp = new T[_capacity];
    			for (size_ i = 0; i < _size; i++)
    			{
    				tmp[i] = v._data[i];
    			}
    		}
    		_data = tmp;
    		_size = v._size;
    		_capacity = v._capacity; 
    		return *this;
    	}

接下来用C++模板实现一下整体的代码以及测试函数

vector.h
    #include<iostream>
    using namespace std;
    
    #include<assert.h>
    #include<string>
    
    template <typename T>
    class Vector
    {
    public:
    	Vector()
    		:_data()
    		, _size()
    		, _capacity()
    	{
    
    	}
    
    	//构造函数
    	Vector(Vector<T>&s)
    		:_size(s._size)
    		, _capacity(s._capacity)
    	{
    		_data = new T[_capacity];
    		for (size_t i = 0; i < _szie; i++)
    		{
    			_data[i] = s._data[i];
    		}
    	}
    
    
    	//析构函数
    	~Vector()
    	{
    		delete[] _data;
    		_size = _capacity = 0;
    	}
    
    	//拷贝构造
    	Vector(const Vector<T>& v)
    	{
    		_data = new T[v._size];
    		for (size_t i = 0; i < v._size; i++)
    		{
    			_data[i] = v._data[i];
    		}
    		_size = v._size; _capacity = v._size;
    	}
    
    	//赋值运算符重载
    	Vector<T>& operator=(Vector<T> v)
    	{
    		if (this != v)
    		{
    			T* tmp = new T[_capacity];
    			for (size_ i = 0; i < _size; i++)
    			{
    				tmp[i] = v._data[i];
    			}
    		}
    		_data = tmp;
    		_size = v._size;
    		_capacity = v._capacity; 
    		return *this;
    	}
    
    
    	//任意位置插入一个数据,默认位置是在pos的前面一个位置
    	void Insert(int pos, const T& x)
    	{
    		assert(pos >= 0 && pos <= (int)_size);
    		_checkcapacity();
    		for (int i = (int)_size; i>=pos; i--)
    		{
    			_data[i] = _data[i - 1];
    		}
    		_data[pos - 1] = x;
    		_size++;
    	}
    
    	//删除任意位置的数据
    	void Erase(size_t pos)
    	{
    		assert(_size);
    		fpr(size_t i = pos; i < _size - 1; i++)
    		{
    			_data[i] = _data[i + 1];
    		}
    		_size--;
    	}
    
    	//查找一个数据
    	int Find(const T& x)
    	{
    		for (size_t i = 0; i < _size; i++)
    		{
    			if (_data[i] == x)
    			{
    				return i;
    			}
    		}
    		return -1;
    	}
    
    	//尾部插入一个数据
    	void PushBack(const T& x)
    	{
    		_checkcapacity();
    		_data[_size++] = x;
    	}
    	
    	//尾部删除一个数据
    	void PopBack()
    	{
    		assert(_size);
    		_size--;
    	}
    
    
    	//头部插入一个数据
    	void PushFront(const T& x)
    	{
    		_checkcapacity();
    		if (_size == 0)
    		{
    			_data[_size++] = x;
    		}
    		else
    		{
    			for (size_t i = _size; i > 0; i--)
    			{
    				_data[i] = _data[i-1];
    			}
    			_data[0] = x;
    			_size++;
    		}
    	}
    
    	//头部删除一个数据
    	void PopFront()
    	{
    		assert(_size);
    		for (size_t i = 0; i < _size; i++)
    		{
    			_data[i] = _data[i + 1];
    		}
    		_size--;
    	}
    
    
    	//检查内存是否满并开辟新的空间
    	void _checkcapacity()
    	{
    		if (_size >= _capacity)
    		{
    			size_t newcapacity = _capacity * 2 + 3;
    			T* tmp = new T[newcapacity];
    
    			for (size_t i = 0; i < _size; i++)
    			{
    				tmp[i] = _data[i];
    			}
    			delete[] _data;
    			_data = tmp;
    			_capacity = newcapacity;
    		}
    	}
    
    	void Print()
    	{
    		for (size_t i = 0; i < _size; i++)
    		{
    			cout << _data[i] << "  ";
    		}
    		cout << endl;
    	}
    
    
    protected:
    	T* _data;
    	size_t _size;
    	size_t _capacity;
    };
    
    
    //尾部插入和删除数据
    void Test1()
    {
    	Vector<int> v;
    	v.PushBack(1);
    	v.Print();
    	v.PushBack(2);
    	v.Print();
    	v.PushBack(4);
    	v.Print();
    
    	v.PopBack();
    	v.Print();
    	v.PopBack();
    	v.Print();
    	v.PopBack();
    	v.Print();	
    }
    
    
    //头部插入和删除数据、任意插入
    void Test2()
    {
    	Vector<int> v;
    	//头部插入
    	v.PushFront(4);
    	v.Print();
    	v.PushFront(5);
    	v.Print();
    	v.PushFront(6);
    	v.Print();
    
    	//任意位置插入
    	v.Insert(1, 9);
    	v.Print();
    	v.Insert(2, 11);
    	v.Print(); 
    	v.Insert(3, 14);
    	v.Print();
    
    	//头部删除
    	v.PopFront();
    	v.Print();
    	v.PopFront();
    	v.Print();	
    	v.PopFront();
    	v.Print();
    }
    
    
    vector.cpp
    #pragma once
    #include"vector.h"
    int main()
    {
    	Test1();
    	Test2();
    	system("pause");
    	return 0;
    }