额，不要说我三心二意：一边在看.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> #pragma once template <typename T> class ListSZ { private: T* _mArray; int _capacity; int _elementCount; const int DEFAULT_CAPACITY = 8; void EnsureCapacity(int newCount) { if ((__int64) _elementCount + newCount >= INT_MAX) throw std::out_of_range("ListSZ supports up to 2^31 - 1 elements."); //If _elementCount = _capacity - 1, the buffer is full if (_elementCount + newCount > _capacity) { int new_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 = new T[new_capacity]; memcpy(new_buffer, _mArray, sizeof(T) * _elementCount); delete [] _mArray; _mArray = new_buffer; _capacity = new_capacity; } } void MakeRoom(int index, int count) { if (index >= _elementCount - 1) return; EnsureCapacity(count); int move_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(int capacity) { if (capacity <= 0) throw std::invalid_argument("The capacity of the list cannot be less than 1."); _capacity = capacity; _mArray = new T[_capacity]; //_mArray = (T*) malloc(sizeof(T) * _capacity); memset(_mArray, 0, _capacity * sizeof(T)); } ListSZ(const T* source, int elementCount) : ListSZ(elementCount) { Insert(source, 0, elementCount, 0); } ~ListSZ() { delete [] _mArray; } T GetElement(int index) { if (index < 0 || index >= _elementCount) throw std::invalid_argument("The index is outsize of the boundary of list."); return *(_mArray + index); } void Add(T value) { EnsureCapacity(1); *(_mArray + _elementCount) = value; _elementCount++; } void AddRange(T* source, int count) { Insert(source, 0, count, _elementCount); } void Insert(T value, int index) { if (index < 0 || index >= _elementCount) throw std::invalid_argument("The index is outsize of the boundary of list."); MakeRoom(index, 1); *(_mArray + index) = value; _elementCount++; } void Insert(const T* source, int elementCount, int insertIndex) { Insert(source, 0, elementCount, insertIndex); } void Insert(const T* source, int startIndex, int count, int insertIndex) { if (count <= 0) throw std::invalid_argument("The count of elements to be inserted cannot less than 1."); if (insertIndex < 0 || insertIndex > _elementCount) throw std::invalid_argument("The target index is outside of the boundary of list."); EnsureCapacity(_elementCount + count); MakeRoom(insertIndex, count); memcpy(_mArray + insertIndex, source + startIndex, count * sizeof(T)); _elementCount += count; } T Remove() { if (_elementCount > 0) { _elementCount--; return *(_mArray + _elementCount); } return NULL; } T Remove(int index) { if (index < 0 || index >= _elementCount) throw std::invalid_argument("The index is outsize of the boundary of list."); T ret_value = *(_mArray + index); RemoveRange(index, 1); return ret_value; } void RemoveRange(int startIndex, int count) { if (count <= 0) throw std::invalid_argument("The removing count must greater than 0."); if (startIndex < 0 || startIndex + count >= _elementCount) throw std::invalid_argument("The arguments are removing elements outsize the boundary of the list."); memmove(_mArray + startIndex, _mArray + startIndex + count, (_elementCount - startIndex - count) * sizeof(T)); _elementCount -= count; } inline int Count() { 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] internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);
这个InternalCall和Native Code一样，都是C++写的，因此性能差不多。
所以说.NET的程序不一定比C++的慢（当然叠加了各种功能，甚至滥用了各种特性导致性能变低的除外），如果设计得好的话完全可以放心地用。
最后要说一句，在特定环境下.NET的程序甚至比C++写的程序更快，因为JIT会根据运行平台（比如CPU的架构类型等）生成对应的Native Code，而编译式的程序就没有这个优势，除非是针对了特定的平台做过优化，否则为了兼容各平台只能选用最小的指令集。
无论如何，作为山寨的这个类我认为还不错（不过不论从风格上还是其他方面貌似我还是.NET的风格），以后在学习C++的时候不断适应吧。
【C++实现的泛型List类分享】相关文章：