额，不要说我三心二意：一边在看.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在容量不够时扩容……
直接贴代码：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
#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方法，这个方法就是：
?| 1 2 |
[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++的时候不断适应吧。
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。