Vector顺序表的实现

#include<stdio.h>
#include<Windows.h>
#define SUCCESS           			 1 // 成功							
#define ERROR            			 -1 // 失败							
#define MALLOC_ERROR			 -2 // 申请内存失败							
#define INDEX_ERROR		 	 -3 // 错误的索引号							


template <class T_ELE> // 存储的元素类型为 T_ELE
class Vector{
public:
	Vector();
	Vector(DWORD dwSize);
	~Vector();
public:
	DWORD	at(DWORD dwIndex, OUT T_ELE* pEle);		//根据给定的索引得到元素		  实现	
	DWORD   push_back(T_ELE Element);				//将元素存储到容器最后一个位置	  实现 
	VOID	pop_back();								//删除最后一个元素				  实现
	DWORD	insert(DWORD dwIndex, T_ELE Element);	//向指定位置新增一个元素		  实现	
	DWORD	capacity();					//返回在不增容的情况下,还能存储多少元素	  实现		
	VOID	clear();					//清空所有元素								  实现
	BOOL	empty();					//判断Vector是否为空 返回true时为空			  实现	
	VOID	erase(DWORD dwIndex);		//删除指定元素			
	DWORD	size();						//返回Vector元素数量的大小			
private:
	BOOL	expand();
private:
	DWORD  m_dwIndex;					//下一个可用索引			
	DWORD  m_dwIncrement;				//每次增容的大小			
	DWORD  m_dwLen;						//当前容器的长度			
	DWORD  m_dwInitSize;				//默认初始化大小			
	T_ELE* m_pVector;					//容器指针			
};

template <class T_ELE>
Vector<T_ELE>::Vector():m_dwInitSize(100), m_dwIncrement(5)
{
	//1.创建长度为m_dwInitSize个T_ELE对象	
	m_pVector = new T_ELE[m_dwInitSize];

	//2.将新创建的空间初始化
	memset(m_pVector, 0, 100 * sizeof(T_ELE));

	//3.设置其他值
	this->m_dwIndex = 0;
	this->m_dwLen = 0;
}

template <class T_ELE>
Vector<T_ELE>::Vector(DWORD dwSize):m_dwIncrement(5)
{
	//1.创建长度为dwSize个T_ELE对象	
	m_pVector = new T_ELE[dwSize];

	//2.将新创建的空间初始化		
	memset(m_pVector, 0, sizeof(T_ELE)*dwSize);

	//3.设置其他值
	this->m_dwIndex = 0;
	this->m_dwLen = dwSize;
	this->m_dwInitSize = dwSize;
}		

template <class T_ELE>
Vector<T_ELE>::~Vector()
{
	delete[] m_pVector;
}

template <class T_ELE>
BOOL Vector<T_ELE>::expand()
{
	// 1. 计算增加后的长度
	DWORD temp_len = this->m_dwLen;

	// 2. 申请空间	
	Vector* p_new_vector = new Vector(this->m_dwLen + this->m_dwIncrement);
	if (p_new_vector == NULL){
		return false;
	}

	// 3. 将数据复制到新的空间
	for (DWORD i = 0; i < temp_len; i++){
		p_new_vector[i] = this->m_pVector[i];
	}

	// 4. 为各种属性赋值
	p_new_vector->m_dwLen = this->m_dwLen + this->m_dwIncrement;
	p_new_vector->m_dwIndex = this->m_dwIndex;
	p_new_vector->m_dwIncrement = this->m_dwIncrement;
	p_new_vector->m_dwInitSize = this->m_dwInitSize;

	// 5. 释放原来空间
	Vector* p_temp_vector = NULL;
	p_temp_vector->m_pVector = this->m_pVector;
	this->m_pVector = p_new_vector->m_pVector;
	delete[] p_temp_vector;
	return true;
}

template <class T_ELE>
DWORD  Vector<T_ELE>::push_back(T_ELE Element)
{
	//1.判断是否需要增容,如果需要就调用增容的函数
	if (this->m_dwIndex >= this->m_dwLen){
		this->expand();
	}

	//2.将新的元素复制到容器的最后一个位置
	this->m_pVector[m_dwIndex + 1] = Element;

	//3.修改属性值
	this->m_dwLen = this->m_dwLen + 1;
	return SUCCESS;
}

template <class T_ELE>
DWORD  Vector<T_ELE>::insert(DWORD dwIndex, T_ELE Element)
{
	//1.判断是否需要增容,如果需要就调用增容的函数
	if (this->m_dwIndex >= this->m_dwLen){
		this->expand();
	}
	
	//2.判断索引是否在合理区间
	if (dwIndex < 0 || dwIndex > this->m_dwIndex){
		return INDEX_ERROR;
	}

	//3.将dwIndex之后的元素后移
	for (int i = dwIndex; i < this->m_dwLen-1; i++){
		this->m_pVector[i + 1] = this->m_pVector[i];
	}


	//4.将Element元素复制到dwIndex位置
	this->m_pVector[dwIndex] = Element;


	//5.修改属性值
	this->m_dwIndex = this->m_dwIndex + 1;
	return SUCCESS;
}

template <class T_ELE>
DWORD Vector<T_ELE>::at(DWORD dwIndex, T_ELE* pEle)
{
	//判断索引是否在合理区间
	if (dwIndex < 0 || dwIndex > this->m_dwLen){
		return INDEX_ERROR;
	}

	//将dwIndex的值复制到pEle指定的内存									
	*pEle = this->m_pVector[dwIndex];
	return *pEle;
}

template<class T_ELE>
void Vector<T_ELE>::pop_back(){ //最后一个元素置为零
	//最后一个元素置为零
	this->m_pVector[this->m_dwIndex] = 0;

	//修改属性值
	this->m_dwIndex = this->m_dwIndex - 1;
}

template<class T_ELE>
DWORD Vector<T_ELE>::capacity(){//返回在不增容的情况下,还能存储多少元素
	return this->m_dwLen - this->m_dwIndex;
}

template<class T_ELE>
void Vector<T_ELE>::clear(){ //清空所有元素			
	for (DWORD i = 0; i < this->m_dwLen; i++){
		this->m_pVector[i] = 0;
	}
}

template<class T_ELE>
BOOL Vector<T_ELE>::empty(){//判断Vector是否为空 返回true时为空	
	if (this->m_pVector[0] != 0){
		return false;		
	}
	return true;
}

template<class T_ELE>
DWORD Vector<T_ELE>::size(){
	//printf("m_dwIndex: %d\n", this->m_dwIndex);
	//printf("m_dwLen: %d\n", this->m_dwLen);
	DWORD temp_vector_size = 0;
	for (DWORD i = 0; i < this->m_dwLen; i++){
		if (this->m_pVector[i] != 0){
			temp_vector_size += 1;
		}else{
			break;
		}
	}
	return temp_vector_size;
}

template<class T_ELE>
VOID Vector<T_ELE>::erase(DWORD dwIndex){

	//判断索引是否在合理区间
	if (dwIndex < 0 || dwIndex > this->m_dwIndex){
		return INDEX_ERROR;
	}

	//进行前移替换
	for (int i = dwIndex; i < this->m_dwIndex; i--){
		this->m_pVector[i] = this->m_pVector[i + 1];
	}

	//修改属性值
	this->m_dwIndex = this->m_dwIndex - 1;
}

int main(){
	Vector<int>* myVector = new Vector<int>(50);

	printf("m_dwLen: %d\n", myVector->size());
	
	
	myVector->push_back(111);
	
	printf("m_dwLen: %d\n", myVector->size());

	
	return 0;
}
上一篇:32/64 MinHook 库的使用方式


下一篇:从汇编角度看i++ 和++i的区别