额，不要说我三心二意：一边在看.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 oncetemplate <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++的时候不断适应吧。
