C++实现的泛型List类分享
额,不要说我三心二意:一边在看.NET和CLR的原理、一边在看JavaScript、一边在看Java;有时看算法有时看Unity、Hibernate;有时看Hadoop有时看Redis;现在又开始看C++了。
以前觉得无论什么语言嘛,其实都差不多,核心思想基本一致。现在又不这么想了,其实语言的选择对软件的性能、可靠性、开发成本之类的关系很大,所以觉得还是要多接触一些比较核心的东西——那么自然是C++了。以前在学校学的C++完全是酱油,太水了基本没啥用,用来用去和C差不多,所以现在要自己学啦。
废话不说了,第一个任务就是山寨.NET类库里面的List<T>泛型类,还偷看过它的源代码。那么现在就开始用C++进行“山寨”吧。(所以这个类的名字就是ListSZ,SZ=山寨,不是“单维零下标”数组。)
当然刚入手还是碰了不少钉子,最主要的是模版的实现为啥不支持放在cpp里啊?搞得我折腾了老半天。(感谢KC提供技术支持,所以KC要赶快请我吃饭)
主要实现了如下功能:
1.自动扩容(直接抄的List的实现方式,容量不够时翻倍,但InsertRange的时候除外);
2.Add添加到末尾,AddRange在末尾添加多个,Insert在中间插入一个或多个;
3.Remove删除最后一个或其中一个,RemoveRange删除其中一片。
MakeRoom是在中间生成一片空的区域,原来的元素全往后移。EnsureCapacity在容量不够时扩容……
直接贴代码:
#include<stdexcept> #include"stdafx.h" #include<algorithm> #pragmaonce template<typenameT>classListSZ { private: T*_mArray; int_capacity; int_elementCount; constintDEFAULT_CAPACITY=8; voidEnsureCapacity(intnewCount) { if((__int64)_elementCount+newCount>=INT_MAX) throwstd::out_of_range("ListSZsupportsupto2^31-1elements."); //If_elementCount=_capacity-1,thebufferisfull if(_elementCount+newCount>_capacity) { intnew_capacity=_capacity>=INT_MAX/2?INT_MAX:_capacity<<1; if(new_capacity<_elementCount+newCount) new_capacity=std::min((__int64)INT_MAX,(__int64)(_elementCount+newCount)<<1); /*if(new_capacity<_elementCount+newCount) new_capacity=((__int64)(_elementCount+newCount)<<1)>=INT_MAX?INT_MAX,(_elementCount+newCount)<<1; */ T*new_buffer=newT[new_capacity]; memcpy(new_buffer,_mArray,sizeof(T)*_elementCount); delete[]_mArray; _mArray=new_buffer; _capacity=new_capacity; } } voidMakeRoom(intindex,intcount) { if(index>=_elementCount-1)return; EnsureCapacity(count); intmove_count=_elementCount-index; memmove(_mArray+index+count,_mArray+index,move_count*sizeof(T)); memset(_mArray+index,0,count*sizeof(T)); } public: ListSZ():ListSZ(DEFAULT_CAPACITY){}; ListSZ(intcapacity) { if(capacity<=0) throwstd::invalid_argument("Thecapacityofthelistcannotbelessthan1."); _capacity=capacity; _mArray=newT[_capacity]; //_mArray=(T*)malloc(sizeof(T)*_capacity); memset(_mArray,0,_capacity*sizeof(T)); } ListSZ(constT*source,intelementCount):ListSZ(elementCount) { Insert(source,0,elementCount,0); } ~ListSZ() { delete[]_mArray; } TGetElement(intindex) { if(index<0||index>=_elementCount) throwstd::invalid_argument("Theindexisoutsizeoftheboundaryoflist."); return*(_mArray+index); } voidAdd(Tvalue) { EnsureCapacity(1); *(_mArray+_elementCount)=value; _elementCount++; } voidAddRange(T*source,intcount) { Insert(source,0,count,_elementCount); } voidInsert(Tvalue,intindex) { if(index<0||index>=_elementCount) throwstd::invalid_argument("Theindexisoutsizeoftheboundaryoflist."); MakeRoom(index,1); *(_mArray+index)=value; _elementCount++; } voidInsert(constT*source,intelementCount,intinsertIndex) { Insert(source,0,elementCount,insertIndex); } voidInsert(constT*source,intstartIndex,intcount,intinsertIndex) { if(count<=0) throwstd::invalid_argument("Thecountofelementstobeinsertedcannotlessthan1."); if(insertIndex<0||insertIndex>_elementCount) throwstd::invalid_argument("Thetargetindexisoutsideoftheboundaryoflist."); EnsureCapacity(_elementCount+count); MakeRoom(insertIndex,count); memcpy(_mArray+insertIndex,source+startIndex,count*sizeof(T)); _elementCount+=count; } TRemove() { if(_elementCount>0) { _elementCount--; return*(_mArray+_elementCount); } returnNULL; } TRemove(intindex) { if(index<0||index>=_elementCount) throwstd::invalid_argument("Theindexisoutsizeoftheboundaryoflist."); Tret_value=*(_mArray+index); RemoveRange(index,1); returnret_value; } voidRemoveRange(intstartIndex,intcount) { if(count<=0) throwstd::invalid_argument("Theremovingcountmustgreaterthan0."); if(startIndex<0||startIndex+count>=_elementCount) throwstd::invalid_argument("Theargumentsareremovingelementsoutsizetheboundaryofthelist."); memmove(_mArray+startIndex,_mArray+startIndex+count,(_elementCount-startIndex-count)*sizeof(T)); _elementCount-=count; } inlineintCount(){return_elementCount;} };
作为刚入手写的东西算是不错了。当然不能忘记了我比较关心的性能问题,于是做了如下测试(都是在release环境下,且是第二次运行保证不会被JIT编译):
1.添加500万个元素到列表里,C#的类库耗时86毫秒,C++的vector库耗时64毫秒,山寨类(就是我写的类)耗时81毫秒。看起来都差不多,因为扩容的时候似乎都是把原来的东西复制到新的地方去。
2.在表头插入500个元素(在原有500万个元素的基础上),C#的类库和山寨类都基本上耗时4秒左右。vector类没测试,估计也差不多。
可以看到,经过M$手的.NET类库的性能是很高的,基本上接近C++的原生库了。至于为什么,List类大量用到了Array.Copy方法,这个方法就是:
[MethodImpl(MethodImplOptions.InternalCall),ReliabilityContract(Consistency.MayCorruptInstance,Cer.MayFail),SecurityCritical] internalstaticexternvoidCopy(ArraysourceArray,intsourceIndex,ArraydestinationArray,intdestinationIndex,intlength,boolreliable);
这个InternalCall和NativeCode一样,都是C++写的,因此性能差不多。
所以说.NET的程序不一定比C++的慢(当然叠加了各种功能,甚至滥用了各种特性导致性能变低的除外),如果设计得好的话完全可以放心地用。
最后要说一句,在特定环境下.NET的程序甚至比C++写的程序更快,因为JIT会根据运行平台(比如CPU的架构类型等)生成对应的NativeCode,而编译式的程序就没有这个优势,除非是针对了特定的平台做过优化,否则为了兼容各平台只能选用最小的指令集。
无论如何,作为山寨的这个类我认为还不错(不过不论从风格上还是其他方面貌似我还是.NET的风格),以后在学习C++的时候不断适应吧。