在上一篇隨筆<.NET Framework源碼研究系列之---Delegate>中我們一起研究了.NET 中是如何實現委托的.今天我們一起研究一下.NET中我們用的最多的一個集合類之一List.
大家都知道,在.NET集合類中List如Array一樣都是一個順序一維數組,與Array不同的是,我 們可以更方便的操作List類型的集合,比如插入數據,刪除數據,排序等等,那麼.NET源碼中List 是如何實現的呢?我們在使用List相對Array的優點時會不會有其他方面的代價呢?從List的源碼 中我們又能學到什麼呢?帶著這些問題,讓我們開始今天的.NET源碼研究之旅吧.
研究一開始,首先我們看一下List的類型定義.通過對象浏覽器,我們很容易知道List繼承了 IList,IEnumerator,ICollection等接口..NET中是這麼實現的:
public class List<T> : IList<T>, System.Collections.IList
這裡與對象浏覽器裡看到的不一樣,是因為IList接口同樣繼承自IEnumerator,ICollection 接口.
接下來我們看List包含的字段和構造函數:
然後我們看下List的幾個字段.由private const int _defaultCapacity = 4;我們可以看出 List默認最少可以包含4個元素._size字段顧名思義是List當前的長度.通過訪問List.Capacity 屬性我們可以獲取 List當前可以包含多少個元素.通過訪問List.Count屬性可以獲得List當前 包含的元素數.那麼他們有什麼不同呢?經過仔細研究發現,原來 List自增長的實現是這樣子的. 每當添加元素的時候,List會先判斷_size與_items的長度,如果相等,則size擴展到_size+1到 _items.Length*2.詳情請看如下源碼:
仔細看上面的代碼,我們會發現當復制數組時List並沒有自己做,而是調用了Array.Copy這個 方法.遍歷整個List的實現代碼,我們發現List幾乎所有的數據操作,如插入,刪除,查詢,排序,檢 索等等都是通過Array中相應的靜態方法實現的.由此可知上面我說的"List是對Array的一層包 裝"是正確的.
我們知道List繼承了ICollection接口,看對它的實現,我們發現 ICollection.IsSynchronized屬性直接返回了false.由此可知List不是線程安全的(用多線程的 同學要注意咯,這點與Queue不同).
在.NET中,遍歷一個數組我們可以用兩種方法,一個for循環,二是foreach.這兩個的區別是一 個是順序遍歷,另外一個跟順序沒什麼關系..NET中凡是Array和List都支持這兩種遍歷.學習過 設計模式中迭代模式的人這時候看到"與順序無關的遍歷"是不是覺得很熟啊.設計模式中對迭代 模式的定義為:
提供一種方法遍歷訪問一個聚合對象中各個元素，而又不需暴露該對象的內部表示。
沒錯!List就是一個.NET自帶的一個迭代器.嚴格來說,是因為List實現了IEnumerator接口. 也就是說.NET中凡是實現了IEnumerator接口的都是迭代器.大家在工作中無意識的就擁到的設 計模式,是不是覺得很開心呢?!:)
代碼看到最後,發現List也提供了Reverse()方法用於倒排存儲的所有元素,該方法的實現居 然完全照搬Array.Reverse,至此不得不感慨微軟對代碼的復用簡直做到了極致.也發現了以往居 然把這麼強大的東西(Array)丟掉了.
最後我們看兩個List都有的方法(沒有抄襲Array,不容易啊):
public void TrimExcess(){
int threshold = (int)(((double)_items.Length) * 0.9);
if (_size < threshold){
Capacity = _size;
}
}
public bool TrueForAll(Predicate<T> match){
if (match == null){
ThrowHelper.ThrowArgumentNullException (ExceptionArgument.match);
}
for (int i = 0; i < _size; i++){
if (!match(_items[i])){
return false;
}
}
return true;
}
這兩個方法裡TrueForAll則是判斷List中所有的元素是否滿足制定的條件;TrimExcess的功 能是去掉List自增長時增加的多余空間，效果看下面的示例代碼.
List<int> test1 = new List<int>(new int[]{0,1,2,4});
Console.WriteLine("集合實際長度為:{0}",test1.Capacity);
test1.Add(5) ;
Console.WriteLine("集合實際長度為:{0}", test1.Capacity);
test1.TrimExcess();
Console.WriteLine("集合實際長度為:{0}", test1.Capacity);
運行效果為
小結：
今天我們一起研究了.NET Framework是如何實現List，發現了使用List可能帶來的問題， List自身的一些特點，想必參看教程，大家更能深入理解List.
public void Add(T item){
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}
private void EnsureCapacity(int min){
if (_items.Length < min){
int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
if (newCapacity < min) newCapacity = min;
Capacity = newCapacity;
}
}
public int Capacity{
get { return _items.Length; }
set{
if (value != _items.Length){
if (value < _size){
ThrowHelper.ThrowArgumentOutOfRangeException (ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value > 0){
T[] newItems = new T[value];
if (_size > 0){
Array.Copy(_items, 0, newItems, 0, _size);
}
_items = newItems;
}
else{
_items = _emptyArray;
}
}
}
}
通過以上代碼可以獲知List自增長的原理.也有此可知,最壞的情況下,我們插入一個元素可 能導致把前面所有的元素復制到新的數組中去,由此產生的性能問題可見一斑.
public class List<T> : IList<T>, System.Collections.IList{
private const int _defaultCapacity = 4;
private T[] _items;
private int _size;
private int _version;
[NonSerialized]
private Object _syncRoot;
static T[] _emptyArray = new T[0];
public List(){
_items = _emptyArray;
}
public List(int capacity){
if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
_items = new T[capacity];
}
public List(IEnumerable<T> collection){
if (collection == null)
ThrowHelper.ThrowArgumentNullException (ExceptionArgument.collection);
ICollection<T> c = collection as ICollection<T>;
if (c != null){
int count = c.Count;
_items = new T[count];
c.CopyTo(_items, 0);
_size = count;
}
else{
_size = 0;
_items = new T[_defaultCapacity];
using (IEnumerator<T> en = collection.GetEnumerator ()){
while (en.MoveNext()){
Add(en.Current);
}
}
}
}
請注意List的第三個構造函數.從以上代碼我們可以發現原來List內部是用了一個Array來存 儲數據的.有此我們可以認為List不過是對Array的一層包裝,也有此可以斷定List的性能肯定不 如Array(包裝往往會帶來性能的損失).
