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

时间：2022-03-27 19:52:06

        C++之所以得到这么多人的喜欢，是因为它既具有面向对象的概念，又保持了C语言高效的特点。而对于STL中：vector: C++中的一种数据结构,确切的说是一个类.它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的。 首先在程序开头处加上： 

    #include<vector>以包含所需要的类文件vector，还有一定要加上using namespace std。用模板写函数或类都与类型无关，因此，STL中都是用模板实现容器，下面我们来介绍用模板实现顺序表。

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


typedef int DataType;
class Vector
{
public:
	//声明为explicit的构造函数不能在隐式转换中使用
	explicit Vector(size_t capacity = 3)
		:_pData(new DataType[capacity])//开辟空间
		, _size(0)
		, _capacity(capacity)
	{}

	// 有n个值为data的元素
	Vector(size_t n, const DataType& data)
	{

	}

	Vector(const Vector& v)
		: _capacity(v._capacity)
		, _size(v._size)
	{
		_pData = new DataType[_capacity];
		for (size_t idx = 0; idx < _size; ++idx)
			_pData[idx] = v._pData[idx];
	}

	Vector& operator=(const Vector& v)
	{
		if (this != &v)
		{
			DataType*temp = new DataType[v._capacity];
			for (int i = 0; i < (int)v._size; ++i)
			{
				temp[i] = v._pData[i];
			}
			delete _pData;
			_pData = temp;
			_capacity = v._capacity;
			_size = v._size;
		}
		return *this;
	}

	~Vector()
	{
		if (NULL != _pData)
		{
			delete _pData;
			_pData = NULL;
			_size = 0;
			_capacity = 0;
		}
	}


	//功能函数
	void PushBack(const DataType& data);
	void PopBack();
	void Insert(size_t pos, const DataType& data);
	void Erase(size_t pos);
	int Find(const DataType& data)const;
	void Clear();
	size_t Size()const;
	void ReSize(size_t size, const DataType& data = DataType());
	size_t Capacity()const;
	bool Empty()const;
	DataType& Front();
	const DataType& Front()const;
	DataType& Back();
	const DataType& Back()const;
	void Assign(size_t n, const DataType& data = DataType());
	DataType& operator[](size_t index);
	const DataType& operator[](size_t index)const;
	DataType& At(size_t n);
	const DataType& At(size_t n)const;

	void PrintVector();


private:
	//检查容量是否已满
	void CheckCapacity()
	{
		if (_size >= _capacity)//如果容量满，则扩容
		{
			DataType*temp = new DataType[_capacity * 2];
			for (int i = 0; i < _size; i++)
			{
				temp[i] = _pData[i];
			}
			delete _pData;
			_pData = temp;
			_capacity *= 2;
		}
	}

	friend std::ostream& operator<<(std::ostream& _cout, const Vector& v);
private:
	DataType* _pData;
	size_t _capacity;
	size_t _size;
};


void Vector::PrintVector()
{
	for (int i = 0; i < (int)_size; i++)
	{
		cout << _pData[i] << ' ';
	}
	cout << endl;
}


//尾插函数
void Vector::PushBack(const DataType& data)
{
	CheckCapacity();
	_pData[_size++] = data;
}

//尾删
void Vector::PopBack()
{
	if (!Empty())
	{
		_size--;
	}
}


//任意位置的插入函数
void Vector::Insert(size_t pos, const DataType& data)
{
	assert(_size >= pos);
	CheckCapacity();
	for (int i = _size; i >= pos; i--)
	{
		_pData[i] = _pData[i - 1];//将第_size个元素赋值给第_size+1个元素
	}
	_pData[pos - 1] = data;//将data赋给第pos个元素
	_size++;
}

//删除
void Vector::Erase(size_t pos)
{
	assert(_size >= pos);
	if (!Empty())
	{
		for (int i = pos; i <_size; i++)//如果从后往前，会引起覆盖
		{
			_pData[i - 1] = _pData[i];
		}
		_size--;
	}

}

//查找
int Vector::Find(const DataType& data)const
{
	for (int i = 0; i < _size; i++)
	{
		if (_pData[i] == data)
		{
			return i + 1;//找到返回data所在的位置
		}
	}
	return 0;//没找到，返回0
}

//清空
void Vector::Clear()
{
	if (NULL != _pData)
	{
		delete _pData;
		_pData = NULL;
		_size = 0;
		_capacity = 0;
	}
}

//有效元素个数
size_t Vector::Size()const
{
	return _size;
}

//改变Vector中_size的大小
void Vector::ReSize(size_t size, const DataType& data)
//默认参数都是在声明时定义的，定义的时候不能有，否则会造成重定义的问题
{
	if (size < _size)
	{
		_size = size;
	}
	else if (size>_size)
	{
		int _oldsize = _size;
		_size = size;
		while (1)
		{
			if (_size < _capacity)
			{
				break;
			}
			else
			{
				CheckCapacity();
			}
		}
		CheckCapacity();
		for (int i = _oldsize; i < _size; i++)
		{
			_pData[i] = data;
		}
	}
}

//容量
size_t Vector::Capacity()const
{
	return _capacity;
}

//判空函数
bool Vector::Empty()const
{
	return 0 == _size;
}

//第一个元素
DataType& Vector::Front()
{
	return _pData[0];
}


const DataType& Vector::Front()const//常对象调用
{
	return _pData[0];
}

//最后一个元素
DataType& Vector::Back()
{
	return _pData[_size - 1];
}


const DataType& Vector::Back()const
{
	return _pData[_size - 1];
}

//[]的重载函数
DataType& Vector::operator[](size_t index)
{
	assert(index >= 0 && index < _size);
	return _pData[index];
}

const DataType& Vector::operator[](size_t index)const
{
	assert(index >= 0 && index < _size);
	return _pData[index];
}

//返回一个引用位置为n的元素
DataType& Vector::At(size_t n)
{
	assert(n>0 && n <= _size);
	return _pData[n - 1];
}


const DataType& Vector::At(size_t n)const
{
	assert(n>0 && n <= _size);
	return _pData[n - 1];
}





void FunTest1()
{
	Vector v;
	v.PushBack(1);
	v.PushBack(2);
	v.PushBack(3);
	v.PushBack(4);
	v.PrintVector();

	v.PopBack();
	v.PrintVector();

	v.Insert(1, 66);
	v.Insert(3, 88);
	v.PrintVector();

	v.Erase(2);
	v.PrintVector();

	cout << v.Find(88) << endl;

	//v.Clear();
}

void FunTest2()
{
	Vector v;
	v.PushBack(1);
	v.PushBack(2);
	v.PushBack(3);
	v.PushBack(4);
	cout << v.Size() << endl;

	v.ReSize(8);
	v.PrintVector();

	cout << v.Capacity() << endl;
}

int main()
{
	FunTest1();
//	FunTest2(); 
	system("pause");

	return 0;
}
      以上就是模板实现顺序表，部分注释已经在代码出给出。通过使用模板实现Vector可以提高代码的复用度，vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。vector是一块连续分配的内存，从数据安排的角度来讲，和数组极其相似，不同的地方就是：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。

      而对于模板来说：

【优点】
模板复用了代码，节省资源，更快的迭代开发，C++的标准模板库(STL)因此而产生。
增强了代码的灵活性。
【缺点】
模板让代码变得凌乱复杂，不易维护，编译代码时间变长。
出现模板编译错误时，错误信息非常凌乱，不易定位错误。


标签：

相关文章