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++的时候不断适应吧。