自己动手写vector

时间:2023-01-13 09:03:39

    最近学习c++的STL,把STL中的vector自己写了一下,写的过程中对c++进行学习。

主要的几个模块:

 (1)构造析构函数、拷贝构造和赋值函数(类的几个基本函数)
(2)增加、删除函数
(3)遍历函数
(4)大小及判空函数
(5)其它(swap或者assign)

// MyVector.cpp : 定义控制台应用程序的入口点。
/*******************我的Vector实现*********************************
**功能:自己动手写stl中的vector
**作者:谢凡凡
****************************************************/
#include "stdafx.h"
#include <iostream>
#include <assert.h>

using namespace std;

//vector类模板
template <class T>
class MyVector
{
public:
	typedef T* iterator;           //迭代器类型
	typedef T* pointer;
	typedef T & reference;
//构造函数
	MyVector():start(0),endx(0),end_of_storage(0),nsize(0),ncapacity(0){}             //列表初始化  默认的构造函数
	MyVector(int nSize,const T& val)                     //n个元素,且初始化为val
	{
		if (!nSize)
		{
			start = 0;
			endx = 0;
			end_of_storage = 0;
			nsize = 0;
			ncapacity = 0;
		}
		else
		{
			int iTotalLen = 1;
			while (iTotalLen < nSize)                     //空间大小是2倍增长
			{
				iTotalLen *= 2;
			}
			start = new T[iTotalLen];                     //申请空间
			iterator start_cc = start;
			endx = start + nSize;
			end_of_storage = start + iTotalLen;
			nsize = nSize;
			ncapacity = iTotalLen;
			while(nSize--)
			{
				*start_cc++ = val;
			}
		}
	}
	MyVector(int nSize)                                       //n个元素,初始化为0
	{
		if (!nSize)
		{
			start = 0;
			endx = 0;
			end_of_storage = 0;
			nsize = 0;
			ncapacity = 0;
		}
		else
		{
			int iTotalLen = 1;
			while (iTotalLen < nSize)
			{
				iTotalLen *= 2;
			}
			start = new T[iTotalLen];                     //申请空间
			iterator start_cc = start;                    //一份拷贝
			endx = start + nSize;
			end_of_storage = start + iTotalLen;
			nsize = nSize;
			ncapacity = iTotalLen;			
		}
	}
	MyVector(const MyVector& mv)                              //拷贝构造函数
	{
		if (this == &mv)
		{
			return ;
		}
		if (mv.empty())
		{
			start = 0;
			endx = 0;
			end_of_storage = 0;
			nsize = 0;
			ncapacity = 0;
		}
		else
		{
			int iTotalLen = mv.capacity();                            //当前容器最大容量
			int isize = mv.size();
			start = new T[iTotalLen];
			endx  = start + isize;
			end_of_storage = start + iTotalLen;
			nsize = isize;
			ncapacity = iTotalLen;
		}
	}

	~MyVector()                               //析构函数  注意对容器中的元素调用析构函数
	{
		iterator index;
		for (index = start;index < end_of_storage;++index)
		{
			index->~T();                       //调用容器中的元素的析构函数
		}
		delete [] start;
		start = NULL;
		endx  = NULL;
		end_of_storage = NULL;
		nsize = 0;
	}

	iterator begin() const                    //获取起始迭代器
	{
		return start;
	}
	iterator end() const
	{
		return endx;
	}

	int size() const                              //返回容器中元素的个数
	{
		return nsize;       
	}
	void resize(int newSize,const reference x);       //调整容器尺寸
	int capacity() const                             //获取容器最多可以存储多少个元素
	{
		return ncapacity;
	}
	bool empty() const                               //容器是否为空
	{
		return (start == endx);
	}
	reference operator[](int n)                      //对下标运算符进行重载,返回该位置的一个引用
	{
		assert(n >= 0 && n < ncapacity);
		return *(start + n);
	}
	reference operator=(const T& other)             //赋值运算符
	{
		if (this != &other)
		{
			if (other.empty())
			{
				this->clear();
			}
			else
			{
				if (ncapacity < other.capacity())                //左边空间不够  重新分配足够的空间
				{
					start = new T[other.capacity()];
					endx  = start + other.nsize;
					end_of_storage = start + other.capacity();
					nsize = other.nsize;
					ncapacity = other.ncapacity;
					for (int index =0;index < nsize;++index)
					{
						*(start + index) = *(other.begin() + index);
					}
				}                                                //左边有足够空间  用原来的空间
				else
				{
					endx  = start + other.nsize;
					end_of_storage = start + other.capacity();
					nsize = other.nsize;
					ncapacity = other.ncapacity;
					for (int index =0;index < nsize;++index)
					{
						*(start + index) = *(other.begin() + index);
					}					
				}
			}
			return *this;
		}
	}
	reference front()                         //返回首元素引用
	{
		return *start;
	}
	reference back()                          //返回尾元素引用
	{
		return *(endx - 1);
	}
	reference at(int pos)                     //返回指定位置的一个引用  超出范围应该抛出异常
	{
		if (pos >= 0 && pos < ncapacity)
		{
			return *(start + pos);
		}
		else                                   //抛出异常
		{
			throw out_of_range("MyVector out of range"); 
		}
	}

	void push_back(const T& x)                 //尾端插入
	{
		if (endx != end_of_storage)            //容器还有余量
		{
			*endx = x;
			nsize = nsize + 1;
			endx++;
		}
		else                                   //容器没有余量,重新分配空间,并进行数据拷贝,然后删除原来的空间
		{
			insert(end(),1,x);
		}
	}
	void insert(iterator it,const T& x)          //某一个元素前  增加一个元素x
	{
		insert(it,1,x);
	}
	void  insert(iterator it,int n,const T& x);       //某一个元素前  增加n个元素x
	void pop_back()                                   //删除尾端元素
	{
		endx--;
		endx->~T();
		nsize--;
	}
	void erase(iterator pos)                          //删除指定位置的元素
	{
		erase(pos,pos+1);
	}
	void erase(iterator _first,iterator _end)             //删除范围元素  [_first,_end)
	{
		int j = end() - _end;
		for (int index = 0;index < j;++index)             //后边的元素前移
		{
			*(_first + index) = *(_end + index);
		}
		while(end() - _first > j)
		{
			pop_back();
		}
	}
	void clear()                                          //清除容器中的所有元素
	{
		erase(start,endx);
	}
	void swap(MyVector& other)                                   //交换数据
	{
		MyVector tem;
		tem = other;
		other = *this;
		*this = tem;
	}
	void assign(int n,const T& x)                  //给容器中某一个位置赋值
	{
		*(start + n - 1) = x;
	}
private:
	iterator start;                //指向数据区起始地址
	iterator endx;                 //指向数据区末尾地址
	iterator end_of_storage;       //指向容量的末尾,一般留有多余的空间

	int nsize;                     //当前容器中元素个数
	int ncapacity;                 //容器可以存储最多元素个数

};

template <class T>
void MyVector<T>::insert(iterator it,int n,const T& x)       //某一个元素前  增加n个元素x
{
	iterator old_start = start;               //原来的指针
	iterator old_endx = endx;
	iterator new_start;                       //不扩容的话  指向old_start,扩容的话指向new_start
	int numofmove = (endx - it);              //从it到endx中有多少个元素需要向后移动
	bool bNeedChange = false;
	if (endx + n > end_of_storage)            //剩余空间不够了
	{
		bNeedChange = true;
		const int old_size = size();
		const int len = old_size + n;        //加新的元素  有多少个元素
		int it1 = 1;
		while (it1 < len)
		{
			it1 *= 2;
		}

		start = new T[it1];
		endx = start + len;
		end_of_storage = start + it1;
		new_start = start;
		ncapacity = it1;
		nsize = len;
	}
	else
	{
		new_start = start;
		endx = endx + n;
		nsize = nsize + n;
	}
	iterator item = old_start;
	while (item < it)                  //拷贝原始数据
	{
		*new_start++ = *item++; 
	}
	iterator itend = endx;
	iterator old_endx_cc = old_endx;
	while (numofmove--)
	{
		*(--itend) = *(--old_endx_cc);
	}
	while (n--)                       //插入特定数据
	{
		*new_start++ = x;
	}
	if (bNeedChange)                 //需要释放原始空间
	{
		while (old_start != old_endx)
		{
			old_start->~T();
			old_start++;
		}
	}
}



int _tmain(int argc, _TCHAR* argv[])
{
	struct Point
	{
		Point(){}
		Point(int a=0,int b=0):x(a),y(b){}
		int x,y;
	};


	cout<<sizeof(Point)<<endl;
	MyVector<Point>  myvec(3);
	cout<<myvec.size()<<endl;

	for (int i=1;i<3;++i)
	{
		Point ptem(i,2*i);
		myvec.push_back(ptem);
	}
	
	for (MyVector<Point>::iterator it = myvec.begin();it != myvec.end();++it)
	{
		cout<<it->x<<" "<<it->y<<endl;
	}

	return 0;
}

自己写vector的一些感受:

(1)vector其实比string简单
     string看似简单,其实内部函数很多,而且有很多重载函数,实现不麻烦,但是很繁琐。vector的函数较少,重载函数也不多,比较简便。
(2)vector使用的c++模板技术
     这是我写vector的目的之一,学习一下模板的用法,也没那么难。使用模板技术,则该容器可以存储任意类型(包括内置类型和自定义类型)。
(3)对new运算符理解更深刻了
     vector底层数据结构是动态数组,长度可以自动增长,所以使用的new分配内存。new一个内置类型很容易理解(eg. int),但是new一个类对象或者类对象数组,就复杂些了。
     a.分配一块足够大的内存,足以存储类对象或者类对象数组
     b.对类对象调用构造函数进行初始化
     c.返回一个指针,指向分配的内存块
     这里边的调用构造函数对类对象初始化,很重要。